# fair_allocation_based_on_diminishing_differences__4f763563.pdf

Fair Allocation Based on Diminishing Differences

Erel Segal-Halevi Bar-Ilan University erelsgl@gmail.com

Haris Aziz Data61 CSIRO and UNSW haris.aziz@data61.csiro.au

Avinatan Hassidim Bar-Ilan University avinatan@cs.biu.ac.il

Ranking alternatives is a natural way for humans to explain their preferences. It is being used in many settings, such as school choice (NY, Boston), course allocations, and the Israeli medical lottery. In some cases (such as the latter two), several items are given to each participant. Without having any information on the underlying cardinal utilities, arguing about fairness of allocation 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 difference between two items at the top is at least as large as the difference between two items down the list. This assumption implies a preference extension which we call diminishing differences (DD), where a 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 possiblyproportional according to this assumption. Based on this characterization, we present a polynomialtime algorithm for ﬁnding a necessarily-DDproportional allocation if it exists. Simulations based on a simple random model show that with high probability, a necessarily-proportional allocation does not exist but a necessarily-DDproportional allocation exists. Moreover, that allocation is proportional according to the underlying cardinal utilities.

1 Introduction

Algorithms for fair assignment of indivisible items differ 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 [Herreiner and Puppe, 2002], Approximate-CEEI procedure [Budish, 2011] and Undercut two-agent procedure [Brams et al., 2012; Aziz, 2015]. 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 often 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 [Brams and Taylor, 2000], approximate-maximin-share procedure [Procaccia and Wang, 2014] and Maximum Nash Welfare procedure [Caragiannis et al., 2016]. 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 (i.e, report a total order among) individual items. Such algorithms are often termed ordinal. Ordinal algorithms are ubiquitous in mechanism design, and are often used in real world applications, such as the National Residency Matching Program [Roth and Peranson, 1997] (even when married couples insert their preferences together [Ashlagi et al., 2014]), school choice applications [Abdulkadiroglu and S onmez, 2003], and university admittance [Hassidim et al., 2016a; 2016b]. One reason for this is that it is relatively easy for people to state ordinal preferences. Another reason is related to legacy systems: often the designer can change the allocation mechanism, but can not change the input procedure, as agents do not want to learn new ways to insert their input to the system. Ordinal algorithms are also common in AI and in fair division. Examples are the AL two-agent procedure [Brams et al., 2013], optimal-proportional procedure [Aziz et al., 2015], picking-sequence procedures [Brams and Kaplan, 2004; Bouveret and Lang, 2011] and the envy-free procedures of [Bouveret et al., 2010]. Such algorithms often assume that the agents preferences are implicitly represented by an additive

