Fair and Welfare-Efficient Constrained Multi-Matchings under Uncertainty

Authors: elita  lobo
justin  payan
cyrus  cousins
yair  zick
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 00:27:18

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.

Main paper: 
 introduction: 
 Constrained resource allocation without money underpins many important systems, including reviewer 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] . In these settings we assign resources to agents. Agents and resources are constrained; each agent has bounds on the minimum or maximum number of items they receive from different categories, and each item has required minimums and limited total capacity. Each agent has a valuation for every item, and we optimize a 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 reviewers, reviewers have upper limits on the number of papers they can review, and conflicts of interest prevent some reviewers from being assigned to certain papers.A crucial factor in all of the above settings is the presence of uncertainty. Uncertainty often stems from the fact that agents' valuations for resources depend on future outcomes. In reviewer assignment, a reviewer-paper pair's match quality is observed only after the reviewer submits his or her review. Uncertainty may also stem from our limited ability to collect data; for example, in deciding where to target lead pipe mitigation projects based on number of school-aged children per neighborhood, we may have access to imperfect school enrollment records, allowing only an 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 we have access to a probability distribution over preferences, we optimize the conditional expectation of the distribution at percentiles of interest [33, 50] . 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-aware optimization approaches can often result in significantly different allocations from the default of optimizing for welfare over a 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 to 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, 11, 32, 33] , to our knowledge it has not addressed the intersection of fairness and uncertainty in the constrained multi-matching problem.We study the broad problem of fair and efficient constrained multi-matchings under uncertainty about agents' valuations. We optimize for welfare while simultaneously accounting for the uncertainty inherent in real-world resource allocation problems. Specifically, we develop methods to efficiently 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 containing 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 valuations. 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 welfare functions and arbitrary convex uncertainty sets, we apply the relatively expensive adversarial projected subgradient ascent algorithm of Cousins et 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, then solve the resulting linear program or LP (as in Propositions 4.1 and H.3). However, in the case of utilitarian welfare and Gaussian-distributed valuations we present a simple reformulation of the CVaR objective (Proposition 4.3). Optimizing CVaR for general monotonic, concave welfare functions can require solving arbitrary concave optimization problems, even after sampling.We also compare these optimization approaches empirically in Section 5 on reviewer assignment data from AAMAS 2015, 2016, and 2021.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 constrained resource allocation [3, 10, 11, 32] . This work does not explicitly consider multi-matching problems like those considered here, nor does it address the robust egalitarian welfare problem. Pujol et al. [48] study fair division problems with parameters noised for differential privacy, showing that the noise can cause unfair allocations; they propose a Monte Carlo approach to mitigate the unfairness 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 the items to minimize envy. We study a setting without money, both utilitarian and egalitarian objectives, and robust optimization in addition to stochastic optimization.Cousins et al. [16] study robust optimization under the utilitarian objective. They propose an adversarial projected subgradient ascent method which requires solving a 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 5 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 or item availability are uncertain but preferences are known [2, 14, 21, 27] . In our case demand and availability are known but preferences are not. Devic et al. [20] consider fair two-sided matching where the fairness constraint is defined with respect to unknown parameters; we assume knowledge of the parameters that define the fairness constraint (i.e., group identities). 
fair resource allocation under uncertainty: 
 We first introduce the problem of resource allocation without uncertainty, then lay out the two approaches we take to deal with the introduction of uncertainty. Our results are summarized in Table 1 .We have a set of n agents N = {a 1 , . . . a n }, and m item types I = {i 1 , . . . i m }. Agents are partitioned into g groups G = {G 1 , . . . G g }, with each G ⊆ N and each agent i belonging to exactly one group.For any n × m matrix X we use the same lower-case bold letter, i.e., x to denote the vector representing the vectorized form of the matrix X, in row-major order. For any group of agents G, we use x G ∈ R |G|m to denote the vector restricted to the agents in G. Given vectors x, y ⊆ R nm and real number c ∈ R, let x ⪰ c denote that x j ≥ c for all j, and let x ⪰ y denote that xy ⪰ 0. The ⪯ operator is defined analogously.We assume a valuation matrix V * ∈ R n×m 0+ , where V * a,i encodes the true value of assigning item type i to agent a. The values of V * are typically unknown; we discuss our approaches to handle this problem in Section 2.2. We use tildes to denote random variables, for example, x ∼ D x denotes that x is drawn from distribution D x.Given some set of feasible assignments A ⊆ N n×m , we aim to find assignments A ∈ A where A a,i indicates the number of items of type i allocated to agent a. For each agent a ∈ N , we have upper and lower bounds on assignments of the form κ a ≤ i∈I A a,i ≤ κa . For each item i, we have lower and upper bounds on the total assignment of that item; ψ i ≤ a∈N A a,i ≤ ψi . Finally, we have pairwise limits C a,i for each agent a and item type i, requiring that A a,i ≤ C a,i . It is always the case that the constraints define a finite set such that|A| ∈ 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 × R n×m 0+ → R g be an affine function mapping from allocations to utilities for each group. u G (a, v) denotes the utility of the group G under allocation a ∈ A (recall a is the vectorized version of the assignment A). We write u instead of u(a, v) when a and v are clear from context.We assume that u is additive and normalized by group size, sou G = a ⊺ G v G |G| .We define a welfare function W : R g → 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 ∈ R g 0+ denotes the weights on groups in G. When w G = |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 min G∈G u G . 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 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 -α for some confidence parameter α ∈ [0, 1). We then optimize the welfare corresponding to the worst valuation matrix in the uncertainty set, i.e., max a∈A min v∈V W(u(a, v)). This approach applies when we do not have access to a full distribution over valuations but have some other way of describing V [16] .When we have access to a full distribution over the random variable ṽ ∈ R nm , we apply a stochastic approach instead. We compute the welfare distribution and optimize the conditional expectation over an α-percentile of the welfare or Conditional Value at Risk at α (CVaR α ). Suppose we have a random variable x ∼ D x. For any risk level α ∈ (0, 0.5), CVaR α [x] is defined asE x∼Dx [x | x ≤ ν α ]where ν α denotes the α-percentile of x. This approach is only appropriate when D x is fully known, or when we can sample from it. We investigate this regime in Section 4, where we will compute and optimize CVaR α [W(u(a, ṽ))] for a random variable ṽ ∼ D ṽ. 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) or dislikes it (utility 0). Agent preferences are Bernoulli random variables, where Pr[ṽ 1,1 = 1] = 0.8, Pr[ṽ 1,2 = 1] = 0.9, Pr[ṽ 2,1 = 1] = 0.5, and Pr[ṽ 2,2 = 1] = 0.8. If we maximize the expected USW, we would assign i 1 to a 1 and i 2 to a 2 , for a total expected USW of 1.6. However, consider instead the CVaR 0.3 of USW. When we make the expectation-maximizing assignment, then Pr[W(u) = 0] = 0.04 and Pr[W(u) = 1] = 0.32. However, if we assign i 2 to agent a 1 and item i 1 to agent a 2 , we have that Pr[W(u) = 0] = 0.05 and Pr[W(u) = 1] = 0.5. This means that the conditional expectation of welfare at the 30 th percentile is higher if we assign i 2 to a 1 and i 1 to a 2 (it is .32 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.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 no 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 a 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 authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a 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 approach. For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it 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 address 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 important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
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 a 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 expensive or intractable, as demonstrated empirically in Section 5. 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.The robust approach detailed in Section 2 assumes the availability of an uncertainty set of the valuation matrix. For the sake of computational tractability, we focus on the class of uncertainty sets defined by linear and ellipsoidal constraintsV = v ∈ R nm | ∀i ∈ [1, ℓ], (v -vi )S -1 i (v -vi ) ≤ r 2 i , Qv ⪰ e, v ⪰ 0 ,where the i th ellipsoidal uncertainty set has center vi ∈ R nm 0+ , covariance matrix S i ∈ R nm×nm , with radius r i ∈ R, Q ∈ R k×nm , and e ∈ R k .We will further assume that the covariance matrices corresponding to the ellipsoidal uncertainty sets are positive semi-definite. 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 not feasible or computationally tractable, we relax the set of feasible integer assignments A ⊆ N n×m to a set of feasible continuous allocations A ⊆ R n×m 0+ . One can obtain integer allocations satisfying all constraints by applying a randomized rounding technique that generalizes the Birkhoff-von Neumann decomposition [13] . The fractional solutions can thus be interpreted as randomized allocations.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 asEQUATIONThe objective and constraints of the inner-minimization 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 inner-minimization problem, we can simplify the problem in (1) into a single equivalent maximization problem. We provide the dual formation in Proposition 3.1.To simplify notation in the results that follow, we assume, without loss of generality, that each group G has weight w G = |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 β ∈ R k 0+ be the dual variable corresponding to the linear constraints Qv ⪰ e, λ ∈ R ℓ 0+ be the dual variable associated with the ellipsoidal constraints, and ξ ∈ R nm be the variable that combines the primal variable a with the dual variable of the non-negativity constraint on v for variable elimination. We define a set of feasible ξ asEQUATIONwhich is Pareto-dominated by A. Proposition 3.1 (Robust Utilitarian Welfare Dual). The problem in (1) is equivalent to solvingEQUATIONwherep = ξ -Q ⊺ β, q = ℓ i=1 λ i S -1 i vi , and T = ℓ i=1 λ i S -1 i -1. Let ξ * be the optimal ξ in (3). Then the optimal allocation a * can be derived from ξ * by finding a ∈ A such that∀G ∈ G : a G ⪯ ξ * G .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 allocation a * from ξ * by solving a system of equations. Notably, the problem in Equation ( 3) is a single maximization problem with fewer variables and constraints as compared to the maxmin problem in (1) , making it simpler to solve. We can either solve it using off-the-shelf convex optimization tools, or by applying a projected subgradient ascent approach (without the previously required adversary).When the valuation uncertainty set is polyhedral, the problem in (3) simplifies further into a linear program (LP) which can be solved efficiently using standard LP solvers like Gurobi [28] . 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 nm | Qv ⪰ e, v ⪰ 0}, the optimal allocation a * for the problem in (1) can be computed by solving the linear programmax a∈A,β∈R k 0+ β ⊺ e s.t. ∀G ∈ G : Q ⊺ G βG ⪯ aG .When the valuation uncertainty set has a single ellipsoidal constraint with a non-negativity constraint, 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.,EQUATION)The exact optimal solution (λ * , ξ * ) to Equation (4) can be computed by alternately performing two steps until convergence: first, fixing ξ and optimizing λ, i.e., λ = ξ ⊺ Sξ /2r, and second, fixing λ and solving a concave quadratic program to optimize ξ. The optimal allocation a * can be computed from ξ * as in Proposition 3.1.We now consider the problem of maximizing egalitarian welfare under the robust approach. We can represent this problem as maxEQUATIONThis problem presents inherent challenges due to the non-smoothness of the inner-minimization 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 or efficiently solve the problem using the quadratic program technique described in Corollary 3.3, though the generic adversarial 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 ∈ G are independent of each other.To simplify notation, we assume, without loss of generality, that the valuations v and the parameters of the valuation uncertainty set V are scaled to incorporate the factor 1 |G| in the representation of the utility of each group G in the corresponding group valuation v G .Assumption 3.4 (Independence of Groups). The uncertainty set V is a Cartesian product of indi- vidual groups' uncertainty sets, V . = G∈G V G .This assumption is not unreasonable in practical scenarios. For example, conferences often group papers into disjoint tracks or require paper authors to select a single primary subject area. Although papers may have multiple secondary subject areas, the top-level grouping remains independent. Assumption 3.4 allows us to reorder the two minimization problems without compromising generality:EQUATIONWe take the dual of the inner minimization problem, 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 solvingEQUATIONwhere for each groupG ∈ G, p G = ξ G -Q ⊺ G β G , q G = ℓ i=1 λ G,i S -1 G,i vG,i , T = ℓ i=1 , λ G,i S -1 G,i -1, and Λ is defined as in Equation (2). The optimal allocation a * can be computed from ξ * as in Proposition 3.1.The dual variables λ G , β G , ζ 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 λ, β and ξ. We can solve it using an off-the-shelf convex programming library or by applying projected subgradient ascent.Under polyhedral uncertainty sets, Equation ( 7) simplifies to a linear program. This is akin to what we observe in the robust utilitarian case (Corollary 3.2). Corollary 3.6 (Group Egalitarian Welfare with Polyhedral Uncertainty). In the case where the uncertainty set V is defined only by linear constraints, i.e., V = {v ∈ R nm | Qv ⪰ e, v ⪰ 0}, the max-min-min problem in (5) transforms into a linear program.When the valuation uncertainty set 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 (β, ξ) until convergence. Corollary 3.7 (Group Egalitarian Welfare with Ellipsoidal Uncertainty). Suppose that the set V in (5) is defined by a single truncated ellipsoidal constraint per group i.e.,V = {v ∈ R nm | ∀G ∈ G : (v G -vG )S -1 G (v G -vG ) ≤ r 2 G , v ⪰ 0}. Then the problem in (5) is equivalent to solving max λ∈R g 0+ ξ∈Λ min G∈G ξ ⊺ G vG - ξ ⊺ G SGξG 4λG -λGr 2 G .The exact optimal solution (λ * , ξ * ) to Equation (4) can be computed by alternately performing two steps until convergence: first, fixing ξ and optimizing λ, i.e., ∀G ∈ G, λ G = ξ ⊺ G S G ξ G /2r G , and second, fixing λ and solving a concave quadratic program to optimize ξ. The optimal allocation a * can be computed from ξ * as in Proposition 3.1.We now extend our findings to a 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 we independently determine the worst valuation in the uncertainty set of 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 maxEQUATIONwhere the welfare function W M is monotonic in the utility of groups. If Assumption 3.4 holds, then (8) simplifies tomax a∈A W M min v G 1 ∈V G 1 u G1 (a G1 , v G1 ), min v G 2 ∈V G 2 u G2 (a G2 , v G2 ), . . . , min v Gg ∈V Gg u Gg (a Gg , v Gg ) .Proposition 3.8 helps us derive simplified versions of Equation ( 8), when Assumption 3.4 holds.The egalitarian problem in ( 5) is an instance of the class of optimization problem described in (8), hence Proposition 3.8 holds under Assumption 3.4 and allows us to derive a 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 algorithms [18, 25, 55] , or adversarial projected gradient ascent [16] . These approaches do not depend on Assumption 3.4, though the optimization may be simplified if independence does hold.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material? Answer: [Yes] Justification: Link provided to code repository on Github in Section 5, link and recommended 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 (https://nips.cc/public/ guides/CodeSubmissionPolicy) for more details. • While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
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 D ṽ. We demonstrate that when the distribution follows a Gaussian distribution, the CVaR of the utilitarian welfare has a simple representation that can be optimized without sample approximation using a projected gradient ascent method. In all other cases, we can approximately optimize CVaR using a sampling-based approach. In particular, when we have monotone, concave welfare functions, we can always approximate the CVaR objective using sampling. However, unlike in Propositions 4.1 and H.3, where the approximated problem becomes linear, with arbitrary monotone, concave welfare functions the problem may require general concave optimization.We wish to find an allocation that maximizes the CVaR α of the weighted utilitarian welfare. Let ṽ represent the random valuation vector. For confidence level α, we formulate the problem asEQUATIONwhere (x) + = max(x, 0) represents the positive part of x [50] . Computing the exact expectation in this problem may not be feasible for every distribution D ṽ. Therefore, we adopt a sampling-based approach. We begin by drawing h i.i.d. samples of the valuation matrix from D ṽ represented as v 1 , v 2 , v 3 , . . . , v h . 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 h i.i.d samples of ṽ, i.e., v 1 , v 2 , v 3 , . . . , v hfrom D ṽ, the optimal allocation for the problem in (9) can be approximately computed by solvingEQUATIONThe CVaR estimator used in ( 10) is a strongly consistent estimator [29] . Therefore, the approximation error of the objective in (10) goes to 0 as h → ∞. In Proposition 4.2, we bound the sample complexity of the problem in (10) when the valuation matrix is sub-Gaussian distributed.For any allocation a, let ĉh,α (a) represent the empirical estimate of CVaR α [w • u(a, ṽ)] computed from h samples and c h,α (a) represent the corresponding true value. We will use |A| to denote the number of feasible allocations and f a : R → R 0+ to denote the density function of the random welfare W(a, ṽ). ν α denotes the α percentile of W(a, ṽ). Proposition 4.2 (Sample Complexity of Approximate CVaR of USW). Suppose that ṽ is a multivariate sub-Gaussian random variable with mean v ∈ R nm and covariance proxy S ∈ R nm×nm , i.e., for all vectors z ∈ R nm : E v∼Dṽ exp((v -v) ⊺ z)) ≤ exp( z ⊺ Sz /2), and that, for any risk level α ∈ (0, 1 2 ) and allocation a ∈ A, there exists probability density threshold η > 0 and radiusγ > 0, s.t., f a (x) > η , ∀x ∈ [ν α -γ, ν α + γ]. Set ∀G ∈ G : a ′ G = w G •a G |G| .Then, for any confidence parameter δ ∈ (0, 1) and error tolerance ε > 0, Pr supa∈A |ĉ h,α (a) -c α (a)| ≤ ε ≥ 1 -δ for h >      8 max max a∈A a ′ ⊺ Sa ′ , 8 ln 6|A| δ min(ε 2 , 16γ 2 )α 2 min(η 2 , 1)      .Proposition 4.2 follows directly from Theorem 3.1 of L.A. et al. [35] . When ṽ is Gaussian distributed, we can circumvent the sampling approach and instead solve an optimization problem (Proposition 4.3), which depends solely on the mean and covariance of ṽ. Proposition 4.3 (CVaR of USW for Gaussian Distributions). If ṽ is distributed as a multivariate Gaussian, i.e., ṽ ∼ N (v, S), then, the optimization problem in (9) simplifies toEQUATIONwhere ϕ and Φ denote the probability density function and cumulative density function, respectively, of the standard normal distribution N (0, 1). The problem in (11) is concave and can be solved without sample approximation using the projected gradient ascent method.For our final objective, we wish to optimize egalitarian welfare under uncertainty using the CVaR approach. We formulate this optimization problem asEQUATION)To optimize the problem described in the above equation, we solve a linear program similar to the one used for optimizing the CVaR utilitarian objective in (9) . See Proposition H.3 for more details. 
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] .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 .5, and no is 0.01. Under the binarized model, we fit a 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 4 roughly balanced clusters of reviewers and papers for each dataset using the procedure outlined in Appendix F. We define our valid set of assignments A as follows. For each paper a ∈ N , we set κ a = κa = 3 for all a in AAMAS 2015, and κ a = κa = 2 for all a in AAMAS 2016 and 2021. For each reviewer i, we set ψ i = 0 and ψi = 15 for 2015 and 2016 and 4 for 2021. We optimize and evaluate CVaR 0.01 ; we take 4, 000 samples from the distribution to optimize for CVaR using the sampling-based approach, and we take 10, 000 samples to estimate the CVaR for evaluation. We optimize and evaluate the robust welfare at the α = 0.3 level (there is a 70% chance the true values lie in the uncertainty set). We constrain the naïve and CVaR approaches to select integer allocations, while the robust approach selects fractional allocations without rounding.All results are averaged over 5 runs of subsampling 20% of each dataset. For each run, we construct 6 allocations, maximizing the naïve central estimate, CVaR and robust statistics 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 a given objective always returns the highest value on that objective, and because the absolute optimal values differ across runs.All code is available at https://github.com/justinpayan/RAU2. Overall Performance Table 2 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 which optimizes for the objective shown in the left-most column. All non-robust methods have 0 robust welfare, indicating that if robustness to adversarial noise is desired, it is very important to consider this objective explicitly. Relatively little noise is actually present in this dataset, as the CVaR 0.01 is quite high for both the naïve USW-optimal and GESW-optimal in all cases.Since the USW-optimal solution has very high GESW, we implement a simulated example to explore when the USW-optimal solution fails to have high GESW. We find that in a number of settings, the GESW of the USW-optimal solution is much lower than the GESW-optimal solution. Appendix I explains the details of the simulation setting and the results. Robustness under Increasing Uncertainty Figure 1 shows the CVaR 0.01 on the Gaussian version of all three datasets as we artificially increase the amount of noise. We multiply the standard deviations of the Gaussian distributions by a scalar and optimize for the CVaR or the naïvely-computed USW and GESW. We then plot CVaR 0.01 as 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 a sharper decline than USW. We see that as the noise increases, the CVaR 0.01 of the baseline USW and GESW maximizing allocations drops off relative to the same value for the CVaR-optimized allocation.We also verify that when we model valuations using a negatively-skewed Gaussian distribution with the same means and variances, we see increasing importance of optimizing for CVaR relative to uncertainty-unaware USW and robust USW. The difference is sharper as the skew parameter gets more negative. Details of this experiment and its results are included in Appendix J.Runtime For the robust optimization setting with ellipsoidal uncertainty sets (derived from confidence intervals over the Gaussian process matrix factorization), we compare the Iterated QP approach (Corollary 3.3) to adversarial projected subgradient ascent on the original max-min problem (as in [16] ). We find that Iterated QP converges much faster than the adversarial projected subgradient ascent algorithm on both AAMAS 2015 (Figure 1 ) and 2016 (Figure 3 ). Adversarial projected subgradient ascent fails to converge in 1, 000 iterations for the robust GESW objective on all datasets and the USW objective on AAMAS 2021. 
conclusion: 
 In conclusion, we explore the stochastic and robust optimization regimes for utilitarian and group egalitarian welfare objectives. The 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 an 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 on 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.Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results? 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 a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. 
experiment statistical significance: 
 Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments? Answer: [Yes] , Justification: All results in the tables Section 5 and Appendix G 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, confidence intervals, or statistical significance tests, at 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).• Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a 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 is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation 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). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?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 a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to 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 a best faith effort.12. Licenses for existing assets Question: 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?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 a 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. 
 
 Appendix: Gorissen et al. [26] provide an excellent overview of optimization under uncertainty, including techniques 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 et 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] .We believe this work has the potential for a significant positive societal impact. Fair resource allocation algorithms are 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. In this work, we develop methods 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.The CVaR approach requires solving linear programs with a large number of samples to be effective, which makes them computationally expensive. One potential solution is to 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] .In this section we demonstrate a simple and natural approach to construct an uncertainty set using a logistic regression estimator. Logistic regression models with bounded cross-entropy 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 a multivariate Gaussian, results in truncated ellipsoidal uncertainty sets. We construct uncertainty sets per group in all cases.Assume we have a discrete set of c values L ⊆ R, with L = {ℓ 1 , . . . ℓ c }. For each agent i and item type j we denote the true distribution over values p * (ℓ|(i, j)) and the distribution predicted by the logistic regression model is p(ℓ|(i, j)).We estimate the cross-entropy loss of the model on a test set T , where |T | = t. This test set can be segmented by the group identity of the agent, such that we have T G1 , T G2 , . . . T Gg for each of the g groups (with sizes t G1 , . . . t Gg ). We assume that the test set comes from the same distribution as 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 so here.For an agent a and item type i, the cross-entropy loss of the distribution p with respect to the distribution p is defined asH(p(ℓ|(a, i)), p(ℓ|(a, i))) .= -ℓ∈L p(ℓ|(a, i)) ln p(ℓ|(a, i)). For each T G , we compute the mean of the cross-entropy loss ξG = 1 t G (a,i)∈T G H(p(ℓ|(a, i)), p(ℓ|(a, i))), as well as the standard errorof the mean ηG = 1 t G (i,j)∈T G (H(p(ℓ|(a, i)), p(ℓ|(a, i))) -ξG ) 2 1 2. We model the distribution over cross-entropy losses for group G as N ( ξG , ηG ). We want an uncertainty set V such that the true values lie outside V with probability at most α. Thus, using a union bound, we require each uncertainty set V G for individual groups to contain the true valuations with probability at least 1α g . We can thus give the bound that the cross entropy loss is at most Φ -1 (1 -α g , ξG , ηG ), where Φ -1 (p, µ, σ) denotes the p percentile of a Gaussian distribution with mean µ and standard deviation σ.In our assignment problem, for each group G with agents N G we obtain the uncertainty set1 t G m a∈N G ,i∈I H(p(ℓ|(a, i)), p(ℓ|(a, i))) ≤ Φ -1 (1 - α g , ξG , η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.Both models define probability distributions over outcomes, which we use to compute and evaluate the CVaR of utilitarian and egalitarian welfare. For the logistic model, we build a polyhedral uncertainty set by estimating the cross-entropy loss on a held-out test set, and for the Gaussian process model we simply consider the confidence intervals of the resulting Gaussian distribution.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 a hidden dimension size d, we construct two matrices X ∈ R n×d and Y ∈ R m×d . We set d = 20. Let V * denote the true binarized bid matrix, where we observe entries for the training set pairs (a, i) ∈ T . We predict the probability of an affirmative bid as σ((XY ⊺ ) a,i ) where σ is the logistic sigmoid function. We select X and Y to minimize the loss function(a,i)∈T -V * a,i ln σ((XY ⊺ ) a,i ) -V * a,i ln (XY ⊺ ) a,i .For CVaR, we take samples from the distribution defined by σ(XY ⊺ ), assuming all pairs are independently-distributed. We also construct an uncertainty set as 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, or give a confidence interval for the joint Gaussian with mn -1 degrees of freedom.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 0. We then construct a 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 to transform the nodes into vectors, and cluster the resulting vectors into 4 clusters to obtain 4 groups containing both papers and reviewers. To ensure a 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 to each cluster.For the binarized AAMAS 2016 and 2021 datasets, Tables 3 and 4 show the performance of the baseline USW and GESW maximizing allocations, the CVaR 0.01 USW and GESW maximizing allocations, and the robust USW and GESW maximizing allocations at the α = 0.3 level. Because so 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 5 to 7 show the same results for the Gaussian matrix factorization version of the 3 datasets, with the CVaR 0.01 estimated by sampling from the estimated Gaussian distribution, and the adversarial welfare computed over the truncated ellipsoidal uncertainty set corresponding to the 1 -α confidence interval of the Gaussian. EQUATIONwherep = ξ -Q ⊺ β, q = ℓ i=1 λ i S -1 i vi , and T = ℓ i=1 λ i S -1 i -1. Let ξ * be the optimal ξ in (3). Then the optimal allocation a * can be derived from ξ * by finding a ∈ A such that∀G ∈ G : a G ⪯ ξ * G .Proof. Consider the inner-minimization problemmin v∈R nm G∈G a ⊺ G v G ∀i ∈ [1, l] : (v -vi )S -1 i (v -vi ) ≤ r 2 i Qv ⪰ e v ⪰ 0 .Note that the above optimization problem is 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 in Boyd et al. [12] ), we know that maximizing the dual of a convex optimization problem is equivalent to minimizing the primal problem. We will therefore use the Lagrangian method for computing the dual of the above problem.The Lagrangian for the above problem is given byEQUATIONFrom the first-order optimality conditions, we get∂L(v, λ ∈ R ℓ 0+ , β ∈ R k 0+ , ζ ∈ R nm 0+ ) ∂v = 0 a + ℓ i=1 2λ i S -1 i (v -vi ) -Q ⊺ β -ζ = 0 =⇒ v = ℓ i=1 2λ i S -1 i vi -(a -Q ⊺ β -ζ) ℓ i=1 2λ i S -1 i .Substituting this value of v in (13), we getmax λ∈R ℓ 0+ β∈R nm 0+ ζ∈R nm 0+ - 1 4 a -Q ⊺ β -ζ ⊺ ℓ i=1 λiS -1 i -1 a -Q ⊺ β -ζ + ℓ i=1 λi v⊺ i S -1 i vi - ℓ i=1 λiS -1 i vi ℓ i=1 λiS -1 i -1 ℓ i=1 λiS -1 i vi + (a -Q ⊺ β -ζ) ⊺ ℓ i=1 λiS -1 i -1 ℓ i=1 λiS -1 i vi - ℓ i=1 λir 2 i + β ⊺ e .Finally, we substitute the above dual problem back into the original problem in (1) to getmax a∈A λ∈R ℓ 0+ β∈R nm 0+ ζ∈R nm 0+ - 1 4 a -Q ⊺ β -ζ ⊺ ℓ i=1 λiS -1 i -1 a -Q ⊺ β -ζ + ℓ i=1 λi v⊺ i S -1 i vi - ℓ i=1 λiS -1 i vi ⊺ ℓ i=1 λiS -1 i -1 ℓ i=1 λiS -1 i vi + (a -Q ⊺ β -ζ) ⊺ ℓ i=1 λiS -1 i -1 ℓ i=1 λiS -1 i vi - ℓ i=1 λir 2 i + β ⊺ e .Note that the dual problem is concave in λ, β, 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 ξ = aζ. From affine-composition rule in convex optimization (Section 3.2.2 in [12] ), we knowthat if f (x) x ∈ R n is convex, then f (Ax + b) A ∈ R n×n , b ∈ R n is also convex in x.Thus, the variable change ξ = aζ results in a objective that is concave in ξ, λ, β. The allocation variable a and the dual variable ζ only appear in a linear constraint, which is also concave. Thus, the objective and the constraints are concave in a, β, λ, and ξ, and ζ.EQUATIONwherep = Q ⊺ β + ξ, T = ℓ i=1 λ i S -1 i -1 , q = ℓ i=1 λ i S -1 i vi , and Λ = A -R nm 0+ = {ξ ∈ R nm | ∀a ∈ N : i∈I ξ am+i ≤ κa , ∀i ∈ I : a∈N ξ am+i ≤ ψi , ξ ⪯ 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 in (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 a ξ ′ ∈ Λ such that ξ ′ = a * -ζ * for at least one optimal pair (a * , ζ * ). It is easy to see that if there exists such a ξ ′ ∈ Λ, then, ξ ′ maximizes the objective in (14) . Furthermore, since Λ is defined solely by upper-bound constraints on ξ imposed by A, we can easily verify that it will contain at least one instance of ξ ′ that satisfies ξ ′ = a * -ζ * . Thus, we can break down the problem in ( 14) into two sub-problems. In the first problem, we obtain the optimal value of λ, ξ and β by solvingζ * , β * , ξ * = arg max ζ∈R nm 0+ β∈R k 0+ ξ∈Λ p ⊺ Tq ⊺ + β ⊺ e - 1 4 p ⊺ Tp + ℓ i=1 λi v⊺ i Si vi -λir 2 i -q ⊺ Tq + p ⊺ T -1 q ⊺ - ℓ i=1 λir 2 i + β ⊺ e , where p = -Q ⊺ β + ξ, q = ℓ i=1 λ i S -1 i vi , and T = ℓ i=1 λ i S -1 i -1. Then, we can compute the set of optimal (a, ζ) pairs by solving the system of equations:{(a * , ζ * ) | a ∈ A, G ∈ G : a G -ζ G = ξ * G , ζ ∈ R nm 0+ }.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 ∈ R nm | Qv ⪰ e, v ⪰ 0}, the optimal allocation a * for the problem in (1) can be computed by solving the linear programmax a∈A,β∈R k 0+ β ⊺ e s.t. ∀G ∈ G : Q ⊺ G βG ⪯ aG .Proof. Now consider the inner-minimization problem:min v∈R nm G∈G a ⊺ G v G Qv ⪰ e v ⪰ 0 .We compute the dual of the above problem using the Lagrangian method.L(v, λ ∈ R ℓ 0+ , β ∈ R k 0+ , ζ ∈ R nm 0+ ) = a ⊺ v -β ⊺ (Qv -e) -ζ ⊺ v = (a -Q ⊺ β -ζ) ⊺ v + β ⊺ e L(λ ∈ R ℓ 0+ , β ∈ R k 0+ , ζ ∈ R nm 0+ ) = β ⊺ e (a -Q ⊺ β -ζ) ⪰ 0 -∞ otherwise .Therefore, the dual is given by maxβ∈R k 0+ ,ζ∈R nm 0+ β ⊺ e Q ⊺ β -ζ ⪯ a .Since ζ is non-negative, we can eliminate it to get maxβ∈R k 0+ β ⊺ e Q ⊺ β ⪯ a .By combining the dual with the outer-maximization problem in (1), we obtain the final result.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.,EQUATION)The exact optimal solution (λ * , ξ * ) to Equation (4) can be computed by alternately performing two steps until convergence: first, fixing ξ and optimizing λ, i.e., λ = ξ ⊺ Sξ /2r, and second, fixing λ and solving a concave quadratic program to optimize ξ. The optimal allocation a * can be computed from ξ * as in Proposition 3.1.Proof. Consider the inner-minimization problemmin v∈R nm G∈G a ⊺ G v G (v -v) ⊺ S -1 (v -v) ≤ r 2 v ⪰ 0 .Similar to the approach in Proposition 3.1, we will use the Lagrangian method for computing the dual of the above problem. The Lagrangian for the above problem is given byEQUATION)From the first-order optimality conditions, we get∂L(v, λ ∈ R 0+ , ζ ∈ R nm 0+ ) ∂v = 0 a + 2λS -1 (v -v) -ζ = 0 =⇒ v = 2λS -1 v -(a -ζ) 2λS -1 .Substituting the value of v in the above equation in (15) , we getmax λ∈R ℓ 0+ ζ∈R nm 0+ - 1 4 a -ζ ⊺ S λ (a -ζ) + (a -ζ) ⊺ v -λr 2 .From the theory of convex optimization [12] , we know that the dual of a convex optimization problem is always concave, and therefore, the above optimization problem is concave in λ and ζ. Combining the dual with the outer-maximization problem in (1), we getmax a∈A max λ∈R ℓ 0+ ζ∈R nm 0+ - 1 4 a -ζ ⊺ S λ (a -ζ) + (a -ζ) ⊺ v -λr 2 .To further obtain concavity in allocation a, we follow the same procedure as in Proposition 3.1 and use the change of variables ξ = aζEQUATIONAs a result of the change of variables, the allocation variable a 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 et al. [12] ), the objective remains retains its concavity. Thus, the above optimization problem is concave in a, λ, ζ, and ξ.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ζ = ξ. 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 set of feasible ξ, which we denote by Λ, such that there exists a ξ ′ ∈ Λ such that ξ ′ = a * -ζ * for at least one optimal pair (a * , ζ * ). It is easy to see that if there exists such a ξ ′ ∈ Λ, then, ξ ′ maximizes the objective in (16) . Furthermore, it easy to verify that Λ satisfies this criteria for optimality, i.e., it contains at least one ξ ′ that satisfies ξ ′ = a * -ζ * , for some optimal pair (a * , ζ * ).Thus, we can efficiently solve the problem in (16) in two steps. First, we obtain the optimal value of λ and ξ by solving the problemλ * , ξ * = arg max λ∈R0+,ξ∈Λ ξ ⊺ v - ξ ⊺ Sξ 4λ -λr 2 .As in Proposition 3.1, we can compute the set of optimal (a, ζ) pairs by solving the system of equations:{(a * , ζ * ) | a ∈ A, G ∈ G : a G -ζ G = ξ * G , ζ ∈ R nm 0+ }.H.4 Proof of Proposition 3.5 Proposition 3.5 (Robust Group Egalitarian Dual). The problem in (5) is equivalent to solvingEQUATIONwhere for each groupG ∈ G, p G = ξ G -Q ⊺ G β G , q G = ℓ i=1 λ G,i S -1 G,i vG,i , T = ℓ i=1 , λ G,i S -1 G,i -1, and Λ is defined as in Equation (2). The optimal allocation a * can be computed from ξ * as in Proposition 3.1.Proof. Consider the following optimization problem. maxEQUATIONIt is important to note that the inner-most minimization is a convex optimization problem and the outer-maximization is a 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 counterparts. 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 problems [12] . The resultant optimization problem is given bymax a∈A min G∈G max λ G ∈R ℓ 0+ β G ∈R nm 0+ ζ G ∈R nm 0+ - 1 4    aG -Q ⊺ G βG -ζG ⊺   ℓ i=1 λiS -1 G,i   -1 aG -Q ⊺ G βG -ζG    + ℓ i=1 λG,i v⊺ G,i S -1 G,i vG,i -   ℓ i=1 λG,iS -1 G,i vG,i   ⊺   ℓ i=1 λG,iS -1 G,i   -1   ℓ i=1 λG,iS -1 G,i vG,i   + (aG -Q ⊺ G βG -ζG) ⊺   ℓ i=1 λG,iS -1 G,i   -1   ℓ i=1 λG,iS -1 G,i vG,i   - ℓ i=1 λG,ir 2 G,i + β ⊺ G eG .Notice that the inner-most maximization problem is concave in λ, β, and ζ. We now apply the same procedure as in the proof of Proposition 3.1 to obtain concavity in allocation a. Using the change of variables ∀G ∈ G :ξ G = a G -ζ G , we get max a∈A min G∈G max λ G ∈R l β G ∈R nm ζ G ∈R nm ξ G ∈R nm β ⊺ G eG + p ⊺ G TqG - 1 4 p ⊺ G TpG + ℓ i=1 λG,i v⊺ G,i TvG,i -λG,ir 2 G,i -q ⊺ G TqG s.t. ξG = aG -ζG ,where for anyG ∈ G, p G = Q ⊺ G β G + ξ G , T = ℓ i=1 λ G,i S -1 G,i -1, and q G = ℓ i=1 λ G,i S -1 G,i vG,i . Since the inner maximization for each group is independent of the other groups, we can re-order the inner minimization over groups and the inner-maximization problem. Thus, without loss of generality, we can write the above optimization problem asmax a∈A ζ∈R nm λ∈R g×l 0+ β∈R g×k 0+ ξ∈R nm min G∈G β ⊺ G e G + p ⊺ G Tq G - 1 4 p ⊺ G Tp G + ℓ i=1 λ G,i v⊺ G,i Tv G,i -λ G,i r 2 G,i -q ⊺ G Tq G s.t. ξ G = a G -ζ G .Using the same technique as in Appendix H.1, we can simplify the problem by eliminating the variables a and ζ in the above problem and then derive them from the optimal ξ.Eliminating ζ and a in the above equation, we getλ * , β * , ξ * = arg max ,λ∈R g×l 0+ , β∈R g×k 0+ ξ∈Λ min G∈G β ⊺ G eG + p ⊺ G TqG - 1 4 p ⊺ G TpG + ℓ i=1 λG,i v⊺ G,i TvG,i -λG,ir 2 G,i -q ⊺ G TqG , where for each group G ∈ G, p G = (ξ G -Q ⊺ G β G ), q G = ℓ i=1 λ G,i S -1 G,i vG,i , T = ℓ i=1 , λ G,i S -1 G,i -1 , and Λ = A -R nm 0+ = {ξ ∈ R nm | ∀a ∈ N : i∈I ξ am+i ≤ κa , ∀i ∈ I :a∈N ξ am+i ≤ ψi , ξ ⪯ c}. As in Proposition 3.1, we can determine the set of optimal (a, ζ) pairs by solving the system of equations:{(a * , ζ * ) | a ∈ A, G ∈ G : a G -ζ G = ξ * G , ζ ∈ R nm 0+ }.H.5 Proof of Corollary 3.6Corollary 3.6 (Group Egalitarian Welfare with Polyhedral Uncertainty). In the case where the uncertainty set V is defined only by linear constraints, i.e., V = {v ∈ R nm | Qv ⪰ e, v ⪰ 0}, the max-min-min problem in (5) transforms into a linear program.Proof. Now consider the inner-minimization problem:max a∈A min G∈G min v G ∈R nm 0+ a G ⊺ v G ∀G ∈ G : Q G v G ⪰ e G .We can compute the Lagrangian dual of the inner-most minimization problem for each group independently by following steps outlined in the proof of Corollary 3.2. Note that since these minimization problems are simple linear programs, their corresponding duals are exact equivalents of their primal counterparts (Section 5.1 in Boyd et al. [12] ). By substituting the duals in the above problem, we obtainmax a∈A,β∈R g×k min G∈G β ⊺ G e G Q ⊺ G β G ⪯ a G .Using simple algebraic manipulations, we can further simplify the above optimization problem asmax a∈A,β∈R g×k ,t∈R t ∀G ∈ G : t ≤ β ⊺ G e G ∀G ∈ G : Q ⊺ G β G ⪯ a G .H.6 Proof of Corollary 3.7Corollary 3.7 (Group Egalitarian Welfare with Ellipsoidal Uncertainty). Suppose that the set V in (5) is defined by a single truncated ellipsoidal constraint per group i.e.,V = {v ∈ R nm | ∀G ∈ G : (v G -vG )S -1 G (v G -vG ) ≤ r 2 G , v ⪰ 0}. Then the problem in (5) is equivalent to solving max λ∈R g 0+ ξ∈Λ min G∈G ξ ⊺ G vG - ξ ⊺ G SGξG 4λG -λGr 2 G .The exact optimal solution (λ * , ξ * ) to Equation (4) can be computed by alternately performing two steps until convergence: first, fixing ξ and optimizing λ, i.e., ∀G ∈ G, λ G = ξ ⊺ G S G ξ G /2r G , and second, fixing λ and solving a concave quadratic program to optimize ξ. The optimal allocation a * can be computed from ξ * as in Proposition 3.1.Proof. Consider the following optimization problem.max a∈A min G∈G min v G ∈R |G|m 0+ a ⊺ G v G ∀G ∈ G : (v G -vG )S -1 G (v G -vG ) ≤ r 2 G v G ⪰ 0 .Similar to the general version of the problem in (17) , the inner-most minimization is a convex optimization problem and the outer-maximization is a concave maximization problem. This is again due to the fact that affine functions are either concave or 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, as computed in Corollary 3.3, we obtainmax a∈A min G∈G max λ G ∈R ℓ 0+ ζ G ∈R nm 0+ - 1 4 aG -ζG ⊺ λS aG -ζG + (aG -ζG) ⊺ vG - ℓ i=1 λG,ir 2 G,i .Note that the dual is computed following the approach outlined in the proof of Proposition 3.1.Using the change of variables ∀G ∈ G :ξ G = a G -ζ G , we get max a∈A min G∈G max λ G ∈R ℓ 0+ ζ G ∈R nm 0+ ζ∈R nm 0+ ξ ⊺ G vG - ξ ⊺ G SGξG 4λG -λGr 2 G s.t. ξG = aG -ζG .Since the inner maximization for each group is independent of the other groups, we can re-order the inner minimization over groups and the inner-maximization problem. Thus, without loss of generality, we can write the above optimization problem asmax a∈A ζ∈R nm λ∈R g×l 0+ ξ∈R nm min G∈G ξ ⊺ G vG - ξ ⊺ G S G ξ G 4λ G -λ G r 2 G s.t. ξ G = a G -ζ G .Using the same technique as in Appendix H.1, we can simplify the problem by eliminating the variables a and ζ in the above problem and then derive them from the optimal ξ.Eliminating ζ and a in the above optimization problem, we getλ * , ξ * = arg max λ∈R g×l 0+ ξ∈Λ min G∈G ξ ⊺ G vG - ξ ⊺ G SGξG 4λG -λGr 2 G s.t. ξG = aG -ζG , where Λ = A -R nm 0+ = {ξ ∈ R nm | ∀a ∈ N : i∈I ξ am+i ≤ κa , ∀i ∈ I : a∈N ξ am+i ≤ ψi , ξ ⪯ c}.As in proposition 3.1, we can now determine the set of optimal (a, ζ) pairs by solving the system of equations: {(a * , ζ * ) | a ∈ A, G ∈ G : a G -ζ G = ξ * G , ζ ∈ R nm 0+ }.where the welfare function W M is monotonic in the utility of groups. If Assumption 3.4 holds, then (8) simplifies tomax a∈A W M min v G 1 ∈V G 1 u G1 (a G1 , v G1 ), min v G 2 ∈V G 2 u G2 (a G2 , v G2 ), . . . , min v Gg ∈V Gg u Gg (a Gg , v Gg ) .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 h i.i.d samples of ṽ, i.e., v 1 , v 2 , v 3 , . . . , v h from D ṽ, the optimal allocation for the problem in (9) can be approximately computed by solvingEQUATIONProof. Consider the CVaR of utilitarian welfare optimization problem, given bymax a∈A CVaR α w • u(a, ṽ) . = max a∈A,b∈R b - 1 α E ṽ∼Dṽ b -w • u(a, ṽ) + ,Substituting the expectation with the empirical expectation computed from the h samples of random valuation ṽ, and using a slack variable y ∈ R h 0+ to convert b -w • u(a, ṽ) + term in the expectation to linear constraints, we get Theorem H.2 (Theorem 3.1 in [35] ). Let (x i ) h i=1 be a sequence of i.i.d random variables. Suppose that xi , i = 1, . . . , n are σ-sub-Gaussian and Assumption H.1 holds. If c α and ĉh,α represent the true CVaR and the empirical CVaR of random variable x estimated from h samples at confidence level α respectively, then for any ε > 0, we havemax aA max y∈R h ,b∈R   b - 1 α h j=1 y j   ∀j ∈ [1, h] : y j ≥ 0 ∀j ∈ [1, h] : j ≥ 1 h   b - G∈G w G |G| • a ⊺ G v j G   a ∈ A .Pr |ĉ h,α -c α | > ε ≤ 6 exp-hα 2 min(ε 2 , 16γ 2 ) min(η 2 , 1) 8 max(8, σ 2 ) .H.9 Proof of Proposition 4.2 Proposition 4.2 (Sample Complexity of Approximate CVaR of USW). Suppose that ṽ is a multivariate sub-Gaussian random variable with mean v ∈ R nm and covariance proxy S ∈ R nm×nm , i.e., for all vectors z ∈ R nm : E v∼Dṽ exp((v -v) ⊺ z)) ≤ exp( z ⊺ Sz /2), and that, for any risk level α ∈ (0, 1 2 ) and allocation a ∈ A, there exists probability density threshold η > 0 and radius γ > 0,s.t., f a (x) > η , ∀x ∈ [ν α -γ, ν α + γ]. Set ∀G ∈ G : a ′ G = w G •a G |G| .Then, for any confidence parameter δ ∈ (0, 1) and error tolerance ε > 0, Pr supa∈A |ĉ h,α (a) -c α (a)| ≤ ε ≥ 1 -δ for h >      8 max max a∈A a ′ ⊺ Sa ′ , 8 ln 6|A| δ min(ε 2 , 16γ 2 )α 2 min(η 2 , 1)      .Proof. From the assumption, we know that the valuation vector v is a sub-Gaussian that satisfies the following condition∀z ∈ R nm : E exp((v -v) ⊺ z)) ≤ exp( z ⊺ Sz /2) .Using the above properties of sub-Gaussian, we can establish that the utilitarian welfare for a given allocation a is also a sub-Gaussian with variance-proxy= G∈G a ′ G ⊺ Sa ′ G where ∀G ∈ G : a ′ G = w G •a|G| . For any allocation a, let ĉh,α (a) represent the empirical estimate of CVaR of utilitarian welfare and c h,α (a) represent the corresponding true value.Then, using Theorem H.2, we can bound the error of approximating the CVaR of the utilitarian welfare for allocation a asPr |ĉ h,α (a) -c α (a)| > ε ≤ 6 exp -hα 2 min(ε 2 , 16γ 2 ) min(η 2 , 1) 8 max(8, G∈G a ′ G ⊺ Sa ′ G ).The approximation error for all allocations can be upper-bounded asEQUATION)To obtain confidence guarantee Pr[∀a ∈ A : |ĉ h,α (a) -c α (a)| ≤ ε] ≥ 1 -δ, we set the R.H.S of (18) to be less than δ, i.e.,|A|6 exp -hα 2 min(ε 2 , 4γ 2 ) min(η 2 , 1) 8 max(8, G∈G a ′ G ⊺ Sa ′ G < δ .Solving for h, we geth >         8 max(max a∈A G∈G a ′ G ⊺ Sa ′ G , 8) ln 6|A| δ min(ε 2 , 4γ 2 )α 2 min(η 2 , 1)         .H.10 Proof of Proposition 4.3 Proposition 4.3 (CVaR of USW for Gaussian Distributions). If ṽ is distributed as a multivariate Gaussian, i.e., ṽ ∼ N (v, S), then, the optimization problem in (9) simplifies toEQUATIONProof. The proof simply follows from the fact that for any Gaussian distributed random variablex ∼ N (µ, σ 2 ) with mean µ ∈ R and standard deviation σ ∈ R 0+ , CVaR[x] = µ -ϕ(Φ -1 (α)) α σ.The mean of the utilitarian welfare under the assumption that v is Gaussian-distributed is given by a ′ ⊺ v and variance is given by a ′ ⊺ Sa ′ , where for any G ∈ G, a ′ G = w G •a |G| . Substituting these values in the previously mentioned expression of CVaR of a Gaussian random variable, we obtain the results stated above.Proposition H.3 (Approximate CVaR of GESW). Given h samples of ṽ, i.e., v 1 , v 2 , v 3 , . . . v h sampled from D ṽ, the optimal allocation for the problem in (12) can be approximately computed by solvingEQUATIONProof. Consider the CVaR of egalitarian welfare optimization problem, given bymax a∈A CVaR α min G∈G 1 |G| • a ⊺ G ṽG . = max b∈R,a∈A    b - 1 α E ṽ∼Dṽ b -min G∈G 1 |G| • a ⊺ G ṽG +    .Substituting the expectation in the above problem with the empirical expectation computed from the h samples of the valuation matrices, we get≈ max b∈R,a∈A    b - 1 αh h i=1 b -min G∈G 1 |G| • a ⊺ G v i G +    .Introducing slack variables y ∈ R h , we can write the above problem asEQUATIONWithout loss of generality, we can represent the above problem asmax a∈A max y∈R h ,b∈R   b - 1 α h j=1 y j   ∀j ∈ [1, h] : y j ≥ 0 ∀j ∈ [1, h] : ∀G ∈ G : y j ≥ 1 h b - 1 |G| • a ⊺ G v j G .We run an experiment to discover scenarios where the USW-optimal solution has very sub-optimal GESW. Using the AAMAS 2015 dataset, we set all of the papers to be group 1, and we create a second, synthetic group of papers by copying and modifying a random subset of the papers. For these papers, we divide the copied valuations by some number, and set to zero all but the top valuations per paper. For each setting we compute the percentage of relative loss in GESW incurred by the maximum USW solution. Figure 4 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, 5 for the number of nonzero entries, and 150 for the size of the minority group (corresponds to a ratio of roughly 20%). Taken together, the results suggest that if one group of papers has overall lower bids than another group, this has a very strong negative effect on the GESW of the USW-optimal solution.We use the AAMAS 2015 dataset and sample each valuation independently from a skewed-Gaussian distribution with varying skew parameter. We use the means and variances estimated by the Gaussian Process matrix factorization model described in Appendix E. The univariate skewed-Gaussian distribution with mean µ, variance σ 2 , and skew α is defined by the probability density functionp(x; α) = 2ϕ(x -µ)Φ(α(x -µ)/σ),where ϕ and Φ are the probability density function and cumulative density function of a standard Gaussian distribution [6] . 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 in 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 or 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. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 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?).

W2. 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?

W3. 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.

W4. 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.

W5. 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.
questions: questions: W1, W2, W3
limitations: limitations: W1, W3, W4, W5
paper_summary: paper_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$).

Their 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.
strength_weakness: strength_weakness: 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.
questions: 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.
2) 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: limitations: N/A
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
2. 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.
3. 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?
questions: 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.
1.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.
2. 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?
3. 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: 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.
paper_summary: paper_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. 

The 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.
strength_weakness: strength_weakness: 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.
questions: questions: I don't have any specific questions.
limitations: limitations: The societal impact is not available.
paper_summary: paper_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.

The 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).

The 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.

The 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.

The 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.
strength_weakness: strength_weakness: 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.

In 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.

I 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.

If 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?
questions: 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?

Q2. 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?

Q3. 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?)

Q4. 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?

Q5. 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.

Q6. 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.

Q7. 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?

Q8. 326:  “Section 5.1”, should this be table 2?

Q9. How is adversarial welfare defined? The worst welfare within the uncertainty set?

Q10. 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).

Q11. 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?
Q12. 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: 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.

Comments: title: Thank you!
Thank you!
Example where considering uncertainty (via CVaR approach) helps over the uncertainty-unaware approaches
Use-cases of CVaR and the negligible difference between CVaR and USW in Figure 1
Thank you!
comment: Thank you again for your time and effort in reviewing our paper, and for both the positive comments and critiques.
Thank you so much for promptly checking our response and raising the score! We sincerely appreciate your feedback and constructive criticism on our paper. We will incorporate the suggested changes in the camera-ready version.
Thank you for responding to my follow-up. The example is useful in helping me understand when uncertainty-aware solutions are better. I would recommend the authors to add an experiment that demonstrates it, to make a stronger case for their paper.

Considering our discussion during this period, I will increase my score by one point.
I'd like to thank the authors for replying to my concerns. I still think that the running time restricts the application of algorithms. But I believe that the studied problem is very interesting. Considering that I am not able to judge the technical novelty of this paper, I will keep my score and confidence unchanged.
The following toy example further demonstrates the robustness of CVaR when the welfare distribution has a fat-tail.

Consider a scenario with two agents and four items, where each agent must be assigned one item. Each agent's valuation for an item is independent and follows a skewed Gaussian distribution. The mean valuations for the items are represented by the following 2D array:
$$
\\begin{bmatrix}
0.39 & 0.49 & 0.51 & 0.53 \\\\
0.52 & 0.51 & 0.53 & 0.54
\\end{bmatrix}
$$

The standard deviations for the Gaussian distributions of the four items are $[0.01, 0.04, 0.05, 0.09]$, with a skewness factor of 5 across all distributions [1].

We aim to optimize the utilitarian welfare, using CVaR$_{0.04}$ as our evaluation metric. This choice maximizes the expected utilitarian welfare over the worst $\alpha = 0.04$ quantile.

To achieve this, we sampled 20,000 valuation matrices from the aforementioned distribution of valuations. We then applied three different optimization approaches: the CVaR approach at $\alpha = 0.04$, the Robust approach, and the Naïve approach that optimizes against the mean valuation.

The following results were observed on a test set of 20,000 valuations sampled from the same distribution:

**CVaR approach:**

*Allocation:*
$$
\\begin{bmatrix}
0 & 0 & 1 & 0 \\\\
1 & 0 & 0 & 0
\\end{bmatrix}
$$
*Test CVaR$_{0.04}$ utilitarian welfare:* 0.985


**Robust approach:**

*Allocation:*
$$
\\begin{bmatrix}
0 & 1 & 0 & 0 \\\\
1 & 0 & 0 & 0
\\end{bmatrix}
$$
*Test CVaR$_{0.04}$ utilitarian welfare:* 0.972

**Naïve approach:**

*Allocation:*
$$
\\begin{bmatrix}
0 & 0 & 0 & 1 \\\\
0 & 0 & 1 & 0
\\end{bmatrix}
$$
*Test CVaR$_{0.04}$ welfare:* 0.947

**Observations**

The naïve approach selects items 3 and 4, as they have the highest mean values, but it does not account for the uncertainty in the preferences. The robust approach, being more conservative, chooses items 1 and 2 due to their lower uncertainty. 

The CVaR approach strikes a balance between these two methods, selecting items 1 and 3. Item 1 has a lower mean value with low uncertainty, while item 3 has a higher mean value but with slightly higher uncertainty than item 2.

We then repeat the experiment, this time optimizing for egalitarian welfare across agents, and evaluate the results by measuring CVaR$_{0.04}$ of the egalitarian welfare.

**CVaR approach:**

*Allocation:*
$$
\\begin{bmatrix}
0 & 0 & 1 & 0 \\\\
1 & 0 & 0 & 0
\\end{bmatrix}
$$
*Test CVaR$_{0.04}$ egalitarian welfare:* 0.47


**Robust approach:**

*Allocation:*
$$
\\begin{bmatrix}
1 & 0 & 0 & 0 \\\\
0 & 1 & 0 & 0
\\end{bmatrix}
$$
*Test CVaR$_{0.04}$ egalitarian welfare:* 0.38

**Naïve approach:**

*Allocation:*
$$
\\begin{bmatrix}
0 & 0 & 0 & 1 \\\\
0 & 0 & 1 & 0
\\end{bmatrix}
$$
*Test CVaR$_{0.04}$ egalitarian welfare:* 0.45

**Observations**

We notice a significant decline in the performance of the robust approach. This decline occurs because, although items 1 and 2 have lower uncertainty compared to items 3 and 4, item 1 has significantly lower uncertainty than item 2, resulting in better worst-case utility for item 1. Since the CVaR approach selected items 3 and 1, it achieves a higher CVaR of egalitarian welfare at $\alpha = 0.04$ compared to the robust approach which selects items 1 and 2.

We also see fairly similar results when setting $\alpha=0.2$ with the other problem parameters remaining the same.

[1] https://docs.scipy.org/doc/scipy/reference/generated/scipy.stats.skewnorm.html
Thank you for asking these important questions.

The utility of CVaR is higher when welfare distributions exhibit a left fat-tail, meaning a greater probability mass is concentrated in the left tail. Unlike the robust (minimax) approach, the CVaR method—particularly at higher $\alpha$ values—balances between extreme pessimism and optimizing for the average performance. This is advantageous in allocation problems with high uncertainty, where worst-case optimization can lead to overly pessimistic and inefficient outcomes.
 
For example, in public housing assignments, where families have uncertain preferences for various housing units, worst-case optimization might result in inefficient allocations, leaving many families dissatisfied. By focusing on the worst $\alpha$-percentile preferences through CVaR, allocations can be made more efficiently (while also being robust to uncertainty with high probability), thereby improving overall satisfaction.
 
However, it's crucial to differentiate between when to apply CVaR and when the robust approach is more appropriate. The robust approach is better suited to scenarios with extremely high stakes, where any failure (no matter how small the probability of occurrence) is unacceptable—such as life-or-death situations (e.g., allocating medical supplies after a disaster). It is also effective in low-uncertainty contexts where optimizing for the worst case is reasonable and doesn't significantly reduce efficiency.
 
There are several reasons why CVaR USW behaves very similarly to the uncertainty-unaware USW maximal in Figure 1.
1) When the valuations are sampled from independent Gaussian distributions, the USW is just the mean of independent Gaussian variables. The variance of the utilitarian welfare is $\\frac{\\sum_a\\sum_i\\sigma_{a,i}^2}{(nm)^2}$ where $\sigma_{a,i}$ is the standard deviation of the valuation of item $i$ according to agent $a$. Due to this the variance of the utilitarian measure is fairly low, and USW is a more stable measure compared to GESW.
2) We were sampling valuations from symmetrical Gaussian distributions and so the noise in the valuations was (mostly) getting averaged out.
3) We also had a large number of items with very small variance. In AAMAS 2015 and 2016, around 8-9% of the entries have variance less than 0.005. 

We verified that when we model valuations using a negatively-skewed Gaussian distribution with the same means and variances [1], we see increasing robustness of CVaR relative to uncertainty-unaware USW. The difference is sharper as the skew parameter gets more negative. For example, on the AAMAS 2015 dataset we tried the following experiment where we sample valuations from a skewed-Gaussian distribution with varying skew parameter. We optimize and evaluate for CVaR$_{0.3}$. 
| Skew | CVaR USW |  USW |
|:----:|:--------:|:----:|
| -0.5 |   1.64   | 1.56 |   
|  -1  |   1.45   | 1.21 |   
|  -2  |   1.33   | 0.96 |   
|  -5  |   1.29   | 0.84 |  
|  -10 |   1.28   | 0.82 |  


[1] https://docs.scipy.org/doc/scipy/reference/generated/scipy.stats.skewnorm.html

Note that in practice, if the valuation matrix is not Gaussian-distributed, we can generate samples from its posterior distribution using Markov Chain Monte Carlo (MCMC) or Variational Inference (VI).
Thanks for answering my questions and concerns. 

The new experiment included in the global response helps show the value of the GESW function. This should be included in the main paper.

I am still not convinced about the need to include CVaR optimization. I agree that it allows better analysis, and it may be widely used, but what is the contribution it makes in the context of this paper? I understand that the paper's contribution is not in designing a better solution to an existing problem, but to define a new optimization. Yet, the benefits of using this optimization could be made clearer.

From Figure 1, yes, the uncertainty-unaware solutions do become worse as the level of uncertainty increases, but so do the uncertainty-aware solutions (especially looking at USW, the difference is negligible). Can the authors comment on why this is, and perhaps give an example where considering uncertainty helps over the uncertainty-unaware approaches (specifically for CVaR)?
Thank you so much for promptly reviewing our rebuttal and raising the score. We greatly appreciate it and are glad that you found our paper interesting!
The authors have addressed all my concerns and I have raised my score by one point. I found the submission very interesting, and think the paper will be a great contribution to the area!