Optimal Efficiency-Envy Trade-Off via Optimal Transport
Authors: Steven Yin
Christian Kroer
Venue: NeurIPS 2022 Accept (2022)
Keywords: Resource Allocation
Fair Division
Optimal Transport

Abstract: We consider the problem of allocating a distribution of items to $n$ recipients where each recipient has to be allocated a fixed, pre-specified fraction of all items, while ensuring that each recipient does not experience too much envy.  We show that this problem can be formulated as a variant of the semi-discrete optimal transport (OT) problem, whose solution structure in this case has a concise representation and a simple geometric interpretation.  Unlike existing literature that treats envy-freeness as a hard constraint, our formulation allows us to \emph{optimally} trade off efficiency and envy continuously.  Additionally, we study the statistical properties of the space of our OT based allocation policies by showing a polynomial bound on the number of samples needed to approximate the optimal solution from samples.  Our approach is suitable for large-scale fair allocation problems such as the blood donation matching problem, and we show numerically that it performs well on a prior realistic data simulator.

Optimal Efficiency-Envy Trade-Off via Optimal Transport
Steven Yin
Department of Industrial Engineering and Operations Research Columbia University
New York, NY 10027
sy2737@columbia edu
Christian Kroer
Department of Industrial Engineering and Operations Research
Columbia University
New York, NY 10027
christian, hrr.rian....rrrroommmbbb...edddd
Abstract
We consider the problem of allocating a distribution of items to n recipients where each recipient has to be allocated fixed, prespecified fraction of all items, while ensuring that each recipient does not experience too much envy. We show that this problem can be formulated problem, whose solution structure this case has concise representation and a simple geometric interpretation. Unlike existing literature that treats envy-freeness as hard constraint, our formulation allows us to optimally trade off efficiency and envy continuously. Additionally, we study the statistical properties of the space of our OT based allocation policies by showing a polynomial bound on the number of samples needed to approximate the optimal solution from samples. Our approach suitable for large-scale fair allocation problems such as the blood donation matching problem, and we show numerically that it performs well prior realistic data simulator.
variant of the semi-discrete optimal transport (OT)
Introduction
In this work, we focus on the problem of finding an allocation policy that divides a pool of items, represented by distribution D, to recipients, under the constraint that each recipient must be allocated a pre-specified fraction p. of the items, where Pt E (0, 1). p" = is an input to the problem that characterizes the priority of each recipient. We refer to {pr T the target matching distribution. addition to this matching distribution constraint, we also require that the recipient's 's envy, which will define formally later, be bounded. Unlike the existing resource allocation literature, where envy-free is either treated as a hard constraint or not considered at all (in divisible settings), allow the central planner to specify the level of envy that is tolerated, and find the most efficient allocation given the amount of envy budget. This allows us to reduce the envy significantly without paying the full price of fairness with respect to efficiency.
To concretely motivate our model, let us consider the blood donor matching problem that was first studied in [21]. The Meta platform has tool called Facebook Blood Donations, where users who opt in to receive notifications are notified about blood donation opportunities near them. Depending on the user's and the blood bank's 's specific characteristies (e.g., age, occupation for the user, and locations, hours for the blood bank), notifications about different donation opportunities have different
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

