# equitable_allocations_of_indivisible_goods__79e87ff4.pdf

Equitable Allocations of Indivisible Goods

Rupert Freeman1 , Sujoy Sikdar2 , Rohit Vaish2 and Lirong Xia2

1Microsoft Research New York City 2Rensselaer Polytechnic Institute rupert.freeman@microsoft.com, sikdas@rpi.edu, vaishr2@rpi.edu, xial@cs.rpi.edu

In fair division, equitability dictates that each participant receives the same level of utility. In this work, we study equitable allocations of indivisible goods among agents with additive valuations. While prior work has studied (approximate) equitability in isolation, we consider equitability in conjunction with other well-studied notions of fairness and economic efﬁciency. We show that the Leximin algorithm produces an allocation that satisﬁes equitability up to any good and Pareto optimality. We also give a novel algorithm that guarantees Pareto optimality and equitability up to one good in pseudopolynomial time. Our experiments on real-world preference data reveal that approximate envy-freeness, approximate equitability, and Pareto optimality can often be achieved simultaneously.

1 Introduction

We consider fair division problems that require a central planner to divide a set of goods among a group of agents each with their own individual preferences over the goods such that the resulting allocation is fair. How exactly one can certify that an allocation is fair remains a subject of debate, but the literature suggests two distinct viewpoints. In the ﬁrst viewpoint, an agent should prefer her bundle of goods to some comparison bundle. The gold standard of fairness here is envyfreeness, which says that each agent should prefer her bundle of goods to any other agents bundle. In this work, we consider the second viewpoint, in which agents compare their happiness levels, or utilities. Here, an allocation is considered fair if the planner is able to make all agents equally well-off. A central fairness notion in this context is equitability: An equitable allocation is one where agents derive equal utilities from their assigned shares. Stated differently, an equitable allocation seeks to minimize the disparity between the best-off and the worst-off agents. Both perspectives have merit, but the practical importance of equitability as a fairness criterion has been highlighted in an experimental study conducted by [2009]. They asked human subjects to deliberate over an assignment of indivisible

Contact Author

goods subject to a time limit. It was found that the chosen outcomes were equitable (and Pareto optimal) far more often than they were envy-free. They concluded that equitability is a signiﬁcant predictor of the perceived fairness of an allocation, often more so than envy-freeness. Like many other fairness notions, equitability has been traditionally studied for divisible goods (i.e., cake-cutting). In this setting, it is known that an equitable allocation always exists [Dubins and Spanier, 1961; Alon, 1987]. On the computability side, it is known that no ﬁnite procedure can ﬁnd an (exact) equitable division [Procaccia and Wang, 2017], though an ε-equitable division can be computed in a ﬁnite number of steps [Cechlárová and Pillárová, 2012a; Cechlárová and Pillárová, 2012b]. For indivisible goods, an equitable (EQ) allocation might fail to exist even with two agents and a single good, motivating the need for approximations. To this end, [2014] proposed the notion of near jealousy-freeness, under which for any pair of agents, the disparity can be reversed by removing any good from the bundle of the agent with higher utility. We refer to this notion as equitability up to any good (EQx) in keeping with the nomenclature for a similar relaxation of envy-freeness [Caragiannis et al., 2016]. We also study equitability up to one good (EQ1), requiring only that inequity can be eliminated by removing some good from the higher-utility-agent s bundle. [2014] showed that for additive valuations, an EQx (hence, EQ1) allocation always exists and can be computed in polynomial time. However, they did not study Pareto optimality (PO), a fundamental and often desirable notion of economic efﬁciency that may still be violated by an (approximately) equitable allocation. Our work takes a deeper dive into the study of (approximately) equitable allocations of indivisible goods in conjunction with Pareto optimality as well as other well-studied notions of fairness (envy-freeness and its relaxations) and considers a host of existence and computational questions. Table 1 provides a comprehensive summary of our results. Some of the highlights are:

We strengthen the aforementioned result of [2014] to show that an EQx and PO allocation always exists for strictly positive valuations (Proposition 3). Without the positivity assumption, even an EQ1+PO allocation might fail to exist (Example 1), and ﬁnding an EQ/EQx/EQ1+PO allocation becomes strongly NP-

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

Fairness + Efﬁciency Existence Results Computational Results general special case general special case EQ even for two agents and one good strongly NP-c even for id (Proposition 1) EQx (Proposition 2) Poly-time (Proposition 2) EQ1

EQ even for two agents and one good Poly-time for bin (Theorem 2) EQx strongly NP-h (Remark 1) Poly-time for bin (Theorem 4) EQ1 (Example 1) for pos (Proposition 3) strongly NP-h (Theorem 1) Pseudopoly-time for pos (Theorem 3)

even for two agents and one good

Poly-time for bin (Remark 3) EQx NP-c even for bin (Remark 4) EQ1

even for bin (Example 1)

