# fair_allocation_with_diminishing_differences__d96c40a1.pdf

Journal of Artiﬁcial Intelligence Research 67 (2020) 471 507 Submitted 12/2018; published 03/2020

Fair Allocation with Diminishing Diﬀerences

Erel Segal-Halevi erelsgl@gmail.com Ariel University, Ariel 40700, Israel

Avinatan Hassidim avinatanh@gmail.com Bar-Ilan University, Ramat-Gan 5290002, Israel

Haris Aziz haris.aziz@unsw.edu.au UNSW Sydney and Data61 CSIRO, Australia

Ranking alternatives is a natural way for humans to explain their preferences. It is used in many settings, such as school choice, course allocations and residency matches. Without having any information on the underlying cardinal utilities, arguing about the fairness of allocations requires extending the ordinal item ranking to ordinal bundle ranking. The most commonly used such extension is stochastic dominance (SD), where a bundle X is preferred over a bundle Y if its score is better according to all additive score functions. SD is a very conservative extension, by which few allocations are necessarily fair while many allocations are possibly fair. We propose to make a natural assumption on the underlying cardinal utilities of the players, namely that the diﬀerence between two items at the top is larger than the diﬀerence between two items at the bottom. This assumption implies a preference extension which we call diminishing diﬀerences (DD), where X is preferred over Y if its score is better according to all additive score functions satisfying the DD assumption. We give a full characterization of allocations that are necessarily-proportional or possibly-proportional according to this assumption. Based on this characterization, we present a polynomial-time algorithm for ﬁnding a necessarily-DD-proportional allocation whenever it exists. Using simulations, we compare the various fairness criteria in terms of their probability of existence, and their probability of being fair by the underlying cardinal valuations. We ﬁnd that necessary-DD-proportionality fares well in both measures. We also consider envy-freeness and Pareto optimality under diminishing-diﬀerences, as well as chore allocation under the analogous condition increasing-diﬀerences.

1. Introduction

Algorithms for the fair assignment of indivisible items diﬀer in the kind of information they require from the users. Some algorithms require the users to rank bundles of items, i.e., report a total order among the bundles. Examples are the Decreasing Demand procedure of Herreiner and Puppe (2002), the Approximate-CEEI procedure of Budish (2011), and the two-agent Undercut procedure of Brams, Kilgour, and Klamler (2012). The computational and communicational burden might be large, since the number of bundles is exponential in the number of items. Other algorithms require the users to evaluate individual items, i.e., supply a numeric monetary value for each item. Such algorithms are often termed cardinal. They tend

c 2020 AI Access Foundation. All rights reserved.

Segal-Halevi, Hassidim, Aziz

to assume that the users valuations are additive, so that the value of a bundle can be calculated by summing the values of the individual items. Examples are the Adjusted Winner procedure of Brams and Taylor (2000), the approximate-maximin-share procedures of Procaccia and Wang (2014), Amanatidis, Markakis, Nikzad, and Saberi (2017), Barman and Krishnamurthy (2017), Ghodsi, Haji Aghayi, Seddighin, Seddighin, and Yami (2018) and the Maximum Nash Welfare procedure of Caragiannis et al. (2019). In this setting, the communication is linear in the number of items, but the mental burden may still be large, since assigning an exact monetary value to individual items is not easy. This is especially true when items are valued for personal reasons (such as when dividing inheritance) and do not have a market price. This paper focuses on a third class of algorithms, which only require the users to rank individual items, i.e., report a total order among items. Such algorithms are often termed ordinal. Ordinal algorithms are ubiquitous in mechanism design. They are often used in realworld applications, such as the National Residency Matching Program (Roth & Peranson, 1997; Ashlagi, Braverman, & Hassidim, 2014), school choice applications (Abdulkadiroglu & S onmez, 2003), and university admittance (Hassidim, Romm, & Shorrer, 2016, 2017). One reason for this is that it is relatively easy for people to state ordinal preferences. Another reason is that in some legacy systems, the input procedure asks for ordinal preferences only. Often, the designer can change the allocation mechanism, but cannot change the input procedure, as agents do not want to learn new ways to enter their input into the system. Ordinal algorithms are also common in AI and in fair division. Examples are the AL twoagent procedure of Brams, Kilgour, and Klamler (2014), the optimal-proportional procedure of Aziz, Gaspers, Mackenzie, and Walsh (2015), picking-sequence procedures (Brams & Kaplan, 2004; Bouveret & Lang, 2011) and the envy-free procedures of Bouveret, Endriss, and Lang (2010). Such algorithms often assume that the agents preferences are implicitly represented by an additive utility function, which is not known to the algorithm. This creates ambiguity in the agents bundle rankings. For example, if an agent ranks four items as w x y z, then, based on additivity, the algorithm can know that e.g. {w, x} {y, z} and {w, y} {x, z}, but cannot know the relation between {w, z} and {x, y}. Algorithms cope with this problem in several ways.

1. Necessary-fairness criteria. An allocation is called necessarily-fair if it is fair for all additive utility proﬁles consistent with the reported item-rankings. Here, fair may be substituted by any fairness criterion, such as envy-freeness or proportionality, as well as Pareto-eﬃciency. Necessary fairness is a strong requirement, which is not always satisﬁable. For example, the AL procedure ﬁnds a necessarily-envy-free allocation, but only for two agents, and even then, it might need to discard some of the items.

2. Possible-fairness criteria. An allocation is called possibly-fair if it is fair for at least one additive utility proﬁle consistent with the reported item-rankings. Again, fair may be substituted by proportional or envy-free or Pareto-eﬃcient. Possible fairness is a weak criterion; algorithms that only return possibly-fair allocations might be considered unfair by users whose actual utility function is diﬀerent.

Fair Allocation with Diminishing Differences

3. Scoring rules. A scoring rule is a function that maps the rank of an item to a numeric score. A common example is the Borda scoring rule (Young, 1974), where the least desired item has a score of 1, the next item has a score of 2, and so on. The score of a bundle is the sum of the scores of its items. It is assumed that all agents have the same scoring function. This means that, even though agents may rank items diﬀerently, the mapping from the ranking to the numeric utility function is the same for all agents (Bouveret & Lang, 2011; Kalinowski, Narodytska, & Walsh, 2013; Darmann & Klamler, 2016),(Baumeister et al., 2017). This strong assumption weakens the fairness guarantee. The allocation may appear unfair to agents whose actual scoring rule is diﬀerent.

1.1 Contribution

The present paper suggests an alternative between the strong guarantee of necessary-fairness and the weak guarantee of possible-fairness and scoring-rule-fairness. We assume that people are more sensitive about which of their high-valued items they receive than about which of their low-valued items they receive. Speciﬁcally, we assume that the utility-diﬀerence between the best item and the second-best item is at least as large as the utility between the second-best and the third-best, and so on. We call this assumption Diminishing Diﬀerences (DD). The DD assumption is satisﬁed by the Borda scoring rule, as well as by many other scoring rules, as well as by lexicographic preferences. The DD assumption is supported by a survey that was recently reported by Bronfman et al. (2015b) in the context of matching medical students to hospitals for internships:

The students were asked to ﬁll surveys, to assert the diﬀerence between the ﬁrst and the second place, the second and the third place, and so on. Based on the surveys results, more weight was given to the diﬀerence between ﬁrst and second place than to the diﬀerence between the ninth and the tenth.

Based on the DD assumption, we formalize several fairness criteria. We call an allocation necessarily-DD-fair (NDD-fair) if it is fair according to all additive utility proﬁles satisfying the DD assumption, and possibly-DD-fair (PDD-fair) if it is fair according to at least one additive utility proﬁle satisfying the DD assumption. Again, fair may be substituted by envy-free or proportional or Pareto-eﬃcient. The following implications are obvious for any fairness criterion:

necessarily-fair = NDD-fair = PDD-fair = Possibly-fair

In other words, the DD-fairness criteria are intermediate in strength between necessaryfairness and possible-fairness. A formal deﬁnition of these criteria appears in Section 3. The ﬁrst question of interest is to decide, given an item ranking and two bundles, whether the NDD or the PDD relation holds between these bundles. We prove characterizations of the NDD and PDD set relations that provide linear-time algorithms for answering these questions. Using these algorithms, it can be decided in polynomial time whether a given allocation is NDD-proportional or NDD-envy-free (Section 4). Next, we prove a necessary and suﬃcient condition for the existence of an NDDproportional (NDDPR) allocation. Essentially, an NDDPR allocation exists if and only if it is possible to:

Segal-Halevi, Hassidim, Aziz

(a) give all agents the same number of items, and (b) give each agent his/her best item. The proof is constructive and presents a simple linear-time algorithm for ﬁnding an NDDPR allocation whenever it exists (Section 5). To appreciate the diﬀerence between NDD-fairness and necessary-fairness, contrast the condition (b) above with the so-called Condition D of Brams et al. (2014), which is necessary and suﬃcient for the existence of a necessarily-proportional (Nec PR) allocation for two agents. For Nec PR, it is required that for every odd integer k {1, 3, . . . , 2l 1} (where the number of items is 2l), the agents have a diﬀerent set of k best items; condition (b) for NDDPR is essentially Condition D limited to k = 1. Intuitively, NDDPR allocations are more likely to exist than Nec PR allocations. On the ﬂip side, an NDDPR allocation is more likely to be considered unfair by some agents (whose utility functions do not satisfy the DD assumption) than a Nec PR allocation. To assess the magnitude of these two opposing eﬀects, we conduct a simple simulation experiment. We ﬁnd that the former eﬀect is substantial: with randomly-generated utility functions (with partially-correlated utilities), NDDPR allocations exist in between 20% and 40% more instances than Nec PR allocations. In contrast, the latter eﬀect is much less substantial: when there are suﬃciently many items, our simple algorithm for ﬁnding NDDPR allocations almost always yields an allocation that is proportional according to the cardinal utilities. This indicates that NDDPR is appealing as a normative fairness criterion (Section 6). While our main interest is in NDD-proportionality, we brieﬂy present several extensions of our model. First, instead of proportionality, we study the stronger property of envy-freeness (EF). Since every EF allocation is PR, every NDDEF allocation is NDDPR. Therefore, conditions (a) and (b) above are still necessary to NDDEF existence. When there are n = 2 agents, EF is equivalent to PR, so NDDPR is equivalent to NDDEF and conditions (a) and (b) are also suﬃcient, and when they are satisﬁed, an NDDEF allocation can be found in linear time. EF and PR diverge when there are three or more agents. When n = 3, we show that an NDDEF allocation might not exist even if conditions (a) and (b) hold. We then study the computational problem of deciding whether an NDDEF allocation exists. Since conditions (a) and (b) are necessary for NDDEF, the decision problem is trivial whenever the number of items is not an integer multiple of the number of agents, since then condition (a) is violated. It is also trivial if the number of items equals the number of agents, since in this case, condition (b) is both necessary and suﬃcient. Therefore the ﬁrst non-trivial case is when the number of items is twice the number of agents. We prove that the decision problem is NP-hard already in this case (Section 7). Second, we study Pareto-eﬃciency (PE). The DD assumption has a substantial eﬀect on fairness criteria: NDD-fair allocations are easier (in terms of existence) than necessary-fair allocations and PDD-fair allocations are harder than possibly-fair allocations. Interestingly, the DD assumption does not have this eﬀect on PE. We show that NDD-PE is equivalent to necessarily-PE and PDD-PE is equivalent to possibly-PE. So the DD assumption does not lead to a new eﬃciency criterion (Section 8). Third, we study the allocation of chores items with negative utilities. We assume that people care more about not getting the worst chore than about getting the best chore; this naturally leads to the condition of increasing diﬀerences (ID). While the basic def-

