Regularized Proportional Fairness Mechanism for Resource Allocation Without Money
Authors: Sihan Zeng
Sujay Bhatt
Alec Koppel
Sumitra Ganesh
Venue: Accepted by TMLR ()

Abstract: Mechanism design in resource allocation studies dividing limited resources among self-interested agents whose satisfaction with the allocation depends on privately held utilities. We consider the problem in a payment-free setting, with the aim of maximizing social welfare while enforcing incentive compatibility (IC), i.e., agents cannot inflate allocations by misreporting their utilities. The well-known proportional fairness (PF) mechanism achieves the maximum possible social welfare but incurs an undesirably high exploitability (the maximum unilateral inflation in utility from misreport and a measure of deviation from IC). In fact, it is known that no mechanism can achieve the maximum social welfare and exact incentive compatibility (IC) simultaneously without the use of monetary incentives (Cole et al., 2013). Motivated by this fact, we propose learning an approximate mechanism that desirably trades off the competing objectives. Our main contribution is to design an innovative neural network architecture tailored to the resource allocation problem, which we name Regularized Proportional Fairness Network (RPF-Net). RPF-Net regularizes the output of the PF mechanism by a learned function approximator of the most exploitable allocation, with the aim of reducing the incentive for any agent to misreport. We derive generalization bounds that guarantee the mechanism performance when trained under finite and out-of-distribution samples and experimentally demonstrate the merits of the proposed mechanism compared to the state-of-the-art.

The PF mechanism acts as an important benchmark for comparing the social welfare of any mechanism. However, there exists no established way of computing its exploitability. The challenge here is that we need to find the maximizer of an optimization problem for which the gradient is only implicitly defined. We for the first time provide a systematic method for finding such (sub)gradients, which enables the evaluation of the exploitability  of the PF mechanism through iterative (sub)gradient ascent.

Published in Transactions on Machine Learning Research (01/2025)
Regularized Proportional Fairness Mechanism for Resource Allocation Without Money
Sihan Zeng JPMorgan Al Research
sihon.seng hean.zzegg@pmmmasee.cm
Sujay Bhatt
sujjgy.baatt@@ppmchsss.com
JPMorgan AI Research
Alec Koppel JPMorgan AI Research
alec.kopped@@ppcchnse.com
Sumitra Ganesh
JoMorgan Al Research
Reviewed on OpenReview: https: // // openreview. net/ forum? id- K85nJ601DR
Abstract
Mechanism design in resource allocation studics dividing limited resources among self- interested agents whose satisfaction with the allocation depends on privately held itilities. We consider the problem in a payment-free setting, with the aim of maximizing social welfare while enforcing incentive compatibility (IC), i.e, agents cannot inflate allocations by misreporting their utilities. The well-known proportional fairness (PF) mechanism achieves the maximum possible social welfare but incurs an undesirably high eaploilabilily (the maximum unilateral inflation in utility from misreport and a measure of deviation from IC). In fact, it is known that no mechanism can achieve the maximum social welfare and exact incentive compatibility (IC) simultaneously without the use monetary incentives (Cole et al. 2013). Motivatod by this fact,, we propose lcarning an approzimate mechanism that desirably trades off the competing objectives. Our main contribution is design an innovative neural network architecture tailored to the resource allocation problem, which we name Regularized Proportional Fairness Network (RPF-Net). RPF-Net regularizes the output of the PF mechanism by learned function approximator of the most exploitable allocation, with the aim of reducing the incentive for any agent to misreport. We derive generalization bounds that guarantee the mechanism performance when trained under finite and out-o--distribuutin samples and experimentally demonstrate the merits of the proposed mechanism compared to the state-of-the-art.
The PF mechanism acts as important benchmark for comparing the social welfare of any mechanism. However, there exists no established way of computing its exploitability. The challenge here that we need to find the maximizer of an optimization problem for which the gradient is only implicitly defined. We for the first time provide systematic method for finding such (sub)gradients, which enables the evaluation of the exploitability of the PF ascent.
mechanism through iterative
1 Introduction
Mechanism design studies how allocate items (resources) to market participants (agents) holding private
preferences with the goal of maximizing a criterion such as cumulative revenue (Manelli Vincent 2007
Navabi & Nayyar 2018 Kazunura et al. 2020) social welfare (Balseiro et. al. 2019 Padala & Gujar 2021

---

Published in Transactions on Machine Learning Research (01/2025)
while ensuring incentive compatibility (IC) (uuwiizz 1973 i.e., that strategic agents cannot inflate their
allocation by misrepresenting utilities.
This problem class breaks down along (i) the number of items to allocate, (ii) whether items are divisible or indivisible, (iit) the manner in which demand is communicated to the supplier (monetary or non non-monetary preferences), (iv) the measure of fairness/
welfare. (v) whether the agents are truthful or strategic. Regarding (i): in the single-item multiple-agent case, optimal mechanism design has been resolved when
monetary payments are made by the agents to the supplier (Mycrson 1981. Addressing the case of multiple bidders and items is the focus of this work, following Cai et al. 22012a Yao 2014).
Regarding (ii), indivisible item settings exhibit fundamental bottlenecks due to combinatorial optimization underpinnings (Chevaleyre et al. 2006; Sömmez & Unver 2011). ).. In this work, we study the divisible setting,
which is applicable to, e.g., financial assets Ko & Lin 2008 and GPU hours (lbrahim et al. 2016 Aguilera
ct al. 2014).
Regarding (iii): an agent requesting resources must indicate its interest in the form of a monetary bid alternatively provide utility function that represents its preferences. Numerous prior works resource allocation consider auctions, where payments indicate interest in resources (Pavlov) 2011 Giannakopoulos
& Koutsoupias, 2014 Dütting et al.) 2023), yet many settings forbid payment (e.g. organ donation, food and necessity distribution by charity, allocation of GPU hours by an institution to its employees). Our work
focuses on designing mechanisms without money (Dekel et al. 2010 Procaccia & Tennenholtz 2013
Cole
et al. 2013).
(iv) In the payment-free setting, measuring whether an allocation is fair among agents social level may be formalized through proportional fairness (PF) (Kelly 1997). An allocation is said to achieve PF if any deviation from the allocation results in a non-positive change in the percentage utility gain summed over all agents. It is known (see Bertsimas et al. (2011)) that PF' is achieved by maximizing Nash social welfare (NSW), the product of all agents' utilitics, which we use as a quantificr of fairncss welfare in this work.
What remains is (v) whether agents are truthful or strategic, i.e., they may misreport their preferences. Tn the later case, the mechanism needs to be designed so as not to provide incentive for the agents to misreport, i.c., to possess incentive compatibility (IC). The PF mechanism, which directly optimizes NSW of the allocation outcome assuming truthful reporting, is not incentive compatible. By contrast, several recent works study 1C mechanism design without money (Dekel et al. 2010: Procaccia & Tennenholtz 2013 Cole et al. 2013). Most germane to this discussion is the Partial Allocation (PA) mechanism (Cole et al. 2013 based on "money burning" (Hartline & Roughgarden, 2008), where the supplier intentionally withholds a proportion of the resources as an artificial payment. However, this mechanism is incentive compatible at significant cost to NSW.
In this work, develop payment-free mechanism that balances the competing criteria of fairness (in NSW sense) and TC. Our approach formulates the allocation problem as the one that maximizes NSW subject to a constraint on exploitability, which quantifics the maximun obtainable gain from misreporting and measures the deviation from exact. IC. Similar trade-olls are considered in related resource allocation settings that require monetary payment (Dütting et al.] 2023 Ivanov et al. 2022) and those not involving payments (Zeng) ct al. 2024), , as well as in game-theoretic pricing models (Goktas & Greenwald 2022). We detail our main contributions below.
We develop a subgradient-based method for computing the exploitability of the PF mechanism. The PF mechanism acts an important benchmark for welfare maximization in resource allocation. However, there exists no established method for computing the exploitability of the PF mechanism yet, making it difficult to compare against. This paper fills in the gap. As the PF mechanism is defined through an optimization program, our main innovation here is to derive the (sub)gradient of the output of the program with respect to the input, extending the results from the differentiable convex programming literature. This allows us calculate the exploitability by iterative (sub)gradient ascent. We believe that the technique for differentiating through the PF mechanism may be of broader interest beyond mechanism design.
2

---