Poly-time for bin (Remark 3) EQx Poly-time for bin (Theorem 4) EQ1

even for pos (Proposition 4)

Poly-time for bin (Remark 3) EQx Poly-time for bin (Theorem 4) EQ1

strongly NP-h (Corollary 1)

Table 1: Summary of results. For Existence Results, a denotes guaranteed existence while a indicates that existence might fail for some instance. For Computational Results, NP-c/NP-h refers to NP-complete/NP-hard. The shorthands bin, id, and pos refer to binary, identical, and strictly positive valuations, respectively.

hard (Theorem 1 and Remark 1).

As a step towards making the above existence result constructive, we design a pseudopolynomial-time algorithm that always returns an EQ1+PO allocation for strictly positive valuations (Theorem 3).

We construct an instance in which no allocation can be EQ1+EF1+PO (Proposition 4).1 We show that determining whether such an allocation exists is, in general, strongly NP-hard (Corollary 1), but the special case of binary valuations is efﬁciently solvable (Theorem 4).

We validate our theoretical results via experiments on the data from the popular fair division website Spliddit2 as well as on synthetically generated instances (Section 4).

Related Work For divisible goods (i.e., cake-cutting), [1961] showed that an equitable division always exists (without providing a bound on the number of cuts). Subsequent work has established the existence of equitable divisions where each agent gets a contiguous piece [Cechlárová et al., 2013; Aumann and Dombb, 2015; Chèze, 2017]. Equitability has also been studied in combination with other fairness and efﬁciency notions. It is known that there always exists a cake division that is simultaneously equitable and envy-free [Alon, 1987]. However, existence might fail if, in addition, one also requires Pareto optimality [Brams et al., 2013] or contiguous pieces [Brams et al., 2006]. Connections between Pareto optimality and social welfare maximizing equitable divisions have also been studied [Brams et al., 2012]. For indivisible goods, in addition to the work of [2014] discussed above, [2019] studies equitable and connected allocations of indivisible goods (i.e., when the goods constitute the vertices of a graph and a feasible allocation assigns every agent a connected subgraph).

1EF1 stands for envy-freeness up to one good, which is a (necessary) relaxation of envy-freeness deﬁned for indivisible goods; see Section 2 for the relevant deﬁnitions. 2http://www.spliddit.org/

2 Preliminaries Problem instance. An instance [n], [m], V of the fair division problem is deﬁned by a set of n N agents [n] = {1, 2, . . . , n}, a set of m N goods [m] = {1, 2, . . . , m}, and a valuation proﬁle V = {v1, v2, . . . , vn} that speciﬁes the preferences of every agent i [n] over each subset of the goods in [m] via a valuation function vi : 2[m] N {0}.3 We will assume that the valuation functions are additive, i.e., for any agent i [n] and any set of goods S [m], vi(S) := P j S vi({j}), where vi( ) = 0. For a singleton good j [m], we will write vi,j instead of vi({j}).

Allocation. An allocation A := (A1, . . . , An) is an npartition of the set of goods [m], where Ai [m] is the bundle allocated to the agent i. Given an allocation A, the utility of an agent i [n] for the bundle Ai is vi(Ai) = P j Ai vi,j.

Equitable allocations. An allocation A is said to be equitable (EQ) if for every pair of agents i, k [n], we have vi(Ai) = vk(Ak). An allocation A is equitable up to one good (EQ1) if for every pair of agents i, k [n] such that Ak = , there exists some good j Ak such that vi(Ai) vk(Ak \ {j}). An allocation A is equitable up to any good (EQx) if for every pair of agents i, k [n] such that Ak = and for every good j Ak such that vk,j > 0, we have vi(Ai) vk(Ak \ {j}).4

Envy-free allocations. An allocation A is envy-free (EF) if for every pair of agents i, k [n], we have vi(Ai) vi(Ak). An allocation A is envy-free up to one good (EF1) if for every pair of agents i, k [n] such that Ak = , there exists some good j Ak such that vi(Ai) vi(Ak \ {j}). An allocation A is envy-free up to any good (EFx) if for every pair of agents i, k [n] such that Ak = and for every good j Ak such that vi,j > 0, we have vi(Ai) vi(Ak \ {j}). The notions

3Integrality of valuations is required only for Theorem 3. Our positive results (i.e., existence and algorithmic results) hold even in the absence of this assumption, and negative results (i.e., nonexistence and hardness results) hold even for integral valuations. 4Our results hold analogously for the following variant of EQx due to [2014]: For every pair of agents i, k [n] such that Ak = , vi(Ai) vk(Ak \ {j}) for every good j Ak.

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

of EF, EF1, and EFx are due to [1967], [2011],5 and [2016], respectively.

Pareto optimality. An allocation A is Pareto optimal if there is no other allocation B such that vk(Bk) vk(Ak) for every agent k [n] with at least one of the inequalities being strict.

Nash social welfare. Given an instance [n], [m], V , the Nash social welfare of an allocation A is deﬁned as