Fair Allocation with Diminishing Differences

initions and lemmas for the DD relations have exact analogues for the ID relations, our characterization for existence of NDDPR allocations of goods has no direct analogue for NIDPR allocation of chores (Appendix A). Finally, we compare the Diminishing-Diﬀerences assumption to another natural assumption which we call Binary. It is based on the assumption that each agent only cares about getting as many as possible of his k best items, where k is an integer that may be diﬀerent for diﬀerent agents. We show that, while the number of utility functions that satisfy this assumption (for a given preference relation) is much smaller than the number of DD utility functions, it does not lead to new fairness criteria: necessary-binary-fairness is equivalent to necessary-fairness and possible-binary-fairness is equivalent to possible-fairness (Appendix B).

1.2 Related Work

Extending preferences over individual items to sets of items is a natural and principled way of succinctly encoding preferences (Barber a, Bossert, & Pattanaik, 2004). One of the most common set extensions is stochastic dominance (SD). It was developed for a diﬀerent but related problem extending preferences over individual outcomes to lotteries over outcomes. If X, Y are lotteries, then X SD Y iﬀE[u(X)] E[u(Y )] for every weaklyincreasing utility function u (Hadar & Russell, 1969; Brandt, 2017). In the context of fair item allocation, SD leads to the notions of necessary-fairness and possible-fairness (Aziz et al., 2015). Other common extensions are downward-lexicographic (DL) and upwardlexicographic (UL) (Cho, 2012; Bouveret et al., 2010; Nguyen, Baumeister, & Rothe, 2015). The diminishing-diﬀerences extension, which is the focus of this paper, is quite natural but has not been formalized in prior work. The most similar extension that we are aware of is the second-order stochastic dominance (SSD). If X, Y are lotteries, then X SSD Y iﬀE[u(X)] E[u(Y )] for every utility function u which is weakly-increasing and weaklyconcave (Hadar & Russell, 1969). In the context of item assignment, weak concavity is equivalent to increasing diﬀerences agents care more about not getting the worst item than about getting the best item. Increasing diﬀerences make sense in fair division of chores (Aziz, Rauchecker, Schryen, & Walsh, 2017). We analyze this assumption in Appendix A. Bronfman, Alon, Hassidim, and Romm (2015a), Bronfman et al. (2015b) present a mechanism for matching students to hospitals for internships, where the students report rankings of the hospitals. Initially, using simulations of random-serial-dictatorship, each student is assigned a vector of probabilities for each hospital. To improve the eﬃciency of the random assignment, probabilities are traded between students with diﬀerent rankings. Ensuring that each trade is mutually beneﬁcial requires an assumption on the students cardinal utilities. Based on the survey quoted in the introduction, it is assumed that the utility each student assigns to each hospital is the square of its Borda score, which is a special case of a DD utility function. Besides fair division, set extensions have been applied for committee voting and multiwinner elections (Aziz, Lang, & Monnot, 2016; Faliszewski, Skowron, Slinko, & Talmon, 2017; Peters, 2018; Darmann, 2019; Faliszewski, Skowron, Slinko, & Talmon, 2019) and social choice correspondences (Kennai & Peleg, 1984; Bossert, 1989, 1995; Barber a, Dutta, & Sen, 2001; Brandt & Brill, 2011; Brandl, Brandt, Geist, & Hofbauer, 2015). Recently,

Segal-Halevi, Hassidim, Aziz

set extensions have also been used in philosophic works on ethics. Suppose an ethical agent has to choose between several actions. He/she is unsure between two ethical theories, each of which ranks the actions diﬀerently. Due to this uncertainty about theories, each action can be considered a lottery. Using the SD set extension, Aboodi (2017) and Tarsney (2018) show that, in some cases, the agent can choose an ethically-best action despite the ethical uncertainty. In social choice theory, it is common to study restricted domains of preference proﬁles, such as single-peaked (Demange, 1982; Bade, 2019), single-crossing (Karlin, 1968; Gans & Smart, 1996; Puppe & Slinko, 2019), top-monotonic (Magiera & Faliszewski, 2019) or level-r-consensus (Mahajne, Nitzan, & Volij, 2015; Nitzan, Nitzan, & Segal-Halevi, 2018). Many problems are much easier to solve in such restricted domains than in the domain of all preferences (Elkind & Lackner, 2014; Elkind, Lackner, & Peters, 2017). The present paper focuses on a restriction to preferences satisfying the DD assumption, which has not been studied so far. Many works on fair allocation of indivisible items look for allocations that are only approximately-fair, for example, envy-free up to at most one item (Lipton, Markakis, Mossel, & Saberi, 2004; Budish, 2011; Suksompong & Segal-Halevi, 2019), or allow to cut a small number of items (Brams & Taylor, 2000; Sandomirskiy & Segal-Halevi, 2019). In contrast, we are interested in allocations that are fair without approximations, and do not cut any item. Naturally, such allocations do not always exist, so we are interested in ﬁnding conditions under which they exist.

2. Preliminaries

There is a set N of agents with n = |N|. There is a set M of distinct items with m = |M|. A bundle is a set of items. A multi-bundle is a multi-set of items, i.e., it may contain several copies of the same item.1

An allocation X is a function that assigns to each agent i a bundle Xi, such that M = X1 Xn and the Xi-s are pairwise-disjoint. Each agent i N has a strict ranking i on items. Each agent may also have a utility function ui on (multi-)bundles. When we deal with a single agent, we often omit the subscript i and consider an agent with ranking and utility-function u. All utility functions considered in this paper are strictly positive and additive, so the utility of a (multi-)bundle is the sum of the utilities of the items in it. A utility function u is consistent with if for every two items x, y:

u({x}) > u({y}) x y

We denote by U( ) the set of additive utility functions consistent with . Given a vector of n rankings 1, . . . , n, we denote by U( 1, . . . , n) the set of vectors of additive utility functions u = (u1, . . . , un) such that for all i N, ui is consistent with i. The following deﬁnition is well-known (see, for example, Aziz et al. (2015)):

1. Multi-bundles are used mainly as a technical tool during the proofs; our primary results concern simple bundles, that contain (at most) a single copy of each item.

Fair Allocation with Diminishing Differences

Deﬁnition 2.1. Given a ranking and two (multi-)bundles X, Y :

X Nec Y u U( ): u(X) u(Y ).

X Pos Y u U( ): u(X) u(Y )

Given a strict ranking , we assign to each item x M a level, denoted Lev(x), such that the level of the best item is m, the level of the second-best item is m 1, etc. (this is also known as the Borda score of the item). We deﬁne the level of a multi-bundle as the sum of the levels of the items in it:

Lev(X) := X

where all copies of the same item have the same level. In this work we assume that the agents truthfully report their rankings to the algorithm; we leave the issue of strategic manipulations to future work.

3. The Diminishing-Diﬀerences Property

We deﬁne our new concept of diminishing diﬀerences (DD) in three steps: ﬁrst, we deﬁne the set of DD utility functions (Deﬁnition 3.1). Based on this, we deﬁne the necessary-DD and possible-DD relations (Deﬁnition 3.3). Based on this, we deﬁne the NDD-fairness and PDD-fairness criteria (Deﬁnition 3.5).

Deﬁnition 3.1. Let be a preference relation and u a utility function consistent with . We say that u has the Diminishing Diﬀerences (DD) property if, for every three items with consecutive levels x3 x2 x1 such that Lev(x3) = Lev(x2) + 1 = Lev(x1) + 2, it holds that u(x3) u(x2) u(x2) u(x1). We denote by UDD( ) the set of all DD utility functions consistent with . Given n rankings 1, . . . , n, we denote by UDD( 1, . . . , n) the set of all vectors of DD utility functions u = (u1, . . . , un), such that for all i N, ui is consistent with i.

The Borda utility function consistent with is a member of UDD( ). Another member is the lexicographic utility function Lex(x) := 2Lev(x), by which bundles are ordered by whether they contain the best item, then by whether they contain the second-best item, etc. An alternative characterization of UDD is given by the following lemma.

Lemma 3.2. u UDD( ) iﬀ, for every four items x2, y2, x1, y1 with x2 x1 and y2 y1 and x2 = y2 and x1 = y1:

u(x2) u(y2) Lev(x2) Lev(y2) u(x1) u(y1) Lev(x1) Lev(y1) (*)

Proof. DD = (*): Let k := |Lev(x2) Lev(y2)|. Then there are k + 1 items whose level is between x2 and y2 (inclusive). Denote these items by zj for j {0, . . . , k}, such that

Segal-Halevi, Hassidim, Aziz

zk zk 1 . . . z0, and either zk = x2, z0 = y2 (if x2 y2) or vice versa: zk = y2, z0 = x2 (if y2 x2). Then, the left-hand side of (*) can be written as:

u(zk) u(z0)

Pk j=1 u(zj) u(zj 1)

This is an arithmetic mean of the k diﬀerences u(zj) u(zj 1), for j {1, . . . , k}. Similarly, let k := |Lev(x1) Lev(y1)|. The right-hand side of (*) is an arithmetic mean of k utility-diﬀerences of items with level between x1 and y1. By assumption x2 x1 and y2 y1, so by DD, to each diﬀerence in the left-hand side corresponds a weakly-smaller diﬀerence in the right-hand side. Therefore, the arithmetic mean in the left-hand side is weakly larger. (*) = DD: in (*), let y2 be the element ranked immediately below x2, let x1 = y2, and let y1 be the element ranked immediately below x1. Then the denominators both equal 1, and u satisﬁes the DD deﬁnition.

Deﬁnition 3.3. Given a ranking and two (multi-)bundles X, Y :

X NDD Y u UDD( ): u(X) u(Y )

X PDD Y u UDD( ): u(X) u(Y )

Remark 3.4. Comparing Deﬁnitions 2.1 and 3.3, it is clear that:

X Nec Y = X NDD Y = X PDD Y = X Pos Y

We now deﬁne the main fairness criterion that we will investigate in this paper proportionality.

Deﬁnition 3.5. Given a vector u of utility functions, an allocation X is called proportional for u if i N : n ui(Xi) ui(M). Given item rankings 1, . . . , n, an allocation X is called:

necessary-DD-proportional (NDDPR) if it is proportional for all u UDD( 1, . . . , n ).

possible-DD-proportional (PDDPR) if it is proportional for at least one u UDD( 1 , . . . , n).

For comparison, recall that an allocation X is called:

necessarily-proportional (Nec PR) if it is proportional for all u U( 1, . . . , n).

possibly-proportional (Pos PR) if it is proportional for at least one u U( 1, . . . , n).

Like in Remark 3.4, it is clear that necessarily-proportionality implies NDD-proportionality implies PDD-proportionality implies possibly-proportionality. We now give alternative characterizations of NDDPR and PDDPR in terms of the NDD and PDD relations. For every integer k and bundle Xi, deﬁne k Xi as the multi-bundle in which each item of Xi is copied k times. Proportionality can be deﬁned by comparing, for each agent i, the bundle Xi copied n times, to the bundle of all items M.

Fair Allocation with Diminishing Differences

Lemma 3.6. Given item rankings 1, . . . , n: (a) An allocation X is NDDPR iﬀ i N : n Xi NDD i M. (b) An allocation X is PDDPR iﬀ i N : n Xi PDD i M.