Published in Transactions on Machine Learning Research (01/2025)
We propose a novel neural network architecture, RPF-Net, that is highly effective for learning an approxinately fair and TC allocation mechanism. RPF-Net can be interpreted from two perspectives. One is that it modifies the PF mechanism by adding a linear regularization designed to increase the robustness to potential misreports. The regularization is computed from the output of a ncural network learned from data. From another perspective, RPF-Net can be viewed as standard neural network with a prrcifii-purposss activation function tailored to the resource allocation problem structure. We derive the (sub)gradient of RPF-Net, which enables efficient end-to-end training.
We provide generalization bound of RPF-Net when it is trained on finite samples (Theorem 2). The result shows that the generalization error decays at rate ((1-1//2) where L is the training sample size. In auction design with payment, Regret.Net, the state-of-the-att learned mechanism proposed in Dütting et al. (2023), also achieves a O(L-1/2 rate, which we match in the non-payment set ting. Our bound is derived by adapting and extending the techniques in Dütting et al. (0223 to the special activation function in RPF-Net.
We provide a guarantee under distribution shift. The implication of this result is that we can train RPF-Net with samples from distribution F' and expect them to perform well under distribution F, provided that the mismatch between F and F' is controlled.
We experimentally validate RPF-Net across problem dimensions and distribution shift. The robustness to distribution shift, specifically, demonstrates the significance of our contribution by allowing the training data itself to be subjected to adversarial contamination.
1.1 Related Work
Our paper relates to the existing literature on resource allocation with and without monetary payments, well as those that study incentive compatibility in the context of mechanism design and beyond. We discuss the most relevant works in these domains to give context to our contribution.
Resource allocation without payment: Guo & Conitzer (2010) considers the problem of allocating two divisible resources to two agents and show that any IC mechanism achieves at most 0.841 of the optimal social welfare in the worst case (defined as an overall utility of all agents). They further show that a linear increasing pereessng--prce mechanism nearly achieves the lower bound. Han al. [2011) obtains an analogous worst-case lower bound for more general case of agents but does not provide mechanism. Cole et al. (2013) proves that no IC mechanism can guarantee to every agent fraction of their proportionally fair allocation greater 2n as the number of resources becomes large, and proposes a partial allocation (PA) mechanism that allocates to each agent a fraction (at least 1/e) of the corresponding PF allocation. These works assume that the supplier has no prior knowledge of the agents' preference (or its distribution), whereas our work considers the seiting where (possibly inacourate) historical samples of the agents' utility parameters are available for training. Also assuming the access to training samples, ZZng et al.) (2024) is highly related to our work. [Zeg ct al. (2024) studies learning an approximately fair and IC mechanism named ExS-Nct parameterized by a neural network and trains the network parameters on the same objective that consider in this work. Our important distinction from ExS-Net lies in the activation function of the output layer: while the activation function in ExS-Net is composed of a simple softmax function and a synthetic agent which receives the portion of resources to be withheld, the activation function we propose leverages a convex optimization program. ExS-Net an important baseline for comparison. In Section 0 we show that the proposed RPF-Net mochanism matcrially outperforms ExS-Net due to the innovation in the network architccture.
than n-1
Auction design/resource allocation with payment: When payments from the agents to the supplier are allowed, Chawla et al. (2010): Roughgarden 2010 Brânzei et al. (2022) design sophisticated monetary transfer schemes that ensure truthful reporting. More recently, (Dütting et al. 2023 Ivanov et al. 2022) adopt a learning-based framework similar to the one in our paper. A peerral-newworkppraaaaee RegretNet, is proposed in (Dütting et al.) 2023), which determines the price of a resource with the aim of increasing supplier's revenue while guarantccing the approximate truthfulness of the agents. Our work is partially inspired by RegretNet. Similar to our "differentiation through an optimization program" approach in spirit, Curry et al. (2022) learns approximately IC and revenue-maximizing auction mechanisms, designed
mechanism,
3

---

Published in Transactions on Machine Learning Research (01/2025)
through differentiable regularized linear program. Compared to RegretNet, the method in Curry et al. (2022) enlargens the solvable class of auctions.
Approximate incentive compatibility in ML: Dekel et al. 2010) consider regression learning where the global goal is to minimize average loss in the setting of strategic agents that might misreport their values over the input space. When payments are disallowed, they present a mechanism which is approximately IC and optimal for the special case of the buyer's utilities defined by the absolute loss. More recently, (Chen et al, 2020) focus learning linear classifiers, when the training data comes in online manner from the strategic agents who can misreport the feature vectors, and propose an algorithm that exploits the geometry of the learner's action space. Ravindranath et al. (2021) is another highly related work that designs approximately IC and stable mechanisms for two-sided matching using concepts from differentiable economics.
Organization. The rest of the paper is structured as follows. In Section 2 formulate the payment-froe resource allocation problem and introduce the existing mechanisms. In Section B present the proposed mechanism with the novel neural network architecture as well as the procedure to train the mechanism. In Section we develop the methods for evaluating the exploitability of the PF mechanism and for back- propagating the gradient through RPF-Net during training. Section of RPF-Net trained under finite and out-of-distribution samples. Simulations that illustrate the merits of the proposed mochanism are presented in Section literabure in Section 7
3 provides guarantees on the performance
Finally, we conclude and reflect on the connection to the
2 Preliminaries & Problem Formulation
We study the problem of allocating finite number M of divisible resources to N agents in the form of a vector a E N.M with aim the amount of resource m allocated to agent i. There a budget bm 2 0 on each B S R.Y. We assume that every agent has a
resource m = 1,... ,M, and we denote b = [6,,,.., bbul" (thresholded) linear additive utility each additional unit of resource m linearly increases the utility of agent by value Vg,,, up to the demand Zim. We represent the overall values and demands as u, = [u,,1,"" Pt,M]", si = [i.,,,.. .Ti,M] and .'..... _NN]
x [xT, . TT Given allocation E RNM, value V, and demand x E D, the utility function R x
V x D R is agent-wise expressed as
Σ M
u4(a, u,
U/m min (arm Timm)
(1)
m
with V S NM D NMM
NM for some scalars U, v.d, d > 0.
The linear additive utility structure widely considered and realistically models satisfaction in many practical problems (Bliem et al. 2016 Camacho et al.) 2021), though the mechanism proposed in the paper may handle alternative utility functions. The supplier knows the functional form of the utility function and relies each agent i to report the parameters vj and v,. It may be in the interest of the agents to report untruthfully.
Since the allocation needs to satisfy budget constraints and should not exceed what the agents request, valid allocations have to be contained in the set Ab..- = {a E RNM : < as.m S Ii,ms Vi, m, E ai.m S b,, Vm). J. A mechanism may incorporate non-negative agent weights w E R to encode prioritization. Next, we formalize that a mechanism is a mapping from values, demands, budgets, and weights to a valid allocation.
Definition 1 (Mechanism). A mapping f x:VxDxBxXB R. + R.N. is mechanism if [(v, w) E Ab. for all E V, E E w E RN
Agent weights w may be determined solely by the supplier before the agents reveal their requests or can potentially be a function of the reported values and demands. Since agents may not directly alter weights, we suppress dependence on w write allocations as f(,
Two competing axes for characterizing the merit of mechanism exist: social welfare and incentive compatibility (IC). Among the many social welfare metrics (sce (Bertsimas et al. 2011 ), we consider Nash social welfare (NSW), which balances fairness and efficiency.
Definition 2 (Nash Social Welfare). The NSW of mechanism f
NSW U,, b) e MT TE b), "
(2)
4

---

Published in Transactions on Machine Learning Research (01/2025)
Due to NSW as the product of agents' utilities, it may become numerically unstable as the number of agents scales up. In comparison, dealing with the logarithm NSW is usually more convenient
logNSW 2, (J,,,
The definition simplifies to (f, w log u(f(r, v.)).
To quantify approximate incentive compatibility, we next introduce exploitability as the maximum positive unilateral deviation in an agent' utility when it misreports its preferences.
Definition 3 (Exploitability). Under mechanism and u V x E DD B, we define the exploitabilily al agent its largest possible utility increase due to misreporting, given that the every agent j # reports U Zj
(,,,,, max us (J((), (14, b), v, -u (J(, u,,)
33)
A mechanism f incentive compatible (TC) if it satisfies expl,(/ v, b) 0, for all n, x. b and i == ..... N.
Assuming that the agents truthfully report their preferences, the following mechanism directly soeks to optimize the (log) NSW and achieves the largest possible NSW by definition. The mechanism usually referred as the Proportional Fairness (PF) mechanism, as the solution satisfies the proportional fairness property: when switching any other allocation the percentage utility changes across all agents sum up to non-positive value CCaragiannis al. 2019
Mechanism: Proportional Fairness
P (v. = argmin
Σ
1= wy log(a, 0;)
aERNM
(4)
s.t. 0sasE, Σn aim S bmy
Vm.
With D= 1 & MMX E MMMNM, the last inoquality of can be expressed in the matrix form Da S
Tt is important note that the PF mechanism not TC, Le., has nonzero exploitability. This fact motivates develop ways ensure it approximately by trading off NSW.
2.1 PF Mechanism Has a Non-Zero Exploitability
In this section, we illustrate the exploitability of the PF mechanism using simple example. Consider two-agent two-resource allocation problem, in which we choose x 1aar, b = 1M, and w 1v- Both agents have a higher valuation for the first resource, with = 1/2} and 122 = 1/4) When agent reports truthfully, Figure [ plots the utility of agent [cf. [1) as it varies the reported preference ratio 01,2/01,1 from 0.1 to 3 (the true ratio is 0.5). With the dashed line indicating the utility of agent under truthful reporting, under-reporting 21,2/v1,1 increases agent I's utility up to 17%. By contrast, RPF-Net proposed in this work substantially reduces the exploitability.
Utility of Agent Under Misreporting
PF Mechanism
0.s
exploitability
RPT Net
1 exploitability
truthful report
Utility of Agent
0.75
truthuul report
0.65
0.55
60
0.5
1.0
1.
2.0
2.5
3.0
Misreported 2
The state-of-the-art IC mechanism in the non- payment setting is Partial Allocation (PA) (Cole et al. 2013), built upon the PF mechanism, which stralegically withholds resources to ensure truthfulnes Under the PA mechanism, each agent can only be
Figure 1: Exploitability of PF and learned RPF-Net.
Detailed presentation of the PA mechanism be found Appendix A

---

Published in Transactions on Machine Learning Research (01/2025)
guaranteed to at least receive 1/e fraction of the resources that it would receive under the PF mechanism, meaning that there is resource waste and significant reduction in NSW. In other words, the best known IC mechanism achieves a sub-optimal NSW, whereas the PF mechanism is optimal in NSW but incurs high exploitability. This dichotomy does not cxist in the auction setting due to payments as an enforcement for truthful reporting. At. least the case m 1, classic auction mechanisms including the VCG mechanism [Vickrey 1961 Clarke. 1971 Groves 1973) and Myerson mechanism (Myerson, 1981) can achieve IC and revenue maximization. However, in the payment-free setting, NSW maximization and IC are conflicting objectives that are provably not perfectly achievable at the same time (Hartline & Roughgarden 2008 Cole
et al. 2013).
2.2 Learning Approximate Payment- Fayment-Free Mechanism
In this work, we are motivated to design a mechanism that approximately optimizes NSW and exploitability and strikes desirable balance between them. Specifically, assuming that in a resource allocation problem the values and demands of the agents and the budgets on the resources follow a joint distribution F, we formalize our objective maximizing the (log)NSW subject to constraint the exploitability for some 2 0.
max A
E(v,2,b) NSW v, v, r,,,,)] b)]
(5)
s.t. ((xxz,)>//expp,(( u, b)] S Vi
We say mechanism is e-incentive compatible the distribution F if it satisfies the constraints in 5
PA and PF mechanisms on the two ends of the trade-off between NSW and exploitability that are not optimal/feasible /feasible in the sense of 5 In this work, we propose parameterizing the mechanism with neural network and learning the solution to 5 from data. This can be regarded as an adaptation of Dütting et al. (003) to the payment-free setting. However, different from the auction setting, due to the impossibility result which states that IC cannot be achieved without "money burning" (i.c., resource withholding) (Hartline & RRoughgarden 2008), a regular neural network not equipped with the ability withhold may fail achieve low exploitability. In the following section, propose mechanism built novel neural network architecture specially designed for learning (5). We show later through numerical simulations that the architectural innovation is crucial- - the mechanism with the proposed architecture performs substantially better than a learned mechanism parameterized by a regular neural network or ExS-Net (Zeng et al. 2024 which is the statc-of-the-art lcarning-bar based solution.
3 Regularized Proportional Fairness Network
We develop novel learning-based mechanism for resource allocation that be regarded as composition of neural network (in this work employ feed-forward neural network of identical structure to parameterize both mechanisms, but in general any function approximation can be used) and novel specific- activation function. The mechanism, RPF-Net (Regularized Proportional Fairness Network). is a regularized variant of the PF mechanism that divcrts allocation from what the agents would like to receive when they misreport to their largest advantage. A schematic represent ation of the mechanism is presented Figure
z
Activation Optimization Program
x
a
Neural Network
b
Exploitability-Awar Proportional Fairness Network fo EXPP
Figure 2: RPF-Net Pipeline.

---

Published in Transactions on Machine Learning Research (01/2025)
3.1 Neural Network Design
The molivation behind RPF-Net is that we would like to reduce the agents' incentive to misreport through a linear regularization added to the NSW objective. We use function approximation to track the allocation that an agent aims to receive when misreporting, and penalize such allocation to be produced.
Suppose that each agent has the perfect information about the mechanism and the parameters of others (x-a, U-z). The most adversarial misreport occurs when it maximizes its own utility under mechanism f, i.., it would select (0;,5;).
(0;, 2;) = argmax of wfw U, e-i), v),
(6)
Let yr fa((e, v-e), x-), RD denote the allocation to agent under the optimal misreport. The goal of agent when misreporting is to obtain allocation y:- To ensure robustnoss to misreporting, the mechanism f should avoid allocating to agent i, which could be enforced as constraint:
(as, vi) S 6, Vi
for some constant O. With ō selected sufficiently small, alignment between the allocation decision az and the direction y/ desired by the untruthful agent i is penalized by the inner-produce constraint, which prevents allocating a; V4- In other words, the constraint 7 ensures that the allocation to untruthful agent deviates from what it most desires, hence reducing the incentive to misreport. This line of reasoning is in the spirit of robust control Zhou & Doyle 1998 Borkar 2002).
Denote the stacked vector of nominal allocations as y = [MT .VMI E RRMM, If y were known, 4 with
the additional inner-product constraint would be equivalent
argmingERX' -m
N i=
wi log(a, uz) >n',,,
4 (ay
(8)
s.t. 05a52, _ as. I bm. Vm
where & is the optimal dual variable associated with the inner-product constraint 7 for cach i. Unfortunately, is difficuut to compute as it encodes notion of self-consistency y defines the mechanism 7 but is simultaneously the output of (7) under specific misreports. Due to difficulty of practical evaluation, we instead approximate from data.
We propose substituting y by a parameterized function approximator. To be more precise, since the vector Yi can be a function of values, demands, and budgets, we fit. =u x D x B - RNM such that [u, 6)]; tracks f under reported values v, demands x, and budgets In this work, we take the function approximator to be feed-forward neural network represents the neural network parameterized by as mapping from the input values, demands, and budgets to an allocation outcome. Here [=,[0, .x.,,,)) b)]; denotes the evaluation of the neural network restricted to the component associated with the allocation of agent i. Substituting Au into 8 leads to our first proposed approach, RPF-Net, whose associated mechanism [cf. Definition I is detailed below.
represents the set of weights and biases while z
Mechanism: Exploitabilliy-AAaar PF
Compute (M, x. as output of neural network Solve
S
RPFF (U,I,b)
argmin aERNM
w; log(a, vx) + 2w,
i=1
s.t. at.0sasa x, a, I bms Vm.
Given learned network parameter w, this procedure describes the operations be performed in the inference phase. For any w, the output of the RPF-Net mechanism is always feasible, i.e., is non-negative, not exceeding
7

---

Published in Transactions on Machine Learning Research (01/2025)
the demand, and within the budget constraint, by the definition of the optimization problem (9) which be regarded as special activation function operating on the output of the neural network (u, b). Note that for (9 to be a proper activation function we need to be able to back-propagate gradients through it. It
is not obvious how we can propppro through (9) as the mapping from zn (v, xz b) to fw
fRPF (v, x, b) is
defined indirectly through an optimization problem. We address this important question in Section 4.3
3.2 Training RPF-Net
While we would like to solve the objective (5) over distribution F, in practice, we often may not have access to F, but instead a training set of values, demand, and budgets {(V _,,,,,,)) ) ~ F We train the mechanisms with the finite dataset via empirical risk minimization (ERM) by forming the sample-averaged estimates of the expected NSW and exploitability.
max
(JNSW(Ju:: ,',
(10)
S.L. expl, v', b') S Se Vi
The sample-averaged performance of mechanism approaches its expectation the number of collected samples increases the gap between them is known as generalization error Shalev-Shwartt & Ben- David 2014). In Sec. 5 mechanisms..
we bound the generalization error by a sublincar function of batch size L for both proposed
It is important to note that the learning objective does not require paired samples of (v', ,,),),,))) and the ground-truth optimal allocation under (u', , ....,b))... b'). We only need samples of valuations, demands, and budgets to learn the optimal parameter in unsupervised manner.
To train the neural network, we optimize descent-ascent algorithm to find the saddle point of the Lagrangian. We present the training scheme Alg. where II, denotes the projection of a scalar to the non-negative range. The dual variable %/ E RR. is associated with the 4sh exploitability constraint in 10
10 with respect to w by using a simple primal-dual gradient
Algorithm 1: Training RPF-Net
Input:
Initial network parameter w0 dual variables {7t 1 N training dataset {(v), x' (2) batch size 8, training iterations K, primal and dual learning rate oz,
Output: Network parameter _(
for k = 0,1,-.., K K-1 do
1) Randomly draw sample index set Sikl with |SW||| and compute empirical logNSW and exploitability
logNSW
[M]
Eissiy logNSW (fut), of 1,,166 (,)',
expl,
[K]
Σ rESi
(JH, Vi
2) Neural network parameter update:
k N expl, logNsW!!) (t)
w |- = wkl awi
3) Dual variable update:
[k+1] = II (7/² [bl %
3 (expl,
[M]
- -)) Vi
end
The RPF-Net mechanism is composed of neural network and an optimization program. The latter can be interpreted special activation function the network output. Passing ttroughh this activation in the
8

---

Published in Transactions on Machine Learning Research (01/2025)
forward direction requires solving 9 Backward pass is practiced in the training stage, in which we need to
[M] [k] logNSW [t] As critical step, we need to find the [k]
proo-pro the training loss (lk) = Σ,n expl,
(glh] gradient, ax given T.
(x
Computing such gradients is challenging task, the mapping from zu to the solution of 9 is defined implicitly through the optimization program. In the following section, we develop
aglk) the technique that allows d= to be computed (relatively) efficiontly. But still, the gradient computation requires inverting a square matrix of dimension (3NM + M) x (3NM + M). Both forward and backward operations can be increasingly expensive as the number of agents and resources scales up, which a fact that have to point out that may limit the scalability of RPF-Net in systems with computational constraints. Detailed complexity evaluation of RPF-Net is given in Section 6.4
We note that our work measures and optimizes exploitability only empirically and cannot guarantee strict exploitability constraint satisfaction, at leost for two reasons. First, we connot guarantee that gradient descent. applied to the right hand side of Eq. 3 with respect to v',,,, finds the global manimizer, especially when the mechanism is a complicated mapping encoded by neural network. Second, while we aim to optimize the objective 10 we cannot guarantee that the parameter w obtained from training is a feasible solution. If the desired exploitability threshold e is chosen too small, we sometimes observe constroint violation.
Remark 1.
4 PF Mechanism Exploitability Evaluation & RPF-Net Differentiation
Two main technical challenges are present at this point in training the proposed mcchanism and evaluating its performance against benchmarks.
1. It is unclear how we may systematically calculate the exploitability of the PF mechanism, which is the fundamental baseline for any 1C mechanism design. With a small number of resources, the exploitability can possibly be computed by exhaustively scarching in the valuation and demand space, which we performed to generate Figure [] However, as the system dimension scales up, an exhaustive parameter search quickly becomes computationally intractable. The main difficulty in computing expl, v. lies in finding the optimal misreport (ö;, f;) as the solution
66) It may be tempting to solve (6) with gradient ascent. However, as the mapping fPF is implicitly defined through an optimization problem
[ it is unclear how 8fFF and afee dz," (and potentially af te since
De. w may be a function of a/,, vg) can be dcrived or even whether fPF is diffcrentiable.
2. It is unclear how to back-prop through RPF-Net. To train RPF-Net with gradient descent, ae
at we need to compute a= given DjRFF(e..)) where E is downstream loss function calculated from SRPP(e, x. b).
We address both challenges in this section, by adapting and extending the techniques from differentiable convex programming (Amos & Kolter) 2017 Agrawal et. al. 2019 As an important contribution of the work, we characterize the (sub)differentiabiii calculating the (sub)gradicnts V. u4 Va u4 V. of (6) (Section 4.2 This allows itcrative (sub)gradicnt
of frr (Section
4.1 and develop efficient method for
ascent to be performed on the utility function to find a (locally) optimal solution of (6). This solution can
then be leveraged to evaluate the exploitability of the PF mechanism according to (3) Building on a similar technique, we present an efficient method for differentiating through RPF-Net in Section 4.3
The main property of f fPF that we exploit drive this innovation is the preservation of the KKT system of at the optimal solution under differential changes to values and demands. We now present the detailed technical development.
4.1 Characterizing Sub- Differentiability of pPF
Our goal is to determine how the differential changes in v, x, and w affect the optimal solution of 4 which denote by a" (v. b) = PPF PPF(u,
ar, b) (or a" for short when v, x. and b are clear from the context). We
9

---

Published in Transactions on Machine Learning Research (01/2025)
start by writing the KKT equations of slackness
4 for stationarity, primal and dual feasibility, and complementary
11 + 1/ + X = 0, vi
(11a)
v/ og
Mimaa 0, Vi,
(11b)
vm (4 - Fi 0, vi,
(1lc)
Xm (Da" b) = 0, vmm
(11d)
where p",v"" X are the optimal dual solutions associated with constraints a 2 0, S æ, and Da S b, respectively. As a" satisfies v. of'o at > 0 for all i (any allocation that makes v. a; 0 for any i blows up the objective of to negative infinity and thus cannot be optimal), [la) can be re-written
(nt - v3 )o oz + wit = 0.
(12)
For 11 to hold when values, demands, and/or weights changes from v, to v v du, x + dz, w + dw, the optimal primal and dual solutions need to adapt accordingly. We can describe the adaptation through the following system equations on the differentials, which we obtain by differentiating (12) and [1b
(dyi - du; - dd")u, a; + (11 - V -x"]du; a; (r Vs - )o da; + w,dv; + dwap = 0, V1, duim oi + 1 dat, = 0, vi,m. m,
du (atm - Ii,m) + Vi (da dxa,m) = 0, Vi, m, din Dma" + X, Dmd - din bm = 0, Vm.
We can equivalently express this system equations a compact matrix form
M [(dat) ((da")".(dd")) (d (dx))" h(de, dx, dw),
(13)
where M& E RUNNM+M)((NNM-MA and wh(de, dæ, dw) E R3NM+M are
Mi
M
M
M3
c(dv, dw) diag(u*)d )dl
M = diag(a*)
diag(a*)
0
0
and h(dv, dx, dw)
diag(v")
0
diag (a" x))
diag(>*)
0
diag( Da* b)
The sub-matrices MG, M2 E RNMMNM M3 E RNM and sub-vector e E RNM are
(0i - v T
0
M
M2 =
(NN UN V
Na MMM
(11) - or - xa)( + wi T dei + ww
Ii af TMX
(nU - 13 - ( + w dos + v2dw2
M3
c(du, dw)= -
((A5 - - (x)))))) + wwNIMxa)ddN + uNdwN.
Under any differential changes du, dr, dw, their impact da- can be derived by solving (3) which by definition gives the (sub)gradients when dv, dr, dw are set to proper identity matrices/ matrices/tennsn tensors..
de Example 4.1. To compute "e evaluate how unit change in du affects da". If M is invertible, solve
[(da') Td (du*) (dx+) M - 0,0)
(14)
10

---

We need to Published in Transactions on Machine Learning Research (01/2025)
and extract da* from the solution, where e RRMM denotes vector with value 1 at the first entry and 0 otherwise. Under a general profile of values and demands, the matrix M need not be invertible. A singular matrix M leads to a non-differentiable mapping f but all solutions of
M (dda)) (ddp")" (dv") (dxx)) = -h(e1, dr, dw)
are in the sub-differential of a' at v1,1.
Theorem 1. Suppose that strict complementary slackness holds at solution (a" (a",p", ,,,,,,,,, X*) "T," and that the demands are non-scro. When at least NM - N inequality constraints in (4) hold as equalities at a', the matriz M is invertible, and the mapping from (v,x) to a is differentiable. Otherwise, the mapping is only sub-differentiable.
Theorem ! provides a sufficient condition for the differentiability of frF, and connects the differentiability to the number of tight constraints. The proof is presented in Appondix B Similar characterizations have been established for quadratic programs and disciplined parameterized programs {Amos & Kolter 2017 Agrawal
itt al.
2019 However, ( does not fall (and cannot be re-formulated fall) under either category. Hence, Theorem generalizes these works to broader category of convex programs; see Appendix L for further discussions.
4.2
Composing (SabiGradients
In principle, one can find da' (and also Ou' da' öa du with an identical approach) by repeatedly solving 14 for the unit change in each entry of v. However, doing would require solving large system of equations for every partial derivative or inverting M and storing its inverse, which is costly operation. Fortunately, the following proposition shows that if aa ((vs, v-:). (zv, b) is used downstream to compute the utility u,(a" ((vy, (Nqr, x-;) b), v, x)) in (6, we can back-propagate the gradient. Va my through the PF mechanism to obtain Us Vz, uh, and V Vw by pre-computing and storing matrix-vector product.
de
Proposition 1. Under the same conditions as Theorem | and at least N NM- - -N inequality constraints of are tight at at ((v,, (Iv,
b), then given Var Ui, we have
V oy = ((4, +x* [ wy w.TMMM ww V 2, U, -dag(u")gn
(M+1))
(15)
V ww u4 u/ (i
with M [ Ip g [g]] [(Va. (O 0
(16)
If the assumptions Prop. do not hold, M singular, whereby 15 defines subgradients of u;, with Ja and Jv as any solution of (16]. In practice, we use the one with minimal l norm. These results enable performing (sub)gradient ascent compute exploitability of the PF mechanism.
4.3 RPF-Net Differentiation
We can repeat the steps in Sections 4.1 and 4.2 on the modified objective 9 and derive the gradient of loss de function computed from 0FRPF (v, b), with respect to zu when given afare (0.2.8)
solve the system of equations
(M') T 19 9p 17..17.96. go _l [ggRPr de (v,
,
where the matrix M' [(GNM++))((NMMM)))) defined in the appendix, shares common entries as M. Then,
with =f (RPF b), have
at
v.J a 9..
(1 x. 6)];
2The detailed derivation deferred Appendix
11

---

Published in Transactions on Machine Learning Research (01/2025)
To evaluate the exploitabiltt of the RPF-Net mechanism using gradient descent as outlined in Section Their expressions are given as follows
also need to find de at and possibly ow:
äe
deg 82
- --W.LIM - (M) v -==-x==2aa)) 9a,iMs(4+1)M
ae- =
ae
de
dx = (iag((")))) 1gv.
Ow. vi 9a,iM:(++1)M
do;
where n0, v², X are the optimal dual solutions of associated with constraints a 2 0, S n, and Da S
5 Theoretical Guarantees
In this section, we establish the convergence of the learned mechanism. First, we bound the sub-sampling error by sublinear function of the batch size, which matches recent rates for auctions (Dütting et al. 2023), and ensures the objective of (10) converges to (5) with enough data. Next, show that the learned mechanism is robust under distribution mismatch, i.e., when we train (5) on distribution F and evaluate on distinct distribution F, the learned mechanism achieves low exploitability with performance determined by distributional distance between and F"
5.1 Generalization Bounds
For mechanism f, we define the genoralization errors with L samples as
ElogNsw (J, I.) -F -loas b)] Σ log (J, of (.),
L) =
Σ i=1 expl, o' ,,,
With a slight abuse of notation, let vn xv, x, b) == (u, b), v, and let y + (v, x. b).
Assumption 1. For each agent i, assume that t S uf (v) th Vye F and some > 1, and us vs( S 1, Vi and all subsets of resources.
An implication of this assumption is that the activation function of RPF-Net is - for some 4 > 0. Theorem 2 (Generalization Bound). Consider RPF-Net parameterized by neural network with R hidden layers with ReLU activation and K nodes per hidden layer. Let d denote the total parameters with the vector of all model parameters ||||| I Q. Under Assumption 7 the following holds with probability at least 5
RPF ,),, Efx, (FRFF , S <O(NN ON v Rd Radlog(LNSP) max (K, MMN) + N
log(1/0)
max(EiogNsw(ff
L
L
The result provides that the generalization error decays at rate (II.-1/2) where L is the training sample size. In auction design with payment, RegretNet, the state-of-the-ate learned mechanism proposed Dütting et al. (2023), also achieves a (L221/2) rate, which we match the non-payment setting. The proof of Theorem 2 is inspired by Dütting et al. (2023), but extended handle: i) the fairness objective (NSW) in the absence of payment; ii) the special activation function in RPF-Net. The arguments in the proof can be used to obtain
similar order the generalization error for the ExS-Net architecture of Zeng et al. 20244
well.
5.2 Robustness to Distribution Mismatch
Let (FF) denote an optimizer of (10) under samples ((v', 20, (b)b) drawn from the distribution F. Next, establish that the performance of Tw*(Fr) on samples from distribution F when trained samples from a different distribution F" in terms of the worst-case exploitability is controlled by the degree of mismatch.
Theorem 3. Suppose the mechanism pRPF with porameter ws is e-incentive compatible over distribution F'. We have for any 1, 1,...,M, ,N
f
(e + 2M oz (Fv
where drv denoles the total variation (TV) distance.
12

---

Published in Transactions on Machine Learning Research (01/2025)
As an implication of Theorem 3
can train RPF-Net with samples from distribution F' and expect them to perform well under distribution F, provided that the mismatch between F and F* is not arbitrarily large. Later in Sec. 6.2 we will verify this result through numerical simulations. The proof of Theorem 3 is presented in Appendix
6 Experiments
We numerically evaluate RPF-Net i) as the number of agents and resources changes; and ii) when the mechanisms are tested distribution different from that observed during training. We also visualize the decision boundary of RPF-Net in contrast to the PF mechanism to provide more insight how RPF-Net deviates from the PF mechanism which it is designed to approximate and enhance. The final subsection discusses the computational time required for training and performing inference with RPF-Net.
Normelized NSW, Exploiabbiity Efficiency
iteess)
Normllized NSW, Explitabillty and Efficiency (10 iens!
c51
P7
0.5
2. PA (Cole et all)
3. P5 RA Mixture
Trained Mechanism without Withholding
(Zeng 2024)
RPt-Net (Propsed)
NSW
Explotaaiility
NSW
Efficency
Figure 3: Mechanism performance in 2x2 and 10x3 systems (normalized with respect to PF mechanism)
Evaluation Metrics: Mechanisms are evaluated on NSW
1
exploitability
N
xx, = (1//)) Σ ex,,,,
and efficiency
ΣM E
iiml fim (e,
eff
2m
6m
Efficiency quantifies the averaged utilization of resources. Mechanisms should preferably have a high efficiency, although efficiency is merely a byproduct of NSW in the training objective. As the total demand for a resource may be smaller than the budget, the maximum efficiency can be smaller than The PF mechanism is fully efficient (i.e., all available resources are allocated if the demand is sufficiently large), and hence serves as benchmark.
Besides the PF mechanism introduced in (4) we evaluate against the PA mechanism (Cole et al,, 2013), denoted by fPA, which achieves state-of-the-aa NSW among 1C mechanisms. A probabilistic mixture of PA and PF provides strong trade-off between NSW and exploitability. Given p E [0, 1]. we consider a new mechanism pmixture.
Baselines:
ifr=1 (PA(U,,,
r ~ Bern(p), pmixxtue (v,
ifr=0 0
Varying between [0, 1] lincarly interpolates PF and PA in expectation. We sct 1=1/2 in the experiments.
Another important baseline is the ExS-Net mechanism proposed in Zeng et al. (2024) which shares the same training objective as RPF-Net and is different in the neural network activation function.
We also compare against standard neural network, which has the same architecture RPF-Net and ExS-Net except that the activation function of its last layer is a standard softmax function and is trained on the same objective for the same amount of iterations. Any performance gain of RPF-Net over ExS-Net and this standard network can be attributed to the architectural innovation.
Data Generation: In all experiments, the true values and demands follow uniform and Bernoulli uniform distributions, respectively, within the range [0.1, Specifically, we generate the test samples according to
Um. Unif(0.1,1) Fi.m Unif((011,)
(17)
13

---

Published in Transactions on Machine Learning Research (01/2025)
Fi,m Bern((.5). Zi.m Di,mDimm
the budget for each resource is set to N where N the number of agents. This creales moderate competition for the resources in expectation. Training data sampled from the same distributions as test data according weights are set to 1.
Unless noted otherwise in Sec. 6.1
2.
17
except in Sec. 6.2 which studies distribution mismatch. All agent
6.1 Varying System Parameters
We test the proposed mechanism as the problem dimension varies. We start with two small-scale problems with 2 agents, resources, and 10 agents, resources. The 2x2 system is the smallest non-trivial case, and the 10x3 system is the largest considered in line of recent. works (Dütting et al. auction design with payment. All reported numbers normalized by that of the PF mechanism. As shown in Figure 3 RPF-Net achieves an advantageous trade-off between PF and PA: it consistently reduces the exploitability of PF by over at least 80% while achieving similar NSW. Compared with PA, RPF-Net improves the efficiency and NSW. For larger numbers of agents, the NSW of PA mechanism decreases drastically being the product of agents' utilities, while RPF-Net still exhibits favorable NSW. In addition, RPF-Net outperforms the interpolated mixture of PF and PA and ExS-Net under all three metries. The performance of the standard neural network is unstable (mechanism 4 in orange) while it performs well in the 2x2 system, it fails to achieve meaningful NSW with 10 agents present.
2023 [vanov et al. 2022
6.2 Distribution Mismatch
It can be difficult in practical problems to know and sample from the true distribution of values, demands, and budgets in the test set. In this section, show that RPF-Net is still effective when the distribution on which they are expected to perform is slightly different from the training distribution. Such distribution mismatch may oceur due to measurement error or more pernicious sources such as strategically misrepresenting preferences.
Recall that denotes the truc distribution of utility function parameters and F' the distribution of the training samples. We denote by (F") the optimal solution to (10) under samples ((vt,,t,)) ~ F'. The performance of (F"") under the true distribution F, measured by [F(NSW(w v, and Er[expl(w* (FF), U, b)], can in theory be sub-optimal by factor of drv(F, F"), which non-ideal under a large discrepancy between F and F'. Nonetheless, empirically we observe robustness: study two sources of distribution mismatch and see in the experiments that F (NSW(w<(F")) v, b)] and E Er(expl(w" (F'), v, b)] closely match [F(NSW(> (F)(), æ, 6)] and EF [f(expl(w" (F), u, xx, 6)].
Randomly perturbed training samples. In a x 2 system we suppose that the distribution F' follows , / generated according to while each training sample ((o(,=*))
b ~ Uni,(O.11,)) 1), Ziym ~ Uni o._ Cauchy (0,00))) Hm.m CauchyyO,0000) 0.01), of__ = jo!... + p4.mlo..1.11
(18)
a Bern(..5). ai.m I + a 10.
Here H[a, for scalar a, b denotes the element-wise projection the interval [a, bj. In other words, F has a perturbed uniform distribution. We would like to draw the perturbation from heavy-tailed distribution to increase the likelihood of generating extreme values. The Cauchy distribution has been used to explain extreme events like Flash Crash Parker 2016) and to describe price fluctuations (Casuutt et al. 2011 which motivates our selection.
Adversarially generated training samples. Again, we consider a 2 x 2 system where the true distribution F described in (17). Suppose that the training dataset composed of historical valuations and demands collected through past interactions of the agents with the supplier. If the agents believe that the supplier runs the PF mechanism in these past. interactions, they may have reported strategically to "trick" the PF
14

---

Published in Transactions on Machine Learning Research (01/2025)
Nash Social Welfare
Machunkm- Aliertion Brasuzze Agene Mrchanien- Alnoaroo Agent
2
45
AUlocction Resource Aegemm
Allocation Roso
NSW
Exploitability
Efficiency
Trained Truthful Data
Trained Randomly Perturbed Data
Trained Adversarial Data
V1.3
Figure 4: Performance of RPF-Net trained under data containing untruthful report. Numbers nor- malized by NSW/eeplootabllity/eeeeeee of PF mechanism.
Figure 5: Allocations from PF (top) and RPF-Net (bottom).
mechanism. The training samples {(v', x²)) will then take the following form:
d ~ Unif((0.1,1), a/.m ~ Uni.
(19)
d/ = arg max u. ((4, oLi), b).
o/
Table and Figure we present the NSW, exploitability, and efficiency of RPF-Net trained under contaminated samples and (19). We observe that under contaminated training samples the metries of RPF-Net closely track those under truthful training data. Notably, the NSW and efficiency unaffected, while the exploitability only mildly increases. The proposed mechanism still achieves near-optimal NSW and efficiency while maintaining low exploitability (not exceeding 20% of that of the PF mechanism). This demonstrates the robustness of the proposed mechanism to mismatch between training and inference distribution and supports the thcoretical results in Soc. 5.2
almost.
Mechanism
NSW
Exploitability
Efficiency (%)
Proportional Fairness Mechanism
8.00e-2+1.5ee
3.70e-3+1.20-3
56.6++3.9
Partial Allocation Mochanism
2.220-24-21c-3
0+::
26.2+22.5
PF-PA Mixture
5.11e-2466.6-3
1.85e-3+6620-4
41.4++3.6
RPF-Net (Trainod on Truthful Data)
7.970-2+1140-22
3.99c-4+1.2cc
56.5#4.0
RPF-Net (Trained on Randomly Perturbed Data)
7.99e-2+1.5022 7.980-2+11.6-22
5.3e-4+2.48
56.5+4.00
RPF-Net (Trained on Adversarial Data)
7.4c-4+8.0c-5
56.5+3.9
Table 1: Performance of RPF-Net trained under data containing untruthful report. Mean and standard deviation reported.
6.3 Visualizing Allocation Under RPF-Net
To shed more light on RPF-Net, we visualize and compare the allocation vectors generated by PF and well-trained RPF-Net 2-agent 2-resource allocation problem. Under specific profile of preferences and
15

---

Published in Transactions on Machine Learning Research (01/2025)
with the reporting of agent 2 fixed, Figure | plots the allocation to agent 1 as 11 and 21,2 vary at the same time. PF has clear and sharp decision boundaries. As an interesting observation, the learned RPF-Net mechanism closely tracks the boundary of PF but determines allocations in a smoother way.
6.4 Complexity of Proposed Mechanism in Training and Inference Phase
In this section, we provide more light on the amount of computation required to train RPF-Net and use it for inference. For this purpose, it is worth comparing with the existing mechanism ExS-Net proposed in Zeng et. al. (024) which considers the same training objective as ours but. parameterizes the mechanism with a much simpler regular neural network architecture. The main difference between RPF-Net and ExS-Net [Zeng et al. 2024 lies in the activation function. In the case of ExS-Net, the activation involves standard scalar/ operation and a softmax function. Both forward and backward passes through the activation can be completed in time O(M)), which means that ExS-Net is fast in both training and inference phases. For RPF-Net, forward pass requires solving the convex optimization program (9. We use an interior-point solver for this program, which is guaranteed to converge within polynomial time, i.c., the time to obtain an solution up to precision
no more than some polynomial function of e, N, and M. However, the exact. complexity is unknown but should be expected to be worse than ((NM))) (Renegar 1988) (as ()) is the time it would take for the interior-point method to converge if (9) were a linear program). In the backward pass, RPF-Net needs to invert solve system of equations of dimension (3NM + M) (3N + M), which requires ((NM))) computation. To summarize, we organize the complexity results in Table 2
We also show in Table 2 the training and inference time on a ten-agent three-resource allocation problem. Note that both PF and PA are hand-designed mechanisms that do not require training, but are time-consuming during inference since they solve optimization programs. The amount of computation required by RPF-Net during inference on the same order as that of PF and PA mechanisms.
Training Time (Theory)
Inference Time (Theory)
Training Time Inference Time (Simulation)
Mechanism
(Simulation)
Proportional Fairness
0
At least (((MN)))
0
40.1
Partial Allocation
O At least ((MN)))
0
310.0
ExS-Net
O(MN) At least (((MN)) AL least ((MN))*
(MMN)
1
RPF-Net (Proposed)
380.2
114.5
Table 2: Training and inference time for a ten-agent three-resource problem with samples generated according Reported training time and inference time of all mechanisms are normalized with respect to those of ExS-Net.
to 17
7 Conclusion
This paper studied the important problem of fair and incentive compatible resource allocation without the use of monetary payment. Identifying that hand-designing mechanisms that achieve the exact IC and maximum NSW is impossible, we considered learning an approximate mechanism that desirably trades off the two competing objectives. As a key contribution, we innovated the neural network architecture used to parameterize the mechanism we proposed RPF-Net, a learned variant of the standard PF mechanism with an optimization-based activation function in the output layer. We establishod a way of difforentiating through the activation function to enable efficient training. On the theoretical side, we showed that the proposed mechanism is consistent (learns better with more training data) and is robust to distributional changes in the data, two properties that make the mechanism useful in practice. We showed through numerical simulations that RPF-Net outperforms the existing methods on a range of evaluation criteria. In particular, compared to the state-of-the-art architecture (Zeng et. al.) 2024), RPF-Net significantly increases the NSW without. incurring a higher exploitability, thereby improving the Pareto frontier.
It is wooh noting the limitation of RPF-Net in its computational complexity. The optimization-ban activation function requires significant amount of computation to evaluate in the forward direction and to
16

---

Published in Transactions on Machine Learning Research (01/2025)
differentiate through in the backward direction. Enhancing the computational complexity of the architecture while not compromising performance is an important future work.
Disclaimer
This paper was prepared for informational purposes I part" if the work is collaborative with external partners] by the Artificial Intelligence Research group of JPMorgan Chase & Co. and its affiliates ('JP Morgan") and is not a product of the Research Department of JP Morgan. JP Morgan makes no representation and warranty whatsoever and disclaims all liability, for the completeness, accuracy reliability of the information contained herein. This document is not intended as investment research or investment advice, or a recommendation, offer or solicitation for the purchase or sale of any security, financial instrument, financial product or service, or to be used in any way for evaluating the merits of participating in any transaction, and shall not constitute a solicitation under any jurisdiction or to any person, such solicitation under such jurisdiction or to such person would be unlawful.
References
Akshay Agrawal, Brandon Amos, Shane Barratt, Stephen Boyd, Steven Diamond, and J Zico Kolter. Differentiable convex optimization layers. Advances in newral information processing systems, 32, 2019.
Paula Aguilera, Katherine Morrow, and Nam Sung Kim. Fair share: Allocation of gpu resources for both performance and fairness. In 2014 IEEE 32nd International Conference on Computer Design (ICCD), pp. 440 447. IEEE, 2014.
Brandon Amos and J Zico Kolter. Optnet: Diffcrentiable optimization as layer in neural networks. In International Conference on Machine Learning, pp. 136-145. PMLR, 2017.
Santiago R Balseiro, Huseyin Gurkan, and Peng Sun. Multiagent mechanism design without money. Operalions Research, 67(5):1417-1436, 2019.
Dimitris Bertsimas, Vivek F Farias, and Nikolaos Trichakis. The price of fairness. Operations research, 59(1): 17-31, 2011.
Bernhard Bliem, Robert Bredereck, and Rolf Niedermeier. Complexity of efficient and envy-free resource allocation: Few agents, resources, or utility levels. In IJCAT, pp. 102-108, 2016.
Vivck S Borkar. Q-lcarning for risk-sensitive control. Mathematics of operations research, 27(2):2943311, 2002.
Simina Brânzei, Vasilis Gkatzelis, and Ruta Mehta. Nash social welfare approximation for strategic agents. Operations Research, 70(1):402 415, 2022.
Yang Cai, Constantinos Daskalakis, and S Matthew Weinberg. An algorithmic characterization of multi- dimensional mechanisms. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing, pp. 459-478, 2012a.
Yang Cai, Constantinos Daskalakis, and S Matthew Weinberg. Optimal multi-dimensional mechanism design: Reducing revenue to welfare maximization. In 2012 IEEE 53rd Annual Symposium on Foundations of Compuler Science, pp. 130- 139. IEEE, 2012b.
Franklin Camacho, Rigoberto Fonseca- Delggdo,, Ramón Pino Pérez, and Guido Tapia. Beyond identical utilities: buyer utility functions and fair allocations. arXiv preprint XfX::2209.008461, 2021.
Joannis Caragiannis, David Kurokawa, Hervé Moulin, Ariel D Procaccia, Nisarg Shah, and Junxing Wang. The unreasonable fairness of maximum nash welfare. ACM Transactions on Economics and Computation (TEAC), 7(3):1-33 2019.
17

---

Published in Transactions on Machine Learning Research (01/2025)
Sébastein Casault, Aard J Groen, and Jonathan D Linton. On the use of the cauchy distribution to describe price fluct uationa in r&d and other forms of real assets. In 8th ESU Conference on Entrepreneurship (2011); p 1-9. Universidad de Sevilla, 2011.
Shuchi Chawla, Jason D Hartline, David L Malec, and Balasubramanian Sivan. Multi-pant parameter mechanism design and sequential posted pricing. In Proceedings of the forty-second ACM symposium on Theory of computing, pp. 311-320, 2010.
Yiling Chen, Yang Liu, and Chara Podimata. Learning strategy-aware lincar classifiers. Advances in Neural Information Processing Systems, 33:15265 15276, 2020.
Y Chevaleyre, PE Dunne, U Endriss, J Lang, M Lemaître, N Maudet, J Padget, S Phelps, JA Rodriguez- Aguilar, and P Sousa. Issues in multiagent resource allocation. Informatica, 30(1), 2006.
Edward H. Clarke. Multipart pricing of public goods. Public choice, pp. 17 33, 1971.
Richard Cole, Vasilis Gkatzelis, and Gagan Goel. Mechanism design for fair division: allocating divisible items without payments. In Proceedings of the fourteenth ACM conference on Electronic commerce, pp. 251 251-268, 2013.
Michael J Curry, Uro Lyi, Tom Goldstein, and John Dickerson. Learning revenue-maxinizing auctions with differentiable matching. In International Conference on Artificial Intelligence and Statistics, pp. 6062-6073. PMLR, 2022.
Ofer Dekel, Felix Fischer, and Ariel D Procaccia. Incentive compatible regression learning, Journal of Computer and System Sciences, 76(8):759-777, 2010.
Paul Dütting, Zhe Feng, Harikrishna Narasimhan, David C Parkes, and Sai Srivatsa Ravindranath. Optimal auctions through deep learning: Advances in differentiable economics. Journal of the ACM, 2023.
Yiannis Giannakopoulos and Elias Koutsoupias. Duality and optimality of auctions for uniform distributions. In Proceedings of the fifteenth ACM conference on Economics and compulation, pp. 259 276, 2014.
Denizalp Goktas and Amy Greenwald. Exploitability minimization in games and beyond. Advonces in Neural Information Processing Systems, 35:4857-4873, 2022.
Theodore Groves. Incentives in teams. Econometrica: Journal of the Econometric Society, pp. 617 631, 1973.
Mingru Guo and Vincent Conitzer. Strategy-proof allocation of multiple items between two agents without payments or priors. In AAMAS, pp. 881-888, 2010.
Li Han, Chunzhi Su, Linpeng Tang, and Hongyang Zhang. On strategy-proof allocation without payments or priors. In Ning Chen, Edith Elkind, and Elias Koutsoupias (eds.). Internel and Network Economics, pp- 182-193, Berlin, Heidelberg, 2011. Springer Berlin Heidelberg. ISBN 978-3-642-25510-66
Jason D Hartline and Tim Roughgarden. Optimal mechanism design and money burning. In Proceedings of the fortieth annual ACM symposium on Theory of computing, pp. 75 84, 2008.
Leonid Hurwicz. The design of mechanisms for resource allocation. The American Economic Review, 63(2): 1-30, 1973.
Ahmed Hosny Ibrahim, Hossam El-Deen Mostafa Faheem, Youssef Bassyouni Mahdy, and Abdel-Rahman Hedar. Resource allocation algorithm for gpus in private cloud. International Journal of Cloud Computing, 5(1-2):45 56, 2016.
Dmitry Ivanov, Iskander Safiulin, Igor Filippov, and Ksenia Balabaeva. Optimal-er auctions through attention. Advances in Neural Information Processing Systems, 35:34734-34747, 2022.
Tomoya Kazumura, Debasis Mishra, and Shigchiro Serizawa. Strategy-proof multi-object mechanism design: Ex-post revenue maximization with non-quasilinear preferences. Journal of Economic Theory, 188:105036, 2020.
18

---

Published in Transactions on Machine Learning Research (01/2025)
Frank Kelly. Charging and rate control for elastic traffic. European transactions Telecommunications, 8 (1):33-3) 37, 1997.
Po- Po-Chang Ko and Ping-Chen Chen Lin. Resource allocation neural network in portfolio selection. Expert Systems with Applications, 35(1-2):330-333) -37,, 2008.
Alejandro M Manelli and Daniel R Vincent. Multidimensional mechanism design: Revenue maximization and the multiple-good monopoly. Journal of Eemomiic theory, 137(1):153 185, 2007.
Roger B Myerson. Optimal auction design. Mathematics of operations research, 6(1):58-15) 73, 1981.
Shiva Navabi and Ashutosh Nayyar. Revenue-optimal mechanism design for rate-differentiated energy services. In 2018 IEEE Conference on Decision and Control (CDC), pp. 1917 1922. IEEE, 2018.
Manisha Padala. and Sujit Gujar. Mechanism design without money for fair allocations. In CRE//WI//ACM International Conference on Web Intelligence and Intelligent Agent Technology, pp. 382 389, 2021.
Edgar Parker. Flash crashes: The role of information processing based subordination and the cauchy distribution in market instability. Journal of Insurance and Financial Management, 2(7), 2016.
Gregory Pavlov. Optimal mechanism for selling two goods. The BE Journal of Theoretical Economics, 11(1): 000011022021933114416664, 2011.
Ariel Procaccia and Moshe Tennenholtz. Approximate mechanism design without money. ACM Transactions on Economics and Compulation (TEAC), 144):1 --2), 2013.
Sai Srivatsa Ravindranath, Zhe Feng, Shira Li, Jonathan Ma, Scott D Kominers, and David C Parkes. Deep learning for two-sided matching, arXiv preprint arXiv:2107.03427, 2021.
James Renegar. A polynomial-time algorithm, based newton's method, for linear programming. Mathe- matical programmingg 40(1-3):59 93, 1988.
Tim Roughgarden. Algorithmic game theory. Communications of the ACM, 53(7):78 86, 2010.
Shai Shalev-Shwariz and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.
Tayfun Sönmez and M Utku Unver. Matching, allocation, and exchange of discrete resources. In Handhook of social Economics, volume 1, pp. 781-852. Elsevicr, 2011.
William Vickrey. Counterspeculation, auctions, and competitive sealed tenders. The Journal of finance, (1):8-37, 1961.
Andrew Chi-Chih Yao. An n-to-1 bidder reduction for multi-item auctions and its applications. In Proceedings of the twenly-sirlh anmual ACM-SIAM symposium on Discrele algorithmss, pp. 92 109. SIAM, 2014.
Sihan Zeng, Sujay Bhatt, Eleonora Kreacic, Parisa Hassanzadeh, Alec Koppel, and Sumitra Ganesh. Learning payment-free resource allocation mechanisms. xrxie preprint ar Xrxiv:2311. 1.9927, 2024.
Kemin Zhou and John Comstock Doyle. Essentials of robust control, volume 104. Prentice hall Upper Saddle River, NJ, 1998.
19

---

Published in Transactions on Machine Learning Research (01/2025)
Contents
Introduction
1
Related Work
3
2
Preliminaries & Problem Formulation
4
2.1
PF Mechanism Has Non-Zero Exploitability
5
2.2
Learning Approximate Payment-Free Mechanism
6
3
Regularized Proportional Fairness Network
6
3.1
Neural Network Design
7
3.2
Training RPF-Nct
8
PF Mechanism Exploitability Evaluation & RPF-Net Differentiation
9
Characterizing Subb-Differentiability of fPF
4.2
Composing (Sub)Gradients
11
RPF-Net Differentiation
11
Theoretical Guarantees
12
5.1
Generalization Bounds
12
2
Robustness to Distribution Mismalel
12
6
Experiments
13
6.
Varying System Parameters
14
Distribution Mismatchl
14
6.3
Visualizing Allocation Under RPF-Net
15
Complexity of Proposed Mechanism Training and Interence Phase
Conclusion
16
Partial Allocation Mechanism
21
B Proof of Theorem
21
C Proof of Proposition
22
D Derivation of Gradients of Exploitabillty--Aeerse Proportional Fairness Mechanism
23
E Proportional Fairness Mechanism and Discipline Parameterized Program
24
Gencralization Bound
25
Definitions Preliminaries
25
20

---

Published in Transactions on Machine Learning Research (01/2025)
2.2 Proof of Theorem 2
26
G Proof of Theorem
28
A Partial Allocation Mechanism
The partial allocation mechanism, proposed in Cole et al. 2013 is built upon the PF mechanism and withholds resources according to an externality ratio. Specifically, given reported valuations E RNX and demands E IR across all agents and resources and budgets b E RM let at 2 f x, b) denote the allocation made by the PF mechanism.
Let x=x RNN denote a modified demand matrix where
it O RR,, i=j
By E RMM
2j
For each agent calculate
a S. 2 fPF (v,
which is the PF allocation outcome that would arise in the absence of agent i. We further compute the externality ratio Ti E R4 for agent as
1/w6
Pi Uy(a", u, 2))
I1 uy(a 0,
where uy is the utility function defined
①
The PA mechanism allocates to agent according to the following rule
(x, r;a
It is casy verify that r; [0, 1]. Therefore, the PA mochanism is always feasible. Cole et al. 2013 Theorem 3.2) proves that it is also perfectly incentive compatible for any v. b.
Proof of Theorem
To show the invertibility of M when at least NM - N constraints are tight, it is equivalent to show that the following system equations has a unique solution [da dd du dd dATTT for any vector [ S [TT
da
dp
B
M
=
dv
dA
We define I, A mii [1...., .N] x [1.... .M] pi,m 0} {(i,m) E [I,...,N] , [1, M] ai 0}, where the second equality is due to strict complementary slackness. Similarly, we define I, (i,m) E [I.....N]] x [1...., .M] v > 0} (i,m) [l...., .N] x [1.....A. .M] a = x.mm) and
I {m [1.... .M. Am > 0} {m [1, [1,...,M. M] Σ, at =bm). We use Iú Ig I to denote their complement sets.
Note that for any m) I,, its corresponding row in the second row block of M only has non-zero entry Similarly, for any (. $ I, ai in the second column block of M. This implics the solution dutm ai
21

---

Published in Transactions on Machine Learning Research (01/2025)
and m $ Ix, are able to immediately write the solutions di.m and d and remove them from the system of equations. Eventually, the system to be solved reduces to
1 diag(ut,))
(M2).I,
(M
-(Ms).Ia
da
diag(az,)
diz,
diag(vi,)
0
diag((a* z),,,)
duz,
diag(AA, DT,
0
diag( (Da Iz,)
ddz,
- (M2) duzg + (M (2) + (Ma)
BI,
YIn
As ai 0 for any (i.m) E Ip (and similarly, ai Jsmm for any (i, (i,m) this be further simplified as
Iv. Ei ai bm for any E Ix),
M1 diag(u (15,) diag(rī.)
(M2).Ia
(M2).
(M3)..
da
0
0
0
duz,
0
0
duz,
diag(A (2t, DDA
0
0
dAz.
Mz
(M2) duzz + (M 23 duz; + (M
Br,
YI,
STA
Note that [I,| + +I [ 2 NM when at least NM N constraints are tight. Since x > 0, the total number of linearly independent constraints on da therefore N N(from M1) (NM M) NM, which uniquely determines da. Due to the diagonal structure of 2,, the block diagonal structure of M3, and the fact that the optimal allocation a" needs to satisfy v až > for all i to avoid making the objective function infinitely negatively large, it is not hard to see that we can determine the remaining variables dizz, dvz,, and d'z,, from the first row block of Mz. The invertibility of leads to the uniqueness of M [
0L TT, ST, OT which obviously implies the differentiability of the mapping from (v,z) to a*. When less than NM - constraints are tight, the number of lincar constraints on da at most NM - 1, which cannot uniquely determine the N NMddimensional vector da.
C Proof of Proposition i
Under the assumptions of the proposition, M is an invertible matrix. The following equations follow from the fact that the utility function u; does not depend on the dual variables
Oe =
Ol TT Oa
OT
OT
_ M h( 0,0)
Tv Da
Ovi,
= Da
heer, 0,0) M (V (V..u,) ToT To. ,
The important observation that the computation of the gradient with respect to any entry in of (and also of and w) uses the product of M and (V.-u))T, _T, .T. , OT [T, and only the vector h is different. Taking advantage of this fact, it is not hard to see (following line of analysis similar to derivation of Eq. (8) in Amos & Kolter (017)) that once we solve
[o 94 In xK M- -T [Voru) -M-T(VV-u.) O TT
22

---

Published in Transactions on Machine Learning Research (01/2025)
the gradients admit the closed-form expressions
Ve ey u4 = (-W;lMxa - (14 - vi - (0
x. Mi diag(u" "iiag("")9)) Vw; = v/ Ma.
D Derivation of Gradients of Exploitabiliy-AAerrs Proportional Fairness Mechanism
With values v and demands x, let at denote the solution of 9 i.e,, a' -BPPF (v, x, b). The aim of this section is to derive the (sub)gradient of a loss function l with respect to 2, v, and when we are given Varl. The arguments used here are mostly straightforward extension of the result in Sec.
The equations in the KKT system
9
include
Wipls
2 14 D + X =0, 0, Vi 1, ,N Pl.m =0, Vi 1,... NN,
of az
M I, ,N, m 1, 1, M
vi. (a Fmsmm = 0,
Xx (Da" b)m O, Vm = 1......... .M.
Since the optimal solution a* need to satisfy Us a3 > for every agent i, the first equation can be simplified as
(pT vs X²),z o3 + was 2u, aj 0, =i= I.,...,, N.
Taking the differential,
(dp} dv; dx* -dz'd at (wj - v/3 X 24 du oj
+ (M6 V, - x+ z.)u? dat + widvi + duavi = 0, du aim +
=0, Vi, m
du; (nim Timm) + VT. (da - dm.mm) = O, Vi, m
dx Dm + Nx, Dm dxa O.
This systems of equations can be written in the concise matrix form
da
c'
dp
o
M'
dv
diag(v da
dA
0
where the matrix M' R(NM++))(BNMM is
M'
M2 diag(a*)
- -M
- M
diag(u*)
0
M'=
diag(u*)
diag(a- -x) 0
diag(>*)
0
diag Da -b)
Liag(Da"
the vector e' E RNM is
ot TTaddz + (aa) de
02 ašdzz + 22 =2( drz
d' c
daa + 22 duy
23

---

Published in Transactions on Machine Learning Research (01/2025)
the matrix Mj RNMNN is
(1) (11-11 -1
M
(u U
NN N
and the matrices 22, M3 and vector e are defined in Sec. 4.1 Again, it can be shown that once pre-compute and save
at
9a
Oa
0
(M')
9v
9x
0
the gradients have the closed-form expressions
dl
w wMlMxM - (1, - - -2>0)) ia
Dv;
00
Ot
diag(v")gu
u; Ia.iM:(i+11MM
Or
Ow;
0l
Us 0 (M,
E
Proportional Fairness Mechanism and Discipline Parameterized Program
Discipline parameterized programs (DPP) are a special class of convex programs introduced Agrawal et al. (2019), which the authors show how (sub)gradients can be derived through the mapping from parameters of a DPP to its optimal solution. We start the discussion by introducing the DPP, which is optimization program of the form
y" = argmin fo(2,0) 0)
y
s.t. fe(y, 0) S0, 1= Mineg
where y E R is the decision variable, 0 Ra is the parameter which we need to derive the gradient for, and the functions fi are convex. In addition, all functions are required to be affine in special sense. An expression is said to be parameter-affin if it is affine in affine in the parameter 0 and variable-free (does not involve variable z). An expression is said to be parameter- free if it does not involve any parameter (it can involve the variable x.). Any expression @prod 22) = 21 as the product of 21 and 22 E RP for any
p affine if at least one of the two conditions true:
Y1 or Y2 both parameter-free and variable-free
among V1 and V2, one is parameter-affin and the other parameter-free
When we try to capture 4 by a DPP, the decision variable y corresponds to allocation a, and the parameter 0 abstracts (u,,,,, w). As part of the objective of { a. us can be verified to be affine since a; is parameter-free and 0/ parameter-affine However, the overall objective - -En w, log(a, v.) not affine as w, is not parameter-fiee and log(a, v.) not variable-free, parameter-affine or parameter-free. While sometimes re- foformulation can be made to transform non-DPP an equivalent DPP, such re-formulation not possible in this case.
24

---

Published in Transactions on Machine Learning Research (01/2025)
F Generalization Bound
F.1 Definitions & Preliminaries
Let F denote a class bounded functions f Z + [-c, cl defined on an imput space z for some c 0. Let be a distribution over and = {21, F2, ... 21.} be a sample drawn iid from some distribution D over input space Z.
Definition 4. The capacity of the function class F measured in terms of empirical Rademacher complezity on sample S is defined as
R(F) L
sup Σ orf((e)
fEJ
2,E8
where E [-1,1]] and each a; is drawn from uniform distribution on {-1,1}. Definition The covering namber of a sel M, denoted as (N,, is the minimal wumber of bulls of radius 6 (measured the 1s0,1 distance) needed cover the set M.
For example, the 1001 distance between mechanisms S,J E M is given as
N
M
maX (2,0,
(u, x, - 1-0--1j5 xv,
Lemma F.1 (Shalev-Shwartz & Ben- David 2014 from D, for F,
Then with probability at least 1 - 5 over draw of S
2 (4/6)
EawDIf(>)] < L 1=1
Σ f(z) + (R)(F) scy
L
Lemma F.2 (Massart). Let g some finite subset of Rm and σ1, 02. random variables. Then,
am be independent Rademacher
/2( sup, E. log G
sup DEG mT
0:9h S
m
Let o: RN + R represent the activation function of the any layer for input E RM given as ,N,MM).. S.
Φ |softmax(s111... .N,,1,. softmax(s1,,
where softmax RN + [0, 1. Note that for any u E R.V,
24
softmax;
ΣN
_k=1 c.
Lemma F.3 (Dütting et al. 2023 ). For any 8,8 E RRM, the activation function for a smft layer is 1- Lipschitz, i.e.,
( - 6(55)ll 11s-
Lemma F.4 (Dütting et al. 2023 Let Fx a class of feed-forward neural networks that maps an imput vector y Rdo to an output vector Rds, with each layer containing Ti nodes and computing z + di (i(w">
and di RT) [-R, n)) Further, for each nelwork in Fu, let the parameler matrices |! W and (| (s') < o||s- s'll1 for any s' E RRTi The covering number of the network is
2nd (F.. (20W))+
where T maxielk] Ti and d is the tolal number of poramelers in the network.
Corollary F.4.1. For the same configuration as in Lemma F.4 but having [[)r(s) 0r(s'))l < -|s--sh s'1l1 for all hidden layer activation functions ( < k), and having (s) - (o(s')l I Ø s' I|1 for the output layer, the covering number is given as
F1 Fod2((2W)
No. Noc 5
25

---

Published in Transactions on Machine Learning Research (01/2025)
F.2 Proof of Theorem 2
Consider parametric class of mechanisms, J M, defined using parameters E Rd for d 0. With slight abuse of notation, let (0, x, b) == (v, b), u, x) and let y y (u, D + (( e-1), ())) Consider the following function classes
U, uY
Σ vim min (f for some f MEM]
N
NSW M { ( R f(y) Σ
log ut (v) for of eui
exp x (1 Y + IR (c(y)) = uf (2)) - for up e U
exp u Yh: = Σ evly) for some (e1,
. . Eexp uu)
Proposition 2. Suppose Assumption holds. Let M denote the closs of mechanisms and far å E (0, (0,1). With probability at least - 6, over draw of L profiles from F, for any parameterized allocation for E M,
1og(1/6) L
y log of (v)
log ut (1 2NA, CNV
where C' is distribution independent constant and
2 2log(No (M,, +))
A
E ((og ei + +D e>0
inf
L
Proof. Using Lemma F.1 the result follows except the characterization of the empirical Rademacher complexity that we derive below. By the definition of the covering number, we have that for any h(y) E NSW o M, there is a h(v) E NSW o M such that max, (h(y) h(v) S e. We have the following
R.SN M)
1 F L
sup
O1
log ue (1)
i=1
T sup
1
())
+ , sup
σ (1))))
$ E. sup
o )
+ E
The result follows from the following arguments:
i.) We shall first establish that
NN o M) S (M.
By definition of the covering number for the mechanism class M, there exists a cover M of size [M] & (M. 3 such that for any fwv E EM there for E M such that for all y,
Σ 1 fir (v) s $
For g(v) EN log ut (g), we have
N
g(v)) ((v) = Σ
log uf - log a (1)
26

---

Published in Transactions on Machine Learning Research (01/2025)
N
1/
(v) 0, (v)
min (v), Fe,m min fim (v), Fi,m
E Ve,m min ( (V), Fi,m min F
(v) fr. (v) <E.
i..) We have from Massart's lemma (Lemmaa F.2
RNSW M) <
Σ
(M(r)t))
2o M),c)
+
ii..) We have the trivial bound,
2 Σ ((())))
S
Σ Σ log us (v(()) + nee)
< <N(log v + +1VT..
The result follows.
Proposition 3. Suppose Assumption 1 holds. Let (wp,(w) = Ey maxy u (1,) -u; wx(v]] and (Tp,(w) =
1 E maxg u(("") ut (r0)). Under the same assumptions as in Theorem & the empirical exploitability
satisfies the following:
1 N (w)
(w) + C' (og((1/)/L
N
where C is distribution independent constant and
2 2oo (M, TN ))
A
inf <00
+ (2tb+ + 1)N1
Proof. As before, using Lemma F.1 the result follows except the characterization of the empirical Rademacher complexity of the class R R(exp o i), which we do below. The proof builds on the following results.
i.) (exp U4 <) S ( (24, +
By the definition of covering number Noc e), there exists cover ú, with size at most Noc (U4 $ such that for any uf E UG there is ay E UG with
max (v) (v)] 2
We have for the exploitability for each agent with any y,
max ((()) (() - max of (vi) at (v)
vi
< ||max of (wi) max at ( (w (1) Se.
vi
where the last incquality follows from the following relation.
max ut (ū:) u (v*)
9:
27

---

Published in Transactions on Machine Learning Research (01/2025)
< + c/2 o4 + +c/2 s max ui (0) + c,
max 07 (w:) - (1")
S ( (. + +e/2 max uf (y) + 2
i..) (.) Noc (U, 2N The result. following by considering cover No (M,, 2N) such that
N
max
1e - (1)) S 2N
and using the same arguments as above.
ii.)) No e), (M,
By definition of the covering number for the mechanism class M, there exists cover M of size M < (M,, such that for any f EM there a fwv E M such that for all y,
Σ (1fmm()) (..(())) Sc 6,m
We have for the class U,
u (v)
055 cf(ww] 5
ΣΣ Vim { min (u), min (v), Fz.m
Ci,m min (v), Ti,m) - min ( (f (V), Fimm
m
Dim fi (v) fr. (w)) <E.
The result follows from Lemma F.2 and similar arguments in Proposition
2
Note that the activation functions all hidden layers ReLU functions, which are 1-Lipschitz. The output. layer of the regularized PF activation is Lipschitz from Assumption [ with some constant & 0.
Using the definitions of A's with the activation having a Lipschitz constant of 4 and the hidden layers having a Lipschitz constant of 1, and with d max K, MN) in Corollary F.4.1. we have from Proposition and Proposition 3 that the following holds with probability at least
(1oggs ( (SS, OWNN RddooolooLLL max K, MNJ) Ny
log(1/6) L
L
G Proof of Theorem 3
It is obvious that the exploitability of any mechanism at agent i cannot exceed the utility agent when its demands are fully satisfied. This means for any mechanism f and E V, E D. E B, we have
expl,f.e,,, b) < Σ Di S MT,
(20)
m==
where the second inequality is due the boundedness of values and demands.
Let pp and pp- denote the probability density function associated with F and F'. We have for any
F (f,,,r
28

---

Published in Transactions on Machine Learning Research (01/2025)
= -eppss)r + ((nna.))-rleppp(( v, x, b]] (o.x)))///pppp u, b)l)
Set / 10 pu 2r, b)) du dx db
Set / |expl, (r((,, - p (u, x, b) do dx db
Se+ MUT (pF(,,x,)) pr (v, b) do da db
- 2M (F,T
where the third inequality applies for any distribution Fi, F2 over &'
20 and the final equation comes from the definition of TV distance, i.e.
(Fi F2) J pF((x) - pr pr- (z) dr.
29


Reviews:
[{"review_id": "qavVqITx0B", "reviewer": "Reviewer_abuk", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n- Their work on differentiating through their optimization problem is nice and is in fact probably of interest even to people who don’t care at all about mechanism design.\n- The distributional robustness result is both very cool and useful. I don’t think I have seen this type of result in a differentiable economics paper before.\n- The experiments are quite solid and convincing. No complaints here.\n- Ability to visualize the mechanism is important, as the main motivation of this work is exploring the space of mechanisms of interest to theorists (vs. actually learning some mechanism that notionally would be fielded).\n\nWeaknesses:\n\n- There aren’t really substantial weaknesses to the paper. It’s a very solid contribution to this line of work.\n- The regret/exploitability measurements are only empirical. This is very common and not a deal-breaker, but it would be even better if there were some true guarantees on IC.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper is a contribution to a growing line of research on “differentiable economics”: the use of rich function approximators and optimization tools adapted from deep learning to solve problems in mechanism design.\n\nThe particular focus is on resource allocation *without money*. So, the goal is to allocate some goods to agents who value those goods differently. As in all mechanism design, the problem is that the agents might misreport their values to manipulate the outcome in their favor, so the mechanism must be made strategyproof. The performance goal is Nash social welfare (product of agent utilities), which formalizes a notion of fairness.\n\nIn this setting, the proportional fairness (PF) mechanism directly computes the Nash social welfare optimizing allocation, but is not strategyproof. (A redundant but important point: this means that a strategyproof mechanism can’t be optimal for this problem.) There is a well-known strategyproof mechanism (Partial Allocation), but it involves deliberately withholding goods and is therefore suboptimal.\n\nWhat the authors want to do is explore mechanisms that are somehow “in between” these — to (informally) make a Pareto improvement by trading off a little Nash Social Welfare to get a lot less IC violation.\n\nThey do this using a neural network as a function approximator, using a roughly similar recipe to Dütting et al., though with significant technical innovations for their problem.\n\nAt a high level, this recipe is that a neural network will map agent reports to an allocation, and will be trained to maximize performance. Its last-layer activation should enforce problem constraints as much as possible. Incentive compatibility should be enforced approximately by having a penalty term in the loss function, and IC violations can be measured by optimizing bidder reports also via a gradient-based method.\n\nFor this problem, the “activation” on the neural network is a regularized version of the proportional fairness problem. So another interpretation of what they do is run a proportional fairness mechanism, with a learned, bidder-dependent regularization term. Both training the neural network and estimating exploitability then require optimizing with respect to the *solution* of that optimization.\n\nIt’s relatively well-known that one can “backprop through an optimization problem” in order to enforce complex or unusual constraints on neural network outputs. Doing it for this particular problem requires the authors to come up with significant technical innovations, though.\n\nPutting all this together, the authors have their RPF-Net architecture and training algorithm, which they run on a bunch of plausible mechanism design problems and show works better than theoretical baselines. A key point is also that it’s possible to visualize and make sense of RPF-Net’s outputs, so it is a tool for exploring the space of mechanisms and not just for optimizing performance.\n\nThere are also some nice extra results, including showing robustness to distribution shift under the TV metric, generalization results following those in Dütting et al.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "The only real reservation I have with the paper is not so important — it’s the last paragraph. I think this paragraph reads oddly given that “differentiating through optimization programs” is something ML researchers have been interested in for many years at this point. The idea is not original and people are well aware of it. (However, this paper’s technical contributions to this long line of research are original.) I think the paragraph could just be safely deleted.\n\nTwo papers that should definitely be cited:\n\n\"Learning revenue-maximizing auctions with differentiable matching\", which does auction design by differentiating through an LP. The technical details are very different (Sinkhorn not inverting KKT system) but similar concept\n\nhttps://proceedings.mlr.press/v151/curry22a.html\n\n\"Deep learning for two-sided matching\": another example of using differentiable economics to explore tradeoffs in a mechanism design situation where there is an impossibility result, though on a completely different problem (Gale-Shapley style matching). For them, it is trading off between stability and IC, as opposed to Nash social welfare and IC.\n\nhttps://arxiv.org/abs/2107.03427\n\nVery weak (not required) request: it would be nice to emphasize very clearly somewhere that exploitability measurements are only empirical. I don't think this counts against a paper like this, but it is sometimes a point of confusion with theorists/economists.", "broader_impact_concerns": "There are no broader impact concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "D7tST4R0DS", "reviewer": "Reviewer_W3sP", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. The authors present a novel method, RPF-Net, which effectively balances Nash Social Welfare (NSW) and potential exploitability.\n\n2. In terms of computational complexity, the authors demonstrate how to compute the gradient, and the algorithm shows lower complexity compared to baseline methods.\n\n3. Experimental simulation results confirm the efficiency of the proposed method.\n\n1. In Section 3, the assumption that the misreport follows a greedy policy with respect to the mechanism in (6) is questionable, especially when agents only have partial information. Under such circumstances, predicting the misreport value through a neural network becomes challenging.\n\n2. From a theoretical perspective, the authors only provide a convergence rate for the generalization error with a finite dataset. However, it is well-known that as the dataset size increases, the generalization error tends to decrease to zero. A more critical issue may be the approximation error from the neural network, which might not approach zero even with an infinite dataset. It is important to discuss whether the neural network can accurately approximate the misreport value and whether gradient descent can find such a network.\n\n3. In the simulation experiments, it is unclear how the misreport value for adversarial agents in (19) is determined, as it appears the mechanism $u_i$ also depends on the misreport value. Additionally, in Table 1, the partial allocation mechanism only achieves about 1/4 of the NSW compared to other methods, which contradicts the related work suggesting that each agent in the PA mechanism should receive at least 1/e of the utility in the corresponding PF mechanism.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work studies the resource allocation problem for divisible items without payment, aiming to improve the Nash Social Welfare (NSW) while reducing exploitability. The authors propose a novel method, RPF-Net, based on a neural network that approximates the misreport value and incorporates a linear regularization designed to enhance robustness against potential misreports. From a theoretical perspective, the authors demonstrate how to calculate the gradient for this complex network and provide a square-root decreasing rate for the generalization error with a finite dataset. Additionally, experimental simulation results support the efficiency of the proposed method.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See Weaknesses.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "1DCYw61pNU", "reviewer": "Reviewer_qw7W", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "One difficulty of this approach is that the optimal misreport depends on the result of the optimization; thus, the gradient of the loss needs to include the outcome of the optimization.  A key technical contribution of the paper is deriving the relationship between the gradient of the optimization's KKT conditions and those of the loss function, allowing for an overall gradient of the loss in terms of the parameters of the neural network.\n\nOverall, this is an exciting and innovative application of the differentiable economics approach to mechanism design.  I think that the gradient translation approach has the potential to be very influential in future work on mechanism design. The technique is developed and described in a very clear way.  The empirical results are largely compelling.  I recommend that the paper be accepted with minor revisions.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors present a neural network architecture that implements an approximately truthful mechanism for maximizing proportional fairness (aka Nash Social Welfare) when allocating resources, without the use of money.  It is known that truthful bidding in this setting cannot be attained without inefficient allocations (e.g., by \"money burning\").  This paper aims to come as close to efficiency as possible while satisfying an approximate truthfulness criterion: that no bidder can improve their allocation very much by lying about their valuation (i.e., their demand and value for each good).\n\nThe proposed system is based on regularization: if we knew the bidders' true valuations in the first place, we could reduce their incentive to lie by nudging each allocation in the opposite direction of their incentive for misreporting.  (i.e., if they bid in a certain way because to increase the allocation of good 1, then artificially reduce their allocation of good 1 in order to make the lie not be worth it).  The auctioneer doesn't know the valuations, so instead a neural network is trained to output an estimated optimal-misreport direction, which will then be used to regularize an optimization that minimizes the regularized NSW.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "My main concerns with this paper revolve around the reporting of some of the empirical results.  I think that these issues will be straightforward to address but will substantially improve the paper.\n\n* Table 1: Are the +/- ranges standard deviations, or 95% CIs, or what?\n* Figure 5: I don't really see support here for the claim that RPF-Net \"determines allocations in a smoother way\" than PF; can you elaborate on what features of this figure lead you to say that?\n* Why does Table 2 give training and inference time for a *specific* ten-agent three-resource problem?  It would be far better to report on the performance on a distribution of such problems and give averages and error bounds (similar to Table 1).\n\n=== Minor issues ===\n\nHere are some additional nitpicks and minor issues.\n\n* p.3: Zeng et al. appear to be /very/ similar; you allude to differences in the \"activation function\" throughout the paper, but it would be very helpful to more explicitly describe the differences early on (most relevantly that they don't need to solve an optimization problem in their output layer).\n* p.3: It's not really accurate to say that [Shoham & Leyton-Brown, 2008] \"design sophisticated monetary transfer schemes\"; this is a textbook.\n* p.3: 0.841 > 3/4, so how do Guo and Conitzer \"nearly\" match 0.841 if Cole et al. prove a bound of 3/4 for $n=2$?\n* p.5: \"By contrast, RPF-Net proposed in this work significantly reduces the exploitability.\": Are you claiming statistical significance?  If so, based on what test?  If not, it is better to use a synonym such as \"materially\" or \"substantially\" to avoid confusion.\n* p.9: Possible typo: $vh(dv,dx,dw)$\n* p.13: \"which shares the same training objective as RPF-Net\": This is somewhat misleading, since ExS-Net doesn't include regularization in its objective, not so?\n* p.14: \"the heavy-tailed Cauchy distribution, which is often used to model unobserved strategic behaviors (Taleb, 2010)\": Is this claim really supported in \"Black Swans\"?  Can you give the relevant passage?\n* Figure 5: Why are all 4 subfigures labelled \"RPF-Net\"?", "broader_impact_concerns": "none", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers all agree that the paper clearly meets the TMLR criteria and would be of pretty broad interest: the approach of differentiating through an optimization problem would be of general interest beyond even just their results in mechanism design.  All of this makes an easy decision.
Decision: Accept (poster)