Proceedings of the Twenty-Sixth International Joint Conference on Artiﬁcial Intelligence (IJCAI-17)

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-efﬁ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 in order to keep its guarantee for necessary-envy-freeness. 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-efﬁ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 different than the one assumed by the algorithm. 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. I.e, even though agents may rank items differently, the mapping from the ranking to the numeric utility function is the same for all agents [Bouveret and Lang, 2011; Kalinowski et al., 2013; Baumeister et al., 2016; Darmann and Klamler, 2016]. This strong assumption weakens the fairness guarantee. Allocation may appear unfair to agents whose actual scoring rule is different.

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 care more about their high-valued items than about their lower-valued items. Speciﬁcally, we assume that the utility-difference 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 Differences (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. DD is justiﬁed in many settings where the agents are more concerned about getting a most preferred item than about not getting a least preferred item. For example, in a matching of doctors to internships, it was reported that doctors care the most about being assigned to one of their top choices [Bronfman et al., 2015a; 2015b]. Based on the DD assumption, we formalize several fairness notions. 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-efﬁcient. The following implications are obvious for any fairness criterion:

Nec-fair = NDD-fair = PDD-fair = Pos-fair

In other words, the DD-fairness criteria are intermediate in strength between necessary-fairness and possible-fairness. A formal deﬁnition of these concepts 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 (Section 4). Next, we prove a necessary and sufﬁcient condition for the existence of an NDD-proportional (NDDPR) allocation. Essentially, an NDDPR allocation exists iff it is possible to (a) give all agents the same number of items and (b) give each agent his best item. The proof is constructive and presents a simple linear-time algorithm for ﬁnding an NDDPR allocation if it exists (Section 5). It is interesting to compare the above condition to Condition D of Brams et al. [2013], which is necessary and sufﬁcient for the existence of a Nec PR allocation for two agents. For Nec PR, it is required that for every odd integer k {1, 3, . . . , 2n 1}, the agents have a different set of k best items; in particular, they should have a different worst item (see Example 2 in Sec. 3). For NDDPR, it is only required that the agents have a different best item. This means that an algorithm that returns NDDPR allocations may have larger recall than an algorithm that returns only Nec PR allocations. On the other hand, the precision of such an algorithm might be lower (i.e, its output allocations may be considered unfair by some agents). To assess the magnitude of these effects, we present a simple preliminary simulation experiment. We construct partially-correlated utility proﬁles at random, estimate the probability that an NDDPR/Nec PR allocation exists, and check whether the NDDPR allocation given by our linear-time algorithm is indeed proportional according to the underlying cardinal utilities. We ﬁnd that the increase in recall is substantial and ranges between 20% and 40%, but the decrease in precision is not substantial: when there are sufﬁciently many items, our simple NDDPR algorithm almost always results in an allocation which is proportional according to the cardinal utilities. While this experiment is preliminary, it indicates that there is potential for further investigation of NDDPR as a normative fairness criterion (Section 6). While our focus on this paper is on proportionality, we have results on other criteria, namely envy-freeness and Pareto-efﬁciency (Section 7). Whereas the DD assumption has a substantial effect on fairness notions, we show that the DD assumption does not lead to a new notion of Pareto-efﬁciency (PE). We show that NDD-PE is equivalent to necessary-PE and PDD-PE is equivalent to possible-PE. Finally, we show that checking whether an NDDEF allocation exists is NP-complete.

Proceedings of the Twenty-Sixth International Joint Conference on Artiﬁcial Intelligence (IJCAI-17)

1.2 Related Work

Extending preferences over individual objects to sets of objects is a natural and principled way of succinctly encoding preferences [Barber a et al., 2004]. One of the most common set-extensions is stochastic dominance (SD). It was developed for a different but related problem extending preferences over individual outcomes to lotteries on outcomes. If X, Y are lotteries, then X SD Y iff E[u(X)] E[u(Y )] for every weakly-increasing utility function u [Hadar and 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 upward-lexicographic (UL) [Cho, 2012; Bouveret et al., 2010; Nguyen et al., 2015]. The DD extension, which is the focus of this paper, is quite natural but has not been formalized in prior work. Interestingly, the DD extension is closely related to secondorder stochastic dominance (SSD). If X, Y are lotteries, then X SSD Y iff E[u(X)] E[u(Y )] for every utility function u which is weakly-increasing and weakly-concave [Hadar and Russell, 1969]. In the context of item assignment, weak concavity is equivalent to increasing differences agents care more about not getting the worst item than about getting the best item. Increasing differences make sense in fair division of chores [Aziz et al., 2017]; in future work we plan to study which of our results apply to that setting. Besides fair division, set-extensions have been applied for committee voting [Aziz et al., 2016a] and social choice correspondences (see e.g., [Barber a et al., 2001]). In social choice theory, it is common to study restricted domains of preference proﬁles, such as single-peaked, singlecrossing or level-r-consensus [Mahajne et al., 2015; Nitzan et al., 2017]. Many problems are much easier to solve in such restricted domains than in the domain of all preferences [Elkind and Lackner, 2014; Elkind et al., 2017]. The present paper focuses on a restriction to preferences satisfying the DD assumption, which has not been studied so far.

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. 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 has a strict ranking i on items. Each agent may also have a utility function ui on (multi-)bundles. All utility functions considered in this paper are positive and additive, so the utility of a (multi-)bundle is the sum of the utilities of the items in it. A utility function ui is consistent with i on items if for every two items x, y: ui({x}) > ui({y}) x i y. The set of all additive utility functions consistent with i is denoted by U( i). The following deﬁnition is well-known:

Deﬁnition 1. For (multi-)bundles Xi, Yi:

Xi Nec i Yi ui U( i): ui(Xi) ui(Yi)

Xi P os i Yi ui U( i): ui(Xi) ui(Yi)

3 DD Utility Functions and Relations Given a strict ranking i, we assign to each item x a level, denoted LEVi(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). Deﬁnition 2. Let i be a preference relation and ui a utility function consistent with i. ui has the Diminishing Differences (DD) property if, for every three items with consecutive levels x i y i z such that LEVi(x) = LEVi(y) + 1 = LEVi(z) + 2, it holds that ui(x) ui(y) ui(y) ui(z). The set of all additive DD utility functions consistent with i is denoted by UDD( i). The Borda utility function is a member of UDD. Another example of a member in UDD is the function Lexi(x) := 2LEVi(x), by which bundles are ordered by whether they contain the best item, then by whether they contain the second-best item, etc. An equivalent deﬁnition of UDD is given by the following lemma. The proof is arithmetic and it is omitted. Lemma 1. The following are equivalent: (i) ui UDD( i) (ii) For every four items x1, x2, x3, x4 with x1 i x3 and x2 i x4 and x1 = x2 and x3 = x4:

ui(x1) ui(x2) LEVi(x1) LEVi(x2) ui(x3) ui(x4) LEVi(x3) LEVi(x4)

3.1 Diminishing-Differences Preference Relations We are now ready to present our main objects of interest the Diminishing-Differences relations. Deﬁnition 3. For (multi-)bundles Xi, Yi:

Xi NDD i Yi ui UDD( i): ui(Xi) ui(Yi)

Xi P DD i Yi ui UDD( i): ui(Xi) ui(Yi)

Remark 1. Comparing Deﬁnitions 1 and 3, it is clear that:

Xi Nec i Yi = Xi NDD i Yi = Xi P DD i Yi = Xi P os i Yi

3.2 Diminishing-Differences Fairness For every integer k and bundle Xi, deﬁne k Xi as the multibundle in which each item of Xi is copied k times. We deﬁne proportionality by comparing, for each agent i, the bundle Xi copied n times, to the bundle of all items M. Deﬁnition 4 (DD-proportionality). An allocation X is called Necessary-DD-proportional (NDDPR) if: i N : n Xi NDD i M. Possible-DD-proportional (PDDPR) if: i N : n Xi P DD i M. Deﬁnition 5 (DD-envy-freeness). An allocation X is called Necessary-DD-envy-free (NDDEF) if for all agents i, j: Xi NDD i Xj.

Proceedings of the Twenty-Sixth International Joint Conference on Artiﬁcial Intelligence (IJCAI-17)

Possible-DD-envy-free (PDDEF) if for all agents i, j: Xi P DD i Xj.

We now show that the DD assumption signiﬁcantly affects the necessary and possible fairness requirements and results in meaningful fairness concepts. We give examples with two agents, so proportionality and envy-freeness coincide.

Example 1. Alice and Bob have the same preferences: 2m 2m 1 ... 4 3 2 1, for some m 3. Both Alice and Bob get m items: Alice gets 2m, 2m 1, ...m + 3, m + 2, 1 and Bob gets m + 1, m, ...3, 2. Intuitively this allocation seems very unfair, since Alice gets all the m 1 best items. However, it is possibly-fair, 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-fair: by Theorem 2 below, Bob s bundle is not PDD-better than Alice s bundle, since Alice s bundle is NDD-better and its level is strictly higher.

Example 2. Now, Alice and Bob have almost opposite preferences, for some m 2: Alice: 2m 2m 1 ... 4 3 2 1. Bob : 2 3 4 ... 2m 1 2m 1. Intuitively we would expect that opposite preferences make it easy to attain a fair division. However, in this case no necessarily-fair allocation exists. This is because Alice and Bob have the same worst item (1), and under the necessaryfairness assumption, no one agrees to receives this item (since the utility function of the agent who receives this item might assign a value near 0 to this item and a value near 1 to all other items). In contrast, our Theorem 3 shows that an NDDfair 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.

4 Characterizing NDD and PDD Relations

In this section we are given a preference relation i on items and two multi-bundles X, Y , and have to decide whether X NDD i Y . We begin by proving a convenient characterization of the NDD relation. For the characterization, we deﬁne the level of a multi-bundle as the sum of the levels of the items in it: LEV(X) := P x X LEV(x) (this is equal to the Borda score of X. Note that all copies of the same item have the same level). We order the items in each multibundle by decreasing level, so X = {x1, . . . , x|X|} where x1 i . . . i x|X| (the order between different copies of the same item is arbitrary). For each k |X| we deﬁne Xk as the k best items in X, Xk := {x1, . . . , xk}.

Theorem 1. Let X, Y be two multi-bundles. X NDD i Y iff

(i) |X| |Y | and

(ii) for each k {1, . . . , |Y |}: LEVi(Xk) LEVi(Yk).

Proof. = : We have to prove that if (i) |Y | > |X|, or (ii) LEV(Yk) > LEV(Xk) for some k, then X NDD i Y , i.e, there is a DD utility function ui such that ui(X) < ui(Y ).

(i) If |Y | > |X|, then take ui(x) = M 2 + LEVi(x). The term M 2 is so large that the utility of a bundle is dominated by its cardinality, so ui(X) < ui(Y ).

(ii) If for some k, LEVi(Yk) > LEVi(Xk), then let k be the smallest integer that satisﬁes this condition; hence yk i xk. Let C := LEVi(xk) 1 and deﬁne ui as:

ui(x) = [LEVi(x) C] M 2 for x i xk ui(x) = LEVi(x) for xk i x

The term M 2 is so large that the utility of a bundle is dominated by the level of its items that are weakly better than xk, so again ui(X) < ui(Y ).

= : Assume that X NDD i Y , and let ui be an additive function in UDD( i) for which ui(Y ) > ui(X). We have to prove that either c (i) |Y | > |X| or d (ii) LEVi(Yk) > LEVi(Xk) for some k. There are two cases. Case #1: |Y | > |X|. Then c (i) is satisﬁed and we are done.

Case #2: |Y | |X|. Then, since ui(Y ) > ui(X), there must be some k {1, . . . , |Y |} for which ui(Yk) > ui(Xk).

Consider the smallest k for which this inequality holds for some ui UDD( i). So for j < k, there exists no function in UDD( i) which assigns to Yj a higher value than to Xj. This means that ui(yk) > ui(xk), and the difference is substantial enough to make the value of Yk more than the value of Xk, i.e:

ui(yk) ui(xk) >

j=1 (ui(xj) ui(yj)) (1)

By our ordering of the items, j < k it holds that yj yk and xj xk. Hence, by Lemma 1, whenever xj = yj:

LEVi(yk) LEVi(xk)

ui(yk) ui(xk) LEVi(yj) LEVi(xj)

ui(yj) ui(xj)

= LEVi(xj) LEVi(yj)

ui(xj) ui(yj) (2)

LEVi(yk) LEVi(xk)

ui(yk) ui(xk)

Pk 1 j=1(LEVi(xj) LEVi(yj))

Pk 1 j=1(ui(xj) ui(yj)) (3)

(the right-hand side of (3) is a weighted average of the righthand sides of (2)). Combining (1) and (3) gives:

LEVi(yk) LEVi(xk) >

j=1 (LEVi(xj) LEVi(yj))

= LEVi(Yk) > LEVi(Xk),

so condition d (ii) is satisﬁed and we are done.

Example 3. Consider the following two bundles, where each item is represented by its level for some speciﬁc agent:

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

Proceedings of the Twenty-Sixth International Joint Conference on Artiﬁcial Intelligence (IJCAI-17)

Note that |X| > |Y |, X is lexicographically-better than Y , and even the Borda score of X is higher. However, the level of the two best items of X is only 12, which is less than that of the best two items of Y . Hence, by Theorem 1, it is not true that X NDD Y . Indeed, X is not better than Y according to all DD valuations. For example, let u(x) = LEV(x)2. The function u has DD, but u(X) = 82 < 83 = u(Y ).

Corollary 1. There is a linear-time algorithm to check whether X NDD i Y

The algorithm is obvious from Theorem 1 and is omitted.

Theorem 2. Let X, Y be two multi-bundles. Then X P DD i Y if and only if Y NDD i X or LEVi(Y ) = LEVi(X).

Proof. = : If Y NDD i X, then by deﬁnition of NDD, X has strictly more utility than Y for some consistent DD utility function. If LEVi(X) = LEVi(Y ), then X has the same Borda utility as Y . In both cases X P DD i Y . = : Suppose that Y NDD i X and LEVi(Y ) = LEVi(X). So LEVi(Y ) > LEVi(X) By Theorem 1 we must have |Y | |X|, and for every k |X|: LEVi(Yk) LEVi(Xk). For every k, Theorem 1 is applicable to the multi-bundles Xk, Yk. So for any function ui UDD( i), ui(Yk) ui(Xk). Moreover, if LEVi(Y|X|) > LEVi(X|X|) then also ui(Y|X|) > ui(X|X|) = ui(X); otherwise, LEVi(Y|X|) = LEVi(X|X|) and ui(Y|X|) = ui(X|X|), so Y must have more than |X| items, and since all items have positive utility, again ui(Y ) > ui(X). In all cases, for all DD consistent utility functions, ui(Y ) > ui(X). Hence, X P DD Y .

Corollary 2. There is a linear-time algorithm to check whether X P DD i Y .

Corollary 3. It can be decided in polynomial time whether a given allocation is NDDPR, NDDEF, PDDPR or PDDEF.

5 Existence of NDD-Proportional Allocations

In this section, we prove the following necessary and sufﬁcient condition for existence of NDDPR allocations.

Theorem 3. An NDDPR allocation exists if-and-only-if:

(a) The number of items is M = m n, where m is an integer and n is the number of agents, and -

(b) Each agent has a different best item.

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

Proof of = . Suppose the two conditions are satisﬁed. We are going to prove that the following simple algorithm produces an NDDPR allocation:

Repeat as long as there are items: For i = 1 . . . n: give agent i his best remaining item. For i = n . . . 1: give agent i his best remaining item.

The proof proceeds in two steps. First, we identify a worst case scenario of the algorithm. Second, we prove that even in this scenario, the allocation is NDDPR.

We will prove that the worst-case scenario is when (1) all agents have the same set of n best items and the same set of M n worst items, and (2) all agents rank the M n worst items in exactly the same way (note that the agents must differ in their ranking on the set of n best items since each agent must still have a different top item). For each agent i, we deﬁne two bundles: Xi the bundle allocated to i by the above algorithm. Yi the bundle that would be allocated to i in the worstcase scenario. We will prove that the following are true for each agent i:

(a) Xi Nec i Yi (i.e, Yi is indeed the worst-case outcome of the algorithm),

(b) n Yi NDD i M (even this worst-case is NDDPR).

The theorem follows from (a) and (b) by transitivity. To prove (a), we use the following well-known characterization [Brams et al., 2013; Bouveret et al., 2010]:

X Nec i Y if-and-only-if there exists a bijection f : X Y such that for all x X: x f(x).

We use the bijection that maps the best item in Xi to the best item in Yi, the 2nd-best item in Xi to the 2nd-best item in Yi, and so on. We prove that for every k, the k-th best item in Xi is at least as good as the k-th best item in Yi. This is certainly true for k = 1 since the best items are the same. For k > 1, when agent i picks his k-th item (which is the k-th best item in Xi), the number of items already taken is kn i (if k is even) or kn (n i + 1) (if k is odd). Therefore, agent i s best remaining item has a level of at least M (kn i) (if k is even) or M kn + (n i + 1) (if k is odd). This is always at least as large as the level of the k-th-best item in Yi. To prove (b), we apply Theorem 1. The ﬁrst condition is |n Yi| |M|. Indeed, in our case |n Yi| = n m = M = |M|. The second condition is that, for each integer k {1, . . . , M}, the level of the best k items in n Yi minus the level of the best k items in M is weakly positive. The following table shows the levels and their differences for k {1, . . . , n} (recall that all items in M are distinct):

n Yi M M . . . M M M M 1 . .. M n + 1 Difference 0 1 . .. n 1

Clearly the level difference is always weakly positive. The total level difference after the best n items is n(n 1)/2. The following table shows the levels and their differences for k {n + 1, . . . , 2n}:

n Yi M 2n + i M 2n + i . . . M 2n + i M M n M n 1 . . . M 2n + 1 Difference i n i n + 1 . . . i 1

Clearly, since i 1, the level difference in the table is weakly larger than (1 n)+(1 n+1)+. . .+(1 1) = n(n 1)/2. Since we already have a level difference of +n(n 1)/2 from the previous n items, the total level difference remains weakly positive. The total level difference in the table is n(n 1)/2 + n(i 1) so the total level difference of the best 2n items is n(i 1).

Proceedings of the Twenty-Sixth International Joint Conference on Artiﬁcial Intelligence (IJCAI-17)

The following table shows the levels and their differences for k {2n + 1, . . . , 3n}:

n Yi M 2n i + 1 M 2n i + 1 . . . M 2n i + 1 M M 2n M 2n 1 ... M 3n + 1 Difference 1 i 2 i ... n i

Clearly, each difference in the table is (i 1) or larger, and there are n such differences. Since we already have a level difference of +n (i 1) from the previous 2n items, the total level difference remains weakly positive. The total level difference in the table is n(n 1)/2 (n 1)i so the total level difference of the best 3n items is n(n 1)/2. We are now back at the same situation as after the best n items, so we can repeat the same reasoning and conclude that the level difference of the best k items is always weaklypositive.

Proof of = . Let (p(1), . . . , p(n)) be an NDDPR allocation. Then for every agent i, n Xi NDD i M. We now apply the two conditions of Theorem 1. (a) For all i: |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. (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 every i, Xi must contains agent i s best item. So the best items of all agents must be different.

6 NDD-Proportionality in Simulations

We compared the various fairness criteria using a quick preliminary simulation experiment with 2 agents. First, we checked to what extent the probability that an NDDPR allocations exists is higher than the probability that an Nec PR allocation exists. These probabilities naturally depend on the correlation between the agents rankings. When the rankings are completely correlated, both NDDPR and Nec PR allocations do not exist; when the rankings are completely independent, both NDDPR and Nec PR allocations exist with high probability; the interesting zone is when the rankings are partially correlated. To simulate such rankings, we determined for each item a market value drawn uniformly at random from [1, 2]. We determined the value of each item to each agent as the item s market value plus noise drawn uniformly at random from [ A, A], where A is a parameter. Based on the cardinal values we determined the agent s ordinal ranking. Then, we checked whether there exists an Nec PR/NDDPR allocation. We did this experiment 1000 times for different values of A {0.1, . . . , 1} and for different numbers of items 2m items for m {2, . . . , 8}. Typical results are plotted in Figure 1; the probability of existence of NDDPR allocations (balls) is clearly higher than that of Nec PR allocations (triangles): Since we had randomly-generated cardinal values, we used them for a secondary purpose we checked whether, when an NDDPR allocation exists, the one found by the simple algorithm of Section 5 is proportional according to these values (dashed lines). Note that, since the randomization we

used is completely uniform and does not use the DD assumption, the probability that DD holds for both agents is very low 1/((2m 1)!)2. Nevertheless, our NDDPR allocation (when it exists) is almost always proportional when the number of items or the noise size are sufﬁciently large, which further shows the robustness of our algorithm. We also checked the probability of existence of PDDPR and Pos PR allocations, and it was nearly 1.0. Thus, apparently 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 many instances (= high recall ) and most solutions are satisfactory (= high precision ).

7 Pareto-efﬁciency and Envy-freeness While the focus of this paper is on the effect of the DD condition on proportionality, we brieﬂy survey below some results that we have for Pareto-efﬁciency and envy-freeness.

7.1 Pareto-efﬁciency In the preceding sections we saw that the DD condition has a substantial effect on fairness notions: NDD-fair allocations are strictly easier (in terms of existence) than necessaryfair allocations, and PDD-fair allocations are harder than possibly-fair allocations (see examples in Subsection 3.2). Interestingly, the DD condition does not have this effect on Pareto-efﬁciency (PE). An allocation is called Necessarily (NDD) PE if it is PE according to all proﬁles with additive (DD) utility functions. Theorem 4. Necessary-PE is equivalent to NDD-PE.

Proof. = : If an allocation is necessarily-PE, then by deﬁnition it is also NDD-PE. = : Suppose an allocation X is not necessarily-PE. Then, by Aziz et al. [2016b] Thm 9, 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. I.e, there are two agents Alice and Bob, such that XBob contains an item which Alice strictly prefers over two items in XAlice. Then X is not NDD-PE, since it is not PE according to the utility proﬁle in which u Alice is lexicographic, and u Bob(x) = M 2 + LEVBob(x), so that his utility is dominated by the number of items he has.

Analogously, Possible-DD-PE is equivalent to Possible PE; proof is omitted. It is interesting that whereas DD leads to new fairness notions, it does not lead a new efﬁciency notion.

7.2 DD-envy-freeness Since every NDDEF allocation is NDDPR, the two conditions of Theorem 3 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 sufﬁcient. But for n = 3 they are no longer sufﬁcient. Example 4. There are six items {1, . . . , 6}. The preferences of the three agents Alice Bob and Carl are: Alice: 6 5 3 4 2 1 Bob: 5 4 3 6 2 1

Proceedings of the Twenty-Sixth International Joint Conference on Artiﬁcial Intelligence (IJCAI-17)

Figure 1: NDD-proportionality in Simulations

Carl: 4 6 3 5 2 1 The conditions of Theorem 3 are clearly satisﬁed. However, no NDDEF allocation exists. Proof: 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 Alice s bundle is {6, 1} and her Borda score is 7. To ensure that Alice is not envious, Bob must get {5, 2} and Carl must get {3, 4}. This allocation is NDDPR but it is not NDDEF, since Bob Bordaenvies Carl.

Since the NDDPR characterization does not work for NDDEF allocations even for three agents, it is an open problem whether the existence of NDDEF allocations can be decided efﬁciently. When the number of agents is not bounded, we have the following hardness result: Theorem 5. Checking the existence of NDDEF allocations is NP-complete when there are n agents and at least 2n items. The reduction is similar to the NP-completeness of checking existence of NEF allocations [Bouveret et al., 2010]. The proof requires carefully checking that the reduction argument works for NDDEF as well. 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 like NDDPR, or NP-hard like NEF [Aziz et al., 2016c]?

8 Conclusions and Future Work We formalized natural ways to compare sets by using the DD (diminishing differences) assumption. The relations lead to new fairness concepts which we studied in detail. In future work, it will be interesting to identify other interesting set extensions that correspond to classes of utility functions. Other future work includes extending some of our results to the case where agents may express weak preferences, or where the items have negative utilities (chores).

Acknowledgments We acknowledge the Dagstuhl Seminar 16232 on Fair Division where this project was initiated. We are grateful to four

anonymous IJCAI reviewers for their very helpful comments. Haris Aziz is supported by a Julius Career Award. Erel is 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.

[Abdulkadiroglu and S onmez, 2003] Atila Abdulkadiroglu and Tayfun S onmez. School choice: A mechanism design approach. The American Economic Review, 93(3):729 747, 2003.

[Ashlagi et al., 2014] Itai Ashlagi, Mark Braverman, and Avinatan Hassidim. Stability in large matching markets with complementarities. Operations Research, 62(4):713 732, 2014.

[Aziz et al., 2015] Haris Aziz, Serge Gaspers, Simon Mackenzie, and Toby Walsh. Fair assignment of indivisible objects under ordinal preferences. Artiﬁcial Intelligence, 227:71 92, October 2015.

[Aziz et al., 2016a] H. Aziz, J. Lang, and J. Monnot. Computing Pareto Optimal Committees. In Proc. IJCAI-16, pages 60 66, 2016.

[Aziz et al., 2016b] Haris Aziz, P ater Bir o, J erˆome Lang, Julien Lesca, and J erˆome Monnot. Optimal Reallocation Under Additive and Ordinal Preferences. In Proc. AAMAS16, pages 402 410, 2016.

[Aziz et al., 2016c] Haris Aziz, Ildiko Schlotter, and Toby Walsh. Control of Fair Division. In Proc. IJCAI-16, pages 67 73, 2016.

[Aziz et al., 2017] Haris Aziz, Gerhard Rauchecker, Guido Schryen, and Toby Walsh. Algorithms for Max-Min Share Fair Allocation of Indivisible Chores. In Proc. AAAI-17, pages 1 7, 2017.

[Aziz, 2015] Haris Aziz. A note on the undercut procedure. Social Choice and Welfare, 45(4):723 728, 2015.

Proceedings of the Twenty-Sixth International Joint Conference on Artiﬁcial Intelligence (IJCAI-17)

[Barber a et al., 2001] S. Barber a, B. Dutta, and A. Sen. Strategy-proof social choice correspondences. Journal of Economic Theory, 101(2):374 394, 2001. [Barber a et al., 2004] S. Barber a, W. Bossert, and P. K. Pattanaik. Ranking sets of objects. In S. Barber a, P. J. Hammond, and C. Seidl, editors, Handbook of Utility Theory, volume II, chapter 17, pages 893 977. Kluwer Academic Publishers, 2004. [Baumeister et al., 2016] Dorothea Baumeister, Sylvain Bouveret, J erˆome Lang, Nhan-Tam Nguyen, Trung Thanh Nguyen, J org Rothe, and Abdallah Safﬁdine. Positional scoring-based allocation of indivisible goods. Autonomous Agents and Multi-Agent Systems, pages 1 28, 2016. [Bouveret and Lang, 2011] Sylvain Bouveret and J erˆome Lang. A General Elicitation-free Protocol for Allocating Indivisible Goods. In Proc. IJCAI-11, pages 73 78. AAAI Press, 2011. [Bouveret et al., 2010] Sylvain Bouveret, Ulle Endriss, and J erˆome Lang. Fair Division Under Ordinal Preferences: Computing Envy-Free Allocations of Indivisible Goods. In Proc. ECAI-10, pages 387 392, Amsterdam, The Netherlands, The Netherlands, 2010. IOS Press. [Brams and Kaplan, 2004] Steven J. Brams and Todd R. Kaplan. Dividing the Indivisible. Journal of Theoretical Politics, 16(2):143 173, 2004. [Brams and Taylor, 2000] Steven J. Brams and Alan D. Taylor. The Win-Win Solution: Guaranteeing Fair Shares to Everybody (Norton Paperback). W. W. Norton & Company, reprint edition, October 2000. [Brams et al., 2012] Steven J. Brams, Kilgour, and Christian Klamler. The undercut procedure: an algorithm for the envy-free division of indivisible items. Social Choice and Welfare, 39(2-3):615 631, October 2012. [Brams et al., 2013] Steven J. Brams, D. Marc Kilgour, and Christian Klamler. Two-Person Fair Division of Indivisible Items: An Efﬁcient, Envy-Free Algorithm. Social Science Research Network Working Paper Series, pages 130 141, June 2013. [Brandt, 2017] F. Brandt. Rolling the dice: Recent results in probabilistic social choice. In U. Endriss, editor, Trends in Computational Social Choice, chapter 1. AI Access, 2017. [Bronfman et al., 2015a] Slava Bronfman, Noga Alon, Avinatan Hassidim, and Assaf Romm. Redesigning the israeli medical internship match. In Proc. EC-15, pages 753 754. ACM, 2015. [Bronfman et al., 2015b] Slava Bronfman, Avinatan Hassidim, Arnon Afek, Assaf Romm, Rony Shreberk, Ayal Hassidim, and Anda Massler. Assigning israeli medical graduates to internships. Israel journal of health policy research, 4(1):6, 2015. [Budish, 2011] Eric Budish. The Combinatorial Assignment Problem: Approximate Competitive Equilibrium from Equal Incomes. Journal of Political Economy, 119(6):1061 1103, December 2011.

[Caragiannis et al., 2016] Ioannis Caragiannis, David Kurokawa, Herve Moulin, Ariel D. Procaccia, Nisarg Shah, and Junxing Wang. The Unreasonable Fairness of Maximum Nash Welfare. In Proc. EC-16, 2016. [Cho, 2012] Wonki J. Cho. Probabilistic assignment: A twofold axiomatic approach. Job-Market Paper, 2012. [Darmann and Klamler, 2016] Andreas Darmann and Christian Klamler. Proportional Borda allocations. Social Choice and Welfare, 47(3):543 558, 2016. [Elkind and Lackner, 2014] Edith Elkind and Martin Lackner. On Detecting Nearly Structured Preference Proﬁles. In Proc. AAAI-14, pages 661 667. AAAI Press, 2014. [Elkind et al., 2017] E. Elkind, M. Lackner, and D. Peters. Structured preferences. In U. Endriss, editor, Trends in Computational Social Choice, chapter 10. 2017. [Hadar and Russell, 1969] Joseg Hadar and William R. Russell. Rules for ordering uncertain prospects. American Economic Review, 59:2 34, 1969. [Hassidim et al., 2016a] Avinatan Hassidim, Assaf Romm, and Ran I Shorrer. Strategic behavior in a strategy-proof environment. In Proceedings of the 2016 ACM Conference on Economics and Computation, pages 763 764. ACM, 2016. [Hassidim et al., 2016b] Avinatan Hassidim, Assaf Romm, Ran I Shorrer, et al. Redesigning the israeli psychology masters match. Technical report, 2016. [Herreiner and Puppe, 2002] Dorothea Herreiner and Clemens Puppe. A simple procedure for ﬁnding equitable allocations of indivisible goods. Social Choice and Welfare, 19(2):415 430, 2002. [Kalinowski et al., 2013] Thomas Kalinowski, Nina Narodytska, and Toby Walsh. A Social Welfare Optimal Sequential Allocation Procedure. In Proc. IJCAI-13, pages 227 233. AAAI Press, 2013. [Mahajne et al., 2015] Muhammad Mahajne, Shmuel Nitzan, and Oscar Volij. Level r consensus and stable social choice. Social Choice and Welfare, 45(4):805 817, 2015. [Nguyen et al., 2015] N-T. Nguyen, D. Baumeister, and J. Rothe. Strategy-proofness of scoring allocation correspondences for indivisible goods. In Proc. IJCAI-15, pages 1127 1133. AAAI Press, 2015. [Nitzan et al., 2017] Mor Nitzan, Shmuel Nitzan, and Erel Segal-Halevi. On Level-1 Consensus Ensuring Stable Social Choice, April 2017. ar Xiv preprint 1704.06037. [Procaccia and Wang, 2014] Ariel D. Procaccia and Junxing Wang. Fair Enough: Guaranteeing Approximate Maximin Shares. In Proc. EC-14, pages 675 692, New York, NY, USA, 2014. ACM. [Roth and Peranson, 1997] A. E. Roth and E. Peranson. The effects of the change in the NRMP matching algorithm. JAMA, 278(9):729 732, 1997. [Young, 1974] H.P Young. An axiomatization of borda s rule. Journal of Economic Theory, 9(1):43 52, 1974.

Proceedings of the Twenty-Sixth International Joint Conference on Artiﬁcial Intelligence (IJCAI-17)