Fair and Welfare-Efficient Constrained Multi-Matchings under Uncertainty
Authors: Elita Lobo
Justin Payan
Cyrus Cousins
Yair Zick
Venue: NeurIPS 2024 poster (2024)
Keywords: Resource allocation
robust optimization
CVaR
constrained allocation
Primary area: fairness

Abstract: We study fair allocation of constrained resources, where a market designer optimizes overall welfare while maintaining group fairness. In many large-scale settings, utilities are not known in advance, but are instead observed after realizing the allocation. We therefore estimate agent utilities using machine learning. Optimizing over estimates requires trading-off between mean utilities and their predictive variances. We discuss these trade-offs under two paradigms for preference modeling – in the stochastic optimization regime, the market designer has access to a probability distribution over utilities, and in the robust optimization regime they have access to an uncertainty set containing the true utilities with high probability. We discuss utilitarian and egalitarian welfare objectives, and we explore how to optimize for them under stochastic and robust paradigms. We demonstrate the efficacy of our approaches on three publicly available conference reviewer assignment datasets. The approaches presented enable scalable constrained resource allocation under uncertainty for many combinations of objectives and preference models.

Fair and Welfare-Efficient Constrained Multi-matchings under Uncertainty
Elita Lobo; Justin Payan, Cyrus Cousins, and Yair Zick University of Massachusetts Amherst
felobo, jpayan, cbcousins, yzick) } @umass.edu
Abstract
We study fair allocation of constrained resources, where a market designer opti- mizes overall welfare while maintaining group fairesss. In many large-scale set- tings, utilities are not known in advance, but are instead observed after realizing the allocation. We therefore estimate agent utilities using machine learning. Op- timizing over estimates requires trading-off between mean utilities and their pre- dietive variances. We discuss these trade-offs under modeling - in the stochastic optimization regime, the market designer has access probability distribution over utilities, and in the robust optimization regime they have access to an uncertainty set containing the true utilities with high prob- ability. We discuss utilitarian and egalitarian welfare objectives, and we explore how to optimize for them under stochastic and robust paradigms. We demonstrate the efficacy of our approaches on three publicly available conference reviewer as- signment datasets. The approaches presented enable scalable constrained resource allocation under uncertainty for many combinations of objectives and preference models.
paradigms for preference
Introduction
Constrained resource allocation without money underpins many important systems, including viewer assignment for peer review (our primary example throughout the paper) [4, 16, 31, 45, 54), assigning resources to homeless populations [5, 34, 49], distributing emergency response resources [51, 56, 57], and more [1, 44, 53]. these settings, we assign resources to agents. Agents and re- sources constrained; each agent has bounds the minimum maximum number of items they receive from different categories, and each item has required minimums and limited total capacity. Each agent has valuation for every item, and optimize welfare function of the agent-item valuations. In the case of reviewer assignment, the reviewer-paper valuations measure the alignment between reviewers and papers, papers must receive a certain number of reviews from unique review- ers, reviewers have upper limits on the number of papers they can review, and conflicts of interest prevent some reviewers from being assigned certain papers.
crucial factor in all of the above settings is the presence uncertainty. Uncertainty often stems from the fact that agents' valuations for resources depend future outcomes. In reviewer assign- ment, reviewer-paper pair's 's match quality is observed only after the reviewer submits his or her reviewUncerraanty may also stem from our limited ability collect data; for example, in deciding where to target lead pipe mitigation projects based on number school-aged children per neighbor- hood, may have access to imperfect school enrollment records, allowing only approximate model of the impacts of mitigation on children in each neighborhood [53]. We adopt two possible stances towards uncertainty, depending on the information available. When have access
Authors contributed equally.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

probability distribution over preferences, we optimize the conditional expectation of the distribu- tion at percentiles of interest [33, 50J. When we have access to a set of possible preferences, we adopt the robust approach, which is related to the minimax regret objective used in solving robust assignment problems [3, 10, 11, 32]. Uncertainty-awan
optimization approaches can often result in significantly different allocations from the default of optimizing for welfare over central estimate (see Example 2.1 for an intuitive explanation for this phenomenon).
Typically, we maximize the sum of agent utilities. However, in many of these settings, we are also concerned with fairness to individuals or groups of agents. Groups of agents may represent subject areas of papers in reviewer assignment, demographic groups in poverty alleviation campaigns, or regional groupings of computational resources in bandwidth allocation. Fairness these groups may be legally required in some cases; in others it is an ethical choice by the decision maker. Although groups are often first-class objects worthy of receiving fair treatment, group fairness is often the smallest granularity of fairness achievable under uncertainty - in a large dataset uncertainty will always cause some individuals to have vanishing welfare, but group welfare can still be upheld. Although there is much literature on combinatorial optimization under uncertainty [3, 10, 32, 33], to our knowledge it has not addressed the intersection of fairness and uncertainty in the constrained multi-matching problem.
1.1 Our Contributions
We study the broad problem of fair and efficient constrained multi multi-matchings under uncertainty about agents' valuations. We optimize for welfare while simultaneously accounting for the uncer- tainty inherent in real-world resource allocation problems. Specifically, we develop methods to effi- ciently optimize the utilitarian and egalitarian welfare objectives using the robust approach [7, 8, 26] and the CVaR approach [50]. Our results are summarized in Table 1.
For robust optimization, we construct an uncertainty set that contains the true preferences with high probability (Section 3). This model is appropriate when building a predictor with statistical error bounds, but without making any assumptions on the full probability distribution over valu- ations. For utilitarian and egalitarian welfare functions, we robustly maximize welfare over such uncertainty sets. When the uncertainty sets are linear, we can efficiently compute the exact optimal allocations for both utilitarian and egalitarian welfare in polynomial time (Corollaries 3.2 and 3.6). Under a single ellipsoidal uncertainty set, we can apply an iterated quadratic programming approach (Corollaries 3.3 and 3.7), while a projected subgradient ascent approach is needed when uncertainty sets consist of multiple ellipsoids (Propositions 3.1 and 3.5). Under general monotonic, concave wel- fare functions and arbitrary convex uncertainty sets, we apply the relatively expensive adversarial projected subgradient ascent algorithm of Cousins el al. [16].
When the market designer can construct a full probability distribution over preferences or sample from such a distribution, we consider stochastic optimization using the concept of Conditional Value at Risk, or CVaR [50]. This approach, laid out in Section 4, selects an allocation that maximizes the conditional expectation of welfare over the left tail of the welfare distribution. We often approximate CVaR objectives using sampling and then solve the resulting linear program or LP (as in Proposi- tions 4.1 and H.3). However, the case of utilitarian welfare and we present a simple reformulation of the CVaR objective (Proposition 4.3). Optimizing CVaaR for general monotonic, concave welfare functions can require solving arbitrary concave optimization problems, even after sampling.
valuations,
We also compare these optimization approaches empirically in Section on reviewer assignment data from AAMAS 2015, 2016, and 2021.
1.2
Related work
We discuss the history of prior work on robust and CVaR optimization in Appendix A.
Some existing work applies stochastic or robust optimization to fair division problems. A line of work studies the minimax regret objective in combinatorial optimization problems, such as con- strained resource allocation [3, 10, 11, 32j. This work does not explicitly consider multi-matching problems like those considered here, nor does it address the robust egalitarian welfare problem. Pu- jol et al. [48] study fair division problems with parameters noised for differential privacy, showing

---

Table I: Summary of optimization algorithms for efficiently computing utilitarian and egalitarian welfare under different robustness concepts. Green highlights indicate problems which require solv- ing single linear program (low difficulty). Yellow highlights indicate solving a small number of linear or quadratic programs (medium difficulty). Red highlights indicate problems which require solving numerous quadratie programs arbitrary concave programs.
Robustness Concept
Robust
CVaR
Linear
One Ellipsoid
e Ellipsoids
Any (approx.)
Gaussian
LP Reduucton (Coro. 3.2)
Iterated QP
Projected SGA (Prop. 3.1)
Sampling + LP
Projected GA
Utilitarian
(Coro. 3.3)
(Prop. 4.1)
(Prop. 4.3)
LP Reduuction
Iterated QP (Coro. 3.7)
Projected SGA
Egalitarian
Sampling (Prop. H.3)
(Coro. 3.6)
(Prop. 3.5)
Monotone,
Adversarial Projected SGA (Sec. 3.3)
Sampling Concave Program (Sec.
Concave
that the noise can cause unfair allocations; they propose Monte Carlo approach to mitigate un- fairness with high probability. Peters et al. [46] study envy-free rent division under probabilistic uncertainty. A central mechanism divides rooms and sets room prices for items to minimize envy. We study setting without money, both utilitarian and egalitarian objectives, and robust optimization in addition to stochastic optimization.
Cousins el al. [16] study robust optimization under the utilitarian objective. They propose ad- versarial projected subgradient ascent method, which requires solving two quadratic programs (one for the adversary and one for the projection) at each iteration for a large number of iterations. Our empirical analysis in Section demonstrates the inefficiency of this method. Fair machine learning algorithms [17, 22, 23, 43, 59] often employ similar adversarial optimization techniques over an uncertainty set in a machine learning context. Other fair allocation research has studied the case where agent demand item availability are uncertain but preferences are known [2, 14, 21, 27J. In our case, demand and availability are known but preferences are not. Devic et al. [20] consider fair two-sided matching where the fairesss constraint is defined with respect unknown parameters; assume knowledge of the parameters that define the fairness constraint (i.e., group identities).
2 Fair Resource Allocation under Uncertainty
We first introduce the problem of resource allocation without uncertainty, then lay out the two ap- proaches we take to deal with the introduction of uncertainty. Our results are summarized in Table
2.1 Fair Resource Allocation
We have a set of n agents N {aj,... ) and m item types / = {ir.... im.....m... Agents are partitioned into groups G [GI,... Gg),, with each G C N and each agent i belonging to exactly one group.
For any m matrix X we use the same lower-case bold letter, i.e., x to denote the vector rep- resenting the vectorized form of the matrix X, in row-major order. For any group of agents G, we use XG E | denote the vector restricted to the agents in G. Given vectors x.y C p and real number E IR, let x 2 denote x, 2 e for all j, and let x > y denote that x - y č 0. The < operator is defined analogously.
We assume a valuation matrix V E R where V encodes the true value of assigning item type to agent The values of V are typically unknown; discuss approaches handle this problem in Section 2.2. We use tildes to denote random variables; for example, à ~ D; denotes that the random variable 5 follows the distribution Dz-
Given some set of feasible assignments A C Naxm, we aim to find assignments A where A ass indicates the number of items of type allocated to agent a. For each agent E N, we have
3

---

upper and lower bounds on assignments of the form KA S. &EEr Au,t S Rg. For each item i, we have lower and upper bounds on the total assignment of that item; v; S S Au,i S dh Finally, we have pairwise limits Co. for each agent and item type i, requiring that Aa, S C.... It is always the case that the constraints define a finite set such that][A| E N. In the example of reviewer assignment, these constraints reflect the review requirements per paper, load bounds for reviewers, conflicts of interest, and the constraint that no reviewer is assigned twice to any given paper.
Let u : A x Bo+ + RS be an affine function mapping from allocations to utilities for each group. (a v) denotes the utility of the group G under allocation a E AA (recall a the vectorized version of the assignment A). We write u instead of u(a, v) when a and v are clear from context. alve
We define a welfare function W 12 + R. where W (u(a, v)) denotes the overall welfare of allocation a. The weighted utilitarian social welfare function is defined as w-u, where w E 184 denotes the weights on groups in G. When wG = [G] for all G, we call this function simply "utilitarian welfare" or "USW." The group egalitarian social welfare function (also "group egalitarian welfare" or "GESW") is defined as mingeg UG. We do not consider individual egalitarian welfare in this work; under robust and stochastic optimization the egalitarian welfare is zero when the number of items is proportional to the number of agents and uncertainty is non-trivial.
We assume that u is additive and normalized by group size, so ug = [G
2.2 Optimizing Allocations under Uncertainty
We consider two main approaches to dealing with uncertainty: the robust optimization approach and the Conditional Value at Risk approach.
In the robust approach (Section 3), we obtain an uncertainty set V that contains the true agent valuations v with probability at least 1- a for some confidence parameter a E [0, 1). We then optimize the welfare corresponding to the worst valuation matrix in the uncertainty set, i.e., 4 minvey W(u(a, v)). This approach applies when we do not have access to a full distribu- tion over valuations but have some other way of describing V [16].
When we have access to complete distribution of the random variable V Ram we apply stochastic approach instead. We compute the welfare distribution and optimize the conditional ex- pectation over an a-percentile of the welfare Conditional Value at Risk at (CVaR,,). Suppose that we have a random variable ă ~ Dz- For any risk level a E (.,).5), CVaR, [+] is defined as Ez-Dz [ ã S [)] where Va. denotes the a-percentile of S. This approach is only appropriate when Da is fully known, or when we can sample from it. We investigate this regime in Section 4, where will compute and optimize CVaR,,W(uu
V)] for a random variable v Dz.
Example 2.1 (The Importance of Considering Uncertainty). Consider a simple two-agent, two-item instance, where each agent needs to get exactly one item, and either likes (utility 1) dislikes it (utility 0). Agent preferences are Bernoulli random variables, where Pr = 1] = 0.8, Pr[V1.2 = 1] 0.5, and Prfsz.2 = 1] 0.8. If we maximize the expected USW, we would
1] = 0.9, Pr[v2,1 assign in to aj and i2 to a2, for a total expected USW of 1.6. However, consider instead the CVaRa. of USW. When we make the expectation-maximizzngg assignment, then Pr( = 0j = 0.04 and (r[ = 1] = 0.32. However, if we assign i2 to agent @1 and item in to agent a2, we have Pr Pr = 0j 0.05 and Pr( = 1] 0.5. This means that the conditional expectation of welfare at the thth percentile is higher if we assign to d1 and i to 02 (it is .22 in the first case and .5 in the second case). If we want to retain welfare in the face of uncertainty, we might well choose to maximize this quantity rather than the expectation of the welfare.
3 Robust Welfare Optimization
We construct the optimization problems for utilitarian and egalitarian welfare objectives with the robust approach. Many of these optimization problems are concave-convex max-min problems that can be directly solved using an adversarial projected subgradient ascent technique [16]: in each iteration of the algorithm, the inner minimization problem is solved to optimality, followed by subgradient step on the allocation a, followed by a projection onto the constraint space A. However, this method does not exploit the structure of these problems and is often computationally expen- sive or intractable, as demonstrated empirically in Section Despite the inherent complexities of these problems, we show that, under specific assumptions, these problems can be reduced to more

---

manageable forms that are easier to optimize. We then discuss a range of algorithms for efficiently optimizing the simplified problems.
Scope:
The robust approach detailed in Section assumes the availability of an uncertainty set of the valuation matrix. For the sake of computational tractability, focus the class of uncertainty sets defined by linear and ellipsoidal constraints
V= v= -={ve R
Vi [1, , (v (s) S Qu Qv
where the zth ellipsoid centered at V; E Rot with a positive definite covariance matrix S; grmmxm and radius r; E Ro+. and Q E R Réxmm, and e E R define additional linear constraints.
This limitation on the structure of uncertainty sets is not too restrictive; it is possible to construct such uncertainty sets for linear regression and logistic regression models using statistical bounds, as shown in Appendix D.
In all of our methods, where obtaining an integer allocation is either feasible computationally tractable, we relax the set of feasible integer assignments A C N to a set of feasible continuous allocations A S Rg+ R One can obtain integer allocations satisfying all constraints by applying a randomized rounding technique that generalizes the Birkhoff-vort Neumann decomposition [13]. The fractional solutions can thus be interpreted as randomized allocations.
3.1 Robust Allocation for Utilitarian Welfare
We consider the problem of finding an allocation that optimizes the weighted utilitarian welfare under the worst valuation matrix in the uncertainty set. We formulate the problem as
(1) The objective and constraints of the minemmiiiiizaiion problem described in (1) are convex. The problem is strictly feasible, which satisfies Slater's condition [12] for strong duality. Therefore, by taking the dual of the minimizaiion problem, we can simplify the problem in (1) into a single equivalent maximization problem. We provide the dual formation in Proposition 3.1.
max min w u(a.v)
a vEV
To simplify the notation in the results that follow, we assume, without loss of generality, that each group G has weight We [G|. In practice, if this assumption does not hold, the weights can be incorporated into the valuations v with a corresponding adjustment to the parameters of the valuation uncertainty set V.
In the dual, let 3 E IR be the dual variable corresponding to the linear constraints Qv > e, A E R4, be the dual variable associated with the ellipsoidal constraints, and & E Ram be the variable that combines the primal variable a with the dual variable of the non-negativity constraint on for variable elimination. We define a set of feasible & as
A
BD= mm
{E E R Rmm
Va E N
Eamti S Ra, ViE: Eam++ S v. = (2)
eEN
which is Pareto-dominated by A. Proposition 3.1 (Robust Utilitarian Welfare Dual). The problem in (1) is equivalent to solving
max EEA XeR BE28
T + BTe 7p
Σ TP
1
(A.V.S '. >it)) TTq
(3)
1=1
where p = -TQ. -- Ei S and T (Ei A.S Let E¹ be the optimal & in (3). Then the optimal allocution a" can frrived E" by finding a A such that a < E
Proposition 3.1 shows that the optimal allocation for the problem in Equation (1) can be computed by first solving the concave program in Equation (3) to obtain &" and then deriving the optimal allo- cation a" from 5* by solving a system of equations. Notably, the problem in Equation (3) is a single maximization problem with fewer variables and constraints (1), making it simpler to solve. We can either solve it using off-the-shelf convex optimization tools, or by applying projected subgradient ascent approach (without the previously required adversary).
compared to the max- -ii problem in
When the valuation uncertainty set polyhedral, the problem in (3) simplifies further into linear program (LP) which can be solved efficiently using standard LP solvers like Gurobi [28].
5

---

Corollary 3.2 (Utilitarian Welfare with Polyhedral Uncertainty). In the case where the uncertainty set V is defined purely by linear constraints, i.e. V {v R Qv e.v = 0}, the optimal allocation for the problem (1) can be computed by solving the linear program
max B
Be
S.1. 3a.
When the valuation uncertainty set has single ellipsoidal constraint with a non-negativity straint, we compute the solution using iterated quadratic programming (Iterated QP).
Corollary 3.3 (Utilitarian Welfare with Ellipsoidal Uncertainty). Suppose that the set V in (1) is defined by a single truncated ellipsoidal constraint, i.e., {v Rmm v v) S r². V = 0}. The problem in (1) is equivalent to solving
ÇTSE
<TV
Ar
XERot, EEA
4A
The exact optimal solution (X*, E*) ) to Equation (4) can be computed by alternately performing two steps until convergence: first, fixing & and optimizing X, i.e., X = VÉ1SE/2r, and second, fixing and solving a concave quadratic program to optimize The optimal allocation at can be computed from 8x as in Proposition 3.1.
3.2 Robust Allocation for Group Egalitarian Welfare
We now consider the problem of maximizing egalitarian welfare under the robust approach. We can represent this problem as
max min min ug (a. a vEV GEV
(5)
This problem presents inherent challenges due to the non-smoothness of the inner- mnmerr-miiizzaiionn problem and the joint constraint on the uncertainties of the valuation matrices of different groups. These factors make it difficult to compute the dual and reduce the problem efficiently solve the problem using the quadratic program technique described Corollary 3.3, although the generic ad- versarial subgradient ascent approach of Cousins et al. [16] can still be applied. For the remainder of this section, we assume that the uncertainty sets for each group G E 9 are independent of each other. To simplify notation, we assume, without loss of generality, that the valuations and the parameters of the valuation uncertainty set V are scaled to incorporate the factor G in the representation of the utility of each group G' in the corresponding group valuation VG.
Assumption 3.4 (Independence of Groups). The uncertainty set V is Cartesian product of indi- vidual groups' uncertainty sets, V = Deeg Vo where each group's uncertainty set VG is given by
Va = E E |R [1 (vG - va.) (S va.a) S f.. Qova 2 ea. ea, va.va
Here the 8th ellipsoid in group G's uncertainty set is centered VG, E G with positive definite covariance matrix SG., E [ and radius rG,s Rot, and QG p and eg I define additional linear constraints.
This assumption is not unreasonable in practical scenarios. For example, conferences often group papers into disjoint tracks require paper authors select single primary subject area. Although papers may have multiple secondary subject areas, the top-level grouping remains independent. As- sumption 3.4 allows reorder the two minimization problems without compromising generality:
max min min aE GES veeVe
aovG
We take the dual of inner minimization problem and then reorder the minimization over groups and the maximization over the dual variables to obtain a single, concave max-min problem. This can be solved with projected subgradient ascent in the general case, or with more efficient approaches in special cases. Proposition 3.5 expresses the general form of the result.

---

Proposition 3.5 (Robust Group Egalitarian Dual). The problem in (5) is equivalent to solving
max EEA ACROXI BEROF
min Blea + P Toqo P Topa+
dey
(7)
Σ (Ao. ToVos Ao.rr.s) ToqG.
Q6Bc. (Eiz, AG. AG.SGa) and A is defined as in Equation (2). The optimal allocation a" can be com- puted from 5r as in Proposition 3.1.
where for each group G E G. PG =G Q qG
Ei To
The dual variables AG, ÇG and &G for each group G are interpreted as in Proposition 3.1. The optimization problem in (7) is concave with respect to the dual variables X, B and &. We can solve it using an off-the-sher convex programming library or by applying projected subgradient ascent.
Under polyhedral uncertainty sets, Equation (7) simplifies to a linear program. This akin to what observe in the robust utilitarian case (Corollary 3.2).
Corollary 3.6 (Group Egalitarian Welfare with Polyhedral Uncertainty). In the case where the un- certainty set is defined only by linear constraints, i.e., V {v E Rum AG G Qava z eG, = 0}, the max-min-min problem in (5) transforms into lineur program.
When the valuation uncertainty is defined by a single ellipsoidal constraint per group. we can employ the iterated quadratic programming (Iterated QP) approach used in Corollary 3.3, alternately fixing À and optimizing the rest of the dual variables (3, {) until convergence.
Corollary 3.7 (Group Egalitarian Welfare with Ellipsoidal Uncertainty). Suppose that the set V in (5) is defined by single truncated ellipsoidal constraint per group i.e., V y= (v E Rnm VG G
(vG va)Sa (vG VG) re è 0}. Then the problem in (5) is equivalent to solving
min &Lve
-xrra
Aea GEG
4ha
CEA
The exact optimal solution (X*E"") to Equation (4) can be computed by alternately performing two steps until convergence: first, fixing & and optimizing X, iee. VG E g. AG = VEhSota/2re. and second, fixing X and solving concave quadratic program optimize The optimal allocation a* can be computed from e" as in Proposition 3.1.
3.3 Robust Allocation for Monotonic Welfare Functions
We now extend our findings to broader class of monotonic welfare functions. Specifically, we show that when optimizing a monotonic welfare objective under Assumption 3.4, we can decompose the problem into sub-problems such that independently determine the worst valuation in the uncertainty set each group, while jointly optimizing the allocation over all groups
Proposition 3.8 (Decomposition for Monotonic Welfare Functions). Consider an optimization problem of the form
max min Wu(u(a,v)) a vEV
(8)
where the welfare function W M monotonic in the utility of groups. If Assumption 3.4 holds, then (8) simplifies to
min UG, (aG., VG,), min uG, uG, VG.). min uG, (ag, vG,)) eVe,
max WM aEAA
(vo EVe
vay EVo,
Proposition 3.8 helps us derive simplified versions of Equation (8), when Assumption 3.4 holds. The egalitarian problem in (5) an instance of the class of optimization problems described in (8), hence Proposition 3.8 holds under Assumption 3.4 and allows to derive single maximization problem (Proposition 3.5). If the allocation and valuation uncertainty sets are convex and compact, the problem in (8) can be solved using constrained convex-concave minimax optimization algo- rithms [18, 25, 55), or adversarial projected gradient ascent [16]. These approaches not depend on Assumption 3.4, although optimization can be simplified if independence does hold.
7

---

4 Stochastic Welfare Optimization
In this section, we optimize the CVaR of utilitarian and egalitarian welfare. This approach works when the distribution D over the valuation matrix is known or when we can sample from Dz. We demonstrate that when the distribution follows Gaussian distribution, the CVaR of the utilitarian welfare has simple representation that can be optimized without sample approximation using projected gradient ascent method. In all other cases, we can approximately optimize CVaR using sampling-basee approach. In particular, when we have monotone, concave welfare functions, we can always approximate the CVaR objective using sampling. However, unlike in Propositions and H.3, where the approximated problem becomes linear, with arbitrary monotone, concave welfare functions the problem may require general concave optimization.
4.1 CVaR Allocation for Utilitarian Welfare
We wish to find an allocation that maximizes the CValR, of the weighted utilitarian welfare. Let v represent the random valuation vector. For confidence level a, we formulate the problem as
max CVaR., [w: u(a, v) aEA
max ac DEA,
b
[66 w u(a, (().)))+ a V-
1
where (x)+ = max( 0) represents the positive part of æ [50]. Computing the exact expectation in this problem may not be feasible for every distribution De. Therefore, we adopt sampling-based approach. We begin by drawing i.i.d. samples of the valuation matrix from D3 represented as v v2, v ..... v We then use these samples to solve the problem described in (9) by solving the linear program outlined in Proposition 4.1.
Proposition 4.1 (Approximate CVaR of USW). Given i.i.d samples vf i.e. v',v² v from De, the optimal allocation for the problem in (9) can be approximately computed by solving
1 (b- u(( Vj [1, yi 2
max max aeA yER
b
b-
Us
(10)
FER
The CVaR estimator used in (10) a strongly consistent estimator [29]. Therefore, the approxima- tion error of the objective in (10) goes to ( as h -> co. In Proposition 4.2, we bound the sample complexity of the problem in (10) when the valuation matrix sub-Gaussian distributed.
For any allocation a, let (a) represent the empirical estimate of CVaR. [w- u(a, v)] computed from h samples and (a) represent the corresponding true value. We will use |A] denote the number of feasible allocations and Sa : IR + Ra+ to denote the density function of the random welfare (a. v). V/a denotes the a percentile of W(a, v).
Proposition 4.2 (Sample Complexity of Approximate CVaR of USW). Suppose that & is multi- variate Gab--aassiann random variable with mean v E Rmm and covariance proxy S E TR mmmxxm iee, for all vectors E RRnm EV-D, [exp((v- - v)Tz}}] S exp((*8x/2), and that, for any risk level (0, 1) and allocation a E A, there exists probability density threshold rj > and radius ? s.I., Ja (x)) n) Vx E [V. - 7, Un + + Sei VG G :::aa wa-an Then, any confidence parameter E (0, 1) and error tolerance & > 0.
mmax (maxae A a" Sa', .8) In [/AI
Pr sup ( - ca (a)) S 2 21-8 for h> aEA
min(E? 16 min(n? 1)
Proposition 4.2 follows directly from Theorem 3.1 of L.A. et al. [35]. When V is Gaussian dis- tributed, we can circumvent the sampling approach and instead solve an optimization problem (Proposition 4.3), which depends solely on the mean and covariance v.
Proposition 4.3 (CVaR of USW for Gaussian Distributions). If V is distributed as a multivariate Gaussion, i.e., V ~ NNV S), then, the optimization problem in (9) simplifies to
max T
TSa
(11)
a
8

---

where AG E G: a/g = w and & and & denote the probability density function and the cumula- |c| tive density function, respectively, of the standard normal distribution (0, 1). The problem in (11) is concave and can be solved using the projected gradient ascent method.
4.2 CVaR Allocation for Group Egalitarian Welfare
For our final objective, we wish to optimize egalitarian welfare under uncertainty using the CVaR approach. We formulate this optimization problem as
min (a v) GEE
b-1 1 E viuDo
[ min uG (a, v) GE9
max CVaRa aed
max aE DED
b
(12)
a
To optimize the problem described in the above equation, we solve linear program similar to the one used to optimize the utilitarian objective CVaR in (9). See Proposition H.3 for more details.
5 Experiments
We run experiments on three reviewer assignment datasets. The datasets contain bids from the International Conference on Autonomous Agents and Multiagent Systems (AAMAS) 2015, 2016, and 2021 [41, 42]. We consider the papers as the "agents" and the reviewers as the "items." " This is a fairly standard assumption in most recent reviewer assignment approaches, reflecting the primary goal of peer review to assign qualified and interested reviewers to papers [16, 30, 31, 38, 45, 54).
The reviewers issue bids of yes, maybe, no, or no response. We run two experiments with this data. In one, we binarize the bids such that yes and maybe are considered affirmative and no is considered negative, while in the other we convert the bids to numerical scores such that yes is 1, maybe is 55, and no is 0.01. Under the binarized model, we fit logistic matrix factorization model to predict whether the bid is affirmative or negative, and in the continuous model, we fit a Gaussian process matrix factorization model [36]. We derive probability distributions and uncertainty sets from these models. More details on prediction and uncertainty set construction are in Appendix E. These datasets do not contain groups of papers and reviewers, so we create roughly balanced clusters of reviewers and papers for each dataset using the procedure outlined in Appendix F. We define our valid set of assignments AA as follows. For each paper a N, we set K, Ka = 3 for all in AAMAS 2015, and K. R. 2 for all in AAMAS 2016 and 2021. For each reviewer i, we set v0 = 0 and vh. = 15 for 2015 and 2016 and 4 for 2021. We optimize and evaluate CVaRo. o1: we take 4, 000 samples from the distribution to optimize for CVaR using the sampling- and we take 10, 000 samples to estimate CVaR for evaluation. We optimize and evaluate robust welfare at the = 0.3 level (there is a 70% chance that the true values lie in the uncertainty set). We constrain the naive and CVaR approaches to select integer allocations, while the robust approach selects fractional allocations without rounding.
approach,
All results are averaged over 5 subsampling runs 20% of each dataset. For each run, we construct 6 allocations, maximizing the naive central estimate, CVaR and robust statisties for USW and GESW respectively. We evaluate each allocation on each metric. For each run, we normalize each metric by the maximum value achieved for that metric by any allocation. We normalize in this manner to highlight that the allocation targeted for given objective always returns the highest value on that objective, and because the absolute optimal values differ across runs. All code is available at http://iihub.coo//sssttpaaaaay
Overall Performance Table shows the results for the binarized version of AAMAS 2015 bids. Similar tables for the 5 other settings are included in Appendix G. Each row shows the metrics for the allocation produced by the method that optimizes for the objective shown in the left-most column. All nonrobust methods have robust welfare 0, indicating that if robustness to adversarial noise is desired, it is very important consider this objective explicitly. Relatively little noise is actually present in this dataset, as the CVaRo.o1 is quite high for both the naïve optimat and GoSw-optimal all cases. Since the upttmml solution has a very high GESW, we implement a simulated example to explore when the USW ooptial solution fails to have a high GESW. We find that in a number of settings, the GESW of the USW-optimal solution is much lower than that of the optimal solution. Appendix explains the details of the simulation setting and the results.

---

CVaRo.01 MoKoo01ll [W]
Rob. USW
100
WaTze USW
GESW
Hiizar Canver
50
Crul
RPP Subgratte
100
200
Standard Deviation Scale
Time (s)
Figure 1: Left: CVaR as noise increases for AAMAS 2015. Right: Convergence behavior of the Iterated Quadratic Program (Iterated QP) vs. Adversarial Projected Subgradient Ascent approach on AAMAS 2015.
Table 2: Performance of different allocations across each metric the AAMAS 2015 dataset.
Evaluation Objective CVaR GESW
Allocation
USW
GESW
CVaR USW
Rob. USW
Rob. GESW
USW
1.00 + 0
1.00 + 0
1.00 +
1.00
0 =
0
GESW
0.97 = 0.01
1.00
0.97 = 0.01
0.97 + 0.02
0
0 0
CVaR USW
1.00
1.00 0
0.99 +
0
0 0
CVaR GESW
0.98 1
0.99
0.97 0.01
1.00
040
0
Rob. USW
0.92 - 0.01
0.90 0.02
0.92 1:92:000 0.01
0.90 + 0.02
1.00 +
Rob. GESW
0.89 = 0.04
0.85 + 0.06
0.89 = 0.04
0.86 + 0.06
0.88 0.02
1.00 =
Robustness under Increasing Uncertainty Figure shows the CVaRo.01 on the Gaussian version of all three datasets tions of the Gaussian distributions by scalar and optimize for the CVaR or the naively-computed USW and GESW. We then plot CVaRo.o1 the noise increases. Although the CVaR approach is less important at low noise levels, the CVaR of welfare decreases for both welfare measures as noise increases. GESW has sharper decline than USW. We see that the noise increases, the CVaRRo of the baseline USW and GESW maximizing allocations drops off relative to the same value for the CValR-optimized allocation. We also verify that when we model valuations using negatively- skewed Gaussian distribution with the same means and variances, we see increasing importance of optimizing for CVaR relative to uncertainty-unaverr sharper as the skewness parameter gets more negative. Details of this experiment and its results are included Appendix J.
artificially increase the amount of noise. We multiply the standard devia-
USW and robust USW. The difference is
Runtime For the robust optimization setting with ellipsoidal uncertainty sets (derived from con- fidence intervals proach (Corollary 3.3) to adversarial projected subgradient ascent on the original max-min problem in [16]). We find that Iterated QP converges much faster than the adversarial projected subgradi- ent ascent algorithm on both AAMAS 2015 (Figure 1) and 2016 (Figure 3). Adversarial projected subgradient ascent fails converge 1, 000 iterations for the robust GESW objective on all datasets and the USW objective on AAMAS 2021.
the Gaussian process matrix factorization), compare the Iterated QP ap-
6 Conclusion
In conclusion, we explore stochastic and robust optimization regimes for utilitarian and group egali- tarian welfare objectives. Robust optimization algorithms depend on the form of the uncertainty set. We show that when the uncertainty set has linear constraints only, the resulting problem is an LP and can be solved efficiently. Under ellipsoidal constraints, we demonstrate that iterative quadratic programming approach converges much faster than adversarial projected subgradient ascent. In the stochastic regime, we lay out the sample complexity of CVaR for the utilitarian welfare objective. We demonstrate the feasibility of estimating probability distributions and uncertainty sets three years of bid data from AAMAS, and show that the robust and CVaR approaches demonstrated in this paper combat the uncertainty present in these three datasets.
10

---

Acknowledgments and Disclosure of Funding
This work is generously supported by Army Research Lab DEVCOM Data and Analysis Center Contract W911QX23D0000 and NSF grant IIS-2327057. Cousins was supported by the University of Massachusetts Center for Data Science Fellowship. This work was carried out using high perfor- mance computing equipment obtained under a grant from the Collaborative R&D Fund managed by the Massachusetts Technology Collaborative.
References
[1] Emily L Aiken, Guadalupe Bedoya, Joshua E Blumenstock, and Aidan Coville. Program target- ing with machine learning and mobile phone data: Evidence from an anti-poverty intervention in afghanistan. Journal of Development Economics, 161:103016, 2023.
[2] Amine Allouah, Christian Kroer, Xuan Zhang. Vashist Avadhanula, Anil Dania, Caner Goemen, Sergey Pupyrev, Parikshit Shah, and Nicolas Stier. Robust and fair work allocation. arXiv preprint arXiv:2202.05 0544 194, 2022.
[3] Igor Averbakh. Minmax regret solutions for minimax optimization problems with uncertainty. Operations Research Letters, 27(2):77-65, 2000.
[4] Haris Aziz, Evi Micha, and Nisarg Shah. Group faimess in peer review. Proceedings of the 37th Annual Conference on Neural Information Processing Systems (NeurIPS), pages 64885-64899 2023.
[5] Mohammad Javad Azizi, Phebe Vayanos, Bryan Wilder, Eric Rice, and Milind Tambe. Design- ing fair, efficient, and interpretable policies for prioritizing homeless youth for housing resources. Proceedings of the 15th International Conference on the Integration of Constraint Program- ming, Artificial Intelligence, and Operations Research (CPAIOR), pages 35-51, 2018.
[6] Adelchi Azzalini and Antonella Capitanio. Statistical applications the multivariate skew normal distribution. Jourmal of the Royal Statistical Society: Series B (Statistical Methodology), 61(3))579-602 602, 1999.
[7] Aharon Bal, Laurent El Ghaoui, and Arkadi Nemirovski. Robust optimization. Princeton University Press, 2009.
[8] Dimitris Bertsimas, David B Brown, and Constantine Caramanis. Theory and applications of robust optimization. SIAM Review, 53(3):464-501, 2011.
[9] John R Birge and Francois Louveaux. Introduction stochastic programming. Springer Science & Business Media, 2011.
[10] Craig Boutilier, Relu Patrascu, Pascal Poupart, and Dale Schuurmans. Constraint-based op- timization and utility elicitation using the minimax decision criterion. Artificial Intelligence, 170(8-9) (0088-9):686-113 2006.
[11] Craig Boutilier. Computational decision support: Regret-based models for optimization and preference elicitation. In Thomas Zentall and Philip Crowley, editors, Comparative Decision Making, chapter 14, pages 423-453 Oxford University Press, 2013.
[12] Stephen Boyd, Stephen Boyd, and Lieven Vandenberghe. Convex optimization. Cambridge University Press, 2004.
[13] Eric Budish, Yeon-Koo Che, Fuhito Kojima, and Paul Milgrom. Implementing random assign- ments: A generalization of the Birkhoff-von Neumann theorem. In Cowles Summer Conference, 2009.
[14] Jan Buermann, Enrico H Gerding, and Baharak Rastegari. Fair allocation of resources with un- certain availability. Proceedings of the 19th International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS), pages 202, 2020.

---

[15] Ioannis 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-32, 2019.
[16] Cyrus Cousins, Justin Payan, and Yair Zick. Into the unknown: Assigning reviewers to papers with uncertain affinities. In Proceedings of the 16th International Symposium on Algorithmic Game Theory (SAGT), pages 179-197, 2023.
[17] Cyrus Cousins. An axiomatic theory of provably-fair welfare-centric machine learning. In Pro- ceedings of the 35th Annual Conference on Neural Information Processing Systems (NeurIPS), pages 16610-16621, 2021.
[18] Constantinos Daskalakis, Stratis Skoulakis, and Manolis Zampetakis. The complexity of con- strained min-max optimization. In Proceedings of the 53rd Annual ACM Symposium on Theory of Computing (STOC), page
2021.
[19] Anand Deo and Karthyek Murthy. Efficient black-box importance sampling for VaR and CVaR estimation. In Proceedings of the 2021 Winter Simulation Conference (WSC), pages 1-12, 2021.
[20] Siddartha Devic, David Kempe, Vatsal Sharan, and Aleksandra Korolova. Fairness in match- ing under uncertainty. Proceedings of the 40th International Conference on Machine Learning (ICML), pages 7775-7794, 2023.
[21] Kate Donahue and Jon Kleinberg. Fairness and utilization in allocating resources with un- certain demand. In Proceedings of the 3rd ACM Conference on Fairness, Accountabilityy and Transparency (FAT*), pages
2020.
[22] Evan Dong and Cyrus Cousins. Decentering imputation: Fair learning at the margins of demo- graphics. In Proceedliggs of the 2022 ICML Queer in Al Workshop, 2022.
[23] John C Duchi and Hongseok Namkoong. Learning models with uniform performance via distributionally robust optimization. The Annals of Statistics, 49(3): 1406, 2021.
[24] Corrado Gini. On the measure of concentration with special reference to income and statistics. Colorado College Publication, General Series, 208(1):73-79, 1936.
[25] Denizalp Goktas and Amy Greenwald. Convex-concave min-max Stackelherg games. Pro- ceedings of the 35th Annual Conference on Neural Information Processing Systems (NeurIPS), pages 2991- 13003, 2021.
[26] Bram Gorissen, Ihsan Yamkoglu, and Dick Den Hertog. A practical guide to robust opti- mization. Omega, 53:124-137, 2015.
[27] Negin Gorlezaei, Patrick Jaillet, and Zijie Zhou. Online resource allocation with samples. arXiv preprint 1rXiv:2210.04774, 2022.
[28] Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2023. Accessed August 21, 2024.
[29] L. Jeff Hong and Guangwu Liu. Monte Carlo estimation of value-at-risk, conditional value- at-risk and their sensitivities. In Proceedings of the 2011 Winter Simulation Conference (WSC), pages 95-107, 2011.
[30] Steven Jecmen, Hanrui Zhang, Ryan Liu, Nihar Shah, Vincent Conitzer, and Fei Fang. Mitigat- ing manipulation in peer review via randomized reviewer assignments. In Proceedings of the 34th Annual Conference on Neural Information Processing Systems (NeurIPS), pages 12533-12545, 2020.
[31] Ari Kobren, Barna Saha, and Andrew McCallum. Paper matching with local fairness con- straints. In Proceedings of the 25th International Conference on Knowledge Discovery and Data Mining (KDD), pages 1247-1257, 2019.
[32] Panos Kouvelis and Gang Yu. Robust discrete optimization and applications. Springer Science & Business Media, 2013.
12

---

[33] Pavlo Krokhmal, Jonas Palmquist, and Stanislav Uryasev. Portfolio optimization with condi- tional value-at-risk objective and constraints. Journal of Risk, 4:43-68, 2002.
[34] Amanda Kube, Sanmay Das, and Patrick J Fowler. Fair and efficient allocation of scarce resources based on predicted outcomes: Implications for homeless service delivery. Journal of Artificial Intelligence Research, 76:1219-1244 1245, 2023.
[35] Prashanth L.A., Krishna Jagannathan, and Ravi Kolla. Concentration bounds for CVaR es- timation: The cases of light-tailed and heavy-tailed distributions. In Proceedings of the 37th International Conference on Machine Learning (ICML), pages 5577-5586, 2020.
[36] Neil D Lawrence and Raquel Urtasun. Non-linear matrix factorization with Gaussian pro- cesses. In Proceedings of the 26th International Conference on Machine Learning (ICML), pages 601-608. 2009.
[37] Daniel Levy, Yair Carmon, John C Duchi, and Aaron Sidford. Large- methods for distri- butionally robust optimization. In Proceedings of the 34th Annual Conference on Neural Infor- mation Processing Systems (NeurIPS), pages 8847-8860, 2020.
[38] Kevin man, and Dinesh Raghu. Matching papers and reviewers at large conferences. Artificial Intelli- gence, 331:10411 19, 2024.
Mausam, Yatin Nandwani, Hedayat Zarkoob, Chris Cameron, Neil New-
[39] Richard J Lipton, Evangelos Markakis, Elchanan Mossel, and Amin Saberi. On approximately fair allocations of indivisible goods. In Proceedings of the 5th ACM Conference on Electronic Commerce (EC), pages 131, 2004.
[40] Elita A Lobo, Mohammad Ghavamzadeh, and Marek Petrik. Soft-robust algorithms for batch reinforcement learning. arXiv preprint arXiv:2011.14495 2020.
[41] Nicholas Mattei and Toby Walsh. Preflib: A library of preference data. In Proceedings of the 3rd International Conference on Algorithmic Decision Theory (ADT), pages 259-270, 2013.
[42] Nicholas Mattei and Toby Walsh. A preflib.org retrospective: Lessons learned and new direc- tions. Trends in Computational Social Choice. Al Access Foundation, pages 289-309, 2017.
[43] Hongseok Namkoong and John C Duchi. Stochastic gradient methods for distributionally robust optimization with f-divergences. Proceedings of the 30th Annual Conference on Neural Information Processing Systems (NeurIPS), pages 2208-22186 2216, 2016.
[44] Wtodzimierz Ogryczak, Adam Wierzbicki, and Marcin Milewski. A multi-criteria approach to fair and efficient bandwidth allocation. Omega, 36(3):451-46 2008.
[45] Justin Payan and Yair Zick. will have order! Optimizing orders for fair reviewer assignment. In Proceedings of the 31 International Joint Conference on Artificial Intelligence (IJCAI), pages 440-446, 2022.
[46] Dominik Peters, Ariel D) Procaccia, and David Zhu. Robust rent division. In Proceedings of the 36th Annual Conference on Neural Information Processing Systems (NeurlPS), pages 13864- 13876, 2022.
[47] András Prékopa. Stochastic progranming, volume 324. Springer Science & Business Media, 2013.
[48] David Pujol, Ryan McKenna, Satya Kuppam, Michael Hay, Ashwin Machanavajihala, and Gerome Miklau, Fair decision making using privacy-protected data. In Proceedings of the 2020 ACM Conference Fairness, Accountability and Transparency (FAT*), pages 189-199, 2020.
[49] Aida Rahmattalabi, Phebe Vayanos, Kathryn Dullerud, and Eric Rice. Learning resource allo- cation policies from observational data with an application to homeless services delivery. In Pro- ceedings of the 2022 ACM Conference Fairness, Accountability and Transparency (FAccT), pages 1240-1256, 2022.
[50] Tyrrelll Rockafellar and Stanislav Uryasev. Optimization of conditional value-at-risk. Journal of Risk, 2:21 2:21-42, 2000.
13

---

[51] Erik Rolland, Raymond A Patterson, Keith Ward, and Bajis Dodin. Decision support for disaster management. Operations Management Research, 3:68-79, 2010.
[52] Andrzej Ruszezyúski and Alexander Shapiro. Stochastic programming models. Handbooks in Operations Research and Management Science, 10:1-64, 2003.
[53] Isaac Slavitt. Prioritizing municipal lead mitigation projects as relaxed knapsack optimiza- tion: a method and case study. International Transactions in Operational Research, 30(6):3719 3737, 2023.
[54] Ivan Stelmakh, Nihar B Shah, and Aarti Singh. PeerReview4All: Fair and accurate reviewer assignment in peer review. In Proceedings of the 30th International Conference on Algorithmic Learning Theory (ALT), pages 828-856, 2019.
[55] Yuanhao Wang and Jian Li. Improved algorithms for convex-coneave minimax optimiza- tion. In Proceedings of the 34th Annual Conference Neural Information Processing Systems (NeurIPS), pages 4800-4810, 2020.
[56] Felix Wex, Guido Schryen, and Dirk Neumann. A fuzzy decision support model for natural disaster response under informational uncertainty. International Journal of Information Systems for Crisis Response and Management (IJISCRAM), 4(3):23-41, 2012.
[57] Felix Wex, Guido Schryen, Stefan Feuerriegel, and Dirk Neumann. Emergency response in natural disaster management: Allocation and scheduling of rescue units. European Journal of Operational Research, 237(3))677-708, 2014.
[58] Tony Sit Yue Xing and Hoi Ying Wong. Variance reduction for risk measures with importance sampling in nested simulation. Quantitative Finance, 22(4):657-673 2022.
[59] Wenbin Zhang and Jeremy C Weiss. Fair decision-making under uncertainty. In Proceedings of the 2 st IEEE International Conference on Data Mining (ICDM), pages 886-895, 2021.
14

---

A Additional Related Work
Gorissen et al. [26] provide excellent overview of optimization under uncertainty, including tech- niques used in this work, while Ben-Tal et al. [7], Bertsimas et al. [8] offer additional background on robust optimization. A standard approach in this regime is analyzing the dual of the uncertainty, as we generally do in this work. Stochastic optimization has a wide literature; the books by Birge and Louveaux [9]. Levy al. [37]. Prékopa [47], Ruszczyúski and Shapiro [52] present wide-ranging introductions to the topic. Conditional value at risk (CVaR) can often be approximately optimized by sampling and optimizing over an objective composing the different samples [35, 40, 50].
B Broader Impacts
We believe this work has the potential for a significant positive societal impact. Fair resource al- location algorithms essential for various systems, including assigning reviewers in peer review processes, allocating resources to homeless and low-income populations, distributing emergency response resources during natural disasters, and resettling refugees. this work, we develop meth- ods for efficiently optimizing allocations of constrained resources under various fairness objectives while addressing uncertainty in resource preferences. These methods can be directly applied to the aforementioned problems. However, we advise users to conduct extensive testing on similar datasets before deploying these algorithms in real-world scenarios. We also encourage users perform rig- orous causal analysis and controlled experiments to validate their predictive models before applying our methods.
C
Limitations
The CVaR approach requires solving linear programs with large number of samples to be effective, which makes them computationally expensive. One potential solution is leverage importance sampling methods to reduce the variance of the estimator [19, 58). Future research could benefit from empirically and theoretically analyzing other fairness objectives like Nash welfare [15], Gini index [24], and envy-freeness [39].
D Constructing uncertainty sets
In this section we demonstrate a simple and natural approach construct an uncertainty set using a logistic regression estimator. Logistic regression models with bounded cross-entrope loss result in polyhedral uncertainty sets. Replacing the logistic regression model with a model with bounded squared-error loss, or simply taking the confidence interval of multivariate Gaussian, results in truncated ellipsoidal uncertainty sets. We construct uncertainty sets per group all cases.
Assume we have a discrete set of e values L C R, with L = (li,... ...). type denote the true distribution over values p" (i)) and the distribution predicted by the logistic regression model is (i)
L.j. For each agent i and item
We estimate the cross-entropy. loss of the model on test set T, where [T] segmented by the group identities of the agents, such that we have TG, TG...... ........c,, for each of the groups (with sizes to, ... .t......,).. We assume that the test set comes from the same distribution the agent-item pairs of the assignment problem; this can be achieved either during dataset construction or by limiting the assignments (through the C constraints) to better reflect the test distribution. We can also apply likelihood reweighting in our uncertainty set construction, as in [16], though we do not do here.
This test set can be
For an agent a and item type i, the cross-entropy loss the distribution ý with respect to the distribution p is defined as
H[((((((a)))) ((L, i))) EieL p(l in For each Te, we compute the mean of the cross-entropy loss ÅGG to EiaieTT H)(({((a, ((E (a, i))), as well as the standard error
of the mean âG to Eo.eeo (H((p( i)), ((el(a,))) pc)) 1/2 We model the distribution over cross-entropy losses for group G as N N oc). We want uncertainty set V such that
15

---

the true values lie outside V with probability at most a. Thus, using a union bound, we require each uncertainty set Ve for individual groups to contain the true valuations with probability least 1 We can thus give the bound that the cross entropy loss is at most Φ - PG, ēG). where (p) denotes the p percentile of a Gaussian distribution with mean μt and standard deviation
In our assignment problem, for each group G with agents NG obtain the uncertainty set lom
(t) & Φ 4- NENG.iE!
a io. ŌG)
The bound can be made tighter if we restrict some pairs using C, in which case the cross-entropy term on the left side is only averaged over the pairs which are not restricted.
E Logistic and Gaussian Process Matrix Factorization
In this section we define matrix factorization models using either logistic regression or Gaussian processes. The logistic regression model can be used for predicting the missing elements of the binarized bid matrices, while the Gaussian process model is used for predicting missing real-valued elements. Both models define probability distributions over outcomes, which and evaluate the C'aRR of utilitarian and egalitarian welfare. For the logistic model, we build a polyhedral uncertainty set by estimating the cross-entropy loss on held-out test set (as shown in Appendix D), and for the Gaussian process model we simply consider the confidence intervals of the resulting Gaussian distribution.
to compute
For the binarized bids, we first set aside some of the observed bids as a test set. We estimate the missing bids and the bids for the held-out test pairs using logistic matrix factorization. Setting hidden dimension size d, we construct two matrices E Rn and Y mgaxd We set d = 20. Let V denote the true binarized bid matrix, where we observe entries for the training set pairs (a, i) E T. We predict the probability of an affirmative bid as f((XX()aa)) )a.s) where f is the logistic sigmoid function. We select X and Y to minimize the loss function
Σ -Vá (0,1)ET
o.i (f((XY))..)) - - (1, (((-)(((Y)))))))
For CVaR, we take samples from the distribution defined by S(XYT), assuming all pairs are independently-de diittitt. We also construct uncertainty set described in Appendix D using the cross-entropy loss on the test pairs.
Under the Gaussian process matrix factorization model [36], we simply predict a mean and variance of a Gaussian distribution for each reviewer-paper pair. We can then sample values independently for each pair, give confidence interval for the joint Gaussian with mn 1 degrees of freedom.
F Grouping Papers and Reviewers
We group papers and reviewers as follows: given the real-valued bids in the set (0.01, .5, 1} we set unknown bids to be O. We then construct graph with all reviewers and papers as nodes, and the bid score between reviewers and papers is the edge weight. All inter-reviewer and inter-paper edges are set to 0 edge weight. We apply spectral embedding with 5 dimensions transform the nodes into vectors, and cluster the resulting vectors into 4 clusters to obtain 4 groups containing both papers and reviewers. To ensure balance of reviewers and papers across clusters, we employ Lloyd's algorithm for KMeans clustering with the modification that during each assignment step we enforce a lower bound on the number of papers and number of reviewers assigned each cluster.
G Additional Experiments
For the binarized AAMAS 2016 and 2021 datasets, Tables 3 and 4 show the performance of the baseline USW and GESW maximizing allocations, the CVaRo.01 USW and GESW maximizing allocations, and the robust USW and GESW maximizing allocations at the 0.3 level. Because
16

---

0.8
CVaRo.01l
CVaRo.oi
Welfree
0.6
GESW
Robust Concept
GESW
CVaR
Robust Concept
0.4-
None
CVaR
None
2
6
4
Standard Deviation Scale
Standard Deviation Scale
(a) AAMAS 2016
(b) AAMAS 2021
Figure 2: CVaRo.01 noise increases for AAMAS 2016 and 2021.
60
Rob. USW
40
20
IQP SabgradAse
100
200
Time (s)
AAMAS 2016
Figure 3: Convergence of the Iterated QP vs. adversarial projected subgradient ascent on AAMAS 2016 dataset for the adversarial USW objective. The Iterated QP (in blue) converges much faster.
many of the bids in AAMAS 2021 are recorded as no, since no is the default bid, we randomly select 90% of the no bids to be converted to no response.
Tables to show the same results for the Gaussian matrix factorization version of the 3 datasets, with the CVaRo..1 estimated by sampling from the estimated Gaussian distribution, and the adver- sarial welfare computed over the truncated ellipsoidal uncertainty set corresponding to the 1 confidence interval of the Gaussian.
Table 3: Performance of different allocations across each metric the AAMAS 2016 dataset.
Evaluation Objective CVaR GESW
Allocation
USW
GESW
CVaR USW
Rob. USW
Rob. GESW
USW
1.00 0
1.00 +
1.00 1
1.00 +
0
0
GESW
0.99 0
1.00
0.99
0.99 + 0.01
0+:
0
CVaR USW
0.99
0.98 0.00
0.99
0.98 #.01
0+0
0+0
CVaR GESW
0.99 - 0.01
0.01
+.001
1.00
0
0
Rob. USW
0.91 - 0.02
0.87
0.91 0.02
0.90
1.00
0
Rob. GESW
0.76 0.05
0.66
0.76
0.65
0.14
17

---

Table 4: Performance of different allocations across each metric on the AAMAS 2021 dataset.
Evaluation Objective
Allocation
USW
GESW
C'aaR USW
CVaRt GESW
Rob. USW
Rob. GESW
USW
1.00 0
1.00 + 0
1.00 1
1.00
0
+ 0.49
GESW
1.00
1.00 10
1.00 00
1.00
0
0.40 + 0.49
CVaR USW
1.00
1.00 10
1.00
1.00
0
0.40 1 0.49
CVaR GESW
0
1.00
0.99
1.00
0
0.40 0.49
Rob. USW
0.85 0.04
0.14
0.04
0.64
1.00
1.00
Rob. GESW
0.48 = 0.09
0.12
0.43
0.20
1.00
Table 5: Performance of different allocations across each metric on the Gaussian AAMAS 2015
dataset.
Evaluation Objective
Allocation
USW
GESW
CVaR USW
CVaR GESW
Rob. USW
Rob. GESW
USW
1.00 + 0
0.95 + 0.03
1.00 +
0.94 0.04
0.61 0.19
0.34 0.34
GESW
0.87
1
0.86 0.09
0.98 0.02
0.42 - 0.30
- 0.35
CVaR USW
1
0.04
1:00
0.96
0.19
0.35 0.34
CVaR GESW
0.90 0.06
0.00
0.07
1
0.21
0.36 0.33
Rob. USW
0.86
0.16
0.88
0.10
1.00
0.99 0.01
Rob. GESW
0.75 0.13
0.77
0.76
0.82
0.09
1
Table 6: Performance of different allocations across each metric on the Gaussian AAMAS 2016
dataset.
Evaluation Objective
Allocation
USW
GESW
CVaR USW
CVaR GESW
Rob. USW
Rob. GESW
USW
1.00 0
0.99 0.01
1.00
0.99
0.02
0.47 0.27
0.25 + 0.38
GESW
0.91 0.06
1.00
0.91 - 0.07
0.98
0.01
0.37 0.32
0.24 1 0.38
CVaR USW
1.00
0.98 0.02
1.00
0.99 + 0.01
0.52 - 0.25
0.27 + 0.37
CVaR GESW
0.92 0.05
0.00
0.02
1.00 0
0.28 0.37
Rob. USW
0.04
0.17
0.86
0.84
1.00
1.
Rob. GESW
0.14
0.16
0.74
0.84
0.09
1.00
Table 7: Performance of different allocations across each metric on the Gaussian AAMAS 2021
dataset.
Evaluation Objective
Allocation
USW
GESW
CVaR USW
CVaR GESW
Rob. USW
Rob. GESW
USW
1.00 + 0
1.00 + 0.01
1.00 0
1.00 = 0.01
0.53 + 0.26
0.21 = 0.40
GESW
0.80 0.12
1.00
0.79
0.99 0.01
0.24 + 0.39
0.20 0.40
CVaR USW
1.00
1.00
1.00
1.00
0.53
CVaR GESW
0.08
1.00 10
0.84
1.00
0.36 - 0.34
0.20 1 0.40
Rob. USW
0.81
0.69 0.16
0.81 0.11
0.71
1.00
1.00 0.01
Rob. GESW
0.70
0.68 0.17
0.71 + 0.17
0.70
0.88 0.10
1.00
18

---

H Proofs
H.1 Proof of Proposition 3.1
Proposition 3.1 (Robust Utilitarian Welfare Dual), The problem in (1) is equivalent to solving
1 TP
A... - Tq
max SEA AERSY 9923)
(3)
where p Š Q 9- E AS and T
-E A.S Let S the optimal & in
(3). Then the optimal allocation a' can be derived from 5" by finding A such that 3 E"
Proof. Consider the inner-ninimization problem
Σ alva
min VERTO
GED
E [1,]] T.
-v (v- v.) s
Qv ee
Vz0.
Note that the above optimization problem convex as the objective is an affine combination of v. which is convex, and the linear and quadratic constraints are also convex. Thus, from the theory of convex optimization (Section 5.1 Boyd et al. [12]), we know that maximizing the dual of a convex optimization problem is equivalent to minimizing its primal counterpart. We will therefore use the Lagrangian method for computing dual of the above problem.
We will use B R to represent the dual variable corresponding to the linear constraints Qv 2 e, À RB4 represent the dual variable associated with the ellipsoidal constraints, and Rg to represent the dual variable corresponding to the non-negativity constraint on v. The Lagrangian for the above problem is given by
((v,A,,,C) a Σ (.v v.) -.) - BT e) -viv.
(13)
1=1
From the first-order optimality conditions, we get
0L(v, 3,C,) =0
dv
a + 2 - (v- - =
i=1
=V=
2A
Σ 2A - -a (a-Q i=1
Substituting this value of v in (13), we get
1 1 (a- QT0 <)'
X.S (1
(a QQB c)) + Σ AvTS,'
AER 3ER5T mm CERMM
8 1.ST 'v:'' ' 1.S -1
X:S;'v
1=1
(a 1--------- C)T 1
X.S. ②
A.S. v.) Σ
2 +
i=1
19

---

Finally, we substitute the above dual problem back into the original problem in (1) to get
4 ( (a A.S, (a
Σ A..Ss'vv
max AERG PER CER
1=1
A.S, v.) A.S.
v.)
+ (a -a-QQ' () 2 A.S A.S. v.)
Σ Arf 3
Note that the dual problem is concave in X, B, and (Section 5.1 in [12]). However, it is unclear if the dual is concave in allocation a. In order to guarantee concavity, we use the change of variables & Ç. From infine-composttinn rule in convex optimization (Section 3.2.2 in [12]), we know that if (x) given æ E IR" convex, then f( f(Ax bb) given A E R=*" b E IR" 2 is also convex in a. Thus, the variable change & = a Ç results in objective that is concave in &. X. B. The allocation variable a and the dual variable Ç only appear in a linear constraint, which is also concave. Thus, the optimization problem is concave in a, B, X, and &. and Ç.
8 (NeTTS Aot) -q
max p BTe 7D Tp +
Σ
$EA.AERO
BER
(14)
s.t. =
where p = - Q (Ein
Ei= - A.S.'v vv and A A - B (E
Rum Va N Eier fam++ Ra, vi e 1: EnEN Eam++ S 1/. $ = c}.
We can solve the optimization problem in (14) using standard convex optimization techniques [12].
Alternatively, we can further simplify the problem by eliminating the allocation variable a and the dual variable Ç and subsequently deriving them from the solution of the resultant problem.
Note that (14), a Ç = &. Let (a", (*) represent an optimal (a, () pair for the problem in (14). Now there can be multiple pairs of (a. () that are optimal. To eliminate & and a, we need to first ensure that there exists g e A such that g' = a" - <" for at least one optimal pair (a",<*) <')) is easy to that if there exists such E' A. then, & maximizes the objective in (14). Furthermore, since A is defined solely by upper-bound constraints on & imposed by A, we can easily verify that will contain at least one instance of E' that satisfies & a' -
Thus, can break down the problem in (14) into two sub- uub-problems. In the first problem, obtain the optimal value of X, and (9 by solving
5' = arg TTq + 3
TD + Σ
(A.v.S, 'v -dr?) - Tq
CERR BER EEA
where p = QTB,qq . Ei=1 i and T= = (E 1, Then, we can compute the
set of optimal pairs (a* (-) by solving the system of equations: {(a, C) a E A. E Byf a < E).
H.2 Proof of Corollary 3.2
Corollary 3.2 (Utilitarian Welfare with Polyhedral Uncertainty). In the case where the uncertainty set V is defined purely by linear constraints, i.e., V = {v E Rmm Qv 2 e,v 2 0}, the optimal allocation a" for the problem in (1) can be computed by solving the linear program
max a k
Bee S.I. Q
20

---

Proof. Now consider the inner- miermminimization problem:
min a m
Qv _ v ト
We compute the dual of the above problem using the Lagrangian method. We will use B B to represent the dual variable corresponding to the linear constraints Qv 2 and Ç E Rof to represent the dual variable corresponding to the non non-negativity constraint on
L(v,8.C) aTv (Qv--ee) vTv = (a - Q - vv
1(3,5) e
(a (a Q otherwise
x
Therefore, the dual is given by
max Be BER ÇERB!
QTB
Since Ç is non-negative, we can eliminate it to get
max ,
BER
e <
By combining the dual with the outer-maximization problem in (1), obtain the final result.
H.3 Proof Corollary 3.3
Corollary 3.3 (Utilitarian Welfare with Ellipsoidal Uncertainty). Suppose that the set V in (1) is
defined by a single truncated ellipsoidal constraint, i.e., {v gum (v - VS (v v) s
x², v - 0}. The problem in (1) is equivalent solving
STSE 4A
max TVV
X
(4)
XeBo+. EEA
The exact optimal solution (X*, ) to Equation (4) can be computed by alternately performing two steps until convergence: first, fixing & and optimizing X, i.e., X = VÊTSE/2r, and second, fixing and solving a concave quadratic program to optimize E. The optimal allocation a" can be computed from e in Proposition 3.1.
Proof. Consider the inner-minimization problem
Σ alvo
min veRum
GEg
(v vV -v- v)
v 0
Similar to the approach in Proposition 3.1, we will use the Lagrangian method for computing the
dual of the above problem. We will use X Ro+ to represent the dual variable associated with the ellipsoidal constraint, and Ç E Egy to represent the dual variable corresponding to the non- negativity constraint on v. The Lagrangian for the above problem is given by
L(v, X, aTv ((v vVv-v) v)
v) - -²²) - -CTV.
(15)
21

---

From the first-order optimality conditions, we get
@I(v, X. = 0
δv
+ 2AS
I(v v)
S
(2AS- (aa (a-{)) <))
2X
Substituting the value of v in the above equation in (15), we get
((a (a-<)² 5) () (a ()
(a-C)TV Ar²
AER0I
CER
From the theory of convex optimization [12], we know that the dual of a convex optimization prob- lem is always concave, and therefore, the above optimization problem concave in À and Ç. Com- bining the dual with the outer- outer-maximization problem in (1), we get
1 (a
max max aEA AER
+ +aa-5) -
SERT
To further obtain concavity allocation a, we follow the same procedure as in Proposition 3.1 and use the change of variables & = a - Ç to get
max TV ETSE
dr
a
4A
AER EEA
(16)
s.t. E = 5
where A is defined as in (2).
As result of the change of variables, the allocation variable and the dual variable now appear only in a linear constraint, which is convex. Furthermore, due to the affine composition property of convex functions (Section 3.2.2 in Boyd al. [12]), the objective remains concave in À and &. Thus, the above optimization problem is concave in a, X, Ç. and g.
Similar to the approach used in the proof of Proposition 3.1, we further simplify the problem by eliminating the allocation variables a and the dual variable Ç and subsequently deriving them from the solution of the resultant problem.
From (16), we know that that a <= = E. Let (a", represent an optimal (a, () pair for the problem in (14). Note that there can be multiple pairs of (a, () that are optimal. To eliminate Ç and a. we need to find a of feasible g. which we denote by A, such that there exists that g === a" -S" for at least one optimal pair (*). It is easy to see that if there exists such e' E A, then, maximizes the objective (16). Furthermore, easy to verify that satisfies this criteria for optimality, i.e., it contains at least one ç that satisfies g = a* S" for some optimal pair (a*,(*) ).
E such
Thus, we can efficiently solve the problem in (16) in two steps. First, we obtain the optimal value of and by solving the problem
ETSE
X- arg max TTV
Ar
XE
41
EEA
As in Proposition 3.1, compute the set of optimal pairs (a", (a*{")) by solving the system of equations: ((a, <) a A, 5 E RR a = E
22

---

H.4 Proof of Proposition 3.5
Proposition 3.5 (Robust Group Egalitarian Dual). The problem in (5) is equivalent to solving
max min Blea + Tooaa 4 Po Topo+ GSg
ECA
AE BERUX
(A Tavva - Aasra.s) To4T.
where for each group G E G. PG = Ec Q6.c. qG = Da, Tc =
(Eizi Ag.SSa)) and A is defined as in Equation (2). The optimal allocation a" can be com-
puted from 8r as in Proposition 3.1.
Proof. Consider the following optimization problem.
min min aEA GEG voEVe
aLva
ei [1,4] VG G: (va v..c) vi.o) S
(17)
VG E G Qave eg
VG v
important to note that the inner-most minimization is a convex optimization problem and the muter-maximizztion is concave maximization problem. This is due to the fact that affine functions are either concave or convex and minimum of concave objectives is concave.
Notice that the inner-most minimization problem for each group is independent of other groups. Thus, we can simply replace each of these minimization problems with their Lagrangian dual coun- terparts. Furthermore, we note that these duals are computed following the approach outlined in the proof of Proposition 3.1 and are exact equivalents of their respective primal counterparts [12]. The resultant optimization problem is given by
min AgE A 64 COER ml
4 (ac Qh.aa
CG)
Σ
(ac QoBc - Scs) (ca) )+
1
Σ AG.V 1
Σ Sc,
Σ Ac
Σ
No, vo.
(ag - -6-30 - -ca)T
Σ Sa.
Aa c VGG
Σ A B7.G
Notice that the inner-most maximization problem for each group G concave in AG. Ba, and ÇG- We now apply the same procedure as in the proof of Proposition 3.1 to obtain concavity in allocation Using the change of variables VG G EG ac CG. we get
max min AE GES AGERt Beec + +ooToG
max
4 ToPe + Σ (Na.vo. Tovo,, -oos---c.tte do.râ.)) q Toqc
ACERE fi faca/cim
s.t. εσ = ag Co
where for any G E G.PG EG - 1o. To = (Eln Sa. and qo Σ' Ac.
Since the inner maxinization for each group independent of the other groups, we can re-order the inner minimization groups and the inner-maximizati problem. Thus, without loss of
23

---

generality, we can write the above optimization problem as
max min Blea + PoTcoe - p Σ
Tope
Tovos - -a, ToToc
asA GE9 CER*M X
Beage EER"m
S.L. EG - ag - SG
Using the same technique as in the proof of Proposition 3.1, simplify the problem by climi- nating the variables a and Ç in the above problem and then derive them from the optimal &. Eliminating Ç and the above equation, we get
arg max min A GEG
3yec + Toqc P Tope + Σ
Aa, Na.Vo,Tova. - Ao,rras - ToTcqe
BERDT x
where for each group G g, PG (Eg ())), qa Ei Ac.Ss,.C,, To
E ).. -1, and A A Ritt { Rum Va N Eier Eier I: EaEN Samti S Vi. 3 c).
Ray Vi
As in Proposition 3.1, we can determine the of optimal pairs (a*) by solving the system of equations: {(a, () E A, Ç R a E}.
H.S Proof Corollary 3.6
Corollary 3.6 (Group Egalitarian Welfare with Polyhedral Uncertainty). In the case where the un- certainty set V is defined only by linear constraints, ie., V = {v E Rum VG E G Qava 2 eg, - 0}, the max-min-min problem in (5) transforms into linear program.
Proof. Now consider the innermminimization problem:
max min a GED voE m
min
aG TvG
VG g: Qova 2 eg
We can compute the Lagrangian dual of the mner-most minimization problem for each group inde- pendently by following steps outlined in the proof of Corollary 3.2. Note that since these minimiza- tion problems are simple linear programs, their corresponding duals are exact equivalents of their Boyd al. [12]). By substituting the duals the above problem and reordering the inner-maximizatin and minimization problems, we obtain
primal counterparts (Section
max min acA GEg BEReXE
0. aag
ag
Using simple algebraic manipulations, we can further simplify the above optimization problem as
max 1
BER tR
YG g 3.ec
YG G Q3 ag
24

---

H.6 Proof of Corollary 3.7
Corollary 3.7 (Group Egalitarian Welfare with Ellipsoidal Uncertainty). Suppose that the set V in (5) is defined by single truncated ellipsoidal constraint per group i.e., V = {v R VG G
(va - VaaSaa (va va) r. 0}. Then the problem (5) is equivalent solving
max min VVvG x GED CEA
Acra
4AG
The exact optimal solution (X"E") ) to Equation (4) can be computed by alternately performing two steps until convergence: first, fixing & and optimizing X, i.e., VG E G, AG VV5Sata/aa and second, fixing X and solving concuve quadratic program to optimize &. The optimal allocation can be computed from E as in Proposition 3.1.
Proof. Consider the following optimization problem.
max min min a GEG VoER
aLvG
VG E g: (va - vo) va) S
VG = 0
Similar to the general version of the problem in (17), the inner-most minimization is convex op- timization problem and the outer-maximization is a concave maximization problem. This is again due to the fact that affine functions are either concave convex and minimum of concave objectives is concave.
The inner-most minimization over the uncertainty set of valuation matrices is independent for each group. Therefore, by simply replacing each of these minimization problems with their respective Lagrangian duals, computed in Corollary 3.3, obtain
((ac - " So -0----5 (o) (ag vo X 4AG
max min max 304
60 Glim
Note that the dual is computed following the approach outlined in the proof of Proposition 3.1.
Using the change of variables VG g &G aG CG. we get
max min max Vo ScEC Xar aEA Geg
Ag
4AG
CoER!0 s.t. EG = ag CG
Ecezlojm
Since the inner maximization for each group is independent of the other groups, re-order the inner minimization over groups and the inner-mxiimization problem. Thus, without loss of generality, write the above optimization problem as
max min Vo SoEC -
aεA GEG
4NG
XER
CERNO &ER
s.t. EG ag CG Using the same technique as in the proof of Proposition 1.1, simplify the problem by elimi- nating the variables a and Ç in the above problem and then derive them from the optimal g.
Eliminating Ç and the above optimization problem, we get
EoSocee 1AG
arg min &. GES
AGr2
XERY
εEλ
where A = A - Rot
R mm V
Eigr Samti EagrEamti Ray Vi E 1 EaEN Com+i S
wi.& E < c).
As in Proposition 3.1, we can now determine the set optimal pairs (a*,5*) by solving the system of equations: ((a, () a A, Ram.
D
25

---

H.7 Proof of Proposition 3.8
Proposition 3.8 (Decomposition for Monotonic Welfare Functions), Consider an optimization problem of the form
max min WM((((, aEd veV
(8)
where the welfare function W M is monotonic in the utility of groups. If Assumption 3.4 holds, then (8) simplifies to
min uc, (aG, vc.)) vog EVG,
max WM min aEA
UG, (ag Narh min ucg (aG2, VGz).... va, EVaz
VG, VG,
Proof. The result directly follows from the monotonic property of the welfare function and the independence of the uncertainty sets across groups.
H.8 Proof of Proposition 4.1
Proposition 4.1 (Approximate CVaR of USW), Given iid samples of V, i.e. v², v2 v ,.... from Dv, the optimal allocation for the problem in (9) can be approximately computed by solving
b- a
VJE vs 2 1 x (b- uuaa
max max aEA NER
yi
(10)
BER
Proof. Consider the CVaR of utilitarian welfare optimization problem, given by
{--1 1 E vnDo
CVaRa [w- u(a, v) = aEA
max aEA,EER
[ w u(a v))+
Substituting the expectation with the empirical expectation computed from the h samples of ran- dom valuation v. and using slack variable y E R to convert (b u(a, v)) term in the expectation linear constraints, we get
1
max max REA VER",NER HER
b
Σ
yi
Vj E [L, h] yj 0
Vj E [L,h] y h
WG G
GEg
a AEA.
Assumption H.1 (L.A. el al. (35]). The random variable is continuous with probability density function f that satisfies the following condition: There exists 1). >> O such that Vy [Va 7, Va + 7] f(y) > n,, where V. = =F)
Theorem H.2 (Theorem 3.1 in [35]). Let (ā:)/= be sequence of i.d random variables. Suppose and Assumption H.1 holds. If co and En represent the
that T,, i = 1,..., n are true CVaR and the empirical CVaR. of random variable estimated from h samples confidence
level a respectively, then for any E >> 0, we have
-ha² min(e? 1672) min(n?:1)
Pr |Cohaa Cal > E| s 6exp
max(8, 02)
26

---

H.9 Proof of Proposition 4.2
Proposition 4.2 (Sample Complexity of Approximate CVaR of USW). Suppose that & is a multi- variate sub- Gaussian random variable with mean v E I and covariance proxy S E Rmmxxo xm ie., for all vectors E Rum EE [exp((v - v)T2))] S exp(x*8x/2), and that, for any risk and radius 7 > O, s.t., Ja (2r) > 1J Vx E ( - Vn +7]. Sei VG G ::a wese Then, for any confidence parameter E (0, 1) and enror tolerance & > 0,
level a (0, 2) and allocation a E A. there exists probability density threshold
G]
max (maxae a Sa', In min(=², 16 (rin
GLA ((8)
Pr
Cn Ca ca(a E aEA
sup
2 8 for h
Proof. From the assumption, we know that the valuation vector V is sub-Gaussian random variable that satisfies the following condition
Y Rum
E SnDD
[exp((v T=))) S exp(=*Sz/2)
Using the above properties of sub-Gaut Gaussian, we can establish that the utilitarian welfare for a given allocation is also Gabb-aussiinn with variance-proxy a Sa' where VG E g a'g
wa
[G]
For any allocation a, let êa (a) represent the empirical estimate CVaR of utilitarian welfare and ca (a) represent the corresponding true value.
Then, using Theorem H.2,
bound the of approximating the CVaR of the utilitarian
welfare for allocation a as
(hha² min(s? 16,2) min(m)nn())))) 8 max(8, STa'
Pr | (a) (a)) > E| I 6exp
The approximation error for all allocations can be upper-bounded using a union bound as
Pr
sup
(a) co (a)) >
Pr (1)),a(a) ca) > e]
aEA
aEA
(18)
-ha² minn(=?, 47²) min(r?, 1)
exp
8max(8, a (Sa')
To obtain confidence guarantee Pr[Va A: 18 (a) ca (a)l S 2] 2 1 8, we the R.H.S of (18) to be less than 8, i.e.,
-haa min(=? (2)) min(12
ex|6exp
<
8 max(88, Saa)
Solving for h, we get
8 maax(maxac a'TSa, 8) In
(in(=2,47))) min( 1)
H.10 Proof of Proposition 4.3
Proposition 4.3 (CVaR of USW for Gaussian Distributions). V is distributed as a multivariate Gaussian, i.e., & ~ NNV S), then, the optimization problem in (9) simplifies to
2($ 6(0-1(()) (() TSa
max AT
(11)
a
27

---

Proof. The proof simply follows from the fact that for any Gaussian distributed random variable I N o²) with mean μ R and standard deviation E Ro+. CVaR[ā] = - (()= a. The mean of utilitarian welfare under the assumption that v Gaussian distributed given by a v and variance is given by a' Sa', where for any G' a " Substituting these values in
a:
the previously mentioned expression of CVaR of Gaussian random variable, we obtain the results stated above.
H.11 Linear Program for CVaR of Egalitarian Welfare
Proposition H.3 (Approximate CVaR of GESW). Given h samples of v, i.e. v v2 v v sampled from the valuation distribution Dv. the optimal allocation for the problem in (12) can be approximately computed by solving
max max AEA
Σ V0
MER BER
a
(19)
vj E 1, v, 2
b
al abv3)
|G]
Proof. Consider the CVaR of egalitarian welfare optimization problem, given by
(
(
max CVaRa aEA
min GE9
alva
max bER,aEA
TE a V-
min GEg
vo
G
G
Substituting the expectation in the above problem with the empirical expectation computed from the h samples of the valuation matrices, we get
)
abvv))
RJ
max bER,aEA
b
min
ah
GED
G
i=1
Introducing slack variables y E Rh,, write the above problem
1 h b
Σ
max max AEA DER"
Vj
j=l
(20)
Vj E [1 yj 2
Vj E [1, M] yj 2 h
min GEg
abv's
G
Without loss of generality, we can represent the above problem as
b b yj
max max a YERA DER
j=1
Vj E [1,4] y3 20
Vj [1,4] VG G: y1
1 (
b
1
abvi)
h
G
I GESW vs. USW under Different Scenarios
We run an experiment to discover scenarios where the USW-optimal solution has very sub-optimal GESW. Using the AAMAS 2015 dataset, set all of the papers to be group 1, and we create second, synthetic group of papers by copying and modifying random subset of the papers. For these papers, divide the copied valuations by some number, and set zero all but the top valuations
28

---

Relative Loss of USW Solition
Relative USW Soluton
20
80
15
(% Ofttiial)
60
(36 ofoff Optimal)
40
10
20
5
0
10
20
0.08
0.17
0.26
0.32
Ratio of Group Scores
Minority Group Ratio
Rolative Max. USW Solation
20
1% of Optinal)
15
10
5
1
6 11 16 21 26 31 36 41 46
Number of Nonzero Affinites
Figure 4: Relative loss (in GESW) of the maximum USW solution, compared to the optimal GESW solution. Results are reported for a synthetic 2-group example, varying 1) the divisor applied to artificially scale the minority group's valuations. 2) the ratio of the minority group to the overall number papers, and 3) the number of valuations per paper that are artifically set
per paper. For each setting compute the percentage of relative loss in GESW incurred by the maximum USW solution. Figure shows the effects of varying the percentage of papers in the minority group, the number of non-zero entries, and the divisor. We use default values of 2 for the divisor, for the number of nonzero entries, and 150 for the size of the minority group (corresponds ratio of roughly 20%). Taken together, the results suggest that if group of papers has overall lower bids than another group, this has very strong negative effect on the GESW of the USW-optimal solution.
CVaR Performance under Skewed Gaussians
We use the AAMAS 2015 dataset and sample each valuation independently from skewed-Gaussin distribution with varying skew parameter. We use the means and variances estimated by the Gaus- sian Process matrix factorization model described in Appendix E. The univariate skewed-Gaussian distribution with mean μl, variance o², and skew a is defined by the probability density function
p(x: a) 20( (a((((( p)/a).
where & and d are the probability density function and cumulative density function of a standard Gaussian distribution [6].
We compare against the uncertainty unaware from the Gaussian distribution, which is optimistic uncertainty set). We optimize and evaluate for CVaRp.a- Table displays the results. As the skew parameter a gets more negative, the C'aRRo.3 of welfare of the naïve and robust solutions get much worse compared to the CVaRRoptimized solution.
unnawar and robust USW solution (using the ellipsoid derived
We also consider a constructed scenario with two agents and four items, where each agent must be assigned one item. Each agent's valuation for item is independent and follows a skewed Gaussian

---

Table 8: Performance of different allocations for CVaR on the AAMAS 2015 with skewed Gaus- sians.
Skew
CVaR USW
USW
Rob. USW
0.5
1.64
1.56
1.01
-1
1.45
1.21
0.86
-2
1.33
0.96
0.75
5
1.29
0.84
0.70
10
1.28
0.82
0.52
Table 9: Performance of different allocations for CVaR of USW on toy example with skewed Gaus- sians.
Approach
Solution
oV [USW]
Naïve
0.947
0
0
1
0
0
0
0
Robust
0.972
1
0
0
0
1
0
CVaR
0.985
0
0
distribution. The mean valuations for the items are represented by the matrix
0.39
0.49
0.51
0.53
0.52
0.51
0.53
0.54
The item values have standard deviations [0.01 0.04 0.05 0.09] respectively for both agents, and the skew parameter is a = for all item-agent pairs. We sample 20, 000 samples from the skewed Gaussian distibutions. We compute the naïve USW- or GESW-optimal allocations using the mean valuations, and we enumerate all possible allocations to identify the CVaR and robust allocations confidence level of 0.04. To estimate the robust statistic 0.04 confidence level, we assume independence and reject any samples that fall outside the 0.04/8 confidence interval up- per/lower bounds for any individual entry. We then compute the minimum welfare the remaining samples. The computed solutions and the CVaRo.04 of each are displayed in Tables 9 and 10.
In both the USW and GESW cases, the naïve approach selects items 3 and 4, as they have the highest mean values, but does not account for the uncertainty in the preferences. The robust approach, being more conservative, chooses items 1 and 2 duc to their lower uncertainty. The CVaR approach strikes a balance between these two methods, selecting items and Item has lower mean value with low uncertainty, while item has higher mean value but with slightly higher uncertainty than item 2.
Table 10: Performance of different allocations for CVaR of GESW toy example with skewed Gaussians.
Approach
Solution
CVaRo. (WSS
0
Naïve
0.45
0
0
0
0
07
Robust
0.46
1
0
0
0
0
CVaR
0.47
1
0
30

---

K
Machine Specification
All experiments were run on Xcon E5-2680 v4 @ 2.40GHz machines with 128GB RAM with each experiment consuming at most 32 GB of memory. We ran 1500 experiments in total and each experiment took 3-4 hours.
31

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract describes the CVaR and robust optimization approaches taken in the paper, the utilitarian and egalitarian objectives studied, and mentions our theoretical and empirical results.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
See Appendix C.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The au- thors should reflect on how these assumptions might be violated practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the ap- proach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a apeech- speech-to-text system might not be used reliably provide closed captions for online lectures because fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to ad- dress problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
32

---

Answer: [Yes]
Justification:
All our formal statements appear with proof in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theo- rems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be comple- mented by formal proofs provided appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification:
Description of experiment provided Section 5 and Appendix D.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate the research performed.
While NeurIPS does not require releasing code, the conference does require all sub- missions to provide some reasonable avenue for reproducibility, which may depend on the nature the contribution. For example
(a) the contribution primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or a way to re- produce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibilityy may be tricky in some cases, in which case thors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
33

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: Link provided to code repository on Github Section 5, link and recom- mended citation provided for data.
Guidelines:
The answer NA means that paper does not include experiments requiring code. Please see the NeurIPS code and data submission guidelines ltttps:/nnips.ccpubblii
guidessCodeSubbissioonool
for more details.
While we encourage the release of code and data, understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (htips:
for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (e.g.. data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Justification: See Section 5 and appendix D, and code.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question:
Does the paper report error bars suitably and correctly defined or other appropri- ate information about the statistical significance of the experiments?
Answer: [Yes],
Justification: All results in the tables Section 5 and Appendix are averaged over 5 runs of sub-sampling 20% of each dataset.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
34

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report I-sigma error bars, but one should state it. The authors should prefer- ably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative rates).
show in tables or
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory. time of execution) needed to reproduce the experiments?
Question:
Answer:
[Yes].
Justification: The details of the compute resources used for the experiments is reported in Appendix K.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (c.g.. preliminary or failed experiments that didn't t make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer:
[Yes]
Justification:
We reviewed and abide by the code of ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.g., there is a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes],
Justification:
See Appendix B for details.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
35

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact spe- cific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitiga- tion strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA].
Justification:
We have used publicly available datasets in our experiments.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by re- quiring that users adhere to usage guidelines restrictions access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: We have only used Gurboi Solver for solving our optimization problems and have properly cited it.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
36

---

If assets are released, the license, copyright information, and terms of use in the pack- age should be provided. For popular datasets, paperswitheode. httpsswtthooe.ccomaattttttttt com/datasets has cu- rated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and the documenta- tion provided alongside the assets?
Answer: [Yes]
Justification:
We linked to code in Section 5.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
For crowdsourcing experiments and research with human subjects, does the pa- per include the full text instructions given to participants and sereenshots, applicable, well as details about compensation (if any)?
Question:
Answer: [NA]
Justification: No human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contri- bution of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, cura- tion, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper deseribe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: No human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equiva- lent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
37

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
38


Reviews:
[{"review_id": "NprV4xx8pu", "reviewer": "Reviewer_hqEo", "summary": "The authors of this paper investigate the fair multi-matching problem under uncertainty. Both stochastic and robust optimizations are considered to solve the proposed problem.", "questions": "W1, W2, W3", "limitations": "W1, W3, W4, W5", "rating": 4, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "S1. Fairness is an important and practical concern in resource allocation problems.\n\nS2. The theoretical results of this paper seem to be correct.", "weaknesses": "W1. The authors fail to provide a clear motivation example of the proposed research problem in real applications. For the reviewer assignment application, I do not see strong reasons why we need to consider uncertainty (the reviewers have already revealed their preferences over papers clearly) and fairness (the utility of a reviewer is how the assigned papers match her/him?).\n\nW2. What are the major technical challenges of considering both group fairness and uncertainty in the resource allocation problem? Since there are works discussing each factor (fairness and uncertainty), can we just adapt existing techniques to solve the proposed problem? Are there any new technical challenges caused by the combination of fairness and uncertainty?\n\nW3. Does the process of obtaining the uncertainty set assume a true model (usually linear models in statistics) of the uncertain parameters? If so, I am afraid the way of considering uncertainty is still a toy research problem because in reality the data distribution is usually unknown and complicated. The uncertainty set itself may not be constructed in a reliable way. For example, under what conditions can the authors prove that their uncertainty sets described in Appendix D have the true parameters? To prove this, I guess the authors may need strong assumptions about the data distribution.\n\nW4. As the reviewer assignment datasets do not have groups of reviewers, the authors may want to try different ways of grouping reviewers in experiments to make the results more convincing w.r.t. group fairness.\n\nW5. It seems to me that the experiments are just numerical simulations where the objectives are simulated. This makes the research problem a toy one as no real datasets are used to verify the proposed method.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed review. We respond to your comments and questions below.\n\n## W1\n\nAs mentioned on line 306, we adopt the model used by several major conferences: ICML 2022, AAAI 2022-2024, and IJCAI 2022-2024 [1]. In this model, papers are the agents, reviewers are the items, and the value $V_{a,i}$ of assigning reviewer $i$ to paper $a$ is estimated from multiple sources to predict the overall value to the conference of eliciting that review. \n\nAs such, the reviewer assignment problem offers several sources of uncertainty. Reviewers offer extremely sparse partial rankings of papers, with a significant proportion of submissions remaining unranked by *any* reviewer [1, 3]. Affinity score computation systems (e.g. those generated by TPMS [4] and Open Review’s expertise model [5]) utilize NLP methods which have\nwell-documented error rates [5]. [6, 7] both give strong overviews of the components that go into modern automated reviewer assignment systems, along with additional discussion of the noise inherent in the process. We can include all of this discussion in the camera ready.\n\n## W2\n\nPlease see the global response.\n\n## W3\n\nModeling uncertainty and constructing uncertainty sets are not contributions of this paper. Our main contribution is to show that for certain commonly used uncertainty sets (see, e.g., [2] for derivations), the problem of optimizing fair welfare objectives under uncertainty can be efficiently solved using our proposed methods. Cousins et al. [7] also provide more detail on constructing uncertainty sets in the same setting as the current work.\n\nThat being said, Appendix D illustrates a simple example of how to construct an uncertainty set. The simplified bound in Appendix D assumes 1) that the validation set is drawn from the same distribution as the distribution under which we make assignments, and 2) that the cross-entropy loss is normally distributed. The first assumption, although quite strong, is fairly standard in machine learning (see Ch. 6 and 7 of Shalev-Shwartz and Ben-David [8] or Ch. 14 of Mitzenmacher and Upfal [9]). There are also ways to relax this assumption by modeling distribution shift or bounding the total variation distance between the distributions. The second assumption is fairly standard as well, as it holds in the limit by the central limit theorem. While there are certainly more accurate ways of estimating this generalization error, these improvements would only change the real-valued RHS of the inequality between lines 574-575 or add fixed multiplier terms on the LHS (more details in [7]). In both cases the structure of the optimization problem (our main focus in this work) remains unchanged. \n\n## W4\n\nPlease see the global response.\n\n## W5\n\nWe do try to generate results using settings that are as realistic as possible (e.g. basing our experiments on a mix of empirical data and simulated data), however they are ultimately not ‘the real deal’. We have spent a considerable amount of time and effort unsuccessfully trying to convince conference organizers to provide us with some access to reviewer data,\nwith appropriate anonymity and experimental standards in place. Organizers’ reluctance to support meta-analysis of reviewer assignment is (to some extent) understandable: the stakes of conference reviewing are extremely high, and the organizers bear some overhead in supporting the experiments we want to run on real data. \n\nWe also suffer from a chicken-and-egg problem: in order to make the case to conference organizers that our methods make sense, they need to be published in top-tier venues. In order to get our methods published in top-tier venues, we need access to data by conference organizers. \n\n### References\n\n[1] Leyton-Brown, K., Mausam, Nandwani, Y., Zarkoob, H., Cameron, C.,\nNewman, N., & Raghu, D. (2024). Matching Papers and Reviewers at Large\nConferences. Artificial Intelligence, 331.\n\n[2] Gupta, V. (2019). Near-Optimal Bayesian Ambiguity Sets for Distributionally Robust Optimization. Management Science, 65.\n\n[3] Rozenzweig, I., Meir, R., Mattei, N., & Amir, O., (2023). Mitigating Skewed\nBidding for Conference Paper Assignment. International Conference on Autonomous Agents and Multiagent Systems, 22.\n\n[4] https://torontopapermatching.org/webapp/profileBrowser/about_us/\n\n[5] https://github.com/openreview/openreview-expertise?tab=readme-ov-file#performance \n\n[6] Shah, N. (2022). Challenges, experiments, and computational\nsolutions in peer review. Communications of the ACM, 65.\n\n[7] Cousins, C., Payan, J., & Zick, Y. (2023). Into the unknown: Assigning reviewers to papers with uncertain affinities. International Symposium on\nAlgorithmic Game Theory, 16.\n\n[8] Shalev-Shwartz, S. and Ben-David, S. (2014). Understanding Machine Learning: From Theory to Algorithms.\n\n[9] Mitzenmacher, M. & Upfal, E. (2017) Probability and Computing, 2nd edition.", "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": "", "extra_scores": {}}, {"review_id": "WrX2eBwVAs", "reviewer": "Reviewer_ZdA8", "summary": "The authors study a resource allocation problem where the objective is to optimize for efficiency and fairness under the presence of some uncertainty. The agents are partitioned into groups and the items need to be assigned so as to be fair to the groups. They study two maximization objectives : 1) a weighted sum of social welfare of groups and 2) the social welfare of the group with the least amount of welfare. They study two models of uncertainty over the agents' valuations of the items - the first is when there is some explicit uncertainty set and the objective is to maximize the worst-case outcome across this uncertainty set, and the second is when the distribution over the valuations is known and the objective is to maximize the Conditional Value at Risk (CVaR$_\\alpha$).\n\nTheir primary contribution is to present formulations of these problems as various mathematical programs. They make assumptions on the uncertainty sets so as to make these formulations suitable for optimization in certain cases. They present experiments supporting their models and formulations.", "questions": "1) Are there any tractable settings where the agents can be in multiple groups at once? There are many resource allocation, clustering, etc. papers where such settings are considered.\n2) Can't the robust setting be viewed as a subcase of the CVaR setting where you maximize the worst (ie. the 0 percentile) outcome?", "limitations": "N/A", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1) Their experiments suggest that optimizing for CVaR has some benefit under a large uncertainty regime, as well as points to the benefit of considering the robust uncertainty model. \n2) Their formulation and subsequent solution appears to be faster, and more successful, than applying the naive solver.", "weaknesses": "The paper is a bit terse, and hard to follow at times. It would be beneficial to add more details where necessary. For example, in Line 180, please mention the randomized rounding procedure or at least the properties of the output rounded solution. Ideally, there would at least be some more details to get to the propositions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments and suggestions!\n\n**Please mention the randomized rounding procedure or at least the properties of the output rounded solution.**\n\nThank you for the suggestion. We will add more details on the rounding procedure in the camera ready version of the paper. Please see the final answer in our response to Reviewer UQiJ as well, where we discuss the rounding procedure and its relation to our experiments in a bit more detail.\n\nIn general, we can use the extra page in the camera-ready to expand some details that were necessarily compressed for the submission. Reviewer UQiJ also had a great suggestion to move some of the formal theorem statements to the appendix, which should free up additional space for explanations.\n\n**Are there any tractable settings where the agents can be in multiple groups at once?**\n\nOur LP solutions for robust allocation with linear uncertainty sets and CVaR allocation (without normality assumption) for both utilitarian and egalitarian welfare can be trivially extended to the case where agents are in multiple groups. \n\nThis is a good point in the case of robust GESW. However, the independence of groups assumption is not a fundamental limit, but rather a simplifying assumption. The subgradient ascent approach still works for the robust GESW allocation when groups aren’t disjoint. Because the minimizer will concentrate the uncertainty on a single group for GESW anyway, when we compute the minimizer at each step of subgradient ascent, we can just compute the minimizer for each group individually (even though the groups have some overlap). \n\nWe agree the disjoint groups assumption can be limiting, but not unreasonable, in practical scenarios. Conferences often group papers into disjoint tracks and/or require paper authors to submit a unique primary subject area. Although they may have multiple secondary subject areas, the top-level grouping remains independent. We can handle grouping by secondary subject area using subgradient ascent as mentioned above, but it is also reasonable to use the primary subject area grouping and apply the faster approach we describe in our paper.\n\nWe’ll include all this discussion in the paper.\n\n**Robust setting be viewed as a subcase of the CVaR setting.**\n\nYes, it is well-known in the literature that the robust setting is a special case of CVaR where $\\alpha=0$. However, using the CVaR approach proposed in Section 3 is inefficient because it requires a large number of samples to ensure that the uncertainty set implicitly constructed by CVaR captures the worst-case valuation matrix. Instead, we can directly incorporate the learned uncertainty set as a constraint and optimize against the worst-case model in this uncertainty set by solving a max-min optimization problem. This results in a more efficient algorithm that is not limited by the sampling complexity of CVaR.\n\nWe note that prior works [1,2,3] in Distributional Robust Optimization have taken similar approaches when dealing with worst-case objectives.\n\n\n[1] Rahimian, H., Mehrotra, S. (2019). Distributionally Robust Optimization Review. Arxiv.\n\n[2] Lobo, E., Ghavamzadeh, M., Petrik, M. (2020). Soft-Robust Algorithms for Batch Reinforcement Learning. Arxiv.\n\n[3] Virginie Gabrel, Cécile Murat, Aurélie Thiele. (2014). Recent Advances in Robust Optimization: An Overview. European Journal of Operations Research", "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": "", "extra_scores": {}}, {"review_id": "TO3J9U3TwZ", "reviewer": "Reviewer_5Awd", "summary": "This paper looks at the problem of computing resource-agent matchings under uncertainty in a group setting, where the actual valuations of agent-resource matchings are unknown. When the distribution of the valuation uncertainty is known, they look at stochastic optimization using Conditional Value at Risk (CVaR), and when a set of candidate valuations is known, they look at robust optimization through max-min optimization for worst-case valuation. They present methods to optimize for two objectives: utilitarian, where each individual is equally weighted, and egalitarian, where they look at only the group with the minimum utility. They consider uncertainty sets which are either linear or elliptical, and provide derivations of the optimization algorithm for each combination, reducing the solution to an LP in many cases, and with quadratic programming or sub-gradient ascent in others. They also show some empirical results on a reviewer assignment dataset.", "questions": "1. What is the benefit of using the CVaR and Robust variations of the optimization when the base optimization performs better in most cases? Except adversarial welfare for the robust optimization, there seems to be no meaningful benefit of considering uncertainty.\n1.1. Unless I am mistaken, the baseline USW and GESW methods are supposed to be improved by considering uncertainty. If this is not the case, this needs to be mentioned in the paper and clarified.\n2. Why would we need to select the GESW objective when USW performs better in almost all cases? What is the significance of the fairness aspect of the paper in this case?\n3. Where can this be applied? Can you give some examples of allocation problems that are admissible based on the assumptions and limitations of the approaches (e.g. linear/quadratic valuations), and cases where it would not hold?", "limitations": "The paper addresses some limitations in the text. The authors could expand on the situations in which the proposed methods offer an advantage. The authors should also mention the possible negative side effects of using methods that do not lead to intuitive solutions like using CVaR (in Example 2.1, for example). This may lead to affected users perceiving unfairness or inefficiency when the metric is not easy to understand.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper formalizes a set of methods to optimize the important problem of fairness and group-aware resource allocation under uncertainty. The paper is well-written, and sufficient description is given for readers to comfortably follow the theory developed. The solutions to the optimization problems are reduced to computationally tractable instances that are popularly solvable, and the analysis for both linear and quadratic uncertainty sets is a welcome addition. The empirical results also provide context on how well certain solution approaches scale. The approach seems to be novel, and encompasses a range of general use cases.", "weaknesses": "1. One of the limitations I found in this paper was that the authors did not compare the uncertainty-aware solutions to other prior approaches at solving these problems: what benefit does this approach give us? There is no discussion regarding this. From the results, it seems the base methods (USW and GESW) are better than the Rob and CVaR variants.\n2. The results do not show any indication of where the GESW optimization may be beneficial. Instead, it appears that the USW optimization supersedes the GESW optimization. If that is the case, the importance of the 'fairness' part of the paper is greatly diminished. The authors should preferably select an evaluation dataset where the approach can show its benefits, if any, to justify its inclusion.\n3. As the authors state, the CVaR optimization is much slower. It also seems to require more information than the robust variant of the problem. Without a sufficient justification for its use, what is the merit of including it?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments and suggestions! Please see our replies below.\n\n**Compare the uncertainty-aware solutions to other prior approaches at solving these problems?**\n\nWe first emphasize that while we present novel solutions, our primary contribution is suggesting new *objectives* for the constrained allocation problem, i.e., optimizing utilitarian and egalitarian welfares under uncertainty. To our knowledge, the only existing prior work that solves one of these objectives for the constrained allocation problem is [1], which optimizes utilitarian welfare under ellipsoidal uncertainty sets using a projected subgradient ascent method. We compare against this method in the right half of Figure 1. Any algorithm that optimizes the uncertainty-unaware objectives is also an appropriate baseline. Those objectives can be optimized exactly, and we did compare against those uncertainty-unaware optimal baselines (USW and GESW in lines 1 and 2 in each table, and the dashed lines in the left half of Figure 1). We note that [5] focuses on optimizing expected envy or the probability of envy under uncertainty in valuations, which is a fundamentally different objective and thus not comparable to our methods. This distinction also applies to the other prior works mentioned in the related works section. We are happy to compare to other relevant baselines if we are made aware of them.\n\nOur global response on \"Technical challenges in combining fairness and uncertainty\" also applies to this question.\n\n**As the authors state, the CVaR optimization is much slower. It also seems to require more information than the robust variant of the problem. What is the merit of including it?**\n\nThe Conditional Value at Risk (CVaR) of a random variable $ X$ at the $\\alpha$ percentile is the expected value of $ X $ below its $\\alpha$ quantile. By optimizing allocations to maximize the CVaR of welfare, we ensure that the welfare value will be at least $ w$ with $ 1-\\alpha $ probability, where $w$ is the CVaR of welfare corresponding to the CVaR-optimal allocation. Put simply, instead of picking an allocation that ensures a welfare of $\\ge w$ for *every* allocation (as does the max-min approach), CVaR allows a more refined analysis, allowing stakeholders to ensure a welfare of at least $w$ for at least (say) $90\\%$ of the possible valuations. \n\nThus, the CVaR measure is a less conservative objective than the Robust measure and is widely used in Operations Research and Machine Learning literature [2,3,4] to handle fat-tailed loss distributions. \n\nFinally, we emphasize that we do not advocate for any specific uncertainty-aware objectives; we simply demonstrate how to achieve fair allocations under uncertainty using popular uncertainty-aware objectives.\n\n\n**What is the benefit of using the CVaR and Robust variations of the optimization when the base optimization performs better in most cases?**\n\nThe uncertainty-unaware USW and GESW optimization performs very poorly on the robust objectives (the last 2 columns of the tables). In Table 1, the CVaR of USW/GESW is optimal under the uncertainty-unaware baselines, but this is likely due to the fact that there is not very much variance in the distributions we estimate. This is evidenced by Figure 1, where performance of the uncertainty-unaware solutions drops as noise increases. However, we do expect the diagonal entries of all tables to be at, or very close to, 1.0 – i.e., when you (approximately) optimize for some objective, you perform near-optimally on that same objective.\n\nAs shown on the left of Figure 1, the value of the uncertainty-unaware USW and GESW solutions on the CVaR objective becomes worse as the level of uncertainty increases. In our setting, the CVaR measure is particularly useful when the distribution of welfare is long-tailed, where optimizing for the worst case results in an overly conservative allocation (low welfare). We will use our extra page to add this clarifying discussion in the paper.\n\n**Why would we need to select the GESW objective when USW performs better in almost all cases? What is the significance of the fairness aspect of the paper in this case?**\n\nPlease see the section of the global response on \"Different ways of grouping reviewers\".\n\n**Can you give some examples of allocation problems that are admissible based on the assumptions and limitations (e.g. linear/quadratic valuations) of the approaches?**\n\nWe refer the reviewer to Appendices B, D, and E for detailed discussions on allocation problems where our methods are applicable. \n\nPlease see the global response  and our response to Weakness 3 (W3) of reviewer hqEo for discussion on assumptions made in the paper.\n\nWe also note that we have also included a discussion on the runtimes of our proposed algorithms in the global response.\n\n[1] Cousins, C., Payan, J., & Zick, Y. (2023). Into the unknown: Assigning reviewers to papers with uncertain affinities. International Symposium on Algorithmic Game Theory, 16.\n\n[2] Soma, T., Yoshida, Y. (2020) Statistical Learning with Conditional Value at Risk. Arxiv.\n\n[3] Rockafellar, R.T., and Uryasev, S. (2000). Optimization of Conditional Value-at-Risk. Journal of Risk, 2.\n\n[4] Stoyanov, S., Rachev, S., Racheva-Iotova, B., Fabozzi, F. (2011) Fat-tailed models for risk estimation. Journal of Portfolio Management, 37.\n\n[5] Dominik Peters, Ariel D. Procaccia, David Zhu (2022). Robust Rent Division. Advances in Neural Information Processing Systems.", "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": "", "extra_scores": {}}, {"review_id": "AyqXXAIm04", "reviewer": "Reviewer_69cR", "summary": "This paper considers a new fair allocation problem. In the classical fair allocation problem, each item can only be matched with at most one agent, and the utilities are known prior. This paper considers a variant where each item is required to be matched with some number of agents. Agents can also be matched with some number of items. The utilities are not known prior. The problem is motivated by the paper-reviewer matching system. Each agent represents a reviewer and each item is paper. A paper is required to be assigned more than one reviewer. Each reviewer can be matched to more than one paper. In addition, each reviewer has a capacity that indicates the maximum number of papers assigned to her. The utilities are not known prior because the review quality is only known after the assignment. \n\nThe main contribution of this work is that they designed an efficient method to optimize both the utilitarian and egalitarian objectives.  The main technical tools come from the robust optimization area. In particular, they transform the problem into a pure linear programming problem via a series of propositions.", "questions": "I don't have any specific questions.", "limitations": "The societal impact is not available.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper is well-motivated. I like the model studied in this paper. The reviewer-paper matching algorithm is important. I expect that the proposed algorithmic idea should have the impact of a positive practice.\n\n2. The paper is well-written. I am a theoretical person, I appreciate that the theory part of the paper is carefully organized. The whole proof idea is clear to me.", "weaknesses": "I have to say that I am usually working on approximation algorithms and I am not in the right position to judge the technical novelty of these continuous methods. To me, the downside is that the running time of the proposed algorithm is high, especially since the algorithm is required to solve LP. This limits the application of algorithms.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments!\n\n**To me, the downside is that the running time of the proposed algorithm is high, especially since the algorithm is required to solve LP. This limits the application of algorithms.**\n\n\nWe acknowledge that some of our proposed algorithms have high runtimes. However, we would like to highlight the following points:\n\n1. Optimizing fair welfare objectives under uncertainty is an NP-hard problem [3, 4]. Thus, obtaining exact solutions in polynomial time is not feasible.\n\n2. Previous work in the literature on fair allocations and divisions has proposed methods such as MILPs [1, 2, 4] for solving fair allocation problems without considering uncertainty. Therefore, the runtimes of our solutions are comparable to existing methods.\n\n3. Our iterated quadratic programming approach for robust measures with ellipsoidal uncertainty sets is significantly more efficient than the naive subgradient ascent method previously proposed, as shown in Figure 1.\n\nFinally, we recognize that our CVaR approach is limited by its sample complexity. For large instances of fair allocation problems, we recommend using the normal form of CVaR, which can be optimized using SOCP or Projected Gradient Ascent techniques.\n\n[1] Kawase, Y., Nishimura, K., Sumita, H. (2023). Fair Allocation with Binary Valuations for Mixed Divisible and Indivisible Goods. Arxiv.\n\n[2] Caragiannis, I., Kurokawa, D., Moulin, H., Procaccia, A., Shah, N., Wang, J. (2019). The Unreasonable Fairness of Maximum Nash Welfare. ACM Transactions on Economics and Computation, 7.\n\n[3] Cousins, C., Payan, J., & Zick, Y. (2023). Into the unknown: Assigning reviewers to papers with uncertain affinities. International Symposium on Algorithmic Game Theory, 16.\n\n[4] Peters, D., Procaccia, A.D., & Zhu, D. (2022). Robust Rent Division. Advances in Neural Information Processing Systems, 36.", "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": "", "extra_scores": {}}, {"review_id": "lsY3Fgqt9x", "reviewer": "Reviewer_UQiJ", "summary": "The authors propose group-fair multi-matching algorithms in the presence of uncertainty about the valuations of agent-item pairs. The algorithms fall under two families: Conditional Value at Risk (CVaR), and robust optimization. The types of utilities they consider are also two-fold: normal utilitarian, and egalitarian group-fairness. The latter seeks to maximize the utility of the group with the minimum utility.\n\nThe authors begin with the robust optimization approach for overall utility maximization, where they derive max-min guarantees for the worst possible valuation within a particular valuation uncertainty set. Here, they propose solving a natural nested concave-convex program. Due to computational feasibility, they would like to utilize the structure of the specific problem in order to achieve a more efficient problem framing. To do this, they demonstrate that the nested program (eq 1) can be re-written as a single concave cubic program. Furthermore, the optimal assignment can be found by solving a particular system of equations with the optimal dual variables (Proposition 3.1). They also show that under some simplified assumptions on the uncertainty set containing the true valuation matrix, the optimal solution can be found by simply solving a LP or QP (Prop. 3.2, 3.3).\n\nThe authors then move to robust optimization for egalitarian welfare. Here, the problem is more complex since the objective function loses its smoothness, and is now a nested max min min optimization problem. They make a key assumption on the independence of the uncertainty set w.r.t. the data groups, which helps them swap the minimum over groups and minimum valuation over uncertainty sets. By another dual derivation, one can solve the resulting problem with iterated quadratic programming (Prop. 3.4). Furthermore, the problem has the nice property that under simplified uncertainty sets, it still reduces to solving a single LP (Prop. 3.5). The authors also note that the problem can be decomposed in the case of monotonic welfare functions.\n\nThe next topic covered is w.r.t. the CVaR approach, which assumes that the distribution over agent-item valuations is known to the mechanism designer. We begin with the optimal utilitarian assignment. Here, the optimal solution can be computed, but may be computationally infeasible for arbitrary distribution over valuation matrices $D$. Therefore, the authors adopt and approach where they sample many valuation matrices from the distribution, and solve a particular linear program which computes an empirical estimate of the \\alpha-CVaR. Prior work shows that this is a consistent estimator as the number of samples goes to infinity, but they provide a concrete sample complexity bound for subgaussian distributions (Prop. 4.3), under assumption 4.2. When the distribution is normal, only the mean and covariance matter, and a particular QP can be solved (Prop. 4.4). Similar results are discussed for the group egalitarian assignment, in section 4.2.\n\nThe authors close with a series of experiments on real AAMAS reviewer bid data, where they are able to demonstrate the effectiveness and scalability of their method to a modest sample size. Here, uncertainty is defined by a model fit to predict reviewer bids on unseen examples.", "questions": "Q1. 113 “always the case that the constraints define a finite set such that |A| ∈ N.” Do you include the possibility that |A| = 0?\n\nQ2. 116 “Let u : A × $\\mathcal{V}$ × G → R be an affine function mapping from allocations to utilities for each group.” I don't think $\\mathcal{V}$ was defined before this statement, but am assuming that it refers to the set of all valuation matrices. However, in 131, you define $\\mathcal{V}$ to be the uncertainty set containing the true valuation matrix with high probability. There is probably a cleaner way to get around this without overloading, since it seems the uncertainty set definition is more important for your discussion throughout. Perhaps simply define the utility function to map from an arbitrary collection of valuations to R, instead of the set of all valuations?\n\nQ3. 133 Not sure whether $W({u}(a))$ formally type checks properly, shouldn’t $u$ be a function of $V$ as well as the assignment $a$ (and also groups, as defined above?)\n\nQ4. 134 $D_v$ is a distribution over valuation matrices? This seems to be defined in the next paragraph 136-145. Is it possible to switch the order of these two paragraphs?\n\nQ5. 184 can probably do without the $\\forall G \\in \\mathcal{G}$ in the sentence immediately following $w_G$. Also, I believe that the presentation would be enhanced by considering numbers to be not-bold (e.g. $w_G$, $u_{G_1}$, etc.), and to keep vectors bold (which the authors have already done). This would certainly help parse the notation, since there is quite a bit.\n\nQ6. 224: valuation matrices of each group are independent of each other. What are the practical implications of this assumption? What kind of problems are we not capturing by making this assumption? This should be stated clearly, and perhaps the assumption should be stated more formally.\n\nQ7. Equation (9), should the LHS term have an overset of $\\tilde{v} \\sim D_v$ for the CVaR_\\alpha term? My understanding is that CVaR is w.r.t. a particular distribution $D$, not a particular draw of the random variable. Are you sweeping this into the CVaR term somehow?\n\nQ8. 326:  “Section 5.1”, should this be table 2?\n\nQ9. How is adversarial welfare defined? The worst welfare within the uncertainty set?\n\nQ10. I do not believe that $W_{USW}$ or $W_{GESW}$ appear in the main paper, and hence, you may be able to remove these acronyms from section 2.1. Furthermore, throughout the paper, you seem to not use the acronyms until presenting the experimental results (which makes sense).\n\nQ11. 339: “Although the CVaR approach is less important at low noise levels, the CVaR of welfare decreases for both welfare measures as noise increases”. As someone not super familiar with CVaR, why is it less important at lower noise levels? Do we expect the noise to mainly impact the right tail or something like that?\nQ12. 178-180: rounding algorithms in the case of fractional solutions. Do you think you can expand a bit on how these randomized rounding algorithms apply to your specific experiments? How much of a difference do they make? Is there a Birkhoff-von-Neumann decomposition-type result for randomized-multi-matchings which can be used to sample?", "limitations": "The limitations are discussed in the main body of the paper, the most salient of which is that that CVaR requires solving a large number of linear programs to obtain the desired guarantees, and hence can be slow in practice. I don't see this as that big of a problem, however, especially since in the proposed setting of reviewer assignment, only a single matching is constructed and utilized.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The problem considered by the authors, namely, understanding the role of uncertainty in matching algorithms, is important and well-motivated. Furthermore, their setup is extremely practical and testable. I enjoyed reading about the optimization tricks and problem specific structure used to solve each of the instances. I found the fact that the optimal assignment was given by a particular system of linear equations with the optimal dual variables very neat. \n\nOverall, I do not think that any other work in the literature has explored and proposed feasible algorithms for matching in the presence of uncertainty in such a variety of settings (robust optimization under both utility optimal and egalitarian matchings, similarly for CVaR). I also appreciate that the code for running all programs was included. It can be quite difficult to implement programs of this complexity in practice (which a skim of the implemented gurobi programs can verify). I encourage the authors to consider cleaning up and releasing the code as a package, there is certainly a dearth of available code for efficient matching algorithms online currently!", "weaknesses": "I believe that there are numerous opportunities to improve the quality of presentation in the main paper. If addressed, I plan to raise my score. Most importantly, Propositions 3.4, 3.3, 3.1 should — in my opinion — be stated informally in the main text. I don’t believe the reader will gain much by staring at the (impressive!) equations. Having the informal version retain the key takeaway — we can reduce to solving a system of equations with the optimal dual variables — would make it much easier to parse, and also emphasize the important (and cool) part of the proposition.\n\nIn lines 25-30, you specify where uncertainty may arise from. I would also consider mentioning how you capture this uncertainty: namely, by modeling uncertainty over agent-item pair valuations. These valuations completely capture the “preferences” you discuss later in the paragraph. However, when I think of matchings and preferences, concepts like stability come to mind, which is a much harder constraint to satisfy than utility maximization.\n\nI detail more areas for improving clarity and preciseness of writing in the questions section of my response. Most are minor besides simplifying the main statement of the propositions.\n\nIf accepted, I also recommend utilizing the additional space to discuss the experiments in further detail. In particular, is table 2 reporting normalized utilities? Why are most of the results 1.0? Is this to be expected?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed comments and helpful suggestions.\n\nPlease see our replies below.\n\n**Propositions 3.4, 3.3, 3.1 should be stated informally in the main text.**\n\nThank you for the suggestion. We agree that the equations make it less readable.\nWe will replace them with a informal statements describing the propositions, and move the formal statements to the appendix.\n\n**Mention how you capture this uncertainty.**\n\nThank you for the suggestion. We will incorporate this in the main paper.\n\n**Why are most of the results 1.0? Is this to be expected?**\n\nWe briefly mentioned on line 329 objective values are normalized by dividing by the maximum value of that objective per seed.” Table 2 reports means and standard errors over 5 runs. For each run, we execute 6 algorithms (the 6 rows in the table), and evaluate each of those 6 allocations on all 6 objective values. So we get five 6x6 matrices. For each run, we normalize each column by dividing all entries by the max value, so the maximum value is 1.0. We then take the element-wise means and standard errors of those 6x6 matrices over all 5 runs. We normalize in this manner because (a) the absolute optimal welfare differs across runs, and (b) we wanted to highlight the fact that the diagonal is expected to be (weakly) better than the off-diagonal in each run. \n\n**Do you include the possibility that |A| = 0?**\n\nYes, our proposed techniques can handle this special case. However, we observe that in almost all allocation problems, we would have constraints on the number of items that can/must be assigned to an agent.\n\n**There is probably a cleaner way to get around this without overloading.**\n\nYou’re right, this is overloaded. Thank you! We can just replace that with [0,1]^{n \\times m}.\n\n**Shouldn’t $u$ be a function of as well as the assignment and also groups, as defined above?**\n\nWe would like to clean up this notation a bit in general. It is cleaner to write that $\\bf u$ is a vector-valued function giving the welfare for all groups under an allocation and valuation matrix, $\\mathbf{u}: \\mathcal A \\times [0, 1]^{n \\times m} \\to \\mathbb R^g$. On line 133 we will write $W(\\mathbf u(\\mathbf a, \\mathbf v))$.\n\n\n**Are you sweeping this into the CVaR term somehow?**\n\nYes, that’s right. We were “sweeping this into the CVaR term” as you say, but it would be much clearer if we include the overset. In fact, this is the same distribution over $\\tilde{v}$ as in the $\\mathbf{E}\\_{\\tilde{v} \\sim D_v}$ operator on the RHS, so it should be written on the LHS too. We will do the same for the $\\mathrm{CVaR}_\\alpha$ and $\\mathbb{E}$ expressions in Equation 12.\n\n**How is adversarial welfare defined?**\n\nWe can include a sentence in the preliminaries explaining that once an allocation is fixed, we call the minimum welfare over the uncertainty set the “adversarial” welfare.\n\n**Why is CVaR less important at lower noise levels?**\n\nAt low noise levels, the CVaR measures (and optima) for sufficiently large values of $\\alpha$ will be fairly close to the central estimates (and optima based on them) of welfare. As the noise increases, the variance increases. This results in long-tailed distributions, and thus the CVaR optimizer will produce different solutions from the optimizer of the central estimate. By definition, the robust approach is more sensitive than CVaR, which explains the observed differences between them. For further details on how CVaR provides robustness against high risks in fat-tailed distributions, please refer to Example 2.1 and [1].\n\n[1] R. Tyrrell Rockafellar and Stanislav Uryasev. (2002). Conditional Value-at-Risk for General Loss Distributions. Journal of Banking and Finance.\n\n\n**Can expand a bit on how these randomized rounding algorithms apply to your experiments?**\n\nThank you for bringing up this point. \nYes, indeed there is a generalization of Birkhoff-von-Neumann decomposition to multi-matchings [1]. [2] does a nice job of explaining its application in randomized reviewer assignments specifically. \n\nWe should make this clearer in the paper, but we did not round the robust USW/GESW solutions reported in the experiments. In the case of the uncertainty-unaware USW/GESW and the sampling-based CVaR problem for both USW and GESW (the first 4 rows of all our tables), we were able to express these programs as MILP’s and directly solve for the optimal integer solution. We recommend using this approach whenever it is feasible. Theorem 14 of [3] demonstrates that although the rounded robust solutions may differ significantly from the fractional robust solutions, however, in the case of USW the welfare under the true valuations remains high after rounding. In our experiments, we do not assume access to ground truth valuations, so we cannot directly test this. \n\nRounding often degrades the maximin objective value. In a simple analogy, imagine we have 2 coins. We have to pick one coin to flip, and we want it to be heads. An adversary can force one coin to always be tails. If we select a distribution over the coins, and sample from the distribution before the adversary selects their coin, we can obtain a non-zero probability of getting a heads. But it would be a very powerful adversary (perhaps unreasonably powerful) if they could see which coin we picked and force it to be tails. \nThat being said, using the randomized rounding procedure with our methods results in allocations that are robust against adversaries in expectation.\n\n[1] Budish, E., Che, Y.K., Kojima, F., & Milgrom, P. (2009). Implementing random assignments: A generalization of the birkhoff-von neumann theorem. \n\n[2] Jecmen, S., Zhang, H., Liu, R., Shah, N., Conitzer, V., & Fang, F. (2020). Mitigating manipulation in peer review via randomized reviewer assignments. Advances in Neural Information Processing Systems, 33.\n\n[3] Cousins, C., Payan, J., & Zick, Y. (2023). Into the unknown: Assigning reviewers to papers with uncertain affinities. International Symposium on Algorithmic Game Theory, 16.", "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": "", "extra_scores": {}}]

Author rebuttal:
Thank you to all the reviewers for your detailed and thought-provoking reviews. We have responded to most of your points individually, but a few points were worth addressing globally. 

**Algorithm runtime/scaling**

We acknowledge that some of our proposed algorithms have high runtimes. However, we would like to highlight the following points:

1. Optimizing fair welfare objectives under uncertainty is an NP-hard problem [3, 4]. Thus, obtaining exact solutions in polynomial time is not feasible.

2. Previous work in the literature on fair division has proposed methods such as MILPs [2, 4, 5] for solving fair allocation problems without considering uncertainty. Therefore, the runtimes of our solutions are comparable to existing methods.

3. Our iterated quadratic programming approach for robust measures with ellipsoidal uncertainty sets is significantly more efficient than the naive subgradient ascent method previously proposed, as shown in Figure 1.

Finally, we recognize that our CVaR approach is limited by its sample complexity. For large instances of fair allocation problems, we recommend using the normal form of CVaR, which can be optimized using SOCP or Projected Gradient Ascent techniques.

**Technical challenges in combining fairness and uncertainty**

Satisfying fairness notions under deterministic valuations, and optimizing under uncertainty are both rich problems in their own right; combining the two makes the problem that much more difficult. Optimizing the egalitarian welfare objective without uncertainty is already an NP-hard ILP [1]. Robust optimization of a linear objective with integer decision variables is already NP-hard in general as well [3]. When we combine the two, we have a constrained integer max-min problem that is difficult to solve for general uncertainty sets. We therefore must determine how the approaches common in the robust and stochastic optimization literatures adapt to the new objective, and if any simplified forms admit more efficient solutions. The main contribution of this paper is to identify instances of that problem that can be solved exactly or approximated efficiently. We demonstrate that for ellipsoidal and linear uncertainty sets, as proposed in distributionally robust literature, our problem can be simplified to more manageable forms. These can be efficiently solved using linear programming, iterated quadratic programming, or projected gradient ascent methods, as shown in Table 1.

**Different ways of grouping reviewers**

In the reviewer assignment problem, papers are the agents, and reviewers are the items. Therefore, we group papers rather than reviewers. Many conferences categorize papers based on their field or subfield of research. Ideally, each group of papers should receive a sufficient number of qualified reviewers, which we ensure via our proposed algorithms.

We have implemented a simulated example where there are 2 groups and 1 group is disadvantaged compared to the other. We took the AAMAS 2015 dataset, set the original papers to be group 1, and created a second group of papers by randomly selecting $k$ of the papers. For these $k$ papers, we divided the copied valuations by a number $d>1$, and set to $0$ all but the top $b$ valuations per paper. The defaults were $k=150, b=5$, and $d=2$; we tried varying each of these keeping the other two fixed. For each setting we compute the % of relative loss in GESW incurred by the max USW solution, or $\frac{f-g}{f}$, where $f$ is the GESW of the max GESW solution and $g$ is the GESW of the max USW solution. We show in our rebuttal PDF that under this setting, optimizing for USW instead of GESW results in sharp decreases in GESW, and the difference gets sharper as $k$, $b$, or $d$ increase.

**Assumption: Groups have independent uncertainty sets**

This assumption is not a fundamental limit, but rather a simplifying assumption for some cases. Our LP solutions for robust allocation with linear uncertainty sets and CVaR allocation (without normality assumption) for both utilitarian and egalitarian welfare can be trivially extended to the case where agents are in multiple groups. The subgradient ascent approach still works for the robust GESW allocation when groups are not independent. Because the minimizer will concentrate the uncertainty on a single group for GESW anyway, when we compute the minimizer at each step of subgradient ascent, we can just compute the minimizer for each group individually.

We agree the assumption can be limiting, but not unreasonable, in practical scenarios. Conferences often group papers into disjoint tracks and/or require paper authors to submit a unique primary subject area. Although they may have multiple secondary subject areas, the top-level grouping remains independent.

[1] Garg, N., Kavitha, T., Kumar, A. Mehlhorn, K., & Mestre, J. (2010). Assigning papers to referees. Algorithmica, 58.

[2] Caragiannis, I., Kurokawa, D., Moulin, H., Procaccia, A., Shah, N., Wang, J. (2019). The Unreasonable Fairness of Maximum Nash Welfare. ACM Transactions on Economics and Computation, 7.

[3] Cousins, C., Payan, J., & Zick, Y. (2023). Into the unknown: Assigning reviewers to papers with uncertain affinities. International Symposium on Algorithmic Game Theory, 16.

[4] Peters, D., Procaccia, A.D., & Zhu, D. (2022). Robust Rent Division. Advances in Neural Information Processing Systems, 36.

[5] Kawase, Y., Nishimura, K., Sumita, H. (2023). Fair Allocation with Binary Valuations for Mixed Divisible and Indivisible Goods. Arxiv.

Meta-review: The reviews for this paper are largely positive, and I believe the paper should be accepted. There is one negative review, that seems to be sufficiently addressed by the authors; further, one of the reviewers has also highlighted in the discussion that some of the weaknesses pointed out by Reviewer hqEo may be relatively minor.
Decision: Accept (poster)