Fair Allocation based on Diminishing Differences

1 Introduction

Algorithms for fair assignment of indivisible items differ in the kind of information they require from the users.

Avinatan Hassidim

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

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 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 profiles 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-efficiency. Necessary fairness is a strong requirement, which is not always satisfiable. For example, the AL procedure finds 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 profile consistent with the reported item-rankings, Again, "fair" may be substituted by proportional or envy-free or Pareto-efficient. 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. Specifically, 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 satisfied by the Borda scoring rule, as well as by many other scoring rules, as well as by lexicographic preferences.

DD is justified 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 (NDDfair) if it is fair according to all additive utility profiles satisfying the DD assumption, and possibly-DD-fair (PDD-fair) if it is fair according to at least one additive utility profile satisfying the DD assumption. Again, "fair" may be substituted by envy-free or proportional or Pareto-efficient. The following implications are obvious for any fairness criterion:

In other words, the DD-fairness criteria are intermediate in strength between necessary-fairness and possible-fairness. A formal definition of these concepts appears in Section 3.

The first 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 sufficient 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 finding 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 sufficient for the existence of a NecPR allocation for two agents. For NecPR, 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 NecPR 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 profiles at random, estimate the probability that an NDDPR/NecPR allocation exists, and check whether the NDDPR allocation given by our linear-time algorithm is indeed proportional according to the underlying cardinal utilities. We find that the increase in recall is substantial and ranges between 20% and 40%, but the decrease in precision is not substantial: when there are sufficiently 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-efficiency (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-efficiency (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.

1.2 RelatedWork

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 profiles, 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 definition is well-known:

Definition 1. For (multi-)bundles Xi, Yi:

3 DDUtility 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).

Definition 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 U DD (≻i). The Borda utility function is a member of U DD . Another example of a member in U DD 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 definition of U DD is given by the following lemma. The proof is arithmetic and it is omitted.

Lemma 1. The following are equivalent:

• (i) ui ∈ U DD (≻i)
• (ii) For every four items x1, x2, x3, x4 with x1 ⪰i x3 and x2 ⪰i x4 and x1 ̸= x2 and x3 ̸= x4:

3.1 Diminishing-Differences Preference Relations

We are now ready to present our main objects of interest - the Diminishing-Differences relations.

Definition 3. For (multi-)bundles Xi, Yi:

Remark 1. Comparing Definitions 1 and 3, it is clear that:

3.2 Diminishing-Differences Fairness

For every integer k and bundle Xi, define k · Xi as the multibundle in which each item of Xi is copied k times. We define proportionality by comparing, for each agent i, the bundle Xi copied n times, to the bundle of all itemsM.

Definition 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 ≿PDD i M.

Definition 5 (DD-envy-freeness). An allocation X is called

• Necessary-DD-envy-free (NDDEF) if for all agents i, j: Xi ≿NDD i Xj.

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

We now show that the DD assumption significantly 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:

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 PDDRelations

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 define the level of a multi-bundle as the sum of the levels of the items in it: LEV(X) := ∑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 define 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 termM 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 satisfies this condition; hence yk ≻i xk. Let C := LEVi(xk) - 1 and define ui as:

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 U DD (≻i) for which ui(Y ) > ui(X). We have to prove that either ̂ (i) |Y | > |X| or ̂ (ii) LEVi(Yk) > LEVi(Xk) for some k. There are two cases.

Case #1: |Y | > |X|. Then ̂ (i) is satisfied and we are done.

Consider the smallest k for which this inequality holds for some ui ∈ U DD (≻i). So for j < k, there exists no function in U DD (≻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:

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

so:

(the right-hand side of (3) is a weighted average of the righthand sides of (2)).

Combining (1) and (3) gives:

so condition ̂ (ii) is satisfied and we are done.

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

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.

Proof. ⇐= : If Y ̸≿NDD i X, then by definition 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 ≿PDD 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 ∈ U DD (≻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 ̸≿PDD Y .

Corollary 2. There is a linear-time algorithm to check whether X ≿PDD 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 sufficient 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 satisfied. 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 define 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 first 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 inM is weakly positive. The following table shows the levels and their differences for k′ ∈ {1, . . . , n} (recall that all items inMare distinct):

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}:

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

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 exactlyM. 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 NecPR allocation exists. These probabilities naturally depend on the correlation between the agents' rankings. When the rankings are completely correlated, both NDDPR and NecPR allocations do not exist; when the rankings are completely independent, both NDDPR and NecPR 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 NecPR/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 NecPR 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 sufficiently large, which further shows the robustness of our algorithm. We also checked the probability of existence of PDDPR and PosPR allocations, and it was nearly 1.0. Thus, apparently the NecPR requirement is too strong and the PDDPR and PosPR 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-efficiency and Envy-freeness

While the focus of this paper is on the effect of the DD condition on proportionality, we briefly survey below some results that we have for Pareto-efficiency and envy-freeness.

7.1 Pareto-efficiency

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-efficiency (PE).

An allocation is called Necessarily (NDD) PE if it is PE according to all profiles with additive (DD) utility functions.

Theorem 4. Necessary-PE is equivalent to NDD-PE.

Proof. =⇒ : If an allocation is necessarily-PE, then by definition 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 profile in which uAlice is lexicographic, and uBob(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 PossiblePE; proof is omitted. It is interesting that whereas DD leads to new fairness notions, it does not lead a new efficiency 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 sufficient. But for n = 3 they are no longer sufficient.

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

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.