Achieving a Fairer Future by Changing the Past

1 Introduction

One of the most well-studied problems in computational social choice [Brandt et al., 2016] is that of fairly allocating indivisible items when agents have additive valuations [Kurokawa et al., 2018; Bouveret and Lemaˆıtre, 2016; Bouveret et al., 2017; Caragiannis et al., 2016; Barman and Krishnamurthy, 2017; Barman et al., 2018; Amanatidis et al., 2016; Cole and Gkatzelis, 2015]. Here, 'indivisible' means that items cannot be split between multiple agents, and 'additive valuations' means that the value of an agent for a bundle of items is the sum of his values for individual items in the bundle; it remains to define 'fairly.'

In contrast to several prominent fair division settingssuch as cake cutting [Brams and Taylor, 1996; Procaccia, 2016] and rent division [Su, 1999; Gal et al., 2017]-the foregoing setting clearly does not admit solutions that are envy free, in the sense that each agent (weakly) prefers his own bundle to the bundle of any other agent. But a natural relaxation of envy-freeness can always be guaranteed [Lipton et al., 2004]. Specifically, an allocation is envy free up to one item (EF1) if, for every two agents i and j, it is sufficient to remove a single item from the bundle of j to eliminate any envy i might have had. This notion of fairness underlies a widely-used algorithm for the allocation of indivisible items, which is deployed on the website Spliddit.org [Goldman and Procaccia, 2014; Caragiannis et al., 2016].

The picture becomes muddier, however, when the items arrive online instead of being available upfront, and must be allocated as they arrive. This setting was most recently explored by Benad`e et al. [2018]. Assuming values are normalized to be in [0, 1], they show that the maximum envy-the maximum difference between an agent's value for another bundle and his own bundle-must be (roughly) as large as Ω(√T) after T rounds in the worst case. That is, not only is it impossible to achieve EF1, but agents must become increasingly envious over time.

We propose to circumvent this obstacle by slightly relaxing the requirements. Specifically, we allow adjustments to the allocation-each adjustment is a reallocation of a previously allocated item. This is relevant in any setting where allocations are provisional, and can change as new items become available. A common example is the (re)distribution of expensive scientific equipment (such as confocal laser scanning microscopes) among different departments within a college or a medical school.

Needless to say, adjustments are undesirable and should be avoided as much as possible, subject to maintaining fairness. More formally, our research question is:

What is the minimum number of adjustments needed to guarantee EF1 in each round, as a function of the number of items (equivalently, rounds) and the number of agents?

A simple baseline is to reallocate all items in each round, which would require Θ(T 2 ) adjustments for T rounds. Of course, we aim to do better.

1.1 Our Results

We study the foregoing question in two related models. In the first model the allocation algorithm is uninformed, in that it has no information about items that will arrive in the future. In the second model, the algorithm is informed, that is, it knows the future; even in this model adjustments are inevitable due to the requirement of maintaining EF1 in each round. The former model is pertinent when the arrival of items is outside the organization's control, as is the case when items are donated. The latter model is relevant when the arrival of items follows a budgetary or production schedule. Real-world settings are likely to include both predictable and unpredictable item arrivals, but, as we shall see, it is actually quite difficult to leverage (even complete) information about future arrivals.

We first look at the problem when there are only two agents (Section 3), and demonstrate a separation between the informed and uninformed settings. In the uninformed setting, we give an allocation algorithm that uses at most T adjustments to maintain EF1 at each round. We then show that this is tight up to constant factors by constructing an instance that ensures that any allocation algorithm would need Ω(T) adjustments to maintain an EF1 allocation. By contrast, when our algorithm knows the values for all the items that will arrive, it becomes possible to maintain an EF1 allocation without using any adjustments.

For the general case of three or more agents (Section 4), we show that even an informed algorithm requires Ω(T) adjustments to maintain EF1. In addition, we present an uninformed algorithm that uses O(T 3/2 ) adjustments-an improvement over the baseline of O(T 2 ) adjustments. Note that here we cannot separate the informed and uniformed settings, and leave open the challenging problem of obtaining tighter bounds, as we discuss in Section 5.

Our results are summarized in Table 1.

1.2 RelatedWork

On a high level, our paper is related to the literature on online or dynamic fair division [Benad`e et al., 2018; Friedman et al., 2015; Friedman et al., 2017; Aleksandrov et al., 2015; Aleksandrov and Walsh, 2017; Walsh, 2011; Kash et al., 2014]. We elaborate on the two most closely related papers.

Benad`e et al. [2018] consider indivisible items that arrive online, additive valuations, and uninformed algorithms. Assuming values are in [0, 1], they design a deterministic algorithm that achieves maximum envy of ˜O(√T/n), where T is the number of items (rounds) and n is the number of agents. They also show that this bound is tight up to polylogarithmic factors (and extend these results to a setting where items arrive in batches that are allocated simultaneously). By contrast, we are able to achieve EF1, and circumvent the lower bound of Benad`e et al., by allowing adjustments.

Apropos adjustments, they are inspired by the notion of disruptions, first suggested by Friedman et al. [2015] as a way to achieve fairness in an online setting, albeit a fundamentally different one. In their setting, it is the agents-not the items-that arrive dynamically, and, in fact, there is only a single divisible good. The utility of each agent only depends on the fraction of the good he is allocated. A disruption here means taking a fraction of the good that has been allocated to an agent and redistributing it. The goal is to optimize certain measures of fairness (fairness ratio and envy ratio) while minimizing disruptions. Friedman et al. give optimal bounds that relate the allowed number of disruptions per round to their measures of fairness. In a subsequent paper [Friedman et al., 2017], they extend the results to the case where less than one disruption per arrival, on average, is allowed.

2 Preliminaries

For each natural number s ∈ N, we let [s] = {1, . . . , s}. In our setting, there is a set A = {a1, a2, . . . , an} of n agents and a set G = {g1, g2, . . . , gT} of T items (also known as goods, hence the notation).

Each agent ai has a valuation function vi; vi(S) is the value ai has for a subset of items S. We simplify notation by using vi(gj) to denote vi({gj}). A valuation function vi is additive if vi(S) = ∑g∈S vi(g). We assume throughout this paper that agents have additive valuation functions.

An allocation of the goods is a partition A = (A1, . . . ,An), where Ai is the bundle of goods allocated to agent ai. We are interested in fair allocations that are, specifically, envy-free up to one item (EF1). Formally, an allocation (A1,A2, . . .An) is EF1 if for any i, j such that vi(Ai) < vi(Aj), there exists an item g ∈ Aj such that vi(Ai) ≥ vi(Aj \ {g}).

Despite our focus on this 'qualitative' notion of fairness, we often find it useful to refer to a numerical value for envy. Given an allocation A, we define

2.1 The Online Setting

We assume that the items arrive in order, one per round, over T total rounds. Let Gt = {g1, g2, . . . gt} be the set of items that have arrived by round t. We denote an allocation of Gt by At = (At1 , . . . , Atn ). An online allocation algorithm outputs an allocation At of the items Gt for each round t ∈ [T ]. When we say that an online algorithm is EF1, we mean that At is EF1 for all t ∈ [T]. We also use ENVYti,j as a shorthand for ENVYi,j(At ). Throughout the paper we use superscripts in the allocations to denote the round and subscripts to denote the agent.

An adjustment is a reallocation of a previously allocated item to a different agent. The number of adjustments needed by an allocation algorithm at round t is the number of adjustments needed to go from At-1 to At . Formally, this can be expressed as ∑i∈[n] |Ati \(At-1 i ∪{gt})|. The sumof the number of adjustments needed across the T rounds is the number of adjustments needed by an online allocation algorithm.

2.2 Informed and Uninformed Algorithms

Intuitively, an informed algorithm 'knows the future', whereas an uninformed algorithms does not. To formalize this, we can think of the setting as a zero-sum two-player game between an algorithm and an adversary that chooses the values of agents for items. The algorithm must maintain EF1 at each round, and may need to use adjustments to that end. The payoffs in the game are the number of adjustments used (which the algorithm tries to minimize, and the adversary tries to maximize).

An informed algorithmmoves second in this game, that is, it first observes the sequence of values chosen by the adversary, and then decides how to allocate. By contrast, an uninformed algorithmmoves first, i.e. the algorithm is announced, and then the instance is constructed by the adversary.

Consequently, to establish a lower bound against an informed algorithm, we must construct a sequence of values that is independent of the algorithm. To establish a lower bound against an uninformed algorithm, we may design an adversary that chooses values for the items that depend on the history.

3 Two Agents

We start with the case of two agents, i.e., n = 2, which often plays a central role in computational fair division. We establish tight bounds on the required number of adjustments, which, in particular, show that informed algorithms are strictly more powerful than their uninformed counterparts.

3.1 Uninformed Algorithms

In order to present our uninformed algorithm for the twoagent case, we first introduce the concept of fractional allocations. Rather than each item being assigned to an agent, a fractional allocation is an n by m matrix X, where n is the number of agents and m the number of items. For each i, j, Xij represents the proportion of gj allocated to agent i. X is constrained so that ∑i∈[n] Xij = 1 for all j and Xij ∈ [0, 1] for all i, j. For a fractional allocation X, we define the number of fractional items as the number of items gj for which there exists an i such that Xij ∈ (0, 1). All other items are whole items. In addition, let Xi denote the ith row of X. Xi can be thought of as the allocation to agent i.

Given an additive valuation function for each agent, we can extend each agent's valuation function to work with fractional items by treating items as if they were divisible, that is, by setting vi(Xi) = ∑j∈[m] Xijvi(gj). Finally, an allocation is proportional if for all i, vi(Xi) ≥ 1n ∑j∈[m] vi(gj).

We now formulate a lemma that will play a central role in the design of our algorithm. While we require only the n = 2 case of the lemma, we establish a more general version, which may be of independent interest. It is related to a result of Bogomolnaia et al. [2017], but our proof is different.

Lemma 3.1. For any proportional fractional allocation X, there exists a proportional allocation Y where Y has at most n-1 fractional items and every whole item in X is allocated to the same agent in Y . Moreover, Y can be computed in polynomial time.

Proof. Consider the bipartite graph B induced by X, where edges are between two vertex sets A,G representing the agents and items. Let there be an edge between (ai, gj) when Xij > 0.

Suppose B has a cycle C of length 2k. Since the graph is bipartite, it contains k agents and k items. Note that whole items cannot be part of a cycle since they have degree 1. For ease of notation, in the following section, take all indices modulo k. Without loss of generality, assume that for each i ∈ [k], (ai, gi) ∈ C and (ai, gi+1) ∈ C.

Now suppose that for each item gi, we were to transfer δi of the item from ai to ai-1. Consider the vector ∆, where ∆i is the change in each agents' value for their own items. We can express ∆ using the following linear equations, where we denote vij = vi(gj):

Let V be the value matrix defined above. We case on whether V is invertible. If it is invertible, then there exists a vector δ such that V · δ = ∆, where ∆ = ⃗1. If V is not invertible, then there exists a non-zero vector δ such that V δ = ⃗0. In either case, we can find a non-zero δ such that V δ = ∆ where for each i, ∆i ≥ 0.

We conclude that, if we choose c appropriately, c · δ will describe a way to transfer items that is implementable (after the transfer, no agent will have a negative fraction of any item) while ensuring that there is at least one Xij that is now equal to 0. After implementing the transfers c · δ, we know that vi( ˆXi) ≥ vi(Xi), where ˆX is the new allocation. Moreover, the number of i, j such that Xij > 0 decreases by at least 1. Thus, the number of edges in the induced graph also decreases by 1.

We repeat the above until no cycles exist, which is guaranteed to happen because the number of edges is strictly decreasing in each step. Let Y be the resulting allocation. Since for each i, vi(Xi) cannot decrease, Y must be proportional.

Any graph with no cycles has at most |V | - 1 edges. So if there are n agents and m items, there are at most n +m- 1 edges. Since each item must have an edge to at least one agent, this implies that the number of fractional items in Y is at most n - 1. Because cycles do not contain any integral items in X, the allocation of each integral item stays the same.

The proof of existence clearly induces a computationally efficient algorithm, which we will refer to as fractional item elimination.

We next present Algorithm 1. We compute a proportional fractional allocation Xt for every round t. To obtain the fractional allocation for items Gt we start with Xt-1 , give a 1 2 fraction of the newly arrived item to each agent and then apply fractional item elimination, as described in the proof of Lemma 3.1. We obtain the actual allocations by rounding fractional items to the agent with the larger portion of the item. Since the (integral) allocation for round t, At , depends only on the value of the first t items, this is an uninformed algorithm.

Algorithm 1 Fractional Item Rounding

input: v1, v2

• 1: for t = 1, . . . , T do
• 2: Let P ∈ R2×t such that

• 3: Let Xt be the allocation found by applying fractional item elimination to P under v1, v2
• 4: At1 ← {gk ∈ Gt : Xt1,k ≥ 12 }
• 5: At2 ← {gk ∈ Gt : Xt2,k > 12 }
• 6: end for
• 7: return [A1 ,A2 , · · · ,AT ]

Theorem 3.2. Algorithm 1 is an uninformed EF1 algorithm for two agents that uses at most T adjustments.

Proof. We first show that the algorithm maintains an EF1 allocation. From Lemma 3.1, in every round t the underlying fractional allocation Xt satisfies proportionality. When n = 2, this implies that Xt is also an envy-free allocation. Let At be the corresponding rounded allocation. Without loss of generality, assume that a1 is assigned the only fractional item gj. In this case, v1(At1 ) ≥ v1(Xt1 ) ≥ v1(Xt2 ) ≥ v1(At2 ) so a1 does not envy a2. In addition, because a1 received gj, we know that in the fractional allocation, a1 received at least half of it and a2 received at most half of it. Therefore,

Thus, the allocation satisfies EF1.

To show that at most T adjustments are needed, note that, on any round t, the only item that could be reallocated is the fractional item in Xt-1 . Over T rounds, this leads to at most T adjustments.

We complement Theorem 3.2 with an asymptotically tight lower bound.

Theorem 3.3. Any uninformed EF1 algorithm must use at least ⌊T/6⌋ adjustments in the worst case, even when there are two agents.

Proof. We construct an adversary strategy that is built around a repeated 6-step sequence. Sequence sj will describe the values for items 6j+1 to 6j+6. For t = 6j+1, 6j+3, 6j+5, the item values are fixed at v1(gt) = v2(gt) = 14j . For steps t = 6j + 2, 6j + 4, 6j + 6, the adversary chooses item values that depend on the allocation of item gt-1. If a1 received gt-1 in At-1 , then for gt, v1(gt) = 14j and v2(gt) = 1 4 14j . The case where agent a2 receives the item is analogous, with the values swapped. The adversary strategy ensures each pair of items is allocated in a way that increases envy. After each sequence, the values of the items increase exponentially to minimize the effect of the allocation of previous items.

To establish the lower bound, we show that any allocation algorithmmust use at least one adjustment for each 6-step sequence to maintain an EF1 allocation at each round. Assume for the sake of contradiction that for some sequence sj, no adjustments are used during that sequence but the allocation at each round in the sequence is EF1.

We first show that for each item pair (6j+1, 6j+2), (6j+ 3, 6j + 4), (6j + 5, 6j + 6), each agent must receive exactly one item from each pair. Let S6j = ENVY6j 1,2 + ENVY6j 2,1 . It holds that

Note that if v is the largest value of any item in At , for At to be EF1, we must have ENVYti,j < v for any i, j. In particular, the largest item value in A6j is 14j-1 so it must hold that ENVY6j 1,2 ≤ 14j-1 . Since ENVY6j 2,1 = S6j - ENVY6j 1,2 , we put the two inequalities together to conclude that

We can show the same for ENVY6j 1,2 . Thus, if both item6j+1 and 6j + 2 are given to the same agent, the allocation would not be EF1 since the other agent would have envy greater than 14j . To show this also holds for the remaining item pairs, note that after the arrival of any item pair, the envy of each agent can only increase.

Finally, we know that one of the agents received at least two of the (less valuable) items 6j+2, 6j+4, 6j+6. Without loss of generality, suppose it was agent 1. Then we have

implying that the allocation is not EF1.

In Table 2, we give an example of a sequence assuming no adjustments.

3.2 Informed Algorithms

We now turn to the setting where the algorithm is informed of the values of all items upfront. Lipton et al. [2004] introduce the envy cycle elimination algorithm for finding EF1 allocations in the offline setting. We describe a modified version of the algorithm that produces an allocation for the offline setting. This allocation has the property that all prefixes of the allocation are also EF1 allocations. This leads to the surprising result that no adjustments are needed to achieve an EF1 allocation at each round when the algorithm is informed.

Algorithm 2 considers the items one at a time in the order they are to arrive and builds an allocation iteratively, with a candidate allocation C t for each round t. We maintain a counter s that keeps track of the last round s in which C s was envy-free. Given a candidate allocation C y and x ≤ y, define C x,y to be the candidate allocation C y when only considering items in Gy \ Gx .

We generate C t by building from C t-1 . In Lines 3-7, we assign the item gt to an arbitrary unenvied agent in C s,t-1 . If this results in both agents envying each other in C s,t , in Line 9, we swap the allocation of items Gt \ Gs in C t . This step guarantees there will always be an unenvied agent when assigning the next item.

The allocation for round t is found by taking the final candidate allocation C T and only considering the first t items. In contrast to Algorithm 1, therefore, the allocation for round t does depend on the values for all T items, which restricts this algorithm to the informed setting.

Algorithm 2 Envy Balancing

input: v1, v2 1: s ← 0,C 0 = (∅, ∅) 2: for t = 1, . . . , T do 3: if a1 is unenvied in C s,t-1 then 4: C t ← (C t-1 1 ∪ {gt},C t-1 2 ) 5: else 6: C t ← (C t-1 1 ,C t-1 2 ∪ {gt}) 7: end if 8: if a1 and a2 envy each other in C s,t then 9: C t ← ((C t1 \ C s,t 1 ) ∪C s,t 2 , (C t2 \ C s,t 2 ) ∪C s,t 1 ) 10: end if 11: if C s,t is envy-free then 12: s ← t 13: end if 14: end for 15: for t = 1, . . . , T do 16: At = (C T 1 ∩Gt ,C T 2 ∩Gt ) 17: end for 18: return [A1 ,A2 , · · · ,AT ]

To analyze the above algorithm, we introduce the following notation. Let A be the allocation given by Algorithm 2. Then define Ax,y to be the allocation A but only considering items in Gy \ Gx , and let ENVYx,y i,j = ENVYi,j(Ax,y ).

Theorem 3.4. Algorithm 2 is an informed EF1 algorithm for two agents that requires no adjustments.

Proof. The algorithm requires no adjustments by design, so we focus on establishing EF1. Consider an arbitrary t ∈ [T]

and let s be the last round before t in which candidate allocation C s is envy-free. Let M1 = max{v1(gj) : gj ∈ As,t 2 }. Let M2 be defined analogously.

We claim that it is sufficient to show that

Indeed, for any t,

By definition of s, ENVYs1,2 ≤ 0 and from Equation (1), ENVYs,t 1,2 ≤ M1. Therefore ENVYt1,2 ≤ M1, and the analogous inequality holds for agent a2.

We therefore focus on proving (1). We will show that ENVYs,t 1,2 ≤M1; the proof of ENVYs,t 2,1 ≤M2 is analogous.

We claim that either As,t = (C s,t 1 ,C s,t 2 ) or As,t = (C s,t 2 ,C s,t 1 ). First, no swaps occur between s and t. To see why, observe that if a swap occurred when generating C x for s < x ≤ t, the candidate allocation would be envy-free since C x consists of C s and C s,x and both portions are now envy free, so s would have been updated to x. Now consider the next candidate allocation C y , for y > t, which is envy free (if any). If a swap occurred on round y, then As,t = (C s,t 2 ,C s,t 1 ) and otherwise As,t = (C s,t 1 ,C s,t 2 ). As a result, it is sufficient to show that |ENVY1,2(C s,t )| ≤M1.

We can show this through induction on t. Suppose that s = t - 1. In this case, the allocation C s,t consists of one item so |ENVY1,2(C s,t )| ≤ M1. Otherwise, we know that s < t - 1. In this case, we can apply the induction hypothesis which tells us that for the same s and some M ′1 ≤ M1, |ENVY1,2(C s,t-1 )| ≤ M ′1 .

Now suppose that ENVY1,2(C s,t-1 ) > 0. a2 is envied so this implies the next item would be given to a1. Since the value of the next item is at most M1, we know that ENVY1,2(C s,t ) ≥ -M1. In addition, the envy can only decrease which means ENVY1,2(C s,t ) ≤ M ′1 ≤ M1.

Otherwise, ENVY1,2(C s,t-1 ) ≤ 0. Since s < t - 1, the allocation C s,t-1 is not envy-free, and so it must be that a1 is envied, and the next item is given to a2. Recalling that ENVY1,2(C s,t-1 ) ≥ -M1, it follows that |ENVY1,2(C s,t )| ≤ M1.

4 More Than Two Agents

In this section we explore the general case of n > 2, whichwe will show-is qualitatively different from the case of two agents.

For our upper bound, consider the round-robin protocol for allocating items. In this protocol, we start with an arbitrary ordering of agents. Following this ordering, each agent takes turns selecting their most preferred item out of the remaining available items, continuing until no items remain.

This protocol is used in the following algorithm for the uninformed setting for more than two agents. For ease of exposition, we will assume here that T is a perfect square.

For each round t, we take the items Gt and divide them into a main pile and side pile. Let q = ⌊t/√T⌋. The first q√T items go into the main pile while the remaining t - q√T go to the side pile. Equivalently, in each round, the new item gt goes into the side pile and every √T rounds, the side pile is emptied and the items are moved to the main pile.

On each round, to generate At , we allocate the main pile using the ordering a1 > a2 > · · · > an and the side pile using the reverse ordering an > · · · > a1, and then merge the two allocations together. We use adjustments to maintain the structure of these allocations at each step and, thus, this algorithm is uninformed.

Algorithm 3 Double Round Robin

input: vi for each agent ai

• 1: M ← ∅, S ← ∅ 2: for t = 1, . . . , T do 3: S ←S ∪ {gt} 4: if t is a multiple of √T then 5: M ←M ∪S 6: S ← ∅ 7: end if 8: AM ← ROUND-ROBIN(M, a1 > · · · > an) 9: AS ← ROUND-ROBIN(S, an > · · · > a1) 10: Let At be the combination of allocations AS and AM 11: end for 12: return [A1 ,A2 , · · · ,AT ]

Theorem 4.1. Algorithm 3 is an uninformed EF1 algorithm that requires O(T 3/2 ) adjustments.

Proof. To see why the allocation on each round is EF1, we make a few observations about the round-robin protocol. Let B be an ordering and let ai >B aj denote that ai chooses before aj in that ordering. One can easily see that if we use round-robin to allocate some set of items G, then for any pair of agents ai, aj, ai will envy aj by at most one item. Furthermore, if ai >B aj, then ai will not envy aj. To show this, note that when ai >B aj, we can match each item that aj receives to a distinct item that ai receives such that ai prefers his item to the item it is matched with. Otherwise, when aj >B ai, we can remove the first item aj receives and then proceed with matching.

Since the main and side piles are allocated using reversed orderings, ai envies aj in one allocation only if ai does not envy aj in the other allocation. In both allocations, we know ai envies aj by at most one item, so after combining the allocations, ai still envies aj by at most one item.

Now, we show that this algorithm uses at most O(T 3/2 ) adjustments. If we consider successive rounds, the main pile will only change every √T rounds. The first change uses at most √T adjustments, the second one uses at most 2√T , and so on, until the last change that uses T adjustments, for a total of (at most) T 3/2 adjustments. Meanwhile, the side pile can be completely reallocated every round, but reaches size at most √T . Therefore, the total number of adjustments needed to maintain the allocation of the side pile over T rounds can be upper-bounded by T 3/2 . Overall, this leads to at most 2T 3/2 adjustments.

In contrast to the case of two agents, where informed algorithms can achieve EF1 at each round without adjustments, when n ≥ 3, a linear number of adjustments is inevitable.

Theorem 4.2. For n ≥ 3, any informed EF1 algorithm must use at least Ω(T) adjustments in the worst case.

The theorem's proof is relegated to the full version. 1

5 Discussion

While our results for the case of two agents are tight-and show a stark separation between informed and uninformed algorithms-our bounds for the general case are not. The most interesting open question is whether there is a separation between informed and uninformed algorithms in the general case. Our results allow for the possibility of informed EF1 algorithms that require O(T) adjustments, and a lower bound of Ω(T 3/2 ) on the adjustments required by uninformed algorithms. However, we conjecture that O(T) adjustments are sufficient even for uninformed algorithms. In fact, we can prove this in the special case where n is constant, and each vi(j) can only take a constant number of values; see Appendix B (and Footnote 1) for details.

In addition, our results focus on achieving EF1 at each round, and this fairness guarantee may not be sufficient to ensure truly satisfying outcomes. For example, a number of recent papers aim to guarantee EF1 and Pareto efficiency simultaneously [Caragiannis et al., 2016; Barman et al., 2018]. However, as noted by Benad`e et al. [2018], it is crucial to first understand fairness constraints in isolation; if the requirements were more stringent, our negative results would immediately carry over, while our positive results would potentially serve as building blocks for more elaborate algorithms.

Acknowledgments

This work was partially supported by the National Science Foundation under grants IIS-1350598, IIS-1714140, CCF1525932, and CCF-1733556; by the Office of Naval Research under grants N00014-16-1-3075 and N00014-17-1-2428; and by a Sloan Research Fellowship and a Guggenheim Fellowship.

1 The full version of this paper can be found at http://procaccia. info/papers/adjustments.pdf.