Equitable Allocations of Indivisible Goods

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 first 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 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 significant predictor of the perceived fairness of an allocation, often more so than envy-freeness.

∗Contact Author

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 finite procedure can find an (exact) equitable division [Procaccia and Wang, 2017], though an ε-equitable division can be computed in a finite 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 efficiency 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 finding an EQ/EQx/EQ1+PO allocation becomes strongly NP-

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 efficiently solvable (Theorem 4).
• We validate our theoretical results via experiments on the data from the popular fair division website Spliddit 2 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 efficiency 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).

1 EF1 stands for envy-freeness up to one good, which is a (necessary) relaxation of envy-freeness defined for indivisible goods; see Section 2 for the relevant definitions.

2 http://www.spliddit.org/

2 Preliminaries

Problem instance. An instance 〈[n], [m], V〉 of the fair division problem is defined by a set of n ∈ N agents [n] = {1, 2, . . . , n}, a set of m ∈ N goods [m] = {1, 2, . . . ,m}, and a valuation profile V = {v1, v2, . . . , vn} that specifies 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) := ∑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) = ∑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 of EF, EF1, and EFx are due to [1967], [2011], 5 and [2016], respectively.

3 Integrality 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.

4 Our 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.

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 defined as NSW(A) := (∏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 first consider equitability and its relaxations, then consider them in conjunction with Pareto optimality, before finally 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 efficiently 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.

Briefly, [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 after it (up to the removal of the most recently assigned good). The claim now follows by induction over the rounds.

5 [2004] previously defined a slightly weaker notion than EF1, but their algorithm can, in fact, compute an EF1 allocation.

6 [2016] define 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 definition.

7 In fact, the problem is strongly NP-complete due to a similar reduction from 3-PARTITION.

Proposition 2 presents an interesting contrast between the notions of EQx and EFx: An EQx allocation is guaranteed to exist and can be efficiently 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 find a partition of S into r subsets S1, . . . , Sr such that the sum of numbers in each subset is T , where T := 1r ∑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

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

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 finding 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 flow 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 fixed c ∈ N, construct a flow 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 flow 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, satisfies 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 finding 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 finding 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 efficient. However, such outcomes could, in general, lead to fractional allocations and be highly inequitable. Our algorithm addresses the first 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 finding 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 defined: For [2018a], a local improvement is defined 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 outcomeincluding the algorithm of [2018a]-will invariably fail to find the desired EQ1+PO allocation, motivating the need for an alternative approach.

Given the success of market-based algorithms in finding EQ1+PO allocations, it is natural to ask whether these techniques can be extended to find 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 (fPO) allocation, but there exist instances where no EQx allocation satisfies fPO [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.

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 find 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 satisfies 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.

9 An allocation A is perfect if for every i, k ∈ [n], vi(Ak) = 1n . 10 An allocation A is proportional if for every i ∈ [n], we have vi(Ai) ≥ 1n ∑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}) ≥ 1n ∑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 profiles (up to renaming of agents). As a result, every Nash optimal allocation satisfies EQ1. It is known that every Nash optimal allocation satisfies 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 satisfies 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

[2008], who showed that finding 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 efficiency 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. fromDirichlet distribution. The concentration parameter for each item is set to 10 to generate normalized valuations. 12

We consider the following fairness and efficiency 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 satisfied 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. Whenever 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 satisfies 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.

11 More than 80% of the instances have three agents and six goods.

12 We 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.

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 satisfies 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 satisfiable [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.