NSW(A) := Q i [n] vi(Ai) 1/n . An allocation A is called Nash optimal or MNW (Maximum Nash Welfare) if it maximizes the Nash social welfare among all allocations.6

Leximin-optimal allocations. A Leximin-optimal allocation [Dubins and Spanier, 1961] is one that maximizes the minimum utility that any agent achieves, subject to which the second-minimum utility is maximized, and so on. The utilities induced by a Leximin-optimal allocation are unique, although there may exist more than one such allocation.

3 Results This section presents our theoretical results, summarized in Table 1. We ﬁrst consider equitability and its relaxations, then consider them in conjunction with Pareto optimality, before ﬁnally adding envy-freeness (and its relaxations) to the mix.

3.1 Existence and Computation of EQ, EQ1, EQx We will start by observing that envy-freeness and equitability (and their corresponding relaxations) become equivalent when the valuations are identical (i.e., when, for every good j [m], vi,j = vk,j for all i, k [n]). Proposition 1. For identical valuations, an allocation is EF/EF1/EFx if and only if it is EQ/EQ1/EQx. It is known that determining whether a given instance has an envy-free (EF) allocation is NP-complete even for identical valuations (via a straightforward reduction from PARTITION) [Lipton et al., 2004].7 Proposition 1 implies that the same holds for equitable (EQ) allocations. By contrast, an EQx (and therefore EQ1) allocation always exists and can be efﬁciently computed (Proposition 2) even for non-identical valuations. Proposition 2 ([Gourvès et al., 2014]). An EQx allocation always exists and can be computed in polynomial time. Brieﬂy, [2014] prove Proposition 2 using a greedy algorithm. In each round, the algorithm assigns a least-happy agent its favorite good from among the remaining goods. Thus, at any stage, the most recent good assigned to an agent is also its least-favorite good in its own bundle. Since each new good is assigned to an agent with the least utility, an allocation that is EQx prior to the assignment continues to be so

5 [2004] previously deﬁned a slightly weaker notion than EF1, but their algorithm can, in fact, compute an EF1 allocation. 6[2016] deﬁne a Nash optimal allocation as one that provides positive utility to the largest set of agents, and subject to that, maximizes the geometric mean of valuations. Our results hold even under this extended deﬁnition. 7In fact, the problem is strongly NP-complete due to a similar reduction from 3-PARTITION.

after it (up to the removal of the most recently assigned good). The claim now follows by induction over the rounds. Proposition 2 presents an interesting contrast between the notions of EQx and EFx: An EQx allocation is guaranteed to exist and can be efﬁciently computed, whereas for EFx, even the question of guaranteed existence is an open problem.

3.2 Equitability and Pareto Optimality We now turn our attention to computing an allocation that is both equitable up to one good and Pareto optimal (we use the shorthand EQ1+PO for such allocations). Unfortunately, such allocations might fail to exist when the valuations are allowed to be zero-valued (Example 1). This provides an interesting contrast with the analogous relaxation of envy-freeness; it is known that an allocation satisfying EF1 and PO always exists [Caragiannis et al., 2016; Barman et al., 2018a]. Example 1 (Non-existence of EQ1+PO). Consider an instance with three agents a1, a2, a3 and six goods g1, . . . , g6. The goods g1, g2, g3 are valued at 1 by a1 and at 0 by a2 and a3. The goods g4, g5, g6 are valued at 1 by a2 and a3 and at 0 by a1. Any PO allocation must assign g1, g2, g3 to a1 (giving it a utility of 3) and allocate g4, g5, g6 between a2 and a3. Either a2 or a3 receives at most one good, creating an EQ1 violation with a1. Thus, an EQ1 and PO allocation might fail to exist even under binary valuations.

Worse still, when the valuations can be zero-valued, determining whether there exists an EQ1+PO allocation is strongly NP-hard. Similar hardness results hold for EQx+PO and EQ+PO allocations as well (Remark 1). Theorem 1 (Hardness of EQ1 + PO). Given any fair division instance with additive valuations, determining whether there exists an allocation that is equitable up to one good (EQ1) and Pareto optimal (PO) is strongly NP-hard.

Proof. We will show a reduction from 3-PARTITION, which is known to be strongly NP-hard. An instance of 3-PARTITION consists of a set of 3r numbers S = {b1, . . . , b3r} where r N, and the goal is to ﬁnd a partition of S into r subsets S1, . . . , Sr such that the sum of numbers in each subset is T, where T := 1

r P ai S bi.8 We will construct a fair division instance as follows: There are r +1 agents a1, . . . , ar+1 and 3r +2 goods g1, . . . , g3r+2. For every i [r] and j [3r], agent ai values the good gj at bj. The agents a1, . . . , ar all value the goods g3r+1 and g3r+2 at 0. Finally, the agent ar+1 values g3r+1 and g3r+2 at T each, and all other goods at 0. ( ) Suppose S1, . . . , Sr is a solution of 3-PARTITION. Then, an EQ1 and PO allocation A = (A1, . . . , Ar+1) can be constructed as follows: For every i [r], Ai := {gj : bj Si}, and Ar+1 := {g3r+1, g3r+2}. Notice that A is EQ1 because each of the agents a1, . . . , ar has utility T, and the utility of the agent ar+1 exceeds T only by a single good g3r+2. Furthermore, A is PO because each good is assigned to an agent with the highest valuation for it. ( ) Now suppose that A = (A1, . . . , Ar+1) is an EQ1 and PO allocation. Since A is PO, it must assign g3r+1 and g3r+2

8Note that we do not require S1, . . . , Sr to be of size three each; 3-PARTITION remains strongly NP-hard even without this constraint.

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

to ar+1. Furthermore, since A is EQ1, each of the agents a1, . . . , ar should have a utility of at least T under A, i.e., for every i [r], vi(Ai) vr+1(Ar+1 \ {g3r+2}) = T. This induces a solution of the 3-PARTITION instance.

Remark 1 (Hardness of EQx+PO/EQ+PO). The reduction in Theorem 1 can also be used to prove strong NP-hardness of ﬁnding an EQx+PO allocation (same construction works) or an EQ+PO allocation (if ar+1 values g3r+2 at 0). Our next result shows that for the special case of binary valuations (i.e., for all i [n], j [m], vi,j {0, 1}), an EQ+PO allocation, if it exists, can be computed in polynomial time. Later, we will show similar tractability results for EQ1+PO and EQx+PO allocations (Theorem 4).

Theorem 2 (Algorithm for EQ+PO for binary valuations). There is a polynomial-time algorithm that given as input any fair division instance with additive and binary valuations, returns an allocation that is equitable (EQ) and Pareto optimal (PO) whenever such an allocation exists.

Proof. We will use a maximum ﬂow algorithm. For binary valuations, an allocation is PO if and only if it assigns each good to an agent that approves it. For an EQ allocation A, we have vi(Ai) = vk(Ak) = c (say) for every i, k [n]. Consider a bipartite graph G = ([n] [m], E) over the set of agents and goods with an edge (i, j) E for every i [n] and j [m] such that vi,j = 1. For any ﬁxed c N, construct a ﬂow network where the source node S is connected to each agent node in [n] with an edge of capacity c. Each node corresponding to a good in [m] is connected to the sink node T with an edge of capacity 1. The edges between agents and goods are of capacity 1. It is straightforward to check that there exists an EQ+PO allocation in the fair division instance (with common utility c) if and only if the above network admits a feasible ﬂow of value n c. The desired algorithm simply iterates over all integral values of c between 1 and m/n .

On the other hand, when all valuations are strictly positive (i.e., vi,j > 0 for all i, j), there always exists an allocation that is both equitable up to any good and Pareto optimal.

Proposition 3 (Existence of EQx+PO for positive valuations). Given any fair division instance with additive and strictly positive valuations, an allocation that is equitable up to any good (EQx) and Pareto optimal (PO) always exists.

Proof. (Sketch.) We will show that any Leximin-optimal allocation, say A, satisﬁes EQx (Pareto optimality is easy to verify). Suppose, for contradiction, that there exist agents i, k [n] and some good j Ak such that vi(Ai) < vk(Ak \ {j}). Let B be an allocation derived from A by transferring the good j from agent k to agent i. Notice that under B, both agents i and k have strictly greater utility than vi(Ai), while all other agents have exactly the same utility as under A. Thus, B is a Leximin improvement over A a contradiction.

Although Proposition 3 offers a strong existence result, it does not automatically provide a constructive procedure for ﬁnding such allocations. Indeed, computing a Leximinoptimal allocation is known to be intractable [Bezáková and Dani, 2005; Plaut and Roughgarden, 2018]. Our

next result (Theorem 3) addresses this gap by providing a pseudopolynomial-time algorithm for ﬁnding an EQ1 and PO allocation when the valuations are strictly positive.

Theorem 3 (Algorithm for EQ1+PO for positive valuations). Given any fair division instance I = [n], [m], V with additive and strictly positive valuations, an allocation that is equitable up to one good (EQ1) and Pareto optimal (PO) always exists and can be computed in O(poly(m, n, vmax)) time, where vmax = maxi,j vi,j.

In particular, when the valuations are polynomially bounded (i.e., for every i [n] and j [m], vi,j poly(m, n)), our algorithm runs in polynomial time. In contrast, computing a Leximin-optimal allocation remains NPhard even under this restriction [Bezáková and Dani, 2005]. The proof of Theorem 3 is deferred to the full version [Freeman et al., 2019] but a brief idea is as follows: Our algorithm uses the framework of Fisher markets, which are well-studied models of a set of buyers spending their budgets of virtual money on utility-maximizing bundles of goods. Standard welfare theorems in economics guarantee that equilibrium (i.e., market clearing) outcomes in these markets are economically efﬁcient. However, such outcomes could, in general, lead to fractional allocations and be highly inequitable. Our algorithm addresses the ﬁrst challenge by starting with (and always maintaining) an integral equilibrium of some Fisher market. To meet the second challenge, our algorithm uses a combination of local search and price-rise routines to gradually move towards an approximately equitable equilibrium. The analysis for achieving the desired running time and correctness guarantees is intricate, and involves a number of structural observations and potential function arguments. Our techniques are inspired from a similar recent algorithm of [2018a] for ﬁnding allocations that are envy-free up to one good (EF1) and Pareto optimal (PO). A key difference between the two algorithms lies in the way a local improvement is deﬁned: For [2018a], a local improvement is deﬁned in terms of equalizing the agents spendings, whereas for us, it pertains to equalizing the agents utilities. We believe that the latter approach is more direct, and leads to a simpler algorithm and analysis. This distinction is also necessary, because as we will show in Proposition 4, an EQ1+EF1+PO allocation might fail to exist even with strictly positive valuations. Therefore, any algorithm that is tailored to return an EF1 outcome including the algorithm of [2018a] will invariably fail to ﬁnd the desired EQ1+PO allocation, motivating the need for an alternative approach. Given the success of market-based algorithms in ﬁnding EQ1+PO allocations, it is natural to ask whether these techniques can be extended to ﬁnd an EQx+PO allocation. Unfortunately, this is where these techniques hit a roadblock. The problem stems from the fact that the market-based algorithm always outputs a fractionally Pareto optimal (f PO) allocation, but there exist instances where no EQx allocation satisﬁes f PO [Freeman et al., 2019]. Whether an EQx+PO allocation can be computed in (pseudo-)polynomial time with strictly positive valuations is an intriguing question for future research.

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

3.3 Equitability, Envy-Freeness and Pareto Optimality We will now consider all three notions equitability, envyfreeness, and Pareto optimality together. Recall from Proposition 3 that for strictly positive valuations, an EQ1+PO (in fact, an EQx+PO) allocation is guaranteed to exist. It is also known that an EF1+PO allocation always exists. One might therefore ask whether an EQ1+EF1+PO allocation also always exists. Our next result (Proposition 4) rules it out.

Proposition 4 (Non-existence of EQ1+EF1+PO). There exists an instance with strictly positive valuations in which no allocation is simultaneously equitable up to one good (EQ1), envy-free up to one good (EF1) and Pareto optimal (PO).

Proof. Fix some n 2 and 0 < ε < 1 2n+2. Consider an instance with n + 1 agents a1, . . . , an+1 and 3n + 1 goods g1, . . . , g3n+1. Each of a1, . . . , an values each of g1, . . . , gn 1 at 2 and each of gn, . . . , g3n+1 at ε. Agent an+1 values every good at 1. By the pigeonhole principle for the goods g1, . . . , gn 1, some agent among a1, . . . , an must have utility at most (2n + 2)ε < 1. This means that an+1 can be assigned at most one good (otherwise EQ1 is violated). Therefore, if all the goods are allocated (which is a necessary condition for a PO allocation), at least 3n goods must be assigned among a1, . . . , an. This means that one of these agents gets at least three goods, creating an EF1 violation with an+1.

Remark 2. Proposition 4 has several interesting implications. First, it shows that a Nash optimal allocation which is guaranteed to be EF1 and PO [Caragiannis et al., 2016] need not satisfy EQ1. Similarly, the algorithm of [2018a] for computing an EF1 and PO allocation could also fail to return an EQ1 allocation. By contrast, our algorithm in Theorem 3 is guaranteed to ﬁnd an EQ1 and PO allocation. Finally, it shows that the Leximin-optimal allocation which is guaranteed to be EQx and PO for strictly positive valuations (Proposition 3) need not be EF1.

Comparison with cake-cutting. It is worth comparing Proposition 4 with the corresponding results for divisible goods (i.e., cake-cutting). [2013] have shown that there might not exist a division of the cake that simultaneously satisﬁes EQ, EF, and PO. Our result in Proposition 4 shows an analogous impossibility for indivisible goods. Interestingly, the impossibility for cake-cutting goes away when PO is relaxed to completeness (i.e., only requiring that the entire cake is allocated). Under this relaxation, it is known that a perfect allocation of the cake exists [Alon, 1987].9 By contrast, for indivisible goods, the impossibility remains even when PO is relaxed to completeness and EF1 is relaxed to proportionality up to one good (Prop1).10 Indeed, the proof of Proposition 4 works even under these relaxations. Moreover, the proof can be easily extended to show the non-existence of EQk, Propℓ and complete allocations for any constants k, ℓ N.

9An allocation A is perfect if for every i, k [n], vi(Ak) = 1

n. 10An allocation A is proportional if for every i [n], we have vi(Ai) 1

k [n] vi(Ak). An allocation A is proportional up to one good [Conitzer et al., 2017] if for every i [n], there exists a good g such that vi(Ai {g}) 1

k [n] vi(Ak).

We now turn to the computational aspects of allocations with all three properties. Note that the allocation constructed in the proof of Theorem 1 is envy-free. Therefore, from Theorem 1 and Remark 1, we obtain strong NP-hardness of all combinations of the three properties. Corollary 1 (Hardness of EF+EQ+PO). Let X {EF, EFx, EF1}, Y {EQ, EQx, EQ1}, and Z = PO. Then, determining whether a given instance admits an allocation that is simultaneously X, Y , and Z is strongly NP-hard. The intractability in Corollary 1 can, in certain cases, be alleviated when the valuations are restricted to be binary. We will start with an observation concerning EQ and PO allocations under this restriction. Proposition 5. For binary valuations, an allocation that is equitable (EQ) and Pareto optimal (PO) is also envy-free (EF).

Proof. Suppose each agent gets a utility k under the said EQ allocation. For binary valuations, PO implies that each agent i approves all the goods in its bundle. Furthermore, any other agent j gets at most k goods approved by i (simply because agent j gets exactly k goods). Hence, the allocation is EF.

Remark 3. Proposition 5 shows that for binary valuations, an EQ+PO allocation (if it exists) is, in fact, EQ+PO+EF (hence also EQ+PO+EFx/EF1). From Theorem 2, we know that there is a polynomial-time algorithm for determining whether an instance with binary valuations admits an EQ+PO allocation. A similar implication therefore also holds for EQ+PO+EF/EF1/EFx allocations. Theorem 4 shows that binary valuations are also useful when one considers the combination of EQ1, EF1, and PO. Theorem 4 (Algorithm for EQ1+EF1+PO for binary valuations). There is a polynomial-time algorithm that given as input any fair division instance with additive and binary valuations, returns an allocation that is equitable up to one good (EQ1), envy-free up to one good (EF1), and Pareto optimal (PO), whenever such an allocation exists. The proof of Theorem 4 is deferred to the full version [Freeman et al., 2019]. The idea is to show that any EQ1+PO allocation, if it exists, is also Nash optimal. For binary valuations, all Nash optimal allocations induce identical utility proﬁles (up to renaming of agents). As a result, every Nash optimal allocation satisﬁes EQ1. It is known that every Nash optimal allocation satisﬁes EF1 and PO [Caragiannis et al., 2016]. Moreover, for binary valuations, a Nash optimal allocation can be computed in polynomial time [Darmann and Schauer, 2015; Barman et al., 2018b]. Therefore, determining the existence of an EQ1+EF1+PO allocation reduces to checking whether an arbitrary Nash optimal allocation satisﬁes EQ1, which can be done in polynomial time. Notice that for binary valuations, a Pareto optimal allocation is EF1 if and only if it is EFx, and is EQ1 if and only if it is EQx. Therefore, when the valuations are binary, the above algorithm works for all combinations of X + Y + PO, where X {EFx, EF1} and Y {EQx, EQ1}. We conclude this section by observing that some of the problems discussed in Corollary 1 continue to be intractable even for binary valuations. This follows from a result of

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

Figure 1: Experimental results for Spliddit and synthetic datasets.

[2008], who showed that ﬁnding an envy-free (EF) and Pareto optimal (PO) allocation under binary valuations is NPcomplete (refer to Proposition 21 in their paper). Proposition 6 ([Bouveret and Lang, 2008]). Given any fair division instance with additive and binary valuations, determining whether there exists an envy-free (EF) and Pareto optimal (PO) allocation is NP-complete. Remark 4. It is easy to verify that the allocation constructed in the reduction of [2008] is, without loss of generality, equitable up to one good (EQ1). Therefore, for binary valuations, determining whether there exists an allocation that is EF + EQ1/EQx + PO is NP-complete.

4 Experiments In this section, we compare the proposed and existing algorithms (in particular, ALG-EQ +PO, MNW, and Leximin) in terms of how frequently they satisfy various fairness and efﬁciency properties in the real-world and synthetic datasets. For real-world preferences, we used data obtained from the popular fair division website Spliddit [Goldman and Procaccia, 2014]. Out of the 2212 instances in the Spliddit data, we used the 914 instances that had strictly positive valuations and m n. The instances have between 3 and 9 agents, and between 3 and 29 goods.11 Users are restricted to normalized, integral valuations. For synthetic data, we generated 1000 instances with n = 5, m = 20, and (strictly positive) valuations drawn i.i.d. from Dirichlet distribution. The concentration parameter for each item is set to 10 to generate normalized valuations.12 We consider the following fairness and efﬁciency properties: EQ+PO, EQ1+PO, EQx+PO, EQ1+EF1+PO, and EQx+EFx+PO. For each instance of the Spliddit and synthetic datasets, we check whether the property is satisﬁed by the output of ALG-EQ +PO, MNW, and Leximin. Figure 1 presents the relevant histograms. Note that each of the algorithms we consider is Pareto optimal, so the histograms would be unaltered even if we did not assess PO. Not surprisingly, we see that very few instances permit a solution that is Pareto optimal and exactly equitable. When-

11More than 80% of the instances have three agents and six goods. 12We normalize the valuations in the synthetic data to allow for a fair comparison with the Spliddit data, which has normalized valuations by design. We remark that all algorithms studied in this paper work even in the absence of this assumption.

ever such a solution exists, it is provably achieved by Leximin, but this happens in only 1% of Spliddit instances and none of the synthetic instances. For the EQ1 relaxation, we see that not only do Leximin and ALG-EQ +PO satisfy both EQ1 and PO, but so does MNW on over 94% of Spliddit instances (and over 88% of synthetic instances). However, this trend changes when we consider EQx. ALG-EQ +PO, despite being guaranteed to satisfy EQ1, only satisﬁes EQx on 62% of Spliddit instances (and 52% of synthetic instances). A similar drop off is observed with MNW. Thus, for the purpose of achieving (approximately) equitable and Pareto optimal allocations, Leximin is a clear winner. We observe little change when, in addition to approximate equitability and Pareto optimality, we also require approximate envy-freeness. Indeed, in most cases, an allocation that is EQ1+PO/EQx+PO is also EF1/EFx. It is interesting to note that while MNW which is appealing from the perspective of achieving relaxed envy-freeness quite often fails to satisfy EQx, Leximin provably satisﬁes relaxed equitability while also achieving EFx on a large fraction of instances.

5 Discussion

Our work reveals some intriguing similarities and differences between equitability and envy-freeness. In many places, our work parallels the existing literature on envy-freeness: We present Leximin as a canonical algorithm for EQ1+PO, just like MNW achieves EF1+PO. Also, our pseudopolynomialtime algorithm for EQ1+PO uses similar techniques to that of [2018a] for EF1+PO. However, in other places, the differences are more pronounced. Most notably, EQx comes with a universal existence guarantee (often in conjunction with PO), while the existence of EFx allocations remains an open problem. Finally, exact equitability is a knife-edge property often hard to achieve in practice, unlike envy-freeness which is often satisﬁable [Dickerson et al., 2014]. Going forward, it would be very interesting to extend our results to the public decisions model of [2017]. Extensions to models with additional feasibility constraints on the allocations [Bouveret et al., 2017], or settings with both goods and chores [Aziz et al., 2018] will also be interesting.

Acknowledgments

We are grateful to the anonymous IJCAI-19 reviewers for their helpful comments, and to Ariel Procaccia and Nisarg Shah for sharing with us the data from Spliddit. LX acknowledges NSF #1453542 and #1716333 for support.

[Alon, 1987] Noga Alon. Splitting Necklaces. Advances in Mathematics, 63(3):247 253, 1987. [Aumann and Dombb, 2015] Yonatan Aumann and Yair Dombb. The Efﬁciency of Fair Division with Connected Pieces. ACM Transactions on Economics and Computation, 3(4):23, 2015. [Aziz et al., 2018] Haris Aziz, Ioannis Caragiannis, and Ayumi Igarashi. Fair Allocation of Combinations

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

of Indivisible Goods and Chores. ar Xiv preprint ar Xiv:1807.10684, 2018. [Barman et al., 2018a] Siddharth Barman, Sanath Kumar Krishnamurthy, and Rohit Vaish. Finding Fair and Efﬁcient Allocations. In Proceedings of the 2018 ACM Conference on Economics and Computation, pages 557 574, 2018. [Barman et al., 2018b] Siddharth Barman, Sanath Kumar Krishnamurthy, and Rohit Vaish. Greedy Algorithms for Maximizing Nash Social Welfare. In Proceedings of the 2018 International Conference on Autonomous Agents and Multiagent Systems, pages 7 13, 2018. [Bezáková and Dani, 2005] Ivona Bezáková and Varsha Dani. Allocating Indivisible Goods. ACM SIGecom Exchanges, 5(3):11 18, 2005. [Bouveret and Lang, 2008] Sylvain Bouveret and Jérôme Lang. Efﬁciency and Envy-Freeness in Fair Division of Indivisible Goods: Logical Representation and Complexity. Journal of Artiﬁcial Intelligence Research, 32:525 564, 2008. [Bouveret et al., 2017] Sylvain Bouveret, Katarína Cechlárová, Edith Elkind, Ayumi Igarashi, and Dominik Peters. Fair Division of a Graph. In Proceedings of the 26th International Joint Conference on Artiﬁcial Intelligence, pages 135 141. AAAI Press, 2017. [Brams et al., 2006] Steven J Brams, Michael A Jones, and Christian Klamler. Better Ways to Cut a Cake. Notices of the AMS, 53(11):1314 1321, 2006. [Brams et al., 2012] Steven J Brams, Michal Feldman, John K Lai, Jamie Morgenstern, and Ariel D Procaccia. On Maxsum Fair Cake Divisions. In Proceedings of the Twenty-Sixth AAAI Conference on Artiﬁcial Intelligence, pages 1285 1291, 2012. [Brams et al., 2013] Steven J Brams, Michael A Jones, and Christian Klamler. N-Person Cake-Cutting: There May be No Perfect Division. The American Mathematical Monthly, 120(1):35 47, 2013. [Budish, 2011] Eric Budish. The Combinatorial Assignment Problem: Approximate Competitive Equilibrium from Equal Incomes. Journal of Political Economy, 119(6):1061 1103, 2011. [Caragiannis et al., 2016] Ioannis Caragiannis, David Kurokawa, Hervé Moulin, Ariel D Procaccia, Nisarg Shah, and Junxing Wang. The Unreasonable Fairness of Maximum Nash Welfare. In Proceedings of the 2016 ACM Conference on Economics and Computation, pages 305 322, 2016. [Cechlárová and Pillárová, 2012a] Katarína Cechlárová and Eva Pillárová. On the Computability of Equitable Divisions. Discrete Optimization, 9(4):249 257, 2012. [Cechlárová and Pillárová, 2012b] Katarína Cechlárová and Eva Pillárová. A Near Equitable 2-Person Cake Cutting Algorithm. Optimization, 61(11):1321 1330, 2012. [Cechlárová et al., 2013] Katarına Cechlárová, Jozef Doboš, and Eva Pillárová. On the Existence of Equitable Cake Divisions. Information Sciences, 228:239 245, 2013.

[Chèze, 2017] Guillaume Chèze. Existence of a Simple and Equitable Fair Division: A Short Proof. Mathematical Social Sciences, 87:92 93, 2017. [Conitzer et al., 2017] Vincent Conitzer, Rupert Freeman, and Nisarg Shah. Fair Public Decision Making. In Proceedings of the 2017 ACM Conference on Economics and Computation, pages 629 646, 2017. [Darmann and Schauer, 2015] Andreas Darmann and Joachim Schauer. Maximizing Nash Product Social Welfare in Allocating Indivisible Goods. European Journal of Operational Research, 247(2):548 559, 2015. [Dickerson et al., 2014] John P Dickerson, Jonathan Goldman, Jeremy Karp, Ariel D Procaccia, and Tuomas Sandholm. The Computational Rise and Fall of Fairness. In Proceedings of the Twenty-Eighth AAAI Conference on Artiﬁcial Intelligence, pages 1405 1411, 2014. [Dubins and Spanier, 1961] Lester E Dubins and Edwin H Spanier. How to Cut a Cake Fairly. The American Mathematical Monthly, 68(1P1):1 17, 1961. [Foley, 1967] Duncan Foley. Resource Allocation and the Public Sector. Yale Economic Essays, pages 45 98, 1967. [Freeman et al., 2019] Rupert Freeman, Sujoy Sikdar, Rohit Vaish, and Lirong Xia. Equitable Allocations of Indivisible Goods. ar Xiv preprint ar Xiv:1905.10656, 2019. [Goldman and Procaccia, 2014] Jonathan Goldman and Ariel D Procaccia. Spliddit: Unleashing Fair Division Algorithms. ACM SIGecom Exchanges, 13(2):41 46, 2014. [Gourvès et al., 2014] Laurent Gourvès, Jérôme Monnot, and Lydia Tlilane. Near Fairness in Matroids. In Proceedings of the Twenty-First European Conference on Artiﬁcial Intelligence, pages 393 398, 2014. [Herreiner and Puppe, 2009] Dorothea K Herreiner and Clemens D Puppe. Envy Freeness in Experimental Fair Division Problems. Theory and Decision, 67(1):65 100, 2009. [Lipton et al., 2004] Richard J Lipton, Evangelos Markakis, Elchanan Mossel, and Amin Saberi. On Approximately Fair Allocations of Indivisible Goods. In Proceedings of the 5th ACM Conference on Electronic Commerce, pages 125 131, 2004. [Plaut and Roughgarden, 2018] Benjamin Plaut and Tim Roughgarden. Almost Envy-Freeness with General Valuations. In Proceedings of the Twenty-Ninth Annual ACMSIAM Symposium on Discrete Algorithms, pages 2584 2603, 2018. [Procaccia and Wang, 2017] Ariel D Procaccia and Junxing Wang. A Lower Bound for Equitable Cake Cutting. In Proceedings of the 2017 ACM Conference on Economics and Computation, pages 479 495, 2017. [Suksompong, 2019] Warut Suksompong. Fairly Allocating Contiguous Blocks of Indivisible Items. Discrete Applied Mathematics, 2019.

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