Proof. Let P(i, u) be the proportionality predicate n ui(Xi) ui(M) . (a) The NDDPR deﬁnition is For all DD utility proﬁles u, for all agents i, P(i, u). The right-hand side is For all agents i, for all DD utility proﬁles u, P(i, u). These statements are logically equivalent for any predicate P. (b) The PDDPR deﬁnition is There exists a DD utility proﬁle u for which, for all agents i, P(i, u). The right-hand side is: For all agents i, there exists a DD utility proﬁle u such that P(i, u). The former deﬁnition logically implies the latter (for any predicate P). It remains to prove that the latter implies the former. Indeed, suppose that for every agent i N, there exists ui UDD( i) such that ui(n Xi) ui(M). By additivity, ui(n Xi) = n ui(Xi), so for every i, n ui(Xi) ui(M). Therefore the allocation X is proportional by the proﬁle (u1, . . . , un) UDD( 1, , n).

4. Characterizing NDD and PDD Relations

As a ﬁrst step in ﬁnding DD-fair allocations among many agents, we study the NDD and PDD relations for a single agent. We are given a preference relation on items and two multi-bundles X, Y , and have to decide whether X NDD Y and/or X PDD Y . We begin by proving a convenient characterization of the NDD relation. For the characterization, we order the items in each multi-bundle by decreasing level, so X = {x 1, . . . , x |X|} where x 1 . . . x |X| (the order between diﬀerent copies of the same item is arbitrary).2 For each k |X| we deﬁne X k as the k best items in X, i.e., X k := {x 1, . . . , x k}.

Theorem 4.1. Given a ranking and two (multi-)bundles X, Y , X NDD Y if and only if both of the following conditions hold:

(i) |X| |Y | and

(ii) for each k {1, . . . , |Y |}: Lev(X k) Lev(Y k).

Theorem 4.1 implies that there is a polynomial-time algorithm to check whether X NDD

Y ; see Algorithm 1.

Remark 4.2. Contrast this characterization with the following characterization of Nec

from Aziz et al. (2015). X Nec Y iﬀ:

(i) |X| |Y | and

(ii) for each k {1, . . . , |Y |}: Lev(x k) Lev(y k).

Before proving Theorem 4.1, we give some examples.

2. We use negative indices so that the order of indices is the same as the order of levels.

Segal-Halevi, Hassidim, Aziz

Algorithm 1 Checking the NDD relation Input: X, Y M, and a ranking of the items in M. Output: Yes if X NDD Y ; No otherwise.

if |X| < |Y | then

return No {condition (i) is violated} end if Order the items in X and Y by decreasing order of preference, such that x 1 x |X| and y 1 y |Y |. Initialize Total Level Diﬀ:= 0. for j = 1, . . . , |Y | do

Level Diﬀ:= [Lev(x j) Lev(y j)] Total Level Diﬀ+= Level Diﬀ if Total Level Diﬀ< 0 then

return No {condition (ii) is violated} end if end for return Yes

Example 4.3. Suppose the set of items is M = {1, . . . , 8} and we are given a preferencerelation 8 1, so that each item is represented by its level. Consider the following two bundles:

X = {8, 4, 2} Y = {7, 6}

Note that |X| > |Y |, X is lexicographically-better than Y , and even the Borda score of X is higher. However, the level of X 2 (the two best items in X) is only 12 while the level of Y 2 is 13. Hence, by Theorem 4.1, X NDD Y . Indeed, X is not better than Y according to the DD utility function usquare(x) := Lev(x)2, since usquare(X) = 84 < 85 = usquare(Y ).

Example 4.4. Consider the following two bundles:

Z = {8, 5} Y = {7, 6}

Now the conditions of Theorem 4.1 are satisﬁed: |Z| |Y | and Lev(Z 1) Lev(Y 1) and Lev(Z 2) Lev(Y 2). Hence the theorem implies that Z NDD Y . In contrast, condition (ii) in Remark 4.2 is not satisﬁed since Lev(z 2) < Lev(y 2). Therefore Z Nec Y . Indeed, Z is worse than Y by some non-DD utility functions, for example, by usqrt(x) := p

Lev(x), since usqrt(Z) 5.06 < 5.09 usqrt(Y ).

Proof of Theorem 4.1.

NDD = (i) and (ii): We assume that either (i) or (ii) is violated and prove that X NDD Y , i.e., there is a utility function u UDD( ) such that u(X) < u(Y ).

(i) If (i) is violated then |Y | > |X|. Deﬁne u as:

u(z) := m|Y | + Lev(z) for all z M

Fair Allocation with Diminishing Differences

It has diminishing-diﬀerences since the diﬀerence in utilities between items with adjacent ranks is 1.

The term m|Y | is so large that the utility of a bundle is dominated by its cardinality. Formally, for every item x, m|Y | < u(x) m + m|Y |, so:

u(X) |X| (m + m|Y |)

< m|Y | + |X| m|Y | since |X| < |Y |

= (|X| + 1) m|Y |

|Y | m|Y | since |X| < |Y |

Hence X NDD Y .

(ii) If (ii) is violated then for some k 1, Lev(Y k) > Lev(X k). Let k be the smallest integer that satisﬁes this condition; hence y k x k. Let C := Lev(x k) 1 and deﬁne u as:

( Lev(z) for z x k [Lev(z) C] m|X| for z x k

so the utilities of the items worse than x k are 1, 2, . . . , C, and the utilities of x k and the items better than it are m|X|, 2m|X|, 3m|X|, . . ..

This u has diminishing-diﬀerences, since the diﬀerence in utilities between adjacent items ranked weakly above x k is m|X|, the diﬀerence between x k and the nextworse item is less than m|X| and more than 1, and the diﬀerence between adjacent items ranked below x k is 1.

The term m|X| is so large that the utility of a bundle is dominated by the level of its items that are weakly better than x k. Formally:

u(X) = u({x 1, . . . , x k}) + u({x (k+1), . . . , x |X|})

= m|X| [Lev({x 1, . . . , x k}) k C] + Lev({x (k+1), . . . , x |X|})

The assumption Lev(Y k) > Lev(X k) implies that Lev(X k) Lev(Y k) 1. Hence the leftmost term is at most m|X| [Lev({y 1, . . . , y k}) 1 k C]. Since the level of an item is at most m, the rightmost term is less than m|X|. Hence:

u(X) < m|X| [Lev({y 1, . . . , y k}) 1 k C] + m|X|

= m|X| [Lev({y 1, . . . , y k}) k C]

= u(Y k) since y 1, . . . , y k x k u(Y ).

Hence X NDD Y .

(i) and (ii) = NDD: We assume that |X| |Y | and that k {1, . . . , |Y |} : Lev(X k) Lev(Y k). We consider an arbitrary utility function u UDD( ) and prove

Segal-Halevi, Hassidim, Aziz

that k {1, . . . , |Y |} : u(X k) u(Y k). This will imply that u(X) u(Y ), so that X NDD Y . During the proof, we assume that for every j {1, . . . , |Y |}: x j = y j. This does not lose generality since if for some j we have x j = y j, we can just remove this item from both X and Y ; this changes neither the assumptions nor the conclusion. In the proof, we use the following notation.

lk := Lev(x k) Lev(y k).

Lk := Lev(X k) Lev(Y k) = Pk j=1 lk.

uk := u(x k) u(y k).

rk := uk/lk.

Uk := u(X k) u(Y k) = Pk j=1 uk = Pk j=1 rklk.

In this notation, our assumptions are that k {1, . . . , |Y |} : lk = 0 and Lk 0. We have to prove that k {1, . . . , |Y |} : Uk 0. Suppose we walk on the graph of Lk (see Figure 1). When we move from Lj 1 to Lj, we make lj steps (upwards if lj > 0 or downwards if lj < 0). By assumption, the graph is always above zero. Hence, an earlier upwards step corresponds to every downwards step. Suppose we walk simultaneously on the graph of Uk. When we move from Uj 1 to Uj, we make a step of size uj = rjlj, or equivalently, lj steps of size rj (upwards if lj > 0 or downwards if lj < 0). Hence, to every step of size 1 on the graph of Lk corresponds a step of size rj on the graph of Uk (see Figure 1). Now, we claim that rk is a weakly-decreasing function of k. Particularly, we claim that i < j implies ri rj. To prove the claim we apply Lemma 3.2. Since u UDD( ), the lemma is applicable to u. Since i < j, we have x i x j and y i y j. By assumption, we have x j = y j and x i = y i. Therefore, the lemma implies:

u(x i) u(y i) Lev(x i) Lev(y i) u(x j) u(y j) Lev(x j) Lev(y j)

ui/li uj/lj ri rj.

Hence, to every step downwards of size rj on the graph of Uk corresponds an earlier step upwards, and its size is at least rj. Therefore, the graph of Uk, too, always remains above 0.

Our next theorem gives an analogous characterization of the PDD relation.

Theorem 4.5. Given a ranking and two (multi-)bundles X, Y , Y PDD X if and only if at least one of the following conditions hold:

(i) |Y | > |X|, or

(ii) for some k {1, . . . , |Y |}: Lev(Y k) > Lev(X k), or

Fair Allocation with Diminishing Differences

Figure 1: An illustration of the graphs of Lk and Uk in the proof of Theorem 4.1.

(iii) Lev(Y ) Lev(X).

(i) or (ii) or (iii) = PDD: If (i) holds, then u(Y ) u(X) by the DD function u(z) in the proof of Theorem 4.1(i). Similarly, if (ii) holds, then u(Y ) u(X) by the DD function u(z) in the proof of Theorem 4.1(ii). If (iii) holds, then u(Y ) u(X) by the DD function u(z) := Lev(z). PDD = (i) or (ii) or (iii): We assume that none of the three conditions holds, and prove that Y PDD X. So we have: c (i) |X| |Y |, and d (ii) k {1, . . . , |Y |} : Lev(X k) Lev(Y k), and d (iii) Lev(X) > Lev(Y ). We consider an arbitrary function u UDD( ), and show that u(X) > u(Y ). During the proof, we denote K := |Y |. We use the notation of the proof of Theorem 4.1. By conditions c (i) and d (ii), the graph of Lk is always weakly above zero. Hence, to every step downwards corresponds an earlier step upwards. As in the proof of Theorem 4.1, the graph of Uk is always weakly above zero, so k {1, . . . , K} : u(X k) u(Y k). Now we consider two cases. Case #1: the graph of Lk ends strictly above zero. Hence, there exists a step upwards with no corresponding step downwards. Therefore the graph of Uk, too, ends strictly above zero. Therefore, we have u(X K) > u(Y K). Since u(X) u(X K) and Y K = Y , we get u(X) > u(Y ).

Segal-Halevi, Hassidim, Aziz

Case #2: the graph of Lk ends at zero. So we have Lev(X K) = Lev(Y K) = Lev(Y ). Now, d (iii) says that Lev(X) > Lev(Y ); this means that X must contain items that are not in X K. We assume that utilities are strictly positive, so u(X) > u(X K). Since u(X K) u(Y K) and Y K = Y , we get u(X) > u(Y ). The same is true for every u UDD( ). Hence Y PDD X.

Theorem 4.5 implies that there is a polynomial-time algorithm to check whether X PDD

Y ; the algorithm is similar to Algorithm 1 and we omit it. Using Theorem 4.5, we illustrate the diﬀerence between PDD-fairness and possiblefairness.

Example 4.6 (PDD-fairness vs. possible-fairness). There are m = 2l items, for some l 3. Alice and Bob have the same preferences:

2l 2l 1 ... 4 3 2 1

Both Alice and Bob get l items: Alice gets 2l, 2l 1, ...l+3, l+2, 1 and Bob gets l+1, l, ...3, 2. Intuitively this allocation seems very unfair since Alice gets all the l 1 best items. However, it is possibly-proportional, since Bob s utility function might assign the a value near 0 to item 1 and a value near 1 to all other items. In better accordance with our intuition, the above allocation is not PDD-proportional: by Theorem 4.5, Bob s bundle is not PDD-better than Alice s bundle, since it does not satisfy any of the conditions (i) to (iii).

Based on the two constructive theorems proved in this section, we have:

Corollary 4.7. The following problems can be decided in polynomial time: (a) Given an allocation, decide whether it is NDDPR; (b) Given an allocation, decide whether it is PDDPR.

5. Existence of NDD-Proportional Allocations

In this section, we prove a necessary and suﬃcient condition for the existence of NDDPR allocations.

Theorem 5.1. An NDDPR allocation exists if and only if:

(a) The number of items is a multiple of the number of agents, i.e., m = l n, where l is an integer and n is the number of agents, and

(b) Each agent has a diﬀerent best item.

In case it exists, it can be found in time O(m).

NDDPR = (a) and (b): Let X1, . . . , Xn be an NDDPR allocation. So for all i N, n Xi NDD i M. By the two conditions of Theorem 4.1: (a) For all i N: |n Xi| |M| = n |Xi| m. But this must be an equality since the total number of items in all n bundles is exactly m. Therefore, the total number of items is n |Xi| which is an integer multiple of n.

Fair Allocation with Diminishing Differences

Algorithm 2 Balanced round-robin allocation of items

while there are remaining items do

for i = 1, . . . , n do

Give agent i his best remaining item. end for for i = n, . . . , 1 do

Give agent i his best remaining item. end for end while

(b) For all i, the level of the best item in n Xi must be weakly larger than the level of the best item in M. So for all i N, Xi must contain agent i s best item. So the best items of all agents must be diﬀerent. (a) and (b) = NDDPR: We show that, if (a) and (b) hold, then the balanced round-robin algorithm (Algorithm 2) produces an NDDPR allocation. Let Xi be the bundle allocated to agent i by balanced-round-robin. We prove that n Xi NDD i M by the two conditions of Theorem 4.1. Condition (i) is satisﬁed with equality, since by (a) each agent gets exactly l items, so |n Xi| = nl = m = |M|. Condition (ii) says that, for every k {1, . . . , m}, the total level of the k best items in the multi-bundle n Xi should be at least as large as the total level of the k best items in M. It is convenient to verify this condition following Algorithm 1: we have to prove that, when going over the items in both bundles from best to worst, the total level-diﬀerence between them (the variable Total Level Diﬀin the algorithm) remains at least 0. We ﬁrst prove that this is true after the ﬁrst round. By condition (b), in the ﬁrst round, each agent receives his best item, so the level of the best n items in n Xi is m. The following table shows the levels and their diﬀerences for k {1, . . . , n} (here, it is important that all items in M are distinct):

k = 1 k = 2 k = 3 . . . k = n n Xi m m m . . . m M m m 1 m 2 . . . m n + 1 Level Diﬀ 0 1 2 . . . n 1 Total Level Diﬀ 0 1 3 . . . n(n 1)/2

We now prove that, after each round r 1, the accumulated level-diﬀerence Total Level Diﬀ for agent i is at least n(n 1)/2 when r is odd, and at least n(i 1) when r is even. We also prove that Total Level Diﬀis always at least 0. The proof is by induction on r. We have just proved the base r = 1. Suppose now that r > 1 and r is even. When agent i picks an item, the number of items already taken is rn i. Therefore, agent i s best remaining item has a level of at least m (rn i). Therefore, the level-diﬀerences for k {(r 1)n + 1, . . . , rn} are as in the following table (where the last row uses the accumulated level-diﬀerence of n(n 1)/2 from the induction assumption):

Segal-Halevi, Hassidim, Aziz

n Xi m rn + i m rn + i . . . m rn + i M m rn + n m rn + n 1 . . . m rn + 1 Level Diﬀ i n i n + 1 . . . i 1 Total Level Diﬀ n(n 1)

2 + i n n(n 1)

2 + 2i 2n + 1 . . . n(i 1)

The sum of terms in the Level Diﬀrow is n[(i n)+(i 1)]

2 = n[ n 1]

2 + ni. Adding the n(n 1)

2 from the induction assumption gives that, at the end of the round, Total Level Diﬀis at least ni n = n(i 1) as claimed. We now show that Total Level Diﬀis at least 0 throughout the round. Level Diﬀis non-positive in the ﬁrst n i + 1 columns of the table, and positive afterwards. So Total Level Diﬀattains its smallest value at step n i + 1. The sum of Level Diﬀfrom step 1 to step n i + 1 is (i n)(n i + 1)/2. Hence Total Level Diﬀat step n i is at least n(n 1)/2 (n i + 1)(n i)/2. Since n n i + 1 and n 1 n i, this expression is at least 0. Suppose now that r > 1 and r is odd. When agent i gets an item, the number of items already taken is rn (n i + 1). Therefore, agent i s best remaining item has a level of at least m rn + (n i + 1). Therefore, the level-diﬀerences for k {(r 1)n + 1, . . . , rn} are as in the following table:

n Xi m rn + n i + 1 m rn + n i + 1 . . . m rn + n i + 1 M m rn + n m rn + n 1 . . . m rn + 1 Level Diﬀ 1 i 2 i . . . n i Total Level Diﬀ n(i 1) + 1 i n(i 1) + 3 2i . . . n(n 1)/2

The sum of terms in the Level Diﬀrow is n[(1 i)+(n i)]

2 ni. Adding the n(i 1) from above gives that, at the end of the round, Total Level Diﬀis at least n(n 1)/2 as claimed. We now show that Total Level Diﬀis at least 0 throughout the round. Level Diﬀis non-positive in the ﬁrst i columns of the table, and positive afterwards. So Total Level Diﬀ attains its smallest value at step i. The sum of Level Diﬀfrom step 1 to step i is i(1 i)/2. Hence Total Level Diﬀat step i is at least n(i 1) + i(1 i)/2 = (i 1)(n i/2) 0.

Using Theorem 5.1, we illustrate the diﬀerence between NDD-fairness and necessaryfairness.

Example 5.2 (NDD-fairness vs. necessary-fairness). Suppose the set of items is M = {1, . . . , 2l}, for some l 2. Alice and Bob have almost opposite preferences:

Alice: 2l 2l 1 ... 4 3 2 1

Bob: 2 3 4 ... 2l 1 2l 1

Intuitively, we would expect that opposite preferences make it easy to attain a fair division. However, in this case, no necessarily-proportional allocation exists: By Remark 4.2, in a necessarily-fair allocation both agents must receive the same number of items (l). But Alice and Bob have the same worst item (1), so one of them must get it. Suppose it is Alice. So Alice has only l 1 items better than 1, while Bob has l items better than 1. Hence, the allocation is not necessarily-proportional for Alice (her utility function might assign a value near 0 to this item and a value near 1 to all other items). In contrast, our Theorem 5.1 shows that an NDD-proportional allocation exists. Intuitively, since it is possible to give each agent his/her best items, they are willing to compromise on the less important items.

Fair Allocation with Diminishing Differences

Figure 2: Estimated recall the fraction of preference-proﬁles that admit an allocation satisfying each fairness criterion. Vertical bars denote sample standard error. Lines connecting data-points are for eye-guidance only. The top line corresponds to both Pos PR and PDDPR for both of them the estimated recall is 1, which means that all utility proﬁles we checked admit such allocations. The lines below them correspond to NDDPR and Nec PR, respectively.

6. Simulation Experiments

A mechanism designer who has to choose a fairness criterion faces a tradeoﬀ: choosing a weak criterion (such as Pos PR or PDDPR) makes it easier to ﬁnd an allocation that satisﬁes the criterion but also makes it more likely that some agents will consider it unfair. In contrast, with a strong criterion (such as NDDPR or Nec PR), it is harder to ﬁnd an allocation, but once an allocation is found, it is more likely that agents will consider it fair. This tradeoﬀis analogous to the tradeoﬀbetween recall and precision in information retrieval and binary classiﬁcation.3 Given a fairness-criterion, we deﬁne its recall and precision as follows:

The recall of the criterion is the probability that a random utility-proﬁle admits an allocation satisfying this criterion.

The precision of a fairness-criterion is the probability that a random allocation satisfying this criterion according to the ordinal rankings is indeed fair according to the cardinal valuations.

We estimated the recall and precision of various fairness criteria as follows.

3. See the Wikipedia page Precision and Recall for a deﬁnition of these terms in information retrieval and binary classiﬁcation.

Segal-Halevi, Hassidim, Aziz

Figure 3: Estimated precision the fraction of allocations that are fair according to the cardinal valuations, among those that are fair by the ordinal fairness criterion. Vertical bars denote sample standard error. Lines connecting data-points are for eye-guidance only. The lines, from top to bottom, correspond to: (a) Nec PR by deﬁnition, it is necessarily always 1 (the point at noise size 0.1 is missing since no proﬁle with this noise admitted a Nec PR allocation); (b) The NDDPR allocations found by the balanced-round-robin protocol (Algorithm 2); (c) An arbitrary NDDPR allocation; (d) An allocation found by a baseline protocol in which the ﬁrst round is like Algorithm 2 but the following items are allocated at random; (e) An arbitrary PDDPR allocation; (f) An arbitrary Pos PR allocation.

6.1 Randomly-Generated Instances

To simulate valuations with partial correlation, we determined for each item a market value drawn uniformly at random from [1, 2]. We determined the cardinal value of each item to each agent as the item s market value plus noise drawn uniformly at random from [ A, A], where A [0, 1] is a parameter. Based on the cardinal values, we determined the agent s ordinal ranking. Then, for each such utility-proﬁle, we checked various statistics:

How many allocations are Nec PR/NDDPR/PDDPR/Pos PR according to the ordinal rankings;

How many Nec PR/NDDPR/PDDPR/Pos PR allocations are indeed proportional according to the underlying cardinal valuations;

Whether the speciﬁc NDDPR allocation found by the procedure of Theorem 5.1 is proportional according to the underlying cardinal valuations;

Fair Allocation with Diminishing Differences

As a baseline, we also checked the fairness of an allocation found (under the conditions of Theorem 5.1) by giving each agent its favorite item and dividing the remaining items randomly.

We did this experiment for n {2, 3} agents, for diﬀerent values of A {0.1, . . . , 1}, and for diﬀerent numbers l of items per agent l {2, . . . , 8} when n = 2 or l {2, . . . , 5} when n = 3. For each combination, we checked 1000 randomly-generated instances.4

Below we report the results for n = 2 agents; the results for n = 3 agents are qualitatively similar and we omit them from the paper.5

6.2 Results Recall

Figure 2 presents the results for recall (probability of existence). As expected, the recall of the weak criteria Pos PR and PDDPR is almost always 1; the recall of NDDPR is lower, but it is still signiﬁcantly higher than that of Nec PR. Thus, an NDDPR allocation is likely to exist in many cases in which a Nec PR allocation does not exist. As expected, both kinds of allocations are more likely to exist when the noise size A is larger, since larger noise corresponds to less correlated rankings. Similarly, both kinds of allocations are more likely to exist when there are more items to share; this ﬁnding resembles the results of Dickerson, Goldman, Karp, Procaccia, and Sandholm (2014) for envy-free allocations with cardinal valuations.

6.3 Results Precision

Figure 3 presents the results for precision (probability of fairness). Nec PR allocations, when they exist, are always proportional by deﬁnition; hence the precision of Nec PR is always 1. The precision of NDDPR is lower than 1, but it is much higher than that of the weaker criteria Pos PR and PDDPR. Interestingly, the speciﬁc NDDPR allocation found by the round-robin protocol of Theorem 5.1 is very likely to be proportional in most cases its precision is very near 1. Note that, since the randomization we used is completely uniform and does not use the DD assumption, the probability that DD holds is very low.6 Nevertheless, the NDDPR allocation of Theorem 5.1 (when it exists) is almost always proportional when the number of items or the noise size is suﬃciently large. This further shows the robustness of our algorithm. Comparing the two graphs, we see that the Nec PR requirement is too strong, and the PDDPR and Pos PR requirements are too weak, while the NDDPR requirement hits a sweet spot between recall and precision: it allows us to solve a large fraction of the instances, and the solutions are likely to be considered fair by the agents.

4. The Python code used for the experiments is available at Git Hub: https://github.com/erelsgl/fair-diminishing-diﬀerences 5. All results and plots can be found online: https://github.com/erelsgl/fair-diminishing-diﬀerences/blob/master/results/Readme.md 6. There are nl items, so there are nl 1 diﬀerences between utilities of adjacent items. DD requires that, for each agent, these diﬀerences be ordered in a descending order. With high probability, all diﬀerences are distinct, so there are (nl 1)! diﬀerent orders, and only one of them corresponds to a DD utility function. Therefore, the probability that DD holds for each single agent is 1/(nl 1)!, and for all n agents it is 1/((nl 1)!)n.

Segal-Halevi, Hassidim, Aziz

7. Envy-Freeness

The following is an analogue of the deﬁnition of proportionality-related fairness criteria (Deﬁnition 3.5):

Deﬁnition 7.1 (Envy-freeness). Given utility functions u1, . . . , un, an allocation X is called envy-free (EF) if i, j N : ui(Xi) ui(Xj). Based on this deﬁnition, necessary DD-envy-free (NDDEF) and possible-DD-envy-free (PDDEF) are deﬁned analogously to NDDPR and PDDPR.

The following is a partial analogue of Lemma 3.6 and contains an alternative characterization of NDDEF:

Lemma 7.2. Given item rankings 1, . . . , n: (a) An allocation X is NDDEF iﬀ i, j N : Xi NDD i Xj. (b) If an allocation X is PDDEF, then i, j N : Xi PDD i Xj.

Proof. Let EF(i, j, u) be the no-envy predicate ui(Xi) ui(Xj). (a) The NDDEF deﬁnition is For all DD utility proﬁles u, for all i and for all j, EF(i, j, u). The right-hand side is for all i, for all j, for all DD utility proﬁles u, EF(i, j, u). Switching the order of for-all quantiﬁers yields logically-equivalent statements. (b) The PDDEF deﬁnition is there exists u for which, for all i and for all j, EF(i, j, u). The right-hand side is for all i and for all j, there exists ui by which EF(i, j, u) . The former statement logically implies the latter.7

Based on Lemma 7.2(a), Corollary 4.7 extends to NDDEF: it is possible to decide in polynomial time whether a given allocation is NDDEF. However, we do not have a stronglypolynomial time algorithm for deciding whether a given allocation is PDDEF.8 Below we focus on the NDDEF criterion. Since every NDDEF allocation is NDDPR, the two conditions of Theorem 5.1 are necessary for the existence of NDDEF allocations for any number of agents. In the special case of n = 2 agents, NDDPR is equivalent to NDDEF so these conditions are also suﬃcient. But for n 3 they are no longer suﬃcient.

Example 7.3. There are six items {1, . . . , 6}. The preferences of the three agents Alice Bob and Carl are:

Alice: 6 5 3 4 2 1

7. In contrast to Lemma 3.6, here the latter statement (which can be called Weak-PDDEF ) does not imply the former (PDDEF) when there are three or more agents. For example, if X1 P DD 1 X2 and X1 P DD 1 X3, then it is possible that agent 1 does not envy agent 2 by some DD function u1,2, and does not envy agent 3 by some other DD function u1,3, but there is no single DD function by which agent 1 envies neither agent 2 nor agent 3. 8. The situation is similar for Pos EF, see Aziz et al. (2015). For both fairness criteria, deciding whether a given allocation is fair can be done using a linear program with mn variables describing the witness utility proﬁle. The constraints require that the allocation is fair, and (for PDDEF) also that the utility proﬁle satisﬁes the DD condition. This requires weakly-polynomial time. As far as we know, it is an open question whether the decision problem can be solved in strongly-polynomial time.

Fair Allocation with Diminishing Differences

Bob: 5 4 3 6 2 1

Carl: 4 6 3 5 2 1

The conditions of Theorem 5.1 are clearly satisﬁed: the number of items is a multiple of 3 and the best items are all diﬀerent. However, no NDDEF allocation exists. To see this, note that the preferences are the same up to a cyclic permutation between 6 5 and 4, so the agents are symmetric and it is without loss of generality to assume that Alice receives item 1. Therefore, to ensure proportionality, Alice s bundle must be {6, 1} and her Borda score is 7. To ensure that Alice is not envious, both Bob and Carl must get items with a Borda score (for Alice) of 7. Thus there are two cases: (a) Bob gets {5, 2} and Carl gets {3, 4}. This allocation is NDDPR but it is not NDDEF, since Bob envies Carl according to the Borda score. (b) Carl gets {5, 2} and Bob gets {3, 4}. This allocation is not even NDDPR since Carl s Borda score is 5 (and Carl necessarily envies Bob).

When the number of agents is not bounded, deciding the existence of NDDEF allocations is computationally hard:

Theorem 7.4. When there are n 3 agents and at least 2n items, checking the existence of NDDEF allocations is NP-complete (as a function of n).

Proof Sketch. By Lemma 7.2, to check whether an allocation is NDDEF, we have to do at most n2 checks of the NDD relation. Each such check can be done in polynomial time by Theorem 4.1 and Algorithm 1. Hence the problem is in NP. The proof of NP-hardness is similar to the proof of Bouveret et al. (2010) for the NP-hardness of checking the existence of necessarily-envy-free allocations. The proof requires carefully checking that the reduction argument works for NDDEF as well. The details are presented in Appendix C.

When the number of agents is constant (at least 3) and the number of items is variable, the runtime complexity of checking NDDEF existence is an open question: is it polynomial in m like NDDPR, or NP-hard like necessary-EF (Aziz, Schlotter, & Walsh, 2016)?

8. Pareto Eﬃciency

An allocation is called Pareto-eﬃcient if every other allocation is either not better for any agent, or worse for at least one agent:

Deﬁnition 8.1 (Pareto-eﬃciency). Given utility functions u1, . . . , un, an allocation X is called Pareto-eﬃcient (PE) if for every other allocation Y, either i N : ui(Xi) ui(Yi), or i N : ui(Xi) > ui(Yi). Based on this deﬁnition, necessary-DD-Pareto-eﬃciency (NDDPE) and possible-DD-Pareto-eﬃciency (PDDPE) are deﬁned analogously to NDDPR and PDDPR.

The criteria of necessary-Pareto-eﬃciency (Nec PE) and of possible-Pareto-eﬃciency (Pos PE) are deﬁned analogously. It is clear from the deﬁnition that Nec PE implies NDDPE implies PDDPE implies Pos PE. With the analogous fairness criteria, these implications are strict, i.e., some possibly-fair allocations are not PDD-fair, and some NDD-fair allocations are not necessarily-fair. But with Pareto-eﬃciency the situation is diﬀerent:

Segal-Halevi, Hassidim, Aziz

Theorem 8.2. An allocation is Nec PE if and only if it is NDDPE.

Proof. The implication Nec PE = NDDPE is obvious by the deﬁnition. We now consider an allocation X that is not Nec PE and prove X is not NDDPE. By Aziz, Bir o, Lang, Lesca, and Monnot (2018) Theorem 9, if X is not Nec PE then there are two options: (i) X is not possibly-PE. Then, it is certainly not NDD-PE. (ii) X admits a Pareto-improving one-for-two-swap. This means that there are two agents, say Alice and Bob, such that XA contains an item x, XB contains two items y, z, and Bob strictly prefers the one item over each of the two: x B y and x B z. Then X is not NDD-PE, since it is not PE for the following utilities:

u A(x) = m2 + Lev A(x) u B(x) = 2Lev B(x)

Note that both utility functions have DD. Alice s utility is dominated by the number of items she has, so she always prefers two items to one. Bob s utility is lexicographic, so he always prefers one good item to any number of worse items. Hence, by switching {x} and {y, z} we get a new allocation that is strictly better for both Alice and Bob, and does not aﬀect any other agent.

Theorem 8.3. An allocation is Pos PE if and only if it is PDDPE.

Proof. The implication PDDPE = Pos PE is obvious by deﬁnition. We now consider an allocation X that is not PDDPE and prove X is not Pos PE. Consider the lexicographic utility proﬁle, by which for each i N, ui(x) = 2Levi(x). Since these utilities have DD, X is not PE according to this proﬁle. So there exists an allocation Y by which for some agent, say Alice: u A(YA) > u A(XA), and for all agents B: u B(YB) u B(XB). Since Alice prefers YA to XA by a lexicographic utility function, there exists some integer k 1 such that XA and YA contain the same k 1 best items, but the k-th best item in YA (denoted by ya) is better for Alice than the k-th best element in XA. In allocation X, item ya belonged to some other agent, say Bob. But Bob must be weakly better-oﬀin Y than in X, so YB must contain a better item that was not in XB; let us call this item yb. In allocation X, item yb belonged to some other agent, say Carl. From similar considerations, Carl must have in Y an item yc that he prefers to yb. Continuing this way, we end with a cycle of agents, each of whom gave an item to the previous agent and received a better item from the next agent. Now consider the allocation Z which is identical to X except that the single-item exchanges in the cycle take place (so ya is given to Alice, yb is given to Bob and so on). Then Z is better than X for all agents in the cycle, and this is true for any additive utility function. Hence, X is not possibly-PE.

So DD leads to new fairness criteria but not to new eﬃciency criteria.

Fair Allocation with Diminishing Differences

9. Conclusions and Future Work

We formalized natural ways to compare sets of goods by using the DD (diminishing differences) assumption. In Appendix A we present the analogous ID (increasing diﬀerences) assumption for chores. The relations lead to new fairness criteria which we studied in detail. Two main open questions remain for future work: one about envy-free allocation of goods (Section 7), and one about fair allocation of chores (Appendix A). Below we present the smallest cases in which these questions are open.

(i) There are three agents with diﬀerent rankings over m goods. Can it be decided in time polynomial in m, whether there exists a necessary-DD envy-free allocation?

(ii) There are three agents with diﬀerent rankings over m chores. Can it be decided in time polynomial in m, whether there exists a necessary-ID proportional allocation?

Besides these questions, it may be interesting to extend the results to the case where agents may be indiﬀerent between items.9

Additionally, it may be interesting to identify other interesting set extensions that correspond to classes of utility functions. For example, suppose that agents care both about getting a best item and about not getting a worst item, but do not care much about intermediate items (so the diﬀerences in utilities are decreasing at ﬁrst and then increasing). What can be said of fair allocations under this assumption?

Acknowledgments

We acknowledge the Dagstuhl Seminar 16232 on Fair Division where this project was initiated. We are grateful to four anonymous IJCAI reviewers and three anonymous JAIR reviewers for their very helpful comments. Haris Aziz is supported by a Scientia Fellowship. Erel Segal-Halevi was supported by the ISF grant 1083/13, the Doctoral Fellowships of Excellence Program and the Mordecai and Monique Katz Graduate Fellowship Program at Bar-Ilan University. Avinatan Hassidim is supported by ISF grant 1394/16.

Appendix A. Chores and Increasing Diﬀerences

In this section, we assume that we have to divide indivisible chores, deﬁned as items with negative utilities. Therefore, all the utility functions we consider in this section assign strictly negative values to all items.

9. Theorem 4.1 is proved for multi-bundles so it holds with indiﬀerences too. But Theorem 5.1 fails. Consider an instance with m = 8 goods and n = 2 agents with the following rankings:

Alice : a b c d = w = x = y z

Bob : b a c d = w = x = y z

The agents have diﬀerent best goods, so we might think that balanced-round-robin might yield an NDDPR allocation. However, when goods are picked in the order ABBAABBA, Alice s bundle is {a, d, x, z}; it is not NDDPR for her, since it is not proportional by Borda scores (the total Borda score is 5 + 4 + 3 + 2 + 2 + 2 + 2 + 1 = 21, while Alice s Borda score is 5 + 2 + 2 + 1 = 10).

Segal-Halevi, Hassidim, Aziz

With chores, the Diminishing Diﬀerences condition means that the diﬀerence between the easiest to the second-easiest chore is larger than the diﬀerence between the secondhardest to the hardest chore. But usually, with chores, people care more about not getting the hardest chores than about getting the easiest chores. Therefore, we introduce the condition of increasing diﬀerences (ID). In many aspects, the ID condition for chores is analogous to the DD condition for goods (subsection A.1). However, ﬁnding necessarily ID-fair allocation for chores is more diﬃcult than necessarily-DD-fair allocation for goods (subsections A.2, A.3 and A.4).

A.1 Increasing Diﬀerences: Basic Deﬁnitions

The following deﬁnition is analogous to Deﬁnition 3.1:

Deﬁnition A.1. Let be a preference relation and u a utility function consistent with . We say that u has the Increasing Diﬀerences (ID) property if, for every three items with consecutive levels x3 x2 x1 such that Lev(x3) = Lev(x2) + 1 = Lev(x1) + 2, it holds that u(x3) u(x2) u(x2) u(x1). We denote by UID( ) the set of all ID utility functions consistent with . Given n rankings 1, . . . , n, we denote by UID( 1, . . . , n) the set of all vectors of ID utility functions, u1, . . . , un, such that ui is consistent with i.

There is a one-to-one correspondence between DD utilities and ID utilities. Given a strict ranking , deﬁne its reverse ranking rev as:

x, y M : y rev x x y

Given a utility function u, deﬁne its reverse function urev as:

x M : urev(x) := u(x)

Lemma A.2. For every ranking and utility function u:

urev UID( rev) u UDD( ).

The proof is technical and we omit it. The negative-Borda utility function, u Borda(x) := Lev(x) m 1, is a member of UID( ), as well as the negative-lexicographic utility function, u Lex(x) := 2m Lev(x). By the latter function, the bundles are ﬁrst ranked by whether they contain the worst chore, then by whether they contain the next-worst chore, etc. An alternative characterization of UID is given by the following lemma. It is analogous to Lemma 3.2 and proved in a similar way, so we omit the proof:

Lemma A.3. u UID( ) iﬀ, for every four items x2, y2, x1, y1 with x2 x1 and y2 y1 and x2 = y2 and x1 = y1:

u(x2) u(y2) Lev(x2) Lev(y2) u(x1) u(y1) Lev(x1) Lev(y1)

Fair Allocation with Diminishing Differences

Analogously to Deﬁnition 3.3 we deﬁne the relations X NID Y and X PID Y . These are closely related to their DD counterparts:

Lemma A.4. Let be a ranking and rev its inverse ranking. Then, for every two multibundles X, Y :

X NID Y Y NDD rev X

X PID Y Y PDD rev X

Again the proof is technical and we omit it. Thus, to check whether X NID Y / X PID Y with regards to some ranking , we can simply use Algorithm 1 with the inverse ranking rev. We now want to prove an analogue of Theorem 4.1 for chores. For this, we order the chores in each multi-bundle by increasing level, so X = {x1, . . . , x|X|} where x1 i . . . i x|X| For each k |X| we deﬁne Xk as the k worst chores in X, Xk := {x1, . . . , xk}.

Theorem A.5. Given a ranking and two (multi-)bundles X, Y of chores, X NID Y if and only if both of the following conditions hold:

(i) |X| |Y |;

(ii) For each k {1, . . . , |Y |}: Lev(Xk) Lev(Y k).

Note that condition (i) is the opposite of condition (i) in Theorem 4.1: X must have weakly less chores than Y . However, condition (ii) is identical to condition (ii) in Theorem 4.1.

Proof. Deﬁne the inverse-level of an item/bundle as its level under the inverse-ranking rev. So the inverse-level of the hardest chore is m and of the easiest chore is 1. By Lemma A.4, X NID Y iﬀY NDD rev X. By Theorem 4.1, this holds iﬀboth the following conditions hold:

(i) |Y | |X|;

(ii) For each k {1, . . . , |Y |}, the inverse-level of the k chores in Y that are best by rev (i.e., worst by ), is at least as high as the inverse-level of the k chores in X that are worst by .

The ﬁrst condition is equivalent to |X| |Y | and the second condition is equivalent to Lev(Xk) Lev(Y k).

A.2 Increasing Diﬀerences: Fairness Criteria

Analogously to Deﬁnition 3.5, we deﬁne the fairness criteria NIDPR (necessary-ID-proportional) and PIDPR (possible-ID-proportional). Analogously to Lemma 3.6 and Corollary 4.7, and with similar proofs that we omit, we have:

Lemma A.6. Given item rankings 1, . . . , n:

An allocation X is NIDPR iﬀ i N : n Xi NID i M.

Segal-Halevi, Hassidim, Aziz

An allocation X is PIDPR iﬀ i N : n Xi PID i M.

Corollary A.7. The following problems can be decided in polynomial time: (a) Given an allocation, decide whether it is NIDPR; (b) Given an allocation, decide whether it is PIDPR.

In Section 5 we proved that an NDD-proportional allocation exists whenever the number of items is an integer multiple of the number of agents, and all agents have diﬀerent best items. At ﬁrst glance, the natural extension of this condition to chores is that all agents should have diﬀerent worst chores. The following two examples show that this condition is neither suﬃcient nor necessary.

Example A.8. There are eight chores and four agents with rankings:

A : a b c d w x y z

B : b c d a w x z y

C : c d a b w z y x

D : d a b c x z y w

Each agent has a diﬀerent best chore and each agent has a diﬀerent worst chore. However, at least one agent (the one who receives y) has a second-worst chore. This implies that an NIDPR allocation does not exist. To see this, suppose that all agents have the same ID scoring function:

996, 997, 998, 999, 1000, 2000, 3000, 4000

The utility of the agent who receives y is at most 3996. However, the total value is 13990 and the fair share is 13990/4 = 3497.5.

Example A.9. There are three chores and three agents with rankings:

All agents have the same best chore, and two agents have the same worst chore. However, the following allocation is NIDPR:

A : {y} B : {x} C : {z}

This is obvious for Bob since he receives his best (easiest) chore. To see that it is also true for Alice, we show that 3 XA NID A M using Theorem A.5. Condition (i) clearly holds since both multi-bundles have 3 chores. For Condition (ii), compare the levels of the k worst chores, for k = 1, 2, 3:

k = 1 k = 2 k = 3 3 XA 2 2 2 M 1 2 3 Diﬀerence +1 0 1 Accumulated diﬀerence +1 +1 0

Fair Allocation with Diminishing Differences

The accumulated diﬀerence is always at least 0, so 3 XA NID A M. By a similar calculation, 3 XC NID C M. Hence the allocation is NIDPR.

Below we present a diﬀerent condition that is necessary for the existence of NIDPR allocations. It is analogous to the only-if part of Theorem 5.1. To state this condition, for each agent i, let Wi be the set of i s n 1

2 worst chores.

Theorem A.10. If there exists a NIDPR allocation of chores among n agents, then both the following conditions must hold: (a) The number of chores is m = l n, for some integer l. (b) It is possible to allocate to each agent i, l chores that are not from Wi. (Hence, the intersection of all n 1

2 -worst-chore sets is empty: i N Wi = ).

Proof. Let (X1, . . . , Xn) be an NIDPR allocation. Then for every agent i, n Xi NID i M. By Theorem A.5. (a) For every i N: |n Xi| |M| = n |Xi| m. But this must be an equality since the total number of items in all n bundles is exactly m. So the total number of items is n |Xi| which is an integer multiple of n. (b) For every i N, the level of the n worst chores in n Xi must be weakly larger than the level of the n worst chores in M. The n worst chores in M have levels 1, . . . , n, so their total level is n(n+1)

2 . The n worst chores in n Xi are just n copies of the worst chore in Xi. Thus, the level of this chore must be at least n(n+1)

2 . Since levels are integers, the smallest level in Xi must be at least n+1

2 . So the agent must not get any of his n 1

2 worst chores. In other words, agent i must not get any chore from the set Wi. Since all chores must be allocated, no chore may be in the intersection of all Wi.

In Example A.8, n 1

2 = 2, and the intersection of the 2-worst-chores sets is not empty (it contains chore y), so a NIDPR allocation does not exist. In Example A.9, n 1

2 = 1, the intersection of the worst-chore sets is empty (not all three agents have the same worst chore), and a NIDPR allocation exists. We do not know if the condition of Theorem A.10 is suﬃcient for the existence of NIDPR allocations in general. Below we prove that they are suﬃcient in two special cases: two agents, and three agents with almost identical rankings.

A.3 NIDPR Allocation for Two Agents

With two agents, for each i {1, 2}, the set Wi contains just the worst chore of agent i, so the necessary condition of Theorem A.10 simply says that each agent has a diﬀerent worst chore. This condition is also suﬃcient for the existence of NIDPR allocations. The following theorem is analogous to the if part of Theorem 5.1 for n = 2.

Theorem A.11. There exists a NIDPR allocation of chores among n = 2 agents whenever the following conditions both hold: (a) The number of chores is m = l n, for some integer l. (b) The worst chores of the agents are diﬀerent. In case it exists, it can be found in time O(m).

Segal-Halevi, Hassidim, Aziz

Theorem A.11 can be proved directly by analyzing the outcome of the balanced roundrobin protocol (Algorithm 2), similarly to the proof of Theorem 5.1. This analysis is technical and we omit it. Intuitively, when there are two agents, allocating chores is equivalent to allocating exemptions from chores. An exemption from chore is a good; hence, chore allocation is equivalent to good allocation.10 An exemption from the worst chore is the best good; hence, Theorem 5.1 implies Theorem A.11.11

A.4 NIDPR Allocations for Three Agents

The analogy between goods and chores does not extend to n 3 agents.12 This is because for each chore, there are n 1 identical exemptions to share, and each agent must get at most one such exemption; this constraint does not exist in the problem of allocating goods. Hence, Theorem A.11 does not generalize to three or more agents. The balanced-roundrobin protocol does not necessarily ﬁnd a NIDPR allocation, even if it exists. In Example A.9, the rankings satisfy the necessary condition of Theorem A.10, and a NIDPR allocation exists, but the round-robin protocol (in the order A B C) yields the allocation:

A : {x} B : {z} C : {y}

which is not NIDPR since it gives Carl his worst chore. For three agents, we consider the following special case:

All agents have the same n worst chores;

All agents have the same m n best chores, and rank them identically.

In some sense this is a worst case of fair allocations, since the agents preferences are as similar as they can be without violating the necessary condition. We prove that, in this worst case , the necessary condition of Theorem A.10 is also suﬃcient.

Theorem A.12. There exists a NIDPR allocation of chores among n = 3 agents whenever the following conditions hold: (a) The number of chores is m = l n, for some integer l. (b) Not all agents have the same worst chore; (c) All agents have the same n worst chores; (d) All agents have the same m n worst chores and rank them identically. In this case, it can be found in time O(m).

Proof. We ﬁrst allocate the n worst chores. By condition (b), it is possible to give each agent a chore with a level of at least 2. Moreover, by simple case analysis it is possible to see that it is always possible to give at least one agent a chore with a level of at least 3. Hence, after this step, the total level-diﬀerences of all agents are at least 0:

10. This observation was already made by Bogomolnaia, Moulin, Sandomirskiy, and Yanovskaya (2017) for divisible resources and by Segal-Halevi (2019) for competitive equilibrium with indivisible objects. 11. The round-robin protocol would be slightly diﬀerent in case of chores: each agent should pick an exemption from a chore, rather than a chore. In other words, each agent in turn should pick a chore and give it to the other agent. 12. As already noted by Bogomolnaia et al. (2017) for divisible resources.

Fair Allocation with Diminishing Differences

k = 1 k = 2 k = 3 n Xi 2 2 2 M 1 2 3 Level Diﬀ 1 0 1 Total Level Diﬀ 1 1 0

and the total level-diﬀerence of at least one agent is 3:

k = 1 k = 2 k = 3 n Xi 3 3 3 M 1 2 3 Level Diﬀ 2 1 0 Total Level Diﬀ 2 3 3

We now have m n remaining chores. By condition (d), the levels of these chores are the same for all agents, namely, 4, . . . , m. We allocate them from worst (4) to best (m), using a round-robin protocol. There are l 1 allocation rounds; in each round, the ﬁrst (worst) chore is given to an agent whose Total Level Diﬀis at least 3. We prove by induction that, indeed, when each round ends, there is at least one agent with Total Level Diﬀat least 3, while all other agents have Total Level Diﬀat least 0. The induction base (r = 1) was already proved above. Assume the claim is true until the beginning of some round r. The level of the next chore to allocate is 3r 2. It is given to an agent with Total Level Diﬀat least 3, so his levels change as follows:

k = 3r 2 k = 3r 1 k = 3r n Xi 3r 2 3r 2 3r 2 M 3r 2 3r 1 3r Level Diﬀ 0 1 2 Total Level Diﬀ 3 2 0

The next chore is 3r 1. It is given to an agent with Total Level Diﬀat least 0, so his levels change as follows:

k = 3r 2 k = 3r 1 k = 3r n Xi 3r 1 3r 1 3r 1 M 3r 2 3r 1 3r Level Diﬀ 1 0 1 Total Level Diﬀ 1 1 0

The next chore is 3r. It is given to an agent with Total Level Diﬀat least 0, so his levels change as follows:

k = 3r 2 k = 3r 1 k = 3r n Xi 3r 3r 3r M 3r 2 3r 1 3r Level Diﬀ 2 1 0 Total Level Diﬀ 2 3 3

As claimed, after round r ends, all agents have Total Level Diﬀat least 0, and one agent has Total Level Diﬀat least 3. Hence, the resulting allocation is NIDPR.

Segal-Halevi, Hassidim, Aziz

Theorem A.12 can be extended to more than 3 agents. Whenever the worst n chores can be allocated such that the total level-diﬀerence of all agents is at least 0 and the total level-diﬀerence of some agents is suﬃciently high, it is possible to allocated the other chores such that the total level-diﬀerence of all agents remains at least 0. Moreover, instead of requiring that all agents have exactly the same ranking to their m n best chores, it is suﬃcient that all agents have the same worst n chores (levels 1, . . . , n), the same next-worst n chores (levels n + 1, . . . , 2n), etc. We omit these results since we believe that the main interesting challenge is generalizing the theorem to arbitrary rankings. Finding a general suﬃcient condition and protocol for NIDPR allocation of chores remains an interesting open problem.

Appendix B. Binary Utilities

In this section, we compare the diminishing/increasing diﬀerences assumptions to another natural assumption, which we call Binary. It is based on the assumption that each agent only cares about getting as many as possible of his k best items, where k is an integer that may be diﬀerent for diﬀerent agents. The binary assumption was also used in Proposition 21 of Bouveret and Lang (2008), who proved that ﬁnding an eﬃcient envy-free allocation with such preferences is NP-complete. The following deﬁnition is analogous to Deﬁnitions 3.1 and A.1:

Deﬁnition B.1. Let be a preference relation and u a utility function consistent with . We say that u is Binary if, for some integer k 1:

( 1 when Lev(x) k 0 when Lev(x) < k

We denote by UBIN ( ) the set of all binary utility functions consistent with .

Analogously to Deﬁnition 3.3 we deﬁne the relations X NBIN Y and X PBIN Y ; analogously to Deﬁnition 3.5 we deﬁne NBIN-fairness and PBIN-fairness. At ﬁrst glance, the Binary assumption seems much more restrictive than the DD assumption. For every , the set UBIN ( ) contains only m utility functions much less than UDD( ). Therefore, one could expect NBIN-fairness to be easier to satisfy than NDDfairness. But this is not the case: NBIN-fairness is equivalent to necessary fairness and PBIN-fairness is equivalent to possible fairness. This follows from the following theorem.

Theorem B.2. For every item-ranking and every multi-bundles X, Y : (a) X Nec Y if and only if X NBIN Y and (b) X Pos Y if and only if X PBIN Y .

Proof. It is suﬃcient to prove the following directions: (a) If X NBIN Y then X Nec Y ; (b) If not X PBIN Y then not X Pos Y . For the proof, we use the following notation.

The m items are denoted by their level, so the best item is m and the worst is 1.

Fair Allocation with Diminishing Differences

For a multi-bundle X and an item j, the number of copies of j in X is denoted X[j].

The m utility functions in UBIN ( ) are denoted by Uk, for k {1, . . . , m}.

In this notation, for every k {1, . . . , m} and multi-bundle X:

j=k X[j] (1)

so Um(X) = X[m] (the agent cares only about the best item), Um 1(X) = X[m]+X[m 1] (the agent cares only about the two best items), etc. Moreover, for every function u U( ) and multi-bundle X:

j=1 u(j) X[j] (2)

Substituting the X[j] in (2) using (1) gives:

u(X) = u(m) Um(X) +

j=2 u(j 1) Uj 1(X) Uj(X)

u(j) u(j 1) Uj(X) + u(1) U1(X)

so every additive function u is a linear combination of the functions Uk. Note that all coeﬃcients in this linear combination are non-negative. Hence:

If k {1, . . . , m}: Uk(X) Uk(Y ), then u U( ) : u(X) u(Y ). This implies (a).

If k {1, . . . , m}: Uk(X) < Uk(Y ), then u U( ) : u(X) < u(Y ). This implies (b).

Appendix C. NP-Hardness of NDDEF

Theorem 7.4. When there are n 3 agents and at least 2n items, checking the existence of NDDEF allocations is NP-hard (as a function of n).

Proof. The proof is similar to the proof of Bouveret et al. (2010) for the NP-hardness of checking existence of Nec EF allocations. We now present their reduction and show that it works for NDDEF as well. The proof is by reduction from the exact-3-cover problem, whose inputs are:

A base set of 3q elements;

A set-family containing n q triplets, C1, . . . , Cn, each of which contains exactly 3 elements from the base-set.

Segal-Halevi, Hassidim, Aziz

The question is whether there exist q pairwise-disjoint triplets whose union is the base-set. Given an instance of exact-3-cover, an instance of fair item allocation is constructed as follows:

To the 3q base elements correspond 3q main items, denoted by Main. To each triplet Ci corresponds a set of three main items, denoted by Maini, such that i {1, . . . , n} : Maini Main. The sets Maini, like the triplets Ci, are not necessarily disjoint. We denote by Main i the main items not in Maini.

There are also 3n dummy items denoted by Dummy. To each triplet Ci corresponds a set of three dummy items, denoted by Dummyi := {di, di , di }. All such sets are pairwise disjoint. We denote by Dummy i the dummy items not in Dummyi.

There are 3(n q) auxiliary items, denoted by Aux. They are partitioned to n q pairwise-disjoint triplets, denoted by Auxj := {xj, xj , xj }, for j {q+1, . . . , n}. All in all, there are 6n items.

To each triplet Ci corresponds a set of three agents, Agentsi = {i, i , i }. The sets Agentsi are pairwise disjoint. All in all, there are 3n agents.

The preferences of the three agents in Agentsi are, in general:

Dummyi Maini Auxq+1 Auxn Dummy i Main i

Their preferences over the three items in Dummyi are cyclic , i.e., for agent i it is di di di , for agent i it is di di di, and for agent i it is di di di . Their preferences over the three items in Maini are cyclic in a similar way. Their preferences over the three items in Auxj, for each j {q + 1, . . . , n}, are cyclic in a similar way. Their preferences over Dummy i and Main i are arbitrary.

Bouveret et al. (2010) prove that there exists a Nec EF allocation iﬀthere exists an exact-3-cover. The proof involves three arguments:

(i) In a Nec EF allocation, each agent must receive the same number of items. Here there are 6n items and 3n agents so each agent must get exactly two items. One of these items must be its top dummy item, which is easy to do since the top dummy items of all agents are diﬀerent. So, it remains to prove that there is an exact-3-cover, if and only if the second items can be allocated in a Nec EF way, i.e., such that each agent prefers the worst item in his bundle to the worst item in any other bundle.

(ii) Cover = allocation: Suppose there is an exact-3-cover, e.g, with the triplets C1, . . . , Cq. Then, the sets of main items Main1, . . . , Mainq are pairwise-disjoint and their union is exactly Main. Then, for each j {1, . . . , q}, it is possible to allocate the three items in Mainj to the three agents in Agentsj, giving each agent his favorite main item. Let s call these 3q agents in the triplets Agents1, . . . , Agentsq, the lucky agents . The allocation is Nec EF for the lucky agents since their worst item is their 4th-best item while the worst item in any other bundle is at most their 5th-best item (since their three best items are the dummy items and they are

Fair Allocation with Diminishing Differences

already allocated). It remains to determine an allocation for the 3(n q) unlucky agents, Agentsq+1, , Agentsn. For each j {q +1, . . . , n}, give to the three agents in Agentsj, the three items in Auxj, giving each agent his favorite item from that triplet. This item is better for them than the worst items in the other bundles, which are from Main i or Dummy i, so the allocation is Nec EF for them too.

(iii) Allocation = cover: Suppose there is a Nec EF allocation. For each i {1, . . . , n}, consider the three agents in Agentsi. We claim that either all of them receive a main item from Maini, or none of them does. Proof: suppose e.g. that agent i receives item mi Maini but agent i does not receive any item from Maini. Then, the allocation of i is {di, mi} and the best possible allocation for i is {di , xi }, where xi is the auxiliary item preferred by agent i . But for agent i , both items allocated to agent i are better than xi . Therefore agent i might envy i, so the division is not Nec EF. Since each main item must be allocated to exactly one agent, there exists an exact-3-cover: the triplet Ci is in the cover if and only if the agents in Agentsi receive the items in Maini.

We now show that the reduction also works for NDDEF. Claim (i) works for NDDEF by Theorem 4.1. Claim (ii) clearly works for NDDEF since every NEF allocation is NDDEF. It remains to prove claim (iii). Suppose there exists an NDDEF allocation. This allocation is, in particular, envy-free according to the Borda score. We claim that, for each i {1, . . . , n}, either all three agents in Agentsi receive an item from Maini, or none of them does. Proof: consider the following two cases:

One agent, say i, receives his main item mi, but the other agents i , i do not receive their main items. The dummy items give agent i a Borda-advantage of 1 over i. The best second item that can be allocated to i is his best auxiliary item, but this leaves him with a Borda-disadvantage of 2 relative to i, so i Borda-envies i.

Two agents, say i , i , receive their main items mi , mi , but agent i does not receive his main item. The dummy items give agent i a Borda-advantage of 1 over i . The best second item that can be allocated to i is his best auxiliary item, but this leaves him with a Borda-disadvantage of 2 relative to i , so i Borda-envies i .

Therefore the reduction is valid for NDDEF too, and the theorem is proved.

Abdulkadiroglu, A., & S onmez, T. (2003). School choice: A mechanism design approach. The American Economic Review, 93(3), 729 747.

Aboodi, R. (2017). Is there still room for intertheoretic choice-worthiness comparisons?. In Rocky Mountain Ethics Congress (Ro ME), pp. 1 4.

Amanatidis, G., Markakis, E., Nikzad, A., & Saberi, A. (2017). Approximation algorithms for computing maximin share allocations. ACM Transactions on Algorithms (TALG), 13(4), 52.

Segal-Halevi, Hassidim, Aziz

Ashlagi, I., Braverman, M., & Hassidim, A. (2014). Stability in large matching markets with complementarities. Operations Research, 62(4), 713 732.

Aziz, H., Lang, J., & Monnot, J. (2016). Computing Pareto Optimal Committees. In Proc. IJCAI-16, pp. 60 66.

Aziz, H., Bir o, P., Lang, J., Lesca, J., & Monnot, J. (2016 2018). Optimal Reallocation Under Additive and Ordinal Preferences. In Proc. AAMAS-16, pp. 402 410.

Aziz, H., Gaspers, S., Mackenzie, S., & Walsh, T. (2015). Fair assignment of indivisible objects under ordinal preferences. Artiﬁcial Intelligence, 227, 71 92.

Aziz, H., Rauchecker, G., Schryen, G., & Walsh, T. (2017). Algorithms for Max-Min Share Fair Allocation of Indivisible Chores. In Proc. AAAI-17, pp. 1 7.

Aziz, H., Schlotter, I., & Walsh, T. (2016). Control of Fair Division. In Proc. IJCAI-16, pp. 67 73.

Bade, S. (2019). Matching with single-peaked preferences. Journal of Economic Theory, 180, 81 99.

Barber a, S., Bossert, W., & Pattanaik, P. K. (2004). Ranking sets of objects. In Barber a, S., Hammond, P. J., & Seidl, C. (Eds.), Handbook of Utility Theory, Vol. II, chap. 17, pp. 893 977. Kluwer Academic Publishers.

Barber a, S., Dutta, B., & Sen, A. (2001). Strategy-proof social choice correspondences. Journal of Economic Theory, 101(2), 374 394.

Barman, S., & Krishnamurthy, S. K. (2017). Approximation algorithms for maximin fair division. In Proceedings of the 2017 ACM Conference on Economics and Computation, pp. 647 664. ACM.

Baumeister, D., Bouveret, S., Lang, J., Nguyen, N.-T., Nguyen, T. T., Rothe, J., & Saﬃdine, A. (2017). Positional scoring-based allocation of indivisible goods. Autonomous Agents and Multi-Agent Systems, 31(3), 628 655.

Bogomolnaia, A., Moulin, H., Sandomirskiy, F., & Yanovskaya, E. (2017). Competitive division of a mixed manna. Econometrica, 85(6), 1847 1871. ar Xiv preprint 1702.00616.

Bossert, W. (1989). On the extension of preferences over a set to the power set: an axiomatic characterization of a quasi-ordering. Journal of Economic Theory, 49(1), 84 92.

Bossert, W. (1995). Preference extension rules for ranking sets of alternatives with a ﬁxed cardinality. Theory and decision, 39(3), 301 317.

Bouveret, S., Endriss, U., & Lang, J. (2010). Fair Division Under Ordinal Preferences: Computing Envy-Free Allocations of Indivisible Goods. In Proc. ECAI-10, pp. 387 392, Amsterdam, The Netherlands, The Netherlands. IOS Press.

Bouveret, S., & Lang, J. (2008). Eﬃciency and envy-freeness in fair division of indivisible goods: Logical representation and complexity. Journal of Artiﬁcial Intelligence Research, 32, 525 564.

Bouveret, S., & Lang, J. (2011). A General Elicitation-free Protocol for Allocating Indivisible Goods. In Proc. IJCAI-11, pp. 73 78. AAAI Press.

Fair Allocation with Diminishing Differences

Brams, S. J., & Kaplan, T. R. (2004). Dividing the Indivisible. Journal of Theoretical Politics, 16(2), 143 173.

Brams, S. J., Kilgour, & Klamler, C. (2012). The undercut procedure: an algorithm for the envy-free division of indivisible items. Social Choice and Welfare, 39(2-3), 615 631.

Brams, S. J., Kilgour, M., & Klamler, C. (2014). Two-person fair division of indivisible items: An eﬃcient, envy-free algorithm. Notices of the AMS, 61(2), 130 141.

Brams, S. J., & Taylor, A. D. (2000). The Win-Win Solution: Guaranteeing Fair Shares to Everybody (Norton Paperback) (Reprint edition). W. W. Norton & Company.

Brandl, F., Brandt, F., Geist, C., & Hofbauer, J. (2015). Strategic abstention based on preference extensions: Positive results and computer-generated impossibilities. In Twenty Fourth International Joint Conference on Artiﬁcial Intelligence, pp. 18 24.

Brandt, F. (2017). Rolling the dice: Recent results in probabilistic social choice. In Endriss, U. (Ed.), Trends in Computational Social Choice, chap. 1, pp. 3 26. AI Access.

Brandt, F., & Brill, M. (2011). Necessary and suﬃcient conditions for the strategyproofness of irresolute social choice functions. In Proceedings of the 13th Conference on Theoretical Aspects of Rationality and Knowledge, pp. 136 142. ACM.

Bronfman, S., Alon, N., Hassidim, A., & Romm, A. (2015a). Redesigning the Israeli medical internship match. In Proc. EC-15, pp. 753 754. ACM.

Bronfman, S., Hassidim, A., Afek, A., Romm, A., Shreberk, R., Hassidim, A., & Massler, A. (2015b). Assigning israeli medical graduates to internships. Israel journal of health policy research, 4(1), 6.

Budish, E. (2011). The Combinatorial Assignment Problem: Approximate Competitive Equilibrium from Equal Incomes. Journal of Political Economy, 119(6), 1061 1103.

Caragiannis, I., Kurokawa, D., Moulin, H., Procaccia, A. D., Shah, N., & Wang, J. (2019). The unreasonable fairness of maximum nash welfare. ACM Transactions on Economics and Computation (TEAC), 7(3), 12.

Cho, W. J. (2012). Probabilistic assignment: A two-fold axiomatic approach. Job-Market Paper.

Darmann, A. (2019). Manipulability in a group activity selection problem. Social Choice and Welfare, 52(3), 527 557.

Darmann, A., & Klamler, C. (2016). Proportional Borda allocations. Social Choice and Welfare, 47(3), 543 558.

Demange, G. (1982). Single-peaked orders on a tree. Mathematical Social Sciences, 3(4), 389 396.

Dickerson, J. P., Goldman, J., Karp, J., Procaccia, A. D., & Sandholm, T. (2014). The computational rise and fall of fairness. In Twenty-Eighth AAAI Conference on Artiﬁcial Intelligence, pp. 1405 1411.

Elkind, E., Lackner, M., & Peters, D. (2017). Structured preferences. In Endriss, U. (Ed.), Trends in Computational Social Choice, chap. 10, pp. 187 207. Lulu. com.

Segal-Halevi, Hassidim, Aziz

Elkind, E., & Lackner, M. (2014). On Detecting Nearly Structured Preference Proﬁles. In Proc. AAAI-14, pp. 661 667. AAAI Press.

Faliszewski, P., Skowron, P., Slinko, A., & Talmon, N. (2017). Multiwinner voting: A new challenge for social choice theory. Trends in computational social choice, 74, 27 47.

Faliszewski, P., Skowron, P., Slinko, A., & Talmon, N. (2019). Committee scoring rules: Axiomatic characterization and hierarchy. ACM Transactions on Economics and Computation (TEAC), 7(1), 3.

Gans, J. S., & Smart, M. (1996). Majority voting with single-crossing preferences. Journal of public Economics, 59(2), 219 237.

Ghodsi, M., Haji Aghayi, M., Seddighin, M., Seddighin, S., & Yami, H. (2018). Fair allocation of indivisible goods: Improvements and generalizations. In Proceedings of the 2018 ACM Conference on Economics and Computation, pp. 539 556. ACM. ar Xiv preprint 1704.00222.

Hadar, J., & Russell, W. R. (1969). Rules for ordering uncertain prospects. American Economic Review, 59, 2 34.

Hassidim, A., Romm, A., & Shorrer, R. I. (2016). Strategic behavior in a strategy-proof environment. In Proceedings of the 2016 ACM Conference on Economics and Computation, pp. 763 764. ACM.

Hassidim, A., Romm, A., & Shorrer, R. I. (2017). Redesigning the israeli psychology master s match. American Economic Review, 107(5), 205 09.

Herreiner, D., & Puppe, C. (2002). A simple procedure for ﬁnding equitable allocations of indivisible goods. Social Choice and Welfare, 19(2), 415 430.

Kalinowski, T., Narodytska, N., & Walsh, T. (2013). A Social Welfare Optimal Sequential Allocation Procedure. In Proc. IJCAI-13, pp. 227 233. AAAI Press.

Karlin, S. (1968). Total positivity, Vol. 1. Stanford University Press.

Kennai, Y., & Peleg, B. (1984). A note on the extension of an order on a set of the power set. Journal of Economic Theory, 3, 172 175.

Lipton, R. J., Markakis, E., Mossel, E., & Saberi, A. (2004). On approximately fair allocations of indivisible goods. In Proceedings of the 5th ACM conference on Electronic commerce, pp. 125 131. ACM.

Magiera, K., & Faliszewski, P. (2019). Recognizing top-monotonic preference proﬁles in polynomial time. Journal of Artiﬁcial Intelligence Research, 66, 57 84.

Mahajne, M., Nitzan, S., & Volij, O. (2015). Level r consensus and stable social choice. Social Choice and Welfare, 45(4), 805 817.

Nguyen, N.-T., Baumeister, D., & Rothe, J. (2015). Strategy-proofness of scoring allocation correspondences for indivisible goods. In Proc. IJCAI-15, pp. 1127 1133. AAAI Press.

Nitzan, M., Nitzan, S., & Segal-Halevi, E. (2018). Flexible level-1 consensus ensuring stable social choice: analysis and algorithms. Social Choice and Welfare, 50(3), 457 479.

Peters, D. (2018). Proportionality and strategyproofness in multiwinner elections. In Proceedings of the 17th International Conference on Autonomous Agents and Multi Agent

Fair Allocation with Diminishing Differences

Systems, pp. 1549 1557. International Foundation for Autonomous Agents and Multiagent Systems.

Procaccia, A. D., & Wang, J. (2014). Fair Enough: Guaranteeing Approximate Maximin Shares. In Proc. EC-14, pp. 675 692, New York, NY, USA. ACM.

Puppe, C., & Slinko, A. (2019). Condorcet domains, median graphs and the single-crossing property. Economic Theory, 67(1), 285 318.

Roth, A. E., & Peranson, E. (1997). The eﬀects of the change in the NRMP matching algorithm. JAMA, 278(9), 729 732.

Sandomirskiy, F., & Segal-Halevi, E. (2019). Fair division with minimal sharing.. ar Xiv preprint 1908.01669. Submitted to SODA 2020.

Segal-Halevi, E. (2019). Competitive equilibrium for almost all incomes.. ar Xiv preprint 1705.04212.

Suksompong, W., & Segal-Halevi, E. (2019). Democratic fair allocation of indivisible goods. Artiﬁcial Intelligence, 277, 103167.

Tarsney, C. (2018). Exceeding expectations: Stochastic dominance as a general decision theory.. ar Xiv preprint 1807.10895.

Young, H. (1974). An axiomatization of Borda s rule. Journal of Economic Theory, 9(1), 43 52.