probabilities of resulting in an actual blood donation. The platform would like to send each user the most relevant notifications (to maximize the total number of potential blood donations). while maintaining certain fairness criteria for all the blood banks that participate in this program. Although the platform can theoretically send each user multiple notifications about multiple blood banks, for user experience and other practical reasons, this is not done, at least in the model introduced in (27]. Therefore in this problem, users' attention is the scarce resource that the platforms needs to allocate to different blood banks. The most natural type of faimesss criteria in this setting is perhaps the number of users that received notifications about each of the blood banks. For example, it is not desirable to match zero users to particular, potentially reconvenientlylocateee blood bank, even if matching zero users to this blood bank results in more blood donations in expectation.
Another faimess desideratum commonly studied in the literature is called enyy-freenes. We say that recipient envies recipient if A values B's allocation more than her own. Intuitively, an allocation that is envy-free-where no agent envies another agent-is perceived to be fair.
This paper considers both of the two fairness criteria mentioned above: we study a setting where the goal is to maximize social welfare under a matching distribution constraint, while ensuring that each recipient has bounded envy. We make the following contributions in regards this problem:
1.
We formulate it as constrained version of a semi-discrete optimal transport problem and show that the optimal allocation policy has a concise representation and a simple geometric structure. This is particularly attractive for large-scale allocation problems, due to the fast computation of a match given an item. This insight also shines new light on the question of when envy arises, and when the welfare price on envy-freeness is large.
2. We propose an efficient stochastic optimization algorithm for this problem and show that has a provable convergence rate of O(1/vT).
3. We investigate the statistical properties of the space of our optimal transport based allocation policies by showing Probably Approximately Correct (PAC)-like sample complexity bound for approximating the optimal solution given finite samples.
In Section we formally define the problem we are interested in. In Section 4 we show that this problem can be formulated as semi-discrete optimal transport problem, whose solution has simple structure with nice geometric interpretation. Section 5jdevcloss practical stochastic optimization algorithm. In Section we show that an e-approximate solution can be found with high probability given Ō ((2) samples, where n is the number of recipients. Finally, in Section we demonstrate the effectiveness of our approach using both artificial and a semi-real data.
2 Literature Review
Blood donation matching. McElfresh et al. (21) introduced this problem and modeled it as an online matching problem, where the matching quality between an user and blood bank is assumed to be known to the platform. The model formulation there is complex and their matching policy is rather cumbersome, requiring separate parameter for each (donor, recipient) pair. Compared to their paper, we are able to provide better structural insights to the problem by utilizing a simpler model that still captures the most salient part of the problem.
Online Resource Allocation. Another strand of work that our paper is closely related to is that of online resource allocation, especially those with i.i.d. or random permutation input models. Agrawal, Wang, and Ye (2) studied the setting with linear objective and gave competitive ratio bounds. Then, Agrawal and Devanur ( generalized the results to concave objectives and convex constraints. Later, Devanur et al. [4] improved the approximation ratio bounds and relaxed the input assumptions on the budgets. Balseiro, Lu, and Mirrokni (6) show that online mirror descent on the dual multipliers does well under both i.i.d. adversarial, and certain non-stationary input settings. However, none of theses papers study the envy-free criterion. Recently, Balseiro, Lu, and Mirrokni (5) studied an online resource allocation problem with fairness regularization. Although the authors did not explicitly study envy regularization, their regularization framework can be modified to accommodate envy regularization. However, like all the other papers mentioned in this paragraph, the offline solution used as the benehmark to measure regret, but no explicit solution is given to the offline problem. Our analysis focuses on the offline problem, and draws explicit connection to optimal transport,

---

which allowed us to provide a novel PAC-like analysis on the sample complexity of the problem. In another recent paper, Sinclair, Banerjee, and Yu (27] studied the trade-off between minimizing envy and minimizing waste, which refers to un-allocated resources. Despite close similarity between our titles, their offline benchmark the standard Fisenberg-Gale program, which is envy-free, but does not address the welfare cost of achieving envy-freeness.
Fair Division. Envy is a popular concept studied in the fair division literature. A large body of these papers are formulated cake-cutting problem ( ([44 12 23 where the resources are modeled as an interval and the agents' valuations are represented as functions on this interval. Caragiannis et al. [10] provide analysis the worst case efficiency loss due to the envy-freeness constraint. Later Cohler et al. [3] design algorithms for computing optimal envy-free cake cutting allocations under different relatively simple classes of valuation functions. Unlike these papers that focus on the hard constraint of zero envy, we treat the allowable envy as parameter, and find the most efficient solutions subject the desired amount of envy. In indivisible settings, there are some related concepts of envy that does not require strict zero envy. For instance, Budish (9] proposes an approximate competitive equilibrium from equal incomes approach that achieves envy free up to 1 item (EFI). Caragiannis et al. [IT) introduce the concept of envy free up to the Least Valued Good, which is a stronger version of EFI. Although these papers do allow a small amount of envy, these concepts are introduced mainly to circumvent the impossibilities introduced by the indivisible settings, not to allow central planners control the level of envy tolerance. Finally, Donahue and Kleinberg (15) also studies setting where the central planner can set his own tolerance of (un)sairness. However their setting is quite different from ours, as they consider the allocation of fixed amount of identical resource, where as we assume that recipients have different valuations for the different items.
Optimal Transport. OT has been applied before in resource allocation settings in the economics literature (see [17 for survey). For example, the Hotelling location model with continuous mass of consumers can be solved with the same assignment procedure as the one we consider for our allocation problem without envy constraints. The more general method of assigning points in space to finite set of sites via this procedure was developed by Aurenhammer, Hoffmann, and Aronov (4]. Scetbon et al. (23) consider an OT setting with equitability (every agent's final utility the same), which is different faimess criteria from envy, and also not adjustable like in our setting. To the best of our knowledge, no existing application of OT models the envy constraints that we consider here.
2.1 Background on Optimal Transport
Since our work draws explicit connection to optimal transport (OT), we provide a summary of key OT results here. Let a, 3 be two probability measures on the metric spaces X, )' respectively. We define II (3 as the set of joint probability measures X' x ) with marginals a and B. The Kantorovich
Kantorovichhorrmlattoon formulation of the optimal transport problem [19] can be written as
/ cxx, (x)))(((,))) =CIl(o..)) xxx
L(a, 3) = min
where c(z. y) is the cost associated with "moving" x to y. This is called a transportation problem because the conditional probability π (y) specifies a transportation plan for moving probability mass from X' to Y. Note that π (2. T (d))rrddxxr) If ,3 is a discrete measure, i.e. y is finite, then
it is known 3 that the dual to ( can be written as (here we abuse the notation (3 to also represent the vector of probability masses, where 33 is the probability mass on point ys):
max E())= = Σ gER
c(x, wi) g. do(x) + g
sE[n] Lo)
where n 1)%, and Ly is what is sometimes referred to as the Laguerre cell:
Ly (g) {x :ivi + j, j,c(z, v) 9. S c(x, vj) gj}
(3)
Proposition 1 (Proposition 2.1 3)- Ifa is continuous measure, and 3 discrete measure, then L(a, 3)= = max (g), and the optimal solution N of (I) is given by the partition (Ly, (,i E [n]]. i.e. dπ 91) da(x) if E Ly)
9
). 0 otherwise.
3

---

3 Problem Formulation
There is a of n recipients V. There is a "pool" of items, represented by a distribution over X' S [0, _j". Each random draw from this distribution X ~ a is vector representing the n recipients' valuations of this item. The goal is to maximize the expected matched utilities of the recipients, while maintaining the constraint that the recipient is matched p; fraction of the times in expectation. 1 {pt Ji=1 is called the target matching distribution, which intuitively represents recipients' importance. Note that the constrains here are satisfied in expectation, which are sometimes referred as "ex-ante" guarantees. The reason why we consider ex-ante guarantees has do with the type of application we're re interested in. Our motivating example is concerned with recommending hundreds of millions of users to different blood banks. In such settings, even if we want the constraints hold ex-post, the large-scale nature of the problem and the law of large numbers means that in-expectation guarantees translate into something that is very close to holding ex ex-post. That is why for internet platform problems, requiring constraints to hold in expectation is a standard setup (see for example the literature on budget constraints in ad auctions, where this the case (7). matching policy π takes valuation vector and maps it (potentially with randomness) to one of the recipients. Let T T (z) denote the probability of matching the item to y given valuation vector z. The basic problem formulation is to solve the following optimization problem:
Here
a
max EE X
Σ ( XX]
s.t. P [x) p Vie [n]
WLOG, we assume that pt > O for all i. An example of such problem can be see in Figure 1, where is a distribution regions (given to A and B respectively) such that each region covers the desired PAA Pi probability mass. Note that the orange and blue regions are allowed to over lap (probabilistic partition), and that the boundary does not have to be linear as illustrated in the figure. As we will show later in Section 4 despite the large design space permitted by the formulation in smaller design space.
the unit square, and the goal is to partition the square into blue and orange
in fact focus much
In resource allocation problems, it is often the case that care not just about efficiency (the sum of all recipients' utilities), but also other fairness criteria. One of the most commonly studied fairness criteria is envy-freeness. Agent Yi envies another agent y if agent ys values the allocation given to Yy more (after adjusting for their priority weights). We can formally define agent y 's envy as
Eneyyy: max E., X j
P. P5
(xxl
(5)
Instead of the vanilla formulation we consider the following more general formulation:
max Ex
X X)]
(6)
s.t. P ([ = pt Vi [n]
Envy(w: S A Vi
Most existing literature focuses on finding allocations such that Enay(ys) is most for every y:- This can be very restrictive constraint, often satisfied at the cost of reducing efficiency by significant amount (This reduction sometimes referred as the Cost-of- Ffirnes-F We take a different approach, and allow the central planner to set non-negative constraints on envy. Note that since we are motivated by internet-scale problems such as allocating hundreds of millions of users to donation centers, we focus on the ex-ante guarantees on the constraints.
4 Optimal Solution Structure
The space of feasible solutions for (6) is large, which makes the problem difficult to optimize directly. However we can use the tools from OT to reduce the search space to something with much more structure. The key observation is that (6) can be formulated as variation of the semi-discrete optimal transport problem given in Equation

---

Maxthed to
Mastted
Figure 1: Left: An illustration of what Laguerre cells look like when n Consider any distribution on the support [0, 1)2. The optimal division of the space is to move the diagonal line up or down until the probability mass contained in the orange region is equal to p". Right: A pictorial proof of the optimality of such partition. Suppose one can find an mass above this line that is matched to A, and an e mass below the line that matched B, then switching the assignments of these two regions increases the matched weights because B1 + A2 A + B2.
Let's first consider the simpler case in 4 where there are no envy constraints. this case, the problem can be stated in the form of as follows: the cost function is the negative utility of
the matched recipient c(x, y/4 = -2; the 3 measure is the discrete measure Σi= P. 63 and the
matching policy x (ylaz) in (6) exactly the conditional probability of the joint distribution in Α From Theorem Tit follows that the optimal matching policy represented by Laguerre cells given in 3 is matched to y4 if i arg ming -I gs- Note that the dual variables g E R" serve as an "ajjustment" over the agents' reported utilities, and the resulting matching policy is simply a greedy policy over this adjusted valuation vector.
24 t 2 Iy + 9x} To visualize this better, consider the simple setting with two recipients A, B where their valuations for an item is joint distribution supported on [0, 1]2. Suppose we want to match p* fraction of the items to recipient B. Figure I gives a proof-by-picture that the optimal strategy is to divide the space up with a slope-1 diagonal line such that the probability mass lying above the line equal to p'. This geometric interpretation of the matching policy plays crucial role in getting us sample complexity bound later in Section
fx 0 Geometrically, each Laguerre cell simply the intersection of spaces: Lg(g) N
With this geometric interpretation of the solution space in mind, let us consider the more general case with envy constraints as formulated in (6). The envy constraints can be added the OT problem in (1) like so:
rEII(a. Jx ((x,))d7(E,,)
L(, A) min
s.t. / c(z, 9;) (1, / c(x, 91 (d mk)
Bi Be
A v(JA) E in|
Although envy constraints make the solution space more complicated, show that it retains the geometric structure of being the intersection of half-spaces. The dual of (7) can be derived using theorem:
E(g, = Σ I.,,
E//
J.,,,, (an)
Inclæ, By do(() T
Σ Tadg J.b
(8)
VER"MEER""
jE(ni
where
F,.(I, = 1 [1+En
Yikk c(x,3;)
Mkyolz, -nnje(a Uk)
gjs
(9)
B₁
Lg(g,7)= I X
arg min (x, 5/)
(10)
y'Ey
Theorem 1. a is continuous measure, and a discrete measure, then L(a, B, = max Elg, 7).
9.7
and the optimal solution æ of 7 is given by the partition (T.,, 7")4 E [m]): dr (I, da(a))
if x E (g" ,"),,, 0 otherwise.
5

---

Note that when c(z. (k) = -2, (T. L, y) given in Equation (TO) are still intersections of half spaces (some examples are given later in Figure 2). Furthermore, the allocation policy can be interpreted as greedy policy based on the adjusted utility given by which contains additional interaction terms that take envy into account.
(1,,)))))))))) M2) is linear in z, which means that the new Laguerre cells
5 Stochastic Optimization
In Section 4
we showed that the optimal allocation policy to our problem has a simple geometric
structure in the form of Laguerre cells. In this section we present practical algorithm for actually computing the optimal Laguerre cells. First we show that the objective function (gg, 7) in (6) is concave by rewriting the objective follows:
E(g. 7) = / min Fr,c dd(x)) + + iE(n)
E Izkk3
(11)
Since (x, y/) is linear in g and y and taking minimum preserves concavity, the objective function concave. Therefore, the dual problem is a constrained convex optimization problem. The gradient of 7g. can be computed as follows:
VgE(g, 7)s = I (0)))
da(x) + 33
(12)
V,E(g, I (0m))
-.n dxr,)) Bi Be
dx, Uj v)))d(()))))))))))))))))){)))(
da(x)) - X
(13)
(9.))
Algorithm 1: Projected SGD for Envy Constrained Optimal Transport
Input: Distribution o, target matching distribution p", timesteps T. Initialize 9o = 0, 0, /T
do for I <- 0,1,2.....
Sample 2t
J0+1 t 9t + 17 (g(8)))
7++1 f (ne [
6 return Et=1 9t/T,, Σt= T/T
Calculating this gradient is hard, as involves integration over an arbitrary measure a. However, an unbiased, stochastic version of the gradient can be easily obtained from a single sample x ~ a:
veE(g,n) = =11 LLy, (g. 7)] 33
(14)
Bj 1[2 E Lyg (g. r)] X3
(gE 7)sk = c(x, ] E L,, (g. 7)1 - c(xx Uj)
(15)
BR
The details of the algorithm given in Algorithm | Standard projected SGD analysis (see for example (18) tells us that Algorithm converges at the rate E(g", & (E E(rr)) < O
VT
Learning from Samples
So far we have assumed that the true underlying distribution is known, and that we can freely draw independent samples it. In many settings, we only have access a in the form of finite number of i..dd samples. The goal of this section is to establish sample complexity bound for solving the dual problem (8).
In this section, we focus only on the assignment cost function c(x, ys) = - 24, which models our original resource allocation problem proposed in Section 3 independent samples from a. The empirical version the dual objective (II) is:
Let S = {XX X² ..... Xm) be
Es(g,n) 7)
m Σ
min (X y.) + T 3- vEln)
Σ Tekd,
(16)
jkb

---

Let 9s. iss be the empirical maximizer given the set of samples S: (ās. fis) == arg max (g
and g 7" be the population maximizer (g", ?") = arg maggax& [g. 7). We want to bound the number of samples needed so that "(g","") {Øs, fis) is small with high probability. Let's introduce some notations to facilitate our later discussions. Define the following hypothesis class for each
F. x + Fn,el2, wi) + g
E Jkkjjk
RD(n-1) Jhudg g R", 777 R+
(17)
as well as the overall hypothesis class:
F x + min (2, y1) + +
Σ J.bi
Tak : "gER,, R R2(x-1)
(18)
sE|n]
Plugging c(ar, (/3) = -2, into the definition of F7.e- we see that for a given y, and y, the corresponding
hypothesis f. E F; can be written as fi(x) = w x + b, where
(1 + Σ Vik),
if =
wy
and
(19)
31 Yii 33,
if ti
b = 9i + 3 T
Σ
Tz
(20)
J.k.f
also follows that
FC Fin == fx min f((x) fi F.)
(21)
Note that F defined in (18) is the main object of interest, as it contains all the possible Laguerre cell parameters. We showed in (2T) that from n affine hypothesis classes. This interpretation of the original hypothesis class as the minimum over n affine hypothesis classes is the key observation to prove the sample complexity bound. We prove our main result under the following boundedness assumption:
most as complex as Fiins hypothsis class constructed
Assumption 1. The hypothesis f(x) min; f((x) min wt x + b³ corresponding the optimal
dual solution g²,n x imply that F; and F are uniformly bounded by RE + R.
satisfies ||w||
v 16'| < R for some R > particular, these assumptions
that this is essentially bound on the optimal dual variables g g¹, - and a bound on the ratio B//3, both of which are determined by the input distributions a, ,, and do not depend on the number of samples. In other words, R is problem dependent constant.
From (19 and (20)
Theorem 2. Under Assumption
[ for a given sample size m, with probability E(g",
(v (1og (Vuggm)) +log(()))))))))
(
(Viree
E(gs, 1t) O
The proof of this theorem be found in the appendix. We will provide some high level intu- ition here. The proof uses the fat-shattering dimension, which concept that generalizes the Vapnik-Chervonenkia (VC) dimension functions of real values. Like the VC dimension, the fat-shattering dimension is measure of capacity for a class of functions. The larger the fat-shattering dimension, the more "complex" the function class is. Intuitively, the more complex the function class is, the more samples one needs to accurately identify the optimal function within that class. Recall that the object of interest in our paper is the Laguerre cell, whose boundaries are defined by set of hyperplanes. Readers readers familiar with traditional PAC learning results might recall that hyperplanes have a low VC dimension. It turns out that the hypothesis class associated with Laguerre cells defined above in (18) has a low complexity as well. Similar to how low VC dimension leads to low sample complexity classification tasks, the fact the boundaries of our Laguerre cells are consisted of hyperplanes also lead to low sample complexity in our setting.
7

---

Assigned to Assigned to
Assigned to Assigned to
Assigned to Assigned
52
0.4
53 Utitiy A
3.0
20
Ubiloy for
for
Figure 2: Allocation policy for artificial data under different envy constraints. From left to right: = 0.2, 0.1, 0.0. When the envy constraint loose (large e). B envies A, since both agents prefer the items on the top right, but most of them are allocated to A. As the envy constraint tightens, the allocation boundary tilts in the direction that makes the allocations more even between the two agents.
Erivy Welfare Trade-Off
Learning Quality Number Samples
Percent Welfare Cap
Simulator Data
log 291 11"1 260 Vell
Simulattr
Percent Welfare
0.00
Artificial Data
Artifcial
Log
165
0.15
0.25
2.25
0:50
Max Normalized Enwy
lagm
Figure 3: The trade-off curve between envy and welfare for both data-sets. The shaded region between 25th and 75th percentile of the trials. The non-monotonicity in the plot for the simu- lator data is due to the stochasticity in the SGD algorithm.
Figure 4: Approximation gap with respect to sample size. Both and axis in log scale. The solid line is the median and the shaded re- gion is between the 25th and 75th percentile. The dashed lines show what the theoretical 1/ rate would look like.
Relation to Section 5 Note that there is some connection between the convergence a stochastic optimization method (computational complexity). and the sample complexity bound of the same problem (learning complexity). Both say something about the number of steps/samples one needs to arrive good solution. However, in general, these two things not the same. In particular, the learning complexity result from this section is algorithm agnostic. The proof of Theorem 2 actually implies uniform convergence: that matter which hypothesis objective will be close to the expected objective. However, Theorem 2 does not provide a way for practitioners to actually compute the solution. The result from Section 5n the other hand does provide an algorithm for practitioners to use, and shows that the algorithm is computationally efficient. However, the convergence result in Section Jonly works for the specific optimization method that we proposed. Therefore these two results are complements of each other, and together paint a relatively complete picture on how difficult the task it.
considers, its' empirical
Experiments
We test solution with both artificial data, and simulated data from realistic simulator for blood donor matching developed by (21). The artificial data contains two recipients, and their valuation distribution a linearly transformed uniform distribution. This is make visualization of the resulting allocation policy easier. The simulator data is based on geographical and population information from San Francisco, and contains 5 recipients. To set the envy budgets À R", we first decide constant E R4, and then multiply this by the target matching distribution p" E R Xij cp, Vi, j. With this setup e is bound on the normalized envy for each recipient: 1 p. En) I e Vi. Figure 2 change As the envy constraint tightens, the
illustrates how the allocation policy changes decision boundary tilts in the direction that split the "good" (items which both agents prefer) and "bad" (items which both agents dislike) items more evenly between the recipients.
Next we investigate the trade-off between envy and social welfare by using SGD to compute approxi- matcly optimal allocations for varying We plot the percent welfare gap (difference between the
8

---

maximum welfare without envy constraints, and the welfare with envy constraints, divided by the former) with respect to realized, max normalized envy. Figure the result. For the simulator data, the welfare gap is small even with no-envy constraint, which means that aiming for envy free allocations might make sense. In the case of the artificial data however, paying 50% of the full price of fairness reduces 65% of the envy. In such settings, one might want to sacrifice some envy for better welfare.
These experiments also highlight when envy arises. When recipients" utilities are highly correlated, but one recipient has larger variance than others, that recipient receives almost all the good items (which results in large envy for other recipients), even though others value the items almost as much. In such cases, a small reduction welfare can reduce large amount of envy. This seems be the case for the simulator data. On the other hand, if utilities are correlated, but only one recipient has very strong preferences, then allowing a small amount of envy can improve the welfare significantly.
Finally, in Figure we investigate the quality of the empirical solutions as the sample size increases. can been seen that the approximation gap decreases faster than the theoretical rate, confirming our sample complexity bound in Theorem 2
8 Limitations and Future Directions
Although we believe that the model proposed here is natural, and captures the most salient aspects of some of the resource allocation problems in real life, any implementation of our proposed strategy in critical applications such as blood donation should prefaced with more rigorous backtesting in order to minimize the risk of unintended consequences in application specific metrics not studied in this paper.
For future directions, one key property that we did not study in this paper is the problem of incentive compatibility. For our motivating application of blood donation, this is not an issue because online platforms such as Meta has proprictary models that can predict the matching quality between donor and recipient. This means that the platform observes the value of matchings without having to rely on the recipients to self-report. This is also true in many other online matching problems such as sponsored ads. However, in settings where the central planner relies on the recipients to self-report their valuations for each of the items, incentive compatibility becomes a crucial issue. We are excited about the potential of using Optimal Transport in fair-division, and plan on exploring the incentive issues in future work.
References
[1] Shipra Agrawal and Nikhil R Devanur. "Fast algorithms for online stochastic convex pro- gramming". In: Proceedings of the twenty-sixth annual ACM- symposium on Discrete algorithms. SIAM. 2014, pp. 1424-1424.
[2] Shipra Agrawal, Zizhuo Wang, and Yinyu Ye. "A dynamic near-optimal algorithm for online linear programming" In: Operations Research 62.4 (2014), pp. 876-890.
[3] Genevay Aude et al. "Stochastic optimization for large-scale optimal transport". In: arXiv preprint arXiv:1603 08527 (2016).
[4] Franz Aurenhammer, Friedrich Hoffmann, and Boris Aronov, "Minkowski-type theorems and least-squares clustering". In: Algorithmica 20.1 (1998), pp. 61-76.
[5] Santiago Balseiro, Haihao Lu, and Vahab Mirrokni. "Regularized online allocation problems: Fairness and beyond"'. In: International Conference on Machine Learning. PMLR. 2021,
pp. 630-639.
[6] Santiago Balseiro. Haihao Lu, and Vahab Mirrokni. "The best of many worlds: Dual mirror descent for online allocation problems". In: arXiv preprint arXiv:201 /. 10124 1.1122 (2020). [7] Santiago R Balseiro, Omar Besbes, and Gabriel Y Weintraub. "Repeated auctions with budgets in ad exchanges: Approximations and design". In: Management Science 61.4 (2015), pp. 864- 884.
[8] Peter L Bartlett, Philip M Long, and Robert C Williamson. "Fat-shattering and the learnability of real-valued functions". In: journal of computer and system sciences 52.3 (1996), pp. 434- 452.

---

[9] Eric Budish. "The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes". In: Journal of Political Economy 119.6 (2011), pp. 1061-1103.
[10] Ioannis Caragiannis al. "The efficiency of fair division". In: International Workshop on Internet and Network Economics. Springer. 2009, pp. 475-482.
[11] Ioannis Caragiannis et al. "The unreasonable fairness of maximum Nash welfare". In: ACM Transactions on Economics and Computation (TEAC) 7.3 (2019), pp. 1-32.
[12] Yiling Chen et al. "Truth, justice, and cake cutting". In: Games and Economic Behavior 77.1
(2013), pp. 284-297,
[13] Yuga J Cohler et al. "Optimal envy-free cake cutting". In: Twenty-Fifth AAAI Conference on Artificial Intelligence. 2011.
[14] Nikhil R Devanur al. "Near optimal online algorithms and fast approximation algorithms for resource allocation problems". In: Journal of the ACM (JACM) 66.1 (2019), pp. 1-41.
[15] Kate Donahue and Jon Kleinberg. "Fairness and utilization in allocating resources with uncertain demand".. In: Proceedings of the 2020 conference on fairness, accountability, and transparency. 2020, pp. 658-668.
[16] Richard M Dudley. "The sizes of compact subsets of Hilbert space and continuity of Gaussian processes". In: Journal of Functional Analysis 1.3 (1967), pp. 290-330.
[17] Alfred Galichon. Optimal transport methods in economics. Princeton University Press, 2018.
[18] Nicholas Harvey. "Machine Learning Theory Lecture 17". In: (2018).
[19] Leonid Kantorovich. "On the transfer of masses (in russian)". In: Doklady Akademii Nauk,
37(2) (1942), pp. 227-229.
[20] Aryeh Kontorovich and Idan Attias. "Fat-shattering dimension of k-fold maxima". In: arXiv preprint wxXiv:211000766. (2021).
[21] Duncan C McElfresh et al. "Matching algorithms for blood donation".. In: Proceedings of the
s ACM Conference on Economics and Computation. 2020, pp. 463-464.
[22] Shahar Mendelson and Roman Vershynin. "Entropy and the combinatorial dimension". In: Inventiones mathematicae 152.1 (2003), pp. 37-55.
[23] Elchanan Mossel and Omer Tamuz. "Truthful fair division".. In: International Symposium on Algorithmic Game Theory. Springer. 2010, pp. 288-299.
[24]
Jack Robertson and William Webb. Cake-cutting algorithms: Be fair if can. CRC Press, 1998.
[25] Meyer Scetbon et al. "Equitable and optimal transport with multiple agents". In: International Conference on Artificial Intelligence and Statistics. PMLR. 2021, pp. 2035-2043.
[26] Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.
[27] Sean Sinclair, Siddhartha Banerjee, and Christina Lee Yu. "Sequential Fair Allocation:
Achieving the Optimal Envy-Efficiency Tradeoff Curve". In: arXiv preprint (2021).
[28) Karthik Sridharan. Note on Refined Dudley Integral Covering Number Bound. 2021. URT.: https: /stps://www..om cs. fttps://www.cs.cornell.. http///rridaraa/adddiaa .pdffl
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Section 8
(c) Did you discuss any potential negative societal impacts of your work? [Yes] See Section 8
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
10

---

3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main exper- imental results (either in the supplemental material as a URL)? [Yes] Included as supplemental material.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Appendix A..3
(c) Did you report error bars (c.g., with respect to the random seed after running experi- ments multiple times)? [Yes] See Figure -
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See Appendix A..3
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [Yes] Yes, this cited paper is this one:
[1T
(b) Did you mention the license of the assets? [Yes] See Appendix A.2
(c) Did you include any assets either in the supplemental material as URL? [Yes] Our code is provided as supplemental material.
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A] We used the simulator developed, and made public by the authors of paper that we cite. There no personal information in simulator data.
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A] We did not crowdsource or conduct research with human subjects. (b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]


Reviews:
[{"review_id": "uqsFI5ejxS0", "reviewer": "Reviewer_ndyP", "summary": "The paper studies a fair division problem inspired by Facebook’s blood donation program: a continuum of divisible goods must be allocated to “receivers” with additive utilities in such a way that (1) each receiver $i$ receives a target fraction $p_i$ of all goods, such that (2) each receiver $i$ has envy below some given bound $\\lambda_i$, and such that, within these constraints, (3) utilitarian welfare is maximized. The paper reduces this problem to a form of optimal transport, from which they derive results about the structure of optimal allocations, a convex optimization formulation, a stochastic gradient descent algorithm based if the distribution of goods can only be sampled rather than being explicitly given, and a PAC-style learning algorithm if a finite number of samples are available. The authors test these algorithms on synthetic and semi-synthetic data, and empirically investigate the price of tighter envy bounds in terms of welfare.", "questions": "No specific questions, but please feel free to respond to anything you’d like.", "limitations": "No complaints.", "rating": 5, "confidence": 3, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I was pleasantly surprised by the results of this paper. I wasn’t familiar with optimal transport, and would have assumed a priori that the optimization problem solved in the paper would lead to quite messy solutions and approaches. But the authors show that by using the right kind of duality and (what sounds in their writing like standard) approaches from optimal transport and learning theory can make quick inroads into this problem. Given that I am not an expert, I cannot judge the novelty of the technical contribution, but they were new to me.\nI also really appreciate the empirical evaluation, which studies three well-selected questions in little space. Each of the three figures on page 8 tells an interesting story.\n\nMy main point of critique is the exposition, which is very math-heavy and not particularly accessible to an outside audience. In some sense, I think that this is the drawback of my first positive point: some of the paper’s value comes from bringing techniques from other fields into fair division, but the paper could do a better job at actually speaking to a fair-division audience where these tools aren’t yet common knowledge. I want to exclude Section 2.1 from this critique, which did a decent job at laying out the basic background of Optimal Transport. By contrast, a lot of the technical material references so many results from existing papers with so little description that I couldn’t take much intuition from it. I also think that the analysis of Algorithm 1 (stochastic gradient descent) should be proved in the supplementary material. More generally, part of the paper consists of more formulas than text, which makes following along much more painful than it would have needed to be. I would strongly recommend putting more of the technical details into the appendix and trying to convey in words more of an intuition of how the argument proceeds and why it works.\n\n## Minor comments:\n\n(1) To me, the word “receiver” sounds like radio terminology, not fair division. In case this is not already established language, how about “recipient”? At a quick glance, McElfresh et al. seem to also use this word.\n\n(2) Equations like Eq. 2 would be much easier to parse with parentheses.\n\n(3) I was going to complain about the missing derivation of the Fenchel dual, but saw it in Appendix A.1, which isn’t mentioned anywhere in the draft. I’d encourage the authors to change that!", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "kC5nMJvTed2", "reviewer": "Reviewer_GLsA", "summary": "This paper considers the resources allocation problem where each of $n$ receivers has to be allocated a fixed fraction of items. For each round an item is drawn from a distribution $\\mathcal{D}$. Each item can be represented by a vector $x$ in $\\mathbb{R}^n$, where $x_i$ is $i$-th receiver's value of this item. In this model the optimal allocation rule that maximizes social welfare can be model as the solution to a semi-discrete optimal transport (OT) problem. The solution structure and efficient algorithm via stochastic optimization are well-studied in the literature of OT. \n\nThe main contribution of this paper is that they study the tradeoff between envy and efficiency in this model. They add one envy constraint for each receiver: envy of receiver $i$ against any other receiver should be bounded by $\\lambda_i$. The goal is to find a socially optimal allocation rule under these constraints. They apply Fenchel-Rockafellar duality to characterize the optimal solution, which is in a similar form to the original OT optimization problem without envy constraints. The paper shows that with slight modification, the stochastic optimization for the original OT problem is efficient for the new problem. Finally the authors provide a PAC-like sample complexity bound using standard Rademacher complexity argument.\n\nThe authors also provide some numerical simulation results of their framework.", "questions": "- Does not provide many real world applications of their model. The only application discussed in the paper is the blood bank donation. It would be great if the authors can provide more potential real world applications.\n", "limitations": "The authors adequately addressed the limitations and potential negative societal impact of their work.", "rating": 7, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The paper considers an important model of resource allocation. The tradeoff between envy and efficiency is also a natural question to ask in the setting.\n\n- The paper studies this model comprehensively, it not only characterize the optimal tradeoff between envy and efficiency but also give a PAC-like sample complexity bound.\n\n- The paper includes some numerical simulations.\n\nWeaknesses:\n\n- The literature review is a bit problematic. As far as I am concerned, some previous works have been discussed applications of optimal transport in resources allocation and mechanism design problems (see e.g. A. Galichon, Optimal Transport Methods in Economics). The authors should have discussed these results.\n\n- As of technical parts, techniques and proofs are not very interesting in general. Everything seems to be standard. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "T4yQSXCVJ1F", "reviewer": "Reviewer_3mgQ", "summary": "The key contribution of this paper is the formulation of the resource allocation problem with envy restrictions as a variant of the semi-discrete optimal transport problem, which can thus be solved using the projected SGD algorithm.  The paper also shows some statistical properties that may be helpful for its real world applications.\n", "questions": "Though the paper looks reasonable, there are still places that can be improved. \nFor example, the paper did not show clearly the relationship between conditional probability and joint probability in the optimal solution structure, which makes the problem formulation less strict. It would be more convincing if the paper can put these details into the appendix.\n", "limitations": "The paper solves the problem using some SGD method. Thus, from an algorithmic point of view, it does not provide any new method or improvement. Although the paper presents a new way to look at the envy-tolerance resource problem, it does not show  how the optimal transport properties play roles in the solution. Another limitation is that the appendix is not well written. Some deductions in the appendix \nneed to be clearer and more detailed.\n", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The strength (also novelty) of this paper is that it relaxes the resource allocation problem with envy-free restrictions to the one with envy-tolerance. It also proposes a semi-discrete optimal transport variant formulation. \n \nOverall, this is a good paper and well organized. The assumptions and problems are explicitly stated. The novel formulation may provide the possibility of applying various optimal transport methods to envy-related resource allocation problems. \nThe SGD method is not new, but serves the purpose adequately. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "1o13chfEk7X", "reviewer": "Reviewer_yMJc", "summary": "Here the authors consider the problem of allocating a distribution of items to $n$ fixed individuals (named \"receivers\") subject to a fixed fraction constraint, while simultaneously ensuring minimal envy.  At a high level, the authors show that this problem can be formulated as a variant of the optimal transport problem subject to a particular cost function (and the fact that \"one\" if the distributions in the problem is discrete).  The authors then show convergence guarantees for an empirical version of stochastic gradient descent using observed samples from the underlying distribution, and complement their results with a numerical simulation on a synthetic and practically motivated dataset.\n\nTo be more concrete, the authors consider a fixed set $n$ of individuals $Y$.  There is an \"infinite\" number of items represented by a distribution $\\alpha$ over $[0,1]^n$ where each draw from this distribution $\\alpha$ is a vector representing each individual $i$'s utility for the particular item.  The goal is to maximize the expected utilities of the individuals, while maintaining the constraint that each individual $y_i$ is matched at least $p_i$ of the items in expectation.\n\nThe authors consider allocation policies $\\pi$ which takes in a valuation vector (i.e. the $n$ dimensional vector of individual utilities for the item) and maps it to one of the $n$ receivers.  The basic formulation is then to solve the optimization problem to maximize the $\\sum_i X_i \\pi(y_i | X)$ subject to the constraint that $\\Pr(\\pi(y_i | X)) \\geq p_i$.  Note that the objective function maximizes the utilitarian welfare, and the constraint ensures the target matching constraint.  However, one (potentially) additional desired property is envy-freeness.  This can be incorporated by allowing a tolerance $\\lambda_i$ of envy for each individual, and adding the constraint that $\\max_j u_i(\\pi_j) - u_i(\\pi_i) \\leq \\lambda_i$ where we drop some notation and use $u_i(\\pi_j)$ to denote the expected utility for $i$ given $j$'s allocation.\n\nThe main result of the authors is three-fold under this model:\n1. Connection to Optimal Transport: The authors show how while the feasible solution space to this problem is large, tools from OT and Fenchel Duality can be used to show a relationship between Optimal Transport (under a negative linear cost function) to an optimal solution.  In particular, the authors show that the optimal solution is given as a greedy function over a partition (called \"Laguerre cells\").\n2. Practical Optimization: The authors then show that the dual of the optimization problem (in the OT formulation) can be solved either with stochastic gradient descent or samples.  With this the authors show a high probability convergence guarantee on the utilitarian welfare scaling as $1 / \\sqrt{m}$ where $m$ is the number of samples.\n3. Experiments: The authors complement the theoretical results with an experiment on a synthetic dataset and a practically motivated one, highlighting the empirical loss in efficiency as one modifies the fairness constraints and empirical convergence rates.", "questions": "### Questions\n1. The comparison between section 5 and section 6 potentially could use more emphasis.  In Section 5 the authors highlight how stochastic gradient descent with samples (unbiased from the true underlying distribution) achieve a particular convergence guarantee.  However, in section 6, this is then done again via a slightly different method, is the only intuitive difference being obtaining high probability versus in expectation guarantees?\n2. Frequently in the paper the authors mention that their work addresses the welfare cost for achieving envy-free solutions.  Are there any theoretical results supporting this claim, highlighting price of fairness under this model?\n\n### Minor Comments\n- In paragraph , \"Unlike the existing resource allocation literature, where envy-free is treated as a hard constraint or not considered at all\" is not totally true with the ongoing literature studying EF1/EPX, etc with divisible resources, (Donahue + Kleinberg 2019), etc.\n- The second bullet in line 51 could be expanded more\n- The \"proof by picture\" in Figure 1 should be expanded more\n", "limitations": "In Section 8 the authors properly address the limitations and potential negative social impact of their work - notably being that any implementation of the strategy for designing allocation mechanisms must be used carefully in critical scenarios such as blood donation settings.", "rating": 5, "confidence": 3, "soundness": 4, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n1. Model + Theoretical Results: The theoretical results presented in section 4 is novel to the fair resource allocation literature, by making an explicit connection between allocation policies and optimal transport literature.  As the authors state, this avenue leads to interesting future directions both theoretically and practically as more tools from OT are used in the literature.  In particular, to some extent, the model presented can be thought of as an \"infinite resource\" version of many exiting literature, which typically assumes that the distribution governing utility of individual is also discrete.\n2. Quality of Results: The theoretical results presented in section 5 + 6 help highlight the ability to use the dual of the OT formulation practically to an algorithm design.\n3. Relation to Existing Literature: The authors do a good job relating the current analysis to the optimal transport literature, especially for readers in the fairness community who would be less aware of this line of work.\n\n### Weaknesses\n1. Weakness of Results: One aspect that the authors mention frequently in their paper is their ability to understand the \"optimal tradeoff\" between envy and efficiency.  While the OT formulation allows them to optimally solve for the solution given the additional envy constraints, there is no theoretical results or justification on the \"efficiency\" loss one observes when adding the additional envy constraints.  There are numerical simulations highlighting this aspect, but the theoretical results are lacking in that regard.  Outside of formalizing the relationship between allocation policies and optimal transport, the authors provide straightforward ML generalization guarantees and SGD formulation.\n2. Relation to Existing Literature: The authors need to improve on situating their paper in the fair resource allocation literature.  In particular, some model primitives (i.e. ex-ante vs ex-post allocations, relation to the \"price of fairness\" eg (Donahue + Kleinberg, 2019), etc need to be better made clear after describing the model (more of this in next bullet).\n3. Writing + Practical Motivation: The authors do an amazing job highlighting the connection between the optimal transport literature and fair resource allocation.  However, the practical description of their model and relation to previous literature on fair resource allocation needs to be expanded more.\n- Model Description: The paper could use a more concrete model description, in particular substantiating some of the model parameters in the running blood matching example.  For example, in line 40/41 are the receivers here the blood bank vs. individual users of the blood blank matching platform?\n- \"Target Matching Distribution\": The target matching distribution $p_i^\\star$ is introduced with no practical motivation.  It leaves questions open like why the matching policy only needs to satisfy these constraints in expectation instead of almost surely (where then the problem is trivial), how they should be chosen, and their relationship to the envy-free guarantee which is described later.\n- Ex-Ante vs Ex-Post Allocations and the Online Structure: The matching policy solved for $\\pi$ denotes the probability of matching an item to $y$ given a specified valuation vector $X$ (denoting the utility of the $n$ individuals for the given item).  Consider an application of this policy: an item is observed (hence an $X$), and the item is matched or shared at the discrete fractions $\\pi(y | X)$.  However, notably this does not satisfy the target matching distribution (although...if those constraints were added almost surely the problem would be trivial).  However, the hindsight solution (i.e. once $X$ is observed) is trivial, either allocate based on the fractions $p_i^\\star$, or allocate to the individual who cares the most, or subject to some envy-freeness constraints guaranteed by $\\lambda$.  The motivation for considering these \"ex-ante\" allocations is never explicitly given.  Moreover, the objective problem is only situated to consider a \"single\" item drawn from the infinite set of items, instead of considering potentially multiple allocations (although this is somewhat abated by the expectation).  The relationship between the model considered here and the related literature (e.g. Donahue + Kleinberg highlighted earlier and the literature therein), or a discussion on the relationship between the blood bank problem should be included.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept