Robust Allocations with Diversity Constraints
Authors: Zeyu Shen
Lodewijk L. Gelauff
Ashish Goel
Aleksandra Korolova
Kamesh Munagala
Venue: NeurIPS 2021 Poster (2021)
Keywords: Resource allocation
algorithmic fairness
online advertising
Nash Welfare
social welfare

Abstract: We consider the problem of allocating divisible items among multiple agents, and consider the setting where any agent is allowed to introduce {\emph diversity constraints} on the items they are allocated. We motivate this via settings where the items themselves correspond to user ad slots or task workers with attributes such as race and gender on which the principal seeks to achieve demographic parity. We consider the following question: When an agent expresses diversity constraints into an allocation rule, is the allocation of other agents hurt significantly? If this happens, the cost of introducing such constraints is disproportionately borne by agents who do not benefit from diversity. We codify this via two desiderata capturing {\em robustness}. These are {\emph no negative externality} -- other agents are not hurt -- and {\emph monotonicity} -- the agent enforcing the constraint does not see a large increase in value. We show in a formal sense that the Nash Welfare rule that maximizes product of agent values is {\emph uniquely} positioned to be robust when diversity constraints are introduced, while almost all other natural allocation rules fail this criterion. We also show that the guarantees achieved by Nash Welfare are nearly optimal within a widely studied class of allocation rules. We finally perform an empirical simulation on real-world data that models ad allocations to show that this gap between Nash Welfare and other rules persists in the wild.

Robust Allocations with Diversity Constraints
Zeyu Shen Duke University Durham NC 27708-0129 zeyu. shen.ukkee edu
Lodewijk Gelauff
Ashish Goel
Management Science and Engineering Stanford University, Stanford CA 94305 [lodewi jk, ashish ord. edu
Aleksandra Korolova Department of Computer Science University of Southern California korolova@usc.edu
Kamesh Munagala
Department of Computer Science Duke University, Durham NC 27708-0122 kameshōcs. duke edu
Abstract
We consider the problem of allocating divisible items among multiple agents, and consider the setting where any agent is allowed introduce diversity constraints on the items they are allocated. We motivate this via settings where the items themselves correspond
user ad slots task workers with attributes such race and gender on which the principal seeks to achieve demographic parity. We consider the following question: When an agent expresses diversity constraints into allocation rule, is the allocation of other agents hurt significantly? If this happens, the cost of introducing such constraints is disproportionately borne by agents who do not benefit from diversity. We codify this via two desiderata capturing robustness. These are no negative externality other agents are not hurt and monotonicity the agent enforcing the constraint does not see a large increase in value. We show in a formal sense that the Nash Welfare rule that maximizes product of agent values is uniquely positioned to be robust when diversity constraints are introduced, while almost all other natural allocation rules fail this criterion. We also show that the guarantees achieved by Nash Welfare nearly optimal within widely studied class allocation rules. We finally perform an empirical simulation on real-world data that models ad allocations to show that this gap between Nash Welfare and other rules persists in the wild.
Introduction
Allocating heterogeneous divisible items (or resources) among agents with different values over these items is a central problem in economics, with literature dating back many decades 43
37 5]
These problems have gained importance computer science and machine learning due to their resource
applications in, among other things, large-scale online advertising allocation in datacenters
[3
(2 and sharing economy platforms.
Given their wide applicability, there has been a large body of work on elucidating desirable properties of such allocations. One desirable property is fairness equity in the value the allocation provides to different agents. Though there is no universally agreed-upon notion of fairness, one appealing the value they provide to the agents as well as envy-free [43] meaning that no agent should derive more value from another agent's allocation. A less restrictive notion the so-called Pigou-Dalton principle [77 335 or welfarism, which states that given any fixed total value of the agents, an allocation should prefer distributing these values so that there no potential transfer of value from an agent with larger value (the "rich") ") to one with smaller value (the "poor"). This loosely translates to allocations that optimize
notion [44] defines fair allocations those that are both Pareto-optimal
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

a (weakly) concave social welfare function over agents' values. We call rules that optimize separable, symmetric, concave functions of agent values as welfarist allocation rules
Due to their simplicity of implementation and ease of understanding, most allocation rules im- plemented in practice are welfarist rules. Indeed, even when allocations are supported by prices, for instance in revenue-maximizing ad auctions, by Myerson's 's celebrated transformation [36 22 and its generalizations, these can be viewed as optimizing a linear "virtual welfare" function over allocations [O 12]. Further, envy-freeness can also be implemented by the welfarist Nash Welfare
rule 37 that optimizes the product of agents' values, and which we will discuss extensively.
1.1 Allocations with Diversity
In this paper, we consider a different desirable facet of such allocations - diversity. The notion of fairmess presented above attempts to spread value fairly across agents. Suppose, in addition, the items being allocated were also associated with individuals. For instance, consider the following scenario motivated by online advertising the items are ad view slots in an advertising ecosystem, each item labeled with the attributes, such as race, age, gender, of the viewing individual on social media site. The agent represents advertiser who has different preferences over the viewing individuals. The agent may not only seek an allocation of slots that maximizes its own value, but may also want these slots to not be all views by any particular race. In other words, the agent seeks an allocation that is also diverse on the attributes of the corresponding slots. Similarly, in a team formation platform, an agent seeking such team may value diversity in attributes such gender and race of the team members in addition to competence. Diversity has become an increasingly important consideration for eliminating bias in allocation platforms where the items map to humans. Allowing agents specify some form of diversity constraints on allocations are one way for achieving this goal [45]
38).
The simplest diversity constraint we consider is the case where the agent wants items with different attributes (such as race and gender) in fixed proportions, which models the diversity desiderata in the advertising and team formation settings considered above. We term these "proportionality constraints"; see Section 2.2 for a formal definition. More generally, such constraints capture complementarity in the allocation, where agent can say "I want at least as much of this attribute as that attribute." " A different application for such constraints is in machine allocation in data centers, where client could request machines in different geographic regions in certain proportions [41]. For simplicity, we call these constraints diversity constraints, though it should be kept in mind that they model complementarity in general and can easily arise in settings beyond achieving diversity.
In Section 2.2] we model diversity constraints imposed by agent i as simply a convex polytope P. such that the empty allocation Ö E P.. First, this means such constraints preserve feasibility of the allocation. More importantly, these constraints, including proportionality constraints considered above, can have both positive and negative coefficients, and this leads to interesting and non-obvious behavior of welfarist allocation rules. This forms the focus of this paper.
Externality in Diverse Allocations. One natural solution to incorporating diversity is for the allocation platform to ask agents for their constraints and add them to the welfarist optimization
problem. Indeed, recent work on large scale online allocation problems [8] 19 24 shows that even in the presence of arbitrary convex constraints on the allocations that can run across time, the resulting problem can be viewed as online stochastic convex programming and admits efficient approximation
algorithms 3 g Similarly, recent works on auctions with diversity constraints [12 14, 26 also
follow this route and simply add these constraints to an optimization procedure.
In this paper, our main focus is to understand how adding such constraints affects the outcome of the allocation. More precisely, for any welfarist allocation rule, when an agent imposes diversity constraints, this changes the allocation of not just this agent, but all other agents as well. Naturally, seeking a diverse allocation will incur a cost in terms of diminished total value of all the agents. This cost is, of course, counterbalanced by the benefit of diversity to the agent seeking diversity (which does not explicitly appear in our model). Since the agent seeking diversity is the one benefiting from the constraints, it would be desirable from both the other agents' and the platform's 's perspective that this agent should be the one bearing the majority of this cost, while the values for other agents should
We borrow this term from 39 though the concept itself is classic detinitions.)
32 34
(See Section
2.1 for formal

---

Further, the not be significantly impacted. In other words, there should be little negative externality on other agents. We present this desideratum formally in Section 2.3
It is not a priori clear whether the welfarist allocation rules are robust in the above sense and thus the extent to which imposing diversity constraints, even by one agent, may impact other agents. In fact, this lack of clarity may be a major reason for platform to hesitate to implement functionality enabling agents specify such diversity constraints, significant shortcoming for applications such as team selection and online advertising. Thus the focus of our work is on quantifying the potential negative externality and on developing recommendations for finding robust allocations.
1.2 Our Results
To start with, one could reasonably hope that welfarist allocation rules that attempt to find equitable or fair allocations across agents would be naturally robust to the addition of diversity constraints, in the sense that to a good approximation, the negative externality to other agents' values is bounded. Our first analytical result shows that the above intuition is false. In Section [3 we show that almost all welfarist allocation rules regardless of how equitably or fairly they distribute value among agents are not robust in the sense that the negative externality on other agents that stems from imposing even a single diversity constraint unbounded (see Theorem [ On the positive side, we show that the Nash Welfare objective [37 which optimizes the product of agents' values, is the exception in that it achieves negative externality that is bounded above by an absolute constant factor even when constant number of agents impose arbitrary diversity constraints. Further, this constant bound is nearly optimal for any number of agents enforcing such constraints since any allocation rule satisfying the Pigou-Dalton principle also suffers similar negative externality. (Theorems Saaaamsssaan and
We then consider how an agent's 's imposing diversity constraints affects its own value. We define an allocation rule to be monotone if an agent's 's imposing diversity constraints weakly reduces her own value, and is monotone to constant factor if the value increases by most a constant factor. In Section[4 4 we show such monotonicity is correlated with how egalitarian the allocation rule is the more egalitarian (or concave) a rule is, the closer to monotone is (see Theorem 4 Nash Welfare allocation rule is monotone to an absolute constant factor.
In Section 5 we use real-world datasets model ad allocation. For a budget-capped valuation function that is widely studied in this setting, we compare the negative externality induced by various allocation rules. In this setting, the social welfare maximizing rule models first price auctions with budget constrained advertisers, and we empirically show that it indeed suffers large externality and non- monmmoootoiiciy. However, the Nash Welfare rule suffers very small externality and is monotone. hence making a case for that our theoretical insights will apply in the wild as well.
We summarize the upper and lower bounds the amount of negative externality and non- monotonicity for various allocation rules in Section 2.3 Taken together, our main contribution is therefore show that the Nash Welfare objective is uniquely positioned among large class of welfarist allocation rules to be robust, achieving both no negative externality and monotonicity to within small constant factors. Our results also suggest that care must be exercised by the allocation platform when allowing agents to express diversity or complementarity constraints. If these are di- rectly encoded into the optimization like in [12 19
they may create second-order unfairness where the resulting decease in value is borne by agents not directly benefiting from the diversity.
1.3 Related Work
Our work studies robustness of allocations when users can express diversity constraints. This can be cquivalently viewed as an agent specifying different utility function. For instance, a proportionality constraint corresponds to user expressing a Leontief utility function over the allocation instead of linear utility. In that sense, our results can be equivalently viewed as studying the robustness to agents reporting utility functions that capture diversity. Robustness in our sense has been widely studied when agents can arbitrarily misreport utility functions. In this context, monotonicity is simply strategy-po prooffess,, and non-negative externality maps to non- non-bossiness [42). The main result in 42 shows that the only allocation rules that satisfy these properties are variants of serial dictatorships, where agents go one after the other and choose their optimal allocation, and these rules are incompatible with Pareto-optimaliiy and welfarist rules. The only exception is settings resembling matchings [40] 3I), which are much more restrictive than the setting we study.
3

---

Note however that diversity constraint is very specific type of "misreport" given any allocation, the new utility function is necessarily weakly smaller in value, and this is crucial to all our results. Monotonicity can now be viewed as strategy proofness with such misreports. But now, rules that are not strategyproof in general can easily be monotone. Indeed, we show Theorem f that the MMF rule is actually monotone for general constraints, Pareto-optimal, and welfarist, but is trivially very far from being strategyproof if arbitrary misreports are allowed. In the same vein, the non -egaatete externality property is much more specific than non-bossiness with general misreports, and it is priori not obvious that is incompatible with welfarist rules (Theorem 3), One our main results is to show that even with the specific type of utility "misreports" that diversity constraints imply, this property is incompatible to any factor with welfarist rules, except for the NW rule.
Several recent works have considered the question of computing solutions to discrete optimization problems, such as b-matchings 4 stable matching 388, clustering [5], ranking [3 227. voting [[1]
and packing [16], when the items belong to groups that must be allocated fairly in the resulting solution. For instance, each cluster the clustering solution must be assigned a balanced cohort of red and blue points [15]. Our work tackles normative question that arises in this space assuming only a subset of agents care about diversity, what do these constraints mean for the allocations to other agents? Extending our work to discrete optimization problems is interesting open question.
For lack of space, we present a detailed comparison with other notions in Economics and related work on ad auctions in the Supplementary material (Appendix ??).
2 The Diverse Allocation Model
There are n agents and m divisible items, each with unit supply The goal of the platform is to compute an allocation म where Jaj represents the fraction of item j that is assigned to agent i. Each item is assigned at most once fractionally, that is, Σ, Fig S V ittems
In the context of ad auctions, an item represents a type of viewer or keyword, available in a certain quantity. fractional allocation would allocate the corresponding fraction of the ad slots of that type to the advertiser (or agent).
We assume that any agent i's value for allocation 2; is linear. We denote the value Vi( Ej Uij.ij. where Diy is the value the agent for item j. Our positive results extend to the more general setting where Vú are arbitrary non-decreasing, continuous, concave functions, while our negative results apply even to the linear case.
2.1 Welfarist Allocation Rules
We will consider a general subclass of allocation rules called welfarist allocation rules. These optimize E, (V.(), where is a monotonically non-decreasing. continuous and concave function.
Formally, given a choice of f. the welfarist optimization problem is follows:
Max Σ f(V)
V. V =
Σ Vi Vi; Σ Fij S Aijj; ni 2 OVE.
s.t.
Typically, the more concave f is, the more egalitarian across agents is the resulting allocation. The main class of rules we consider are f-fair rules (34), defined as:
f(v) y²
(- 1]
At 7 0. this rule is defined by its limit - so that f(w) Iny.
As special cases, this yields well-known rules in increasing order of how concave / is, in a sense capturing increasing fairess in the resulting allocations.
Social Welfare (SW). f(y) = y. corresponding to 7
Nash Welfare (NW). As 7 + O, we obtain f(y) = In y.
The model trivially generalizes the setting with arbitrary but known supply by scaling the values.

---

Max-min Fairness (MMF). This computes an allocation with V such that if V. < V,, there is no other allocation where agent i's value is larger than Vi and j's value smaller than V,, This corresponds to -00.
Among these functions, SW is the least egalitarian, while MMF is the most. We now note some features of welfarist allocation rules that we will use later.
Pareto-optimality (PO). The optimal allocation T is such that there is no other allocation I such that Vi(rt) Z V((E,) for all agents i, with one inequality strict.
Pigou-Daltone (PD) Principle 1I7 35). Consider any two allocations with values V and V where Σ, V, -E; V,, Fix two agents k and and suppose V,- = V for all j # k &, while V₂ Vi < Ve and V < <V² < Ve. Then the allocation rule weakly prefers V to V.
Anonymity. We finally say that rule is anonymous if the allocation only depends on the revealed vector of values, and not on the identity of the agents. In particular, agents that reveal identical values receive identical allocations.
Note that all welfarist rules described above satisfy (PO), (PD), and anonymity. The NW rule has additional desirable properties. First, it is scale invariant: If an agent i scales all her values di by any factor a with other agents remaining the same, the optimal allocation does not change. Next, the allocation is proportional: Given n agents, the value obtained by any agent in the NW allocation is always at least 1/n of the value it could have obtained had it been the only agent in the system.
2.2 Specifying Diversity
We assume an agent can be interested in receiving a diverse mix of items, and can specify diversity as a constraint set P, on the allocation 2;; it receives. This constraint set is added to the welfarist optimization problem described above. We assume P; is convex and that 0 E P, As mentioned before, such constraints are motivated by settings where the items have attributes related to gender, race, income, etc., and an agent can be interested in obtaining a balanced mix of items, opposed to a welfare maximizing set of items. We consider two types of constraints:
Proportionality Constraint. Here, agent i specifies a partition Si2......... Sik, of subset T of the R; items, along with proportions a;1 0.2...., ark, where Σ Oir 1. It seeks allocations from each Srr in proportion to asr. In other words, the constraint set P; is:
Σ Fiy Ity Cir Ens rzy JES
Vr E (1,2....k)) k}
We can also define an e-approximate notion of proportionality, where the right hand side of the above equality is constrained to be within (1 + factor of the left hand side. In our constructions, we will
only consider exact proportionality.
General Constraint. There is arbitrary convex set P.. with Ō P,. The agent needs 2 P, This is more general than the proportionality setting, and could for instance capture multiple proportionality constraints over different partitions of the items. Further, the unconstrained setting where Pi is all possible allocations is also a special case.
We call an agent who does not specify any constraints an unconstrained agent. A constrained agent can specify a general constraint set, and this includes being unconstrained. Our positive results (Theorems
2 and hold in the most general setting with any number of agents who are initially constrained, while the specific agent switches from being unconstrained to expressing a general constraint. Note that this captures initially unconstrained, and one agent switches to expressing a general constraint. Our impossibility results (Theorems ! 3 and 4 and Corollaries and 3 on the other hand hold even in the special case where there are two agents who are unconstrained and one agent switches to expressing a single proportionality constraint.
special case, the setting mentioned before where all agents
2.3 Robustness Desiderata for Allocations with Diversity
The high level question we consider is: For welfarist allocation nules, does providing the ability for an agent to express diversity constraints lead to undesirable externality in the resulting allocations?
5

---

We study two kinds of externalities: Whether this additional functionality can hurt the agents who do not use this functionality; and whether an agent can gain by mistepresenting themselves as diversity constrained when they are unconstrained in reality. Formally, we consider two natural desiderata for the allocation rule.
Non-negative Externality. (NNE) Suppose č is the allocation when agent i is unconstrained. Sup- pose the agent expresses diversity constraint P; and the new allocation with P. included in the optimization is y. Then for any & + i, we should have (z(e) 2 Vz()). In other words, if agent expresses a diversity constraint, it should not create negative externality to other agents. For a parameter 9 E [0. 1], we say that an allocation rule is q-NNE if (V(e 2 gVz(dz)) for all & + i. For some of our results, this can be naturally generalized k agents are initially unconstrained and simultaneously express arbitrary diversity constraints.
Monotonicity, (MON) Consider the same setting as above. We should have V((A. (1)). In other words, expressing a diversity constraint should not increase the linear value of the agent, since such an increase has the undesirable effect of an agent having the incentive to misreport their constraints. For a parameter E [0, 1I, we say that an allocation rule is p-MON if (T(,) 2 (V.)..
An allocation rule is (p. ( -robust if it is p-MON, and g-NNE, where p, q E (0, 1) are constants. As discussed before, robustness is desirable for practical implementation of diversity constraints.
Summary of Results. In the sequel, we will bound the (p, q) robusstess achievable for various welfarist allocation rules. In particular, we show that among the class of q-Far rules, only the Nash Welfare rule achieves constant q 2 1
1. that is, has bounded negative externality. All other rules have q = Further, the bound attained by NW cannot be significantly improved: No rule satisfying (PO)
and (PD) as defined in Section 2.1 can achieve 9 > z
For monotonicity, we show that p increases with decreasing 7, that is, as the function becomes more concave or fair. At one extreme, for MMF, we have 1. and at the other, for SW, we have 0. The Nash Welfare objective achieves p 2. and the bounds we obtain are tight for all y E (-00, 1].
3 The Non-negative Externality (NNE) Condition
In this part, we will assume f is differentiable and study which functions satisfy the q-NNE condition for some absolute constant q > O. At first glance, one might intuit that the more concave or fair f is, the more likely is to satisfy g- NNN Surprisingly, we show this intuition false. Our main result in this section is that f needs to have very specific form that is unrelated to its fairness or concavity in order for the allocation rule to be q-NNE. In particular, we show that most functions that are not scale-invariant fail the NNE property regardless of how concave they are, while the scale-invariant NW allocation satisfies N-NNE for an absolute constant q.
3.1 An Impossibility Result
Define g(y) = vy). We will assume is continuous. We need the following technical definition. Definition 1. For 5 I 1, we say that f is 5-scaled if is continuous and min 1920
g(v)
= 5.
g(
We show an impossibility result for q-NNE in the following theorem Theorem 1. If is 8-scaled, then it is not q-NNE for any q > 8.
The above theorem rules out achieving g-NNE for any constant y for wide range functions. In particular, we have:
Corollary 1. The y-Fairness rule for any fixed 7 # O does not satisfy q-NNE for any constant >> 0.
This rules out NNE for any constant > 0 for SW and MMF. A similar corollary holds also for additional functions commonly considered in the literature. For the Exponential function f(y)
1 e Av note that glv) Xye- -Ay and g(0) 0. For the Smooth Nash Welfare (25 23 function y/
f(v) = In(1 + y), we have g(y) = 9+1* which is increasing with g(0) = 0. Similarly, for
f(v) In In(1 + v). we have g(y) g+I logletij is decreasing with g(v) + 0 as y + co.
y
Therefore, these functions are only 8-scaled for 8 + 0, and are hence not NNE for any q >
All omitted proofs are in the Supplementary material (Appendix ??).

---

3.2 Externality of Nash Welfare
We now show quite surprisingly that in a sense, the converse of Theorem I is also true. Specifically, this theorem does not rule out achieving g-NNE for functions f that are d-scaled for constant >> 0. We show that a subclass of these functions satisfy q-NNE for constant q > O, and this subclass includes the NW allocation rule. Further, we show that any allocation rule that is Pareto-optimal and satisfies the Pigou-Daltan principle incurs an almost matching negative externality.
Theorem 2. Allocation rules where g(v) yJ' (v) non-increasing and is 8-scaled satisfy q-NNE for q 64.3"
The next corollary follows by directly applying the above theorem NW rule. The proof follows by observing that for NW, f(y) = In y. so that g(y) = 1 is a constant, so that is 5-scaled for 5 = 1. Corollary 2. The NW allocation rule satisfies q-NNE for q =
We note that there could be other functions f satisfying the preconditions of Theorem 2 For instance, f=) = 2 In x In(1 + I)), which a combination of Nash Welfare and Smooth Nash Welfare, is 5-scaled for 5 = 2. so that it is q-NNE for 7
To complete the picture, we now show that no rule that satisfies Pareto-optimality (PO) and the Pigou-Dalton principle (PD) as defined in Section 2.1 can achieve g-NNE for > 1/2.
Theorem 3. No allocation rule that satisfies (PO) and (PD) satisfies Q-NNE for any constant q >
Observations and Extensions. Theorem 2 does not require Vi()))) to be linear function of 2;, It holds long as (a is any concave non-decreasing function as long as Vū(ū) 0. The same holds for all the positive results we subsequently present, e.g., Theorem !
As extension of Theorem 2 suppose & agents express diversity constraints. A naive application yields q-NNE for (6+3)= since each of the agents expressing diversity constraint decreases the value of another agent by factor of at most 5.3. However, show that as long small subset of agents expresses diversity constraints, the externality for 5-scaled functions is bounded.
g*
Corollary 3. For any k. suppose set S of k agents switch from being unconstrained to expressing general diversity constraints. Then, allocation rules where g is non-increasing and f 8-scaled satisfy q-NNE q
5 2648+1
Therefore, the NW allocation is q-NNE for q Z[KTIT. We show matching lower bound below.
Corollary 4. There are instances where any allocation satisfying (PO), (PD), and anonymity is not 1+c q-NNE for q = ki1+e where > is any constant when each of le agents switches to expressing proportionality constraint.
4 The Monotonicity (MON) Condition
Unlike the case of NNE where almost all rules other than NW fail, for monotonicity, we show that increasing fairness or concavity of f is correlated with achieving p-MON for constant p > This is surprising since one would expect that if diversity constraint hurts another agent by arbitrary amount, should help the agent enforcing the constraint also by an arbitrary amount. However, we show that this intuition is false and MON and NNE are indeed very different properties.
For F-Faiinsss, we now show nearly matching upper and lower bounds on P-MON as a function of 7 and show that p decreases with increasing
Theorem 4. For y E (-oo, 1). the F-Frrinsss rule satisfies p-MON where is the solution to p² p177+ 1. Further, this bound p is tight.
The above theorem shows that p increases with decreasing 7, confirming the intuition that achieving p-MON is easier as the function becomes more concave. In particular, have the following corollary by setting 7 appropriately:
Corollary 5. The following bounds on p-MON are light: p = 0 for social welfare (7 = 1); p = 1 Nash welfare (y 0), and p forr max-min fairness (Y - -o))
2 for
7

---

Therefore, the MMF allocation rule satisfies monotonicity, combined with (PO) and (PD), while TheoremBruu out a corresponding result for 1-NNE.
Empirical Simulation
We now augment theoretical analysis with quantitative empirical demonstration of externality and monotonicity achieved by various allocation rules. We consider budget-constrained valuation function that is widely used in ad allocations [33 20 [8] We generate instances from real-world datasets to mimic bidding data in ad allocation, and empirically compare the externality and mono- tonicity properties of various allocation rules. We show that even empirically, rules other than Nash Welfare incur significant negative externality, thus providing evidence that our results are not merely worst-case analysis, but correspond what may also happen in practice.
Datasets and Setup. We use two datasets. The UCI Adult dataset ( tabulates census information such as geographic area, job, gender, and race for around 50,000 individuals. The Yahoo A3 dataset [2 contains bid information for advertisers for a set of ads.
For the Adult dataset, we consider the two genders as items, and the 14 job categories as agents. The value of a gender (item) to job (agent) set to be linearly and positively correlated with the number of people of that gender working in that job. We take the first 500 data points. For the Yahoo dataset, we consider the advertisements as items, and the advertisers as agents. The value of an advertisement to advertiser is set its bid on the advertisement [ We take the first 10,000,000 data points. We arbitrarily take 20 advertisements, together with 6 advertisers who have bid on most of these advertisements. In both cases, the diversity constraint for an agent is the proportionality constraint that equalizes the allocation across items where this agent has non-zero values. (We exclude items with zero value since the agent is clearly not interested in this item.)
In order to make the valuation function mirror advertising applications, we use the budget-capped valuation function 33 20 where for each agent i, its value is
(i = min Bi, Σ ViyDis
(I)
where B; is the budget of the agent. This function has also been termed liquid welfare, since it is an upper bound on the amount of welfare the platform can generate given budget constraints of the advertisers. In our simulation, we draw B, independently and uniformly from T). For the Adult dataset, we set T 20, and for the Yahoo dataset, we set T 10. These are chosen commensurate with the magnitude of the values of the agents for items.
Simulation. We conduct three sets of simulations on each dataset and compare the allocation rules for -Fairresss with 7 = 1 (Social Welfare), 7 = 0.5, 7 = 0.1, 7 - (Nash Welfare), and 7 = (approximating MMF).
In the first single agent simulation, a specific agent expresses the diversity constraint, requiring equal allocation of all items with non-zero values. For each allocation rule and each agent i, we record the largest q such that this rule satisfies gN-NEE when this agent expresses a diversity constraint. We report Jmin min; qi for each rule. In the second double agent simulation, two agents simultaneously express diversity constraints, each requiring equal allocations of all items with non-zero value. As before, we compute the minimum value achieved over all pairs of agents.
For both these simulations, prevent the negative externality from being dominated by tiny values, when computing the negative externality, we ignore agents whose values in the unconstrained case less than 10% of their budget 5
We repeat these simulations 10 times with random seeds.
In the third monotonicity simulation, we again consider the case where a single agent expresses a diversity constraint, requiring its allocation of all items to be equal. For each allocation rule and agent i, we record the largest pt such that this rule satisfics pa- MON when this agent expresses a diversity constraint, and report Punin min, p; for each rule.
'In reality, the value is the times CTR. Though our dataset does not have CTR information, we believe our results will extend to that case.
s Including these preserves performance of NW and F-Fairness for 0. while other rules only do worse.
8

---

(a) Single Agent simulation.
(b) Double Agent Simulation.
Figure 1: The plots (1 qmin) for Social Welfare (SW), Nash Welfare (NW), and y-Fairness for y 0.5,0.1,- -1.
Results. In Figures la and lb present the box plots of (1 qmin) for the single and double agent simulations respectively. For both datasets, Nash Welfare and y-Fairness for y = 0.1 give the best performance with loss value below 10% most cases, while y = 0.5, SW, and 7 are significantly worse, with negative externality at least twice as large. The exception is the good performance of 7 -1 on the Adult dataset. Moreover, in the double agent simulation, NW and y-Faimess for 0.1 perform much better than the worst-case bounds presented before.
For the monotonicity simulation, we find that pmin for all rules except SW. In other words, these rules are monotone. For SW, we have Pmin = 0.36 for Yahoo and Pmin = 0.94 for Adult
Relevance to Ad Auctions. The Social Welfare maximizing rule under the valuation function from Eq (T) closely mirrors allocation rules used in ad auctions [33 18 24 46). In particular, via standard LP duality, the SW allocation has the following structure: It is first price auction where bid (or value) of an advertiser is scaled down by an advertiser-depeenerr parameter. Such an allocation rule mirrors the widely used smooth delivery allocation rules (46) for budget constrained advertisers. Further, rules that allocate adwords in an online fashion essentially compute an approximately SW allocation 33 [8]. Our empirical results show that such rule suffers large negative externality when advertisers are allowed to express diversity constraints, and this can be mitigated if the platform instead uses Nash Welfare. This complements recent line of work in advertising on implementing Nash Welfare 8 and regularization [6] as approaches to mitigate unfairness; we show that these approaches mitigate negative impacts of diversity constraints as well.
6 Conclusion
The conceptual message of this paper is that incorporating diversity constraints into an allocation platform requires careful selection of the underlying optimization algorithm prevent negative externality, One could of course wonder whether negative externality is necessarily bad thing since forces other agents consider diversity themselves. However, our results should be viewed as saying that many allocation rules change values of other agents in an unpredictable or counterintuitive fashion. Since the agents typically are not symmetric either values or what constraints they desire, the resulting externalities will also be asymmetric. This argues for minimizing such negative externality in the first place instead of using
disincentive tool.
Our work is just a first step towards understanding the robustness of allocation rules with diversity constraints, and now present several open questions. In addition to tightening bounds, it would be interesting to study pricing rules and auctions. Though we do not present details, these allocation rules suffer from similar drawbacks. For instance, truthful auctions (30 or online allocations (33 with budgets are not Pareto-optimal with diversity constraints, while rules that compute optimal auctions (36] 12] or market-clearing solutions [5] are not robust any approximation even with quasi-linear utilities. We leave deeper examination of rules with prices and budgets as an interesting open question. Finally, it would be interesting to study such externality in contexts other than allocation problems, for instance, discrete ML problems such as ranking or clustering.
'The performance of SW is unstable under different sets of random budgets, while the other four rules are stable. Thus, for the sake of exposition, select a bad instance for SW present here.

---

Acknowledgments and Disclosure of Funding
This work is supported by NSF awards CCF-1637397. CNS-1943584, CNS-1956435, CCF-2113798, ONR award N00014-19-1-22688, DARPA award FA8650-18-C-788 and gifts from Google and Microsoft.
References
[1]
ictp uci http://www........eeeee//aaaaats
[2] https://nebscope..aaae sanddeooc.eeeeaoooooooooooooooo.
[3] Agrawal and N. Devanur. Fast algorithms for online stochastic convex programming. In
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, page 1405-1 1424, 2015.
[4] F. Ahmed, J. P. Dickerson, and M. Fuge. Diverse weighted bipartite b-matching. In Proceedings of the 26th International Joint Conference on Artificial Intelligence, IJCAI' 17, page 35-41. AAAI Press, 2017.
[5] K. J. Arrow and G. Debreu. Existence of an equilibrium for competitive economy. Economet- rica, 22(3):265-290, 1954.
[6] S. Balseiro, H. Lu, and Mirrokni. Regularized online allocation problems: Fairness and beyond. arXiv 2007.00514, 2020.
[7] R. Balseiro, Feldman, V. Mirrokni, and S. Muthukrishnan. Yield optimization of display advertising with ad exchange. Management Science, 60(12):2886-2900 2014.
[8] M. H. Bateni, Y. Chen, D. Ciocan, and V. Mirrokni. Fair resource allocation in a volatile marketplace. Available at SSRN, 2018.
[9] S. J. Brams and A. D. Taylor. Fair Division: From Cake-Cutting to Dispute Resolution. Cambridge University Press, 1996.
[10] Y. Cai, C. Daskalakis, and S. M. Weinberg. Optimal multi-dimensional mechanism design: Re- ducing revenue to welfare maximization. In 2012 IEEE 53rd Annual Symposium Foundations of Computer Science, pages 130-139, 2012.
[11] L. Celis, L. Huang, and N. K. Vishnoi. Multiwinner voting with fairness constraints. In Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI-18, pages 144-151, International Joint Conferences on Artificial Intelligence Organiza- tion, 7 2018.
[12] L. E. Celis, A. Mehrotra, and N. K. Vishnoi. Toward controlling discrimination in online ad auctions. In Proceedings of the 36th International Conference Machine Learning, ICML, pages 4456-44655 2019.
[13] L. E. Celis, D. Straszak, and N. K. Vishnoi. Ranking with faimess constraints. abs/1704.06840, 2017.
CoRR,
[14] S. Chawla and M. Jagadeesan. Fairness in ad auctions through inverse proportionality. CoRR, abs/2003. 1396., 2020.
[15] F. Chierichetti, R. Kumar, S. Lattanzi, and S. Vassilvitskii. Fair clustering through fairlets. In Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
[16] Chierichetti, R. Kumnrr, S. Lattanzi, and S. Vassilvtiskii. Matroids, matchings. and fairness. In K. Chaudhuri and M. Sugiyama, editors. Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statisties, volume 89 of Proceedings of Machine Learning Research, pages 2212-2220. PMLR, 16-18 Apr 2019.
[17] H. Dalton. The measurement of the inequality of incomes. The Economic Journal, 30(119):348- 361, 1920.
[18] N. R. Devanur and T. P. Hayes. The adwords problem: Online keyword matching with budgeted bidders under random permutations. In Proceedings of the 10th ACM Conference on Electronic Commerce, EC '09, pages 71-78, 2009.
10

---

[19] N. R. Devanur, K. Jain, B. Sivan, and C. A. Wilkens. Near optimal online algorithms and fast approximation algorithms for resource allocation problems. In Proc. 12th ACM EC, pages 29-38, 2011.
[20] S. Dobzinski and R. P. Leme. Efficiency guarantees in auctions with budgets. In Proc. Intl. Conf. Automata, Languages, and Programming (ICALP), pages 392-404, Berlin, Heidelberg, 2014. Springer Berlin Heidelberg.
[21] E. Eisenberg and D. Gale. Consensus of subjective probabilities: The pari-mutuel method. The Annals of Mathematical Statistics, 30(1):165-168, 1959.
[22] E. Elkind. Designing and learning optimal finite support auctions. In Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 736-745. SIAM, 2007.
[23] B. Fain, K. Munagala, and N. Shah. Fair allocation of indivisible public goods. Proceedings of the 2018 ACM Conference on Economics and Compulation, EC 18, page 575-592, 2018.
[24] J. Feldman, M. Henzinger, N. Korula, V. S. Mirrokni, and C. Stein. Online stochastic packing applied to display ad allocation. In Proceedings of the 18th Annual European Conference on Algorithms,, page 182-194, Berlin, Heidelherg, 2010. Springer-Verlag
[25] Fluschmik, P. Skowron, M. Triphaus, and K. Wilker. Fair knapsack. Proceedings of the AAAI Conference on Artificial Intelligence, 33(01):1941-1445 Jul. 2019.
[26] L. Gelauff, A. Goel, A. Korolova, K. Munagala, and S. Yandamuri. Advertising for demograph- ically fair outcomes. CoRR/2006. 039833, 2020.
[27] S. C. Geyik, S. Ambler, and K. Kenthapadi. Fairness-aware ranking in search & recommendation systems with application to linkedin talent search. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD '19, page 2221-2231, New York, NY, USA, 2019. Association for Computing Machinery.
[28] A. Ghodsi, M. Zaharia, B. Hindman, A. Konwinski, S. Shenker, and I. Stoica. Dominant resource fairness: Fair allocation of multiple resource types. In 8th USENIX Symposium on Networked Systems Design and Implementation (NSDI 11), Boston, MA, Mar. 2011. USENIX Association.
[29] G. Goel, S. Leonardi, V. S. Mirrokni, A. Nikzad, and R. P. Leme. Reservation exchange markets for internet advertising. In 43rd Intl. Colloq. Automata, Languages, and Programming, ICALP 2016, pages 142:1-142:13, 2016.
[30] G. Goel, V. Mirrokni, and R. P. Leme. Polyhedral clinching auctions and the adwords polytope.
J. ACM, 62(3), June 2015.
[31] H. Hosseini and K. Larson. Multiple assignment problems under lexicographic preferences. In AAMAS, 2019.
[32] Kelly. Charging and rate control for elastic traffic. European Transactions on Telecommuni- cations, 8(1):33-77, 1997.
[33] A. Mchta, A. Saberi, U. Vazirani, and V. Vazirani. Adwords and generalized online matching. J. ACM, 54(5), 2007.
[34] J. Mo and J. Walrand, Fair end-to-end window-based congestion control. IEEE/ACM Transac- tions on Networking, 8(5):556-567, 2000.
[35] H. Moulin. Fair Division and Collective Welfare. The MIT Press, 2003.
[36] R. B. Myerson. Optimal auction design. Mathematics of Operations Research, 6(1):58-73,
1981.
[37] J. F. Nash. The bargaining problem. Econometrica, 18(2):155-10 1950.
[38] T. Nguyen and R. Vohra. Stable matching with proportionality constraints. In Proceedings of the 2017 ACM Conference on Economics and Computation, EC 17, page 675-676, 2017.
[39] D. Peters and P. Skowron. Proportionality and the limits of welfarism. In Proceedings of the 21 ACM Conference on Economics and Computation, EC '20, page 793-794. 2020.
[40] Pápai. Strategyproof assignment by hierarchical exchange. Econometrica, 68(6):1403-144 2000.
11

---

[41] A. Qureshi, R. Weber, H. Balakrishnan, J. V. Guttag, and B. M. Maggs. Cutting the electric bill for internet-scale systems. In Proceedings of the ACM SIGCOMM 2009 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications, Barcelona, Spain, August 16-21, 2009, pages 123-134. ACM, 2009.
[42] M. A. Satterthwaite and H. Sonnenschein. Strategy-proof allocation mechanisms differen- tiable points. Review of Economic Studies, 48(4))587-597, 1981.
[43] H. Steinhaus. The problem fair division. Econometrica, 17:315-319, 1949.
[44] H. R. Varian. Two problems in the theory of fairness. Journal of Public Economics, 5(3):249-
260, 1976.
[45] K. Yang. V. Gkatzelis, and J. Stoyanovich. Balanced ranking with diversity constraints. In S. Kraus, editor, Proceedings of the Twenty-Eighth International Joint Conference Artificial Intelligence, IJCAI 2019, Macao, China, August 10-16, 2019, pages 6035-6042. ijcai.org, 2019.
[46] W. Zhang, S. Yuan, and Wang. Optimal real-time bidding for display advertising. In Proceedings of the 20th ACM SIGKDD International Conference Knowledge Discovery and Data Mining, page 1077-1086, New York, NY, USA, 2014. Association for Computing Machinery.
12

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] We have described some limita- tions in the introduction.
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] All proofs are in the Supplementary material.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main exper- imental results (either in the supplemental material or as a URL)? [Yes] The code uploaded part of the submission. The datasets publicly available.
(b) Did you specify all the training details (c.g.. data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g.. with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [N/A]
4. If you using existing assets (e.g., code, data, models) or curating/releasing assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "x9a3Sc5ovz-", "reviewer": "Reviewer_gMgx", "summary": "This paper proposes a framework for and and analysis of algorithms that allocate divisible resources to a set of agents when the agents can specify both utilities as well as constraints over the items as well. This is motivated by, e.g., computational advertising settings where we want to allocate users to advertisements so we have a reward (revenue of user) as well as constraints over the distribution (e.g., we do not want to show all job adds to men/women). The framework proposed captures popular allocation rules such as Nash and SW-Max, and the ability to specify constraints can be done through either proportionality or general constraints over the allocation set. The known mechanisms are analyzed in terms of their ability to achieve allocations that come within p,q fractions of allocations that do not impose negative externality and/or are not monotonic.", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall I quite enjoyed the paper. It is well written and the topic is interesting. The framework proposed is nice and the authors are able to incorporate a wide variety of mechanisms in the framework proposed. The problem is well motivated by the computational advertising and recommendation systems settings -- though some more work from the latter could be included, e.g., \n\nAlex Beutel, Jilin Chen, Tulsee Doshi, Hai Qian, Allison Woodruff, Christine Luu, Pierre Kreitmann, Jonathan Bischof, and Ed H Chi. Putting fairness principles into practice: Challenges, metrics, and improvements. In Proceedings of the 2019 AAAI/ACM Conference on AI, Ethics, and Society, pages 453–459, 2019.\n\nBurke, R., Voida, A., Mattei, N., Sonboli, N. and Eskandanian, F., 2020. Algorithmic fairness, institutional logics, and social choice. In Harvard CRCS Workshop: AI for Social Good.\n\nMy main concern with the paper are two fold: (1) it's not clear to me that this is a machine learning paper or has anything to do with learning. In fact, this seems like a more EC type paper given the format and the proofs provided. The (2) second major issue I address more concretely below, but that this paper does not place itself well in the existing literature and I'm not convinced that some of these results are not already known.\n\nIf I read this correctly it seems to be that the NNE property is known as Bossiness in the literature and is already fairly well studied. Given the pretty good background on the other issues in this paper I was surprised to see no discussion of bossiness. Perhaps I am mistaken but I think this is a gross oversight of the paper and makes me think that some of these issues may have been handled already? I checked the supplemental material for the extended discussion and found no mention of the concept.\n\nThe statement of bossiness from Papai is: \"Nonbossiness, a criterion frequently used in the context of strategyproof allocation, ensures that individuals cannot be bossy, that is, change the assignment for others, by reporting different preferences, without changing their own.\"\n\nThis seems exactly to map here to the constrint expression of NNE.  See for example: \n\nPápai, S., 2000. Strategyproof assignment by hierarchical exchange. Econometrica, 68(6), pp.1403-1433.\n\nSATTERTHWAITE, M. A., AND H. SONNENSCHEIN Ž . 1981 : ‘‘Strategy-Proof Allocation Mechanisms at Differentiable Points,’’ Reiew of Economic Studies, 48, 587-597.\n\nHosseini, H. and Larson, K., 2019, May. Multiple assignment problems under lexicographic preferences. In Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems (pp. 837-845).\n\nNote that this literature on strategy-proof allocations is highly relevant and needs to be incorporated because, as you say in the paper, the constraints are a kind of second order utility function and so the strategic aspects are the centerpiece of this paper.\n\nI was also curious that metrics from the healthy literature on diverse matching in the non-divisible space was not discussed. It seems that some of the metrics discussed here should be related to those.\n\nAhmed, F., Dickerson, J.P. and Fuge, M., 2017, August. Diverse weighted bipartite b-matching. In Proceedings of the 26th International Joint Conference on Artificial Intelligence (pp. 35-41).\n\nChierichetti, F., Kumar, R., Lattanzi, S. and Vassilvtiskii, S., 2019, April. Matroids, matchings, and fairness. In The 22nd International Conference on Artificial Intelligence and Statistics (pp. 2212-2220). PMLR.\n\nBurke, R., Voida, A., Mattei, N., Sonboli, N. and Eskandanian, F., 2020. Algorithmic fairness, institutional logics, and social choice. In Harvard CRCS Workshop: AI for Social Good.\n\nIn terms of making the paper better I would suggest the authors add some kind of table of results. By the end it was hard to keep track of the results that were obtained for which rules and how the bounds helped our understanding of the overall setting. E.g., it wasn't clear to me why we needed two constraint formulations and the paper didn't help clarify this -- a table would highlight where the formulations allow for tighter or loser bounds. A concrete example of the difference between the constraints would help too.\n\nLines 105-109 there is some confusion about value moving up or down I think.\n\nIn the formulation of 2.1 it seems that you allow free disposal, but this is not desired right? For then I could always just not assign things and have fair allocations since \\vec{0} is in the set? Or perhaps I misread?\n\nThe experiments need more information -- averages over runs, the confidence bounds, etc. As it stands I had a very hard time interpreting the results and have somewhat little confidence in them since I don't know any error measures.\n\nAlso for the experiments, it would help to implement the constraints as optimization criteria to check as a baseline. I didn't see where this was done and given the size of the allocations being used a simple LP formulation should be able to handle this. As it stands the results are hard to interpret without a baseline.\n\n----- \nUpdated after response and discussion.\n\nI have raised my score slightly but in my opinion this paper is still below the threshold. The author response that bossiness is not directly implied I agree with, but not engaging with that literature and not clearly articulating why it is related and what the improvements for this paper are needs to be addressed. These areas are extremely closely related and the fact that you address truthfulness (hence a component of strategyproofness) and don't address bossiness is a shortcoming. I am not saying you should cite all the literature but the paper should cite at least one paper on bossiness since the paper is directly addressing the same question: how bad can a report of one agent affect the allocation to other agents.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors do address the limitations of the work adequately. The paper is well positioned and some of the potential downsides of the work are discussed (e.g., strategically using constraint sets).", "review_text": "", "extra_scores": {"ethical_concerns": "None at this time -- the framework is interesting and allows for the analysis and tradeoff comparisons that could enable more fair/diverse allocations.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1.5"}, "extra_text": {}}, {"review_id": "sfFedmpYsl", "reviewer": "Reviewer_PQ7X", "summary": "The authors study the problem of allocation in the presence of a diversity constraint. Any participant can impose a diversity constraint - demanding proportional amounts of multiple items. An allocation can be computed using a social objective such as social welfare, Nash \n welfare subject to this constraint. There are two things that can go \"wrong\": a participant other than the one imposing the constraint might obtain lower value and the participant imposing the constraint might obtain higher value. The authors ask the question to what extent does the choice of objective guarantee that things won't go \"too wrong\". That is, any participant not imposing constraint gets at least q fraction of its value and the participant imposing the constraint does not gain more than 1/p factor. \n\nThe authors show that for almost any objective that transforms individual participants values and sums them, it is not possible to obtain q = 1. In particular, for social welfare, \\gamma-fair, max-min fair objectives it is not possible to get q > 0. In contrast, for Nash Social welfare, one can get q = 1/4. Finally, any rule satisfing pareto-optimality, Pigou-Dalton principle cannot get q > 1/2. The authors also extend these to settings where multiple participants impose constraints. \n\nFor the monotonicity - ensuring the constraining participant does not gain too much value - the authors show results for Nash-welfare and \\gamma-fair welfare functions. For Nash welfare, 3/4 > p >= 1/2 and for \\gamma-fairness, p >= (1-\\gamma)^1/\\gamma. They also provide an upper bound on p for  \\gamma-fairness that is given implicitly by an equation. The \\gamma-fairness result implies that for social-welfare p cannot be > 0. \n\nThe authors also provide an empirical evaluation of q and p values obtained on real datasets. \n\n", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The model studied by the authors is interesting and the questions the authors explore seem new. The authors do impose a lot of constraints - pareto-optimal, pigou-dalton allocation rule subject to proportionality constraints, and measure its performance against negative-externality, monotonicity criteria. The allocation rules are natural and to some extent a natural implementation when introducing diversity constraints would be to maintain the old allocation rules and impose extra constraints - and this work points out that this can result in non-monotonicity and negative externality and this can be very bad if using social welfare as opposed to Nash welfare as the objective. \n\nThe paper is very well written. The presentation could be improved a little by having some proofs or examples in the main body to help build intuition.  \n\nThe results authors provide are interesting and provide some understanding of the effect of imposing diversity constraints. There are still some aspects that are not fully explored. One question is about monotonicity - the authors do not provide as thorough an analysis of this. In particular it's not discussed if some PO, PD rule could obtain better than 1/2 approximation. Authors also do not provide bounds for the min-max objective function. For the negative externality, Nash Welfare has \\delta = 1, so potentially a tighter analysis can provide a better bound better than \\delta/\\delta + 3, which can match the lower bound of 1/2 for any PO, PD rule.  The examples used in Theorem 3 and Corollary 4 is very skewed - the buyer prefers \\epsilon fraction for every unit of another item even though both are valued the same. I am curious if less skewed examples can be constructed perhaps by setting proportionality constraint to be equal but allowing the values to be different.\n\nThere are some meta-critiques to the authors approach, the authors have anticipated and discussed these. \n* Authors could have found allocations with proportionality, non-monotonicity, no negative externality constraints and assessed how these perform on the social objectives. Authors do mention this and justify their approach for the unique challenges it poses (optimizing for pareto-optimality and proportionality simultaneously is hard.) Their justification is not fully convincing, but I think what they do is reasonable given what I wrote above. \n* Authors also consider the effect of introducing proportionality constraint in the ads setting - the proportionality constraint is fairly natural in the ad setting, however the value of the participants might need to be evaluated as quasi-linear utility as opposed to just the value of the allocation. The analysis also becomes more involved if the auction is not truthful. Authors discuss this critique and leave it as open question.  \n\nOverall, the results in this paper are interesting and detailed enough to warrant acceptance. The paper will become stronger if some of the bounds were improved. \n\nOne minor note, the proof of theorem 1 is buggy. In line 584, f'(\\alpha(1-\\delta)) > f'(\\alpha). It's not clear what y_\\delta is also g(y_\\delta)/max_y(g(y)) > \\delta - this last inequality in particular breaks the proof and some tweak might be required to make it work. Please specify how this proof can be fixed. I did skim through a few other proofs and they seemed correct and thorough. \n\n\n\n\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Authors have mentioned the limitations of their approach and justified them. The justifications aren't fully satisfactory but the authors approach is still interesting.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "i0PF4G-1lW", "reviewer": "Reviewer_NZRm", "summary": "The paper considers the problem of allocating unit divisible items under several welfare objectives (i.e., social welfare, gamma-fairness, nash welfare, and max-min fairness) subject to general diversity constraints (modeling as a polytope for each agent). The paper presents two notions of measures, non-negative externality (NNE) and monotonicity (MON), that quantify the impact of the constraints and define their approximated notions of q-NNE and p-MON, respectively. \n\nIn particular, they provide a lower bound of q for a class of continuous functions and upper bounds of q for specific welfare functions that depend on the \\delta-scaled. For the MON condition, they provide lower and upper bounds for Nash welfare and \\gamma-fairness objectives. \n\nFinally, they conduct experiments on two real-world ad allocation datasets (i.e., UCI Adult and Yahoo A3) and using the budget-capped valuation function (along with other parameter settings) to demonstrate the q and p values of various social welfare functions.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Abstract: \n\n\"to introduce diversity constraints\" -> does the planner knows about this? How is this different from the setting where you have multiple diversity constraints (say as input)? \nIt would also be good to have some examples of the constraints \n\n\"demographic parity\" -> which is? how would this apply to user ad slots? are you talking about the slots that have race/gender? \n\n\"expresses diversity constraints\" -> how would the agent express this? \n\n\"other agents hurt significantly?\" -> there is a need a way to measure hurts \n\n\"the cost of introducing\" -> how are you defining the cost here? \n\n\"We codify this via two desiderata capturing robustness.\" -> there should be some connections to your previous sentences to robustness in your context (i.e., what are you robust to?) \n\n\"does not see a large increase in value\" -> w.r.t to? \n\n\"the Nash Welfare rule \" -> is that an objective here? rather than rule? what is a rule in your context? or allocation? \n\n\"when diversity constraints \" -> does this depend on the types of the constraints? \n\n\"rules fail this criterion\" -> when you say criterion, do you mean one of the two properties in the previous sentences? \n\n\"class of allocation rules.\" -> what is the benefit of these guarantees? \n\n\n\"We finally perform an empirical simulation\" -> the gap of? it would be good to say a line about the observations \n\n1 Introduction\n\n\"competing agents \" -> is the competing the right situation? how are they competing? heterogeneous agents? \n\n\"their applications in\" -> would be good to specific some concrete examples \n\n\"Pareto-optimal\" -> are you going to shortly define this? i think you define envy-free briefly but not this \n\n\"given any fixed total value of the agents\" -> is it the sum?\n\"is no potential transfer of value\" -> to achieve what property from the potential transfer? \n\n\"separable, symmetric, concave functions\" -> it would be good to provide definitions of them more completely if its necessary/important for the paper\n\n\"envy-freeness can also be implemented by the welfarist Nash Welfare\" -> this can be hard to see ... would Nash welfare implies envy-freeness? \n\n1.1 Allocations with Diversity\n\n\"with people\" -> individuals \n\n\"ad view slots \" -> each slot is labeled with race? \n\n\"to not be all views by say, white males\" -> I would avoid pointing out a specific race\n\n\"diverse on the attributes of the corresponding individuals\" -> I guess over the slots? \n\nFor the provide examples, it would be good to provide some citations for them\n\n\"in fixed proportions\" -> add (e.g., ) \n\n\"I want at least as much of this item\" -> is this over the attributes or attributes? \n\n\"a convex polytope\" -> how are you defining the polytope? a set of linear inequalities? \n\n\"arbitrary convex long-term constraints\" -> can you elaborate? \n\n\"one bearing the majority of this cost,\" -> how will the cost be transferred in such a situation? \n\n1.2 Our Results\n\n\"negative externality to other agents’ values is bounded\" -> one question I have is that can they always satisfy the diversity constraints? If it doesn't, how can you define the overall values? \n\n\" this constant bound is nearly optimal\" -> in what sense? is this the best you can do (i.e., a lower bound)?\n\n\"reduces its own\" -> his/her? \n\n\"budget-capped valuation function\" -> which is? \n\n\"externality and monotonicity to within small constant factors\" -> one is applying to the global objective and the other is applying to the agent's utility\n\n\"If these are directly encoded into the optimization like \" -> it would also be good to show this in experiments \n\n\"Pareto-optimal or even proportional \" -> how important are these notions if you were to valid them a little bit? \n\nI think it is important to have an explicitly related work section in the paper (since Appendix won't be appearing in the proceedings); perhaps cutting out a bit more our results and 1.1 to fit in the related work\n\n2 The Diverse Allocation Model\n\n2.1 Welfarist Allocation Rules\n\n\"used allocation rules below in increasing order \" -> could you just measure this by taking a derivative? \n\nis there a citation for MMF or a more precise definition using max min? the current one doesn't seem that precise per say \n\n\"We now note some\" -> it would be good to say they are useful later on \n\nIs there a more intuitive meaning for PD? \n\n2.2 Specifying Diversity\n\nCan you justify the proportionality constraint a bit more? this seems to be conditional on the items that the agents receive in general (not out of the total allocations) \n\n\"factor of the left hand side\" -> multiplicative? \n\nWhat other constraints do you consider beyond proportionality for fairness? \n\n2.3 Robustness Desiderata for Allocations with Diversity\n\n\"Non-negative Externality\" -> are you only defining this w.r.t. one agent? what if more than one agent change? but also, why would it increase other agents if both agents express diversity constraints? \n\n3 The Non-negative Externality (NNE) Condition\n\nI do have a concern where what if they are impossible to satisfy all the Pi's (no allocation)? \n\n3.1 An Impossibility Result\n\nDefinition 1 -> what if g(x) = 0 or g(y) = 0? or greater than 1? \n\n3.2 Externality of Nash Welfare\n\nthere seems to be a gap between Theorem 1 and Theorem 2\n\nIt's kinda strange that you have a truthful result embedded when the paper is not really about it; i would suggest moving it or discuss it in the conclusion or discussion\n\ncould you also comment on the computational aspects of the problems? \n\nComputational aspects of the problems??\n\n4 The Monotonicity (MON) Condition\n\nDo you have any general results (similar to Theorem 2 for more general function)? \n\nwhat about something like social welfare? max-min fairness? \n\n5 Empirical Simulation\n\nCan you discuss what properties do the budget-capped function satisfy? \n\n\"when this agent expresses a diversity constraint\" -> did you try other types of diversity constraints? How do the results change? \n\n\"In the second double agent simulation\" -> here it doesn't seem like your definition covers this case at all? \n\n\"In the third monotonicity simulation\" -> why can't you measure the same thing for the first and second simulations? \n\nplease increase the fonts of the figures, they are hard to see without zooming in \n\nIt would be good to see the exact parameters for reproducibility", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Overall, I find the paper very interesting and enjoyable to read. While the results are a bit simple, it is interesting to see the upper and bound lowers of the q-NNE and p-MON for various welfare functions.\n\nI do have some concerns regarding the definition of NNE that considers only one agent (and a set of experiments consider two agents with diversity constraints), the (p, q)-robust that isn't really clear studied (what are the best combinations of two instead of fixing one of them), and the results that for MON seem a bit less general than the MME results. There is also a question about where were the proportional constraints used in the study and some random results on truthfulness.\n\nI also wish the experiments would contain other types of constraints.\n\nAll in all, I am slightly positive about this paper (mainly due to its readability, new idea, and its potential insights into the impact of diversity constraints).", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "JW9MeWD2EG-", "reviewer": "Reviewer_xP58", "summary": "The paper studies resource allocation among a group of agents, where\n  the agents can express diversity constraints on the allocations they\n  receive. Here, the diversity constraints require the allocation to\n  satisfy some proportionality constraints on the amount of each\n  resource received by the agent, or more generally requires the\n  allocation to lie in an arbitrary convex set.  In this setting, the\n  authors seek to identify allocation rules that satisfy two natural\n  requirements. First, it is desired that the allocation rule satisfy\n  non-negative externality, wherein the utility of any agent should\n  not decrease due to some other agents' expression of diversity\n  constraints. Second, to maintain the right incentives, it is desired\n  that the allocation rule satisfy monotonicity, wherein an agent\n  cannot increase her utility by expression a diversity\n  constraint. The authors study the class of welfarist allocation\n  rules, which maximize the sum of a concave, continuous function of\n  the agents' utilities. Among the rules in this class, the authors\n  show that the Nash welfare rule uniquely satisfies (approximate\n  versions of) both the requirements. The authors also show that the\n  guarantees of the Nash welfare rule are near optimal, and support\n  their theoretical results with numerical simulation.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "* Pros\n   - The paper studies an important problem of incorporating diversity\n     constraints into resource allocation that arises naturally in the\n     context of ad auctions or assigning workers to tasks, among\n     others.\n   - The two requirements on the allocation rules studied in the paper\n     are natural, and are driven by economic concerns. Furthermore,\n     the characterization of the Nash welfare rule as uniquely\n     satisfying (approximate versions) of the two requirements adds\n     further justification for the Nash welfare rule, beyond the many\n     theoretical properties already known.\n   - The authors further consider other common welfarist rules, and\n     characterize their failure to satisfy the two requirements.\n\n* Comments\n   - It is unclear why the Max-min fairness fits into the class of\n     welfarist rules. I am hardpressed to see the rule as maximizing\n     the sum of concave functions of the agents utilities.\n   - The presentation of the results can be improved. Currently, the\n     paper splits the analysis into different sections (corresponding\n     to the two requirements). This makes it harder to compare the\n     performance of the different rules. Furthermore, the monotonicity\n     properties of the SW and the MMF policies are not discussed.\n   \n\nThe results in the paper are not sufficient to conclude whether the\nNash welfare rule is the best possible welfarist rule for the two\nspecified requirements. The upper bounds provided for non-negative\nexternality ($q=1/2$) are substantially larger than that for the NW\nrule ($q=1/4$). For the monotonicity requirement, no bounds on the\nperformance of a welfarist rule are provided. Nevertheless, I find the\npaper makes an interesting theoretical contribution, exhibiting the\ngood properties of the Nash welfare rule.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review:    Overall the reviewers are quite positive about this paper: every reviewer thought the paper studies an interesting topic, and the results are interesting.  A weakness of the paper is that it does not quite fully explore the space. This makes it hard to really compare the different allocation rules, since various subsets of results are shown for each rule. The paper would be substantially strengthened if it were able to give a more complete accounting of the properties of each allocation rule. It is suggest that the authors partially address this shortcoming by giving some sort of overview of the results that can better facilitate comparison.  One reviewer brought up a deficiency in comparing to the existing concept of "bossiness," which seems highly related to the proposed methods. The authors are strongly encouraged to add some comparison to this literature. 

Decision: Accept (Poster)