# nearly_equitable_allocations_beyond_additivity_and_monotonicity__9e32da53.pdf

Nearly Equitable Allocations beyond Additivity and Monotonicity

Siddharth Barman1, Umang Bhaskar2, Yeshwant Pandit2, Soumyajit Pyne2

1 Indian Institute of Science, Bangalore 2 Tata Institute of Fundamental Research, Mumbai barman@iisc.ac.in, umang@tifr.res.in, soumyajit.pyne@tifr.res.in, yeshwant.pandit@tifr.res.in

Equitability (EQ) in fair division requires that items be allocated such that all agents value the bundle they receive equally. With indivisible items, an equitable allocation may not exist, and hence we instead consider a meaningful analog, EQx, that requires equitability up to any item. EQx allocations exist for monotone, additive valuations. However, if (1) the agents valuations are not additive or (2) the set of indivisible items includes both goods and chores (positively and negatively valued items), then prior to the current work it was not known whether EQx allocations exist or not. We study both the existence and efficient computation of EQx allocations. (1) For monotone valuations (not necessarily additive), we show that EQx allocations always exist. Also, for the large class of weakly well-layered valuations, EQx allocations can be found in polynomial time. Further, we prove that approximately EQx allocations can be computed efficiently under general monotone valuations. (2) For non-monotone valuations, we show that an EQx allocation may not exist, even for two agents with additive valuations. Under some special cases, however, we show existence and efficient computability of EQx allocations. This includes the case of two agents with additive valuations where each item is either a good or a chore, and there are no mixed items.

1 Introduction In the problem of fair division, a central planner (principal) is tasked with fairly partitioning a set of items among interested agents. If the items are indivisible, which is our focus, each item must be allocated integrally to an agent. Every agent i has a valuation function vi that specifies agent i s value for each subset of items. Here, an item x could be a good , if every agent always values it positively, a chore , if every agent always values it negatively, or mixed , if across agents the value for item x can be both positive and negative. What constitutes a fair allocation of items has no single answer. Over the years, various notions have been studied in depth (Moulin 2004). Possibly the most prominent among them are envy-freeness and equitability. An allocation is said to be envy-free if each agent prefers her own bundle of items to the bundle allocated to anyone else (Foley 1966). An allocation is said to be equitable if agents values for their own

Copyright 2024, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

bundles are the same and, hence, the agents are equally content (Dubins and Spanier 1961). If the agents have identical valuations, then the two notions coincide. Envy-freeness has received significant attention in classic fair division literature. It is known, for example, that for additive valuations over divisible goods, an allocation that maximizes the Nash social welfare (the product of the agents values for their allocated bundles) is also envy-free (Varian 1974). The widely used platform Spliddit.org implements multiple methods to provide solutions for common fair division problems (Goldman and Procaccia 2015). The platform uses envy-freeness, in particular, as a fairness criterion for relevant applications. Notably, equitability is a simpler construct to reason about, since it requires fewer comparisons. To test an allocation for equitability, we only need each agent s value for her own bundle, rather than every agent s value for every bundle. Perhaps for this reason, equitable solutions are important in practical applications of fair division. Experimental studies have noted that, in specific fair-division settings, users tend to prefer equitable allocations over other notions of fairness (Herreiner and Puppe 2009).1 Further, in bargaining experiments, equitability often plays a significant role in determining the outcome (Herreiner and Puppe 2010). Also in Spliddit.org, for fairly dividing rent among housemates, equitability was noted to be important as a refining criterion, following envy-freeness. The latest rent-division algorithm used in Spliddit.org computes solutions that satisfy this supporting objective (Gal et al. 2017).2 The real-world significance of equitability is further highlighted by the case of divorce settlements. The two legal means of dividing property in the United States are community property and equitable distribution (Kagan 2021). In the community property rule, holdings are divided equally among the divorcing couple and, hence, the rule induces an envy-free division. Equitable distribution, on the other hand, takes into account various factors (such as the employability and financial needs of each party) for dividing the as-

1These prior works refer to equitability as inequality aversion. 2Specifically, rent divisions that maximize the minimum value, called maximin solutions, are nearly equitable. The latest algorithm implemented in Spliddit.org finds rent divisions that satisfy envyfreeness and are also maximin.

The Thirty-Eighth AAAI Conference on Artiﬁcial Intelligence (AAAI-24)

Existence Polynomial-Time Algorithm Monotone, Beyond Theorem 2 Well-Layered: Theorem 3 Additive (Section 3) Approximate EQx: Theorem 5 Nonmonotone Additive Subjective Valuations: Theorem 6 Two agents, objective valuations: Theorem 7 (Section 4) Identical Chores: Theorem 9 Single Chore: Theorem 10

Table 1: Our Results

sets, and, in particular, makes inter-personal comparisons of value. Most states in the US follow equitable distribution, i.e., the courts divide assets and liabilities based on equitability. The definition of equitability in this situation is somewhat intuitive. However, the evidence clearly suggests that equitability is an important concept in practical situations. Motivated by such considerations, the current work studies equitability (EQ), with the focus on allocating indivisible items. In the discrete fair division context, simple examples (with two agents and a single indivisible item) demonstrate that exactly equitable allocations may not exist. Hence, recent works have focused on relaxations. A compellingly strong relaxation is obtained by requiring that any existing inequality in agents values is switched by the (hypothetical) removal of any good or chore in an appropriate manner. This relaxation is called equitability up to any item, EQx. Specifically, an allocation is said to be EQx if, whenever agent i has a lower value for her bundle, say Ai, than some other agent j for her bundle, say Aj (i.e., vi(Ai) < vj(Aj)), the removal of any positively-valued item (good) from Aj or the removal of any negatively-valued item (chore) from Ai ensures that the inequality is (weakly) reversed. Similarly, an allocation is EFx if, whenever agent i has higher value for agent j s bundle than her own (i.e., vi(Ai) < vi(Aj)), this preference can be weakly reversed by removing a good from Aj or a chore from Ai. Given the relevance of equitability, a fundamental question in discrete fair division is whether EQx allocations always exist. For the specific case of additively valued goods, EQx allocations are known to exist; this result is obtained via a greedy algorithm (Gourv es, Monnot, and Tlilane 2014).3 Beyond this setting, however, this question has not been addressed in the literature. Our work addresses this notable gap. In particular, moving beyond monotone additive valuations, the current work establishes novel existential and algorithmic guarantees for EQx allocations. For general monotone valuations, for example, our work shows the universal existence of EQx allocations.

Our Results and Techniques. Under monotone, nondecreasing valuations, we establish (in Section 3): EQx allocations always exist, and can be computed in pseudo-polynomial time (Theorem 2). Our algorithm is based on a modification of an Add-and-Fix algorithm, proposed earlier for EFx under identical monotone nonincreasing valuations (Barman, Narayan, and Verma 2023).

3EQx is termed as near jealousy-freeness in (Gourv es, Monnot, and Tlilane 2014).

Under weakly well-layered (WWL) valuations, EQx allocations can be computed in polynomial time (Theorem 3). WWL functions are an encompassing and natural class of valuations that include gross substitutes, weighted matroidrank functions, budget-additive, well-layered, and cancelable valuations (Goldberg, Høgh, and Hollender 2023). For any ε (0, 1), a (1 ε)-approximately EQx allocation can be computed in time polynomial in 1/ε and the input size (Theorem 5). Finding an EFx allocation is known to be hard (Plaut and Roughgarden 2020a). Since the negative result holds even for two agents, with identical submodular valuations, the hardness also applies to EQx. This observation signifies that our polynomial-time algorithm for WWL valuations is the best possible, in the sense that such a positive result is unlikely for submodular valuations in general. We then address nonmonotone additive valuations (Section 4). In comparison to monotone valuations, the results here are mixed and highlight a complicated landscape. For agents with subjective valuations when mixed items are allowed EQx allocations may not exist, even for just two agents with normalized valuations (Theorem 6).4 This negative result necessitates focusing on objective valuations, wherein each item is exclusively a good or a chore. For agents with identical additive valuations, Aziz and Rey (2020) develop an efficient algorithm for finding EFx (and, hence, EQx) allocations. By the well-known cut-andchoose protocol, this gives an EFx algorithm for two nonidentical agents. However, cut-and-choose does not work for EQx and, hence, there was no known EQx algorithm for two nonidentical agents. Our next result addresses this gap. For two agents with additive objective valuations, we develop a polynomial-time algorithm for finding EQx allocations (Theorem 7). Many instances of fair division, in fact, consist of just two agents (such as in divorce settlement, or in the experiments of Gal et al. 2017), hence our result for two agents is of practical significance. For n agents with additive objective valuations where each chore c has the same value for the agents (i.e., vi(c) = vj(c) for all agents i and j), we show using the leximin++ ordering that EQx allocations always exist (Theorem 9). For n agents with additive objective valuations and a single chore, we show that EQx allocations exist (Theorem 10). The last result is technically challenging. It is obtained via a local search algorithm, that resolves EQx violations,

4Valuations are normalised if, for the set M of all the goods, vi(M) is equal for all agents i.

The Thirty-Eighth AAAI Conference on Artiﬁcial Intelligence (AAAI-24)

whenever they arise, in a specific order. The analysis is subtle and needs to keep track of multiple progress measures, including the leximin++ value. Table 1 summarizes our results. Due to lack of space, all missing proofs are given in the full version of the paper (Barman et al. 2023). The existence of EQx allocation under objective, additive valuations stands as an interesting, open question.

Additional Related Work. Equitability was first studied in the divisible setting of cake cutting. Here, equitable allocations for n agents exist (Dubins and Spanier 1961; Cechl arov a, Doboˇs, and Pill arov a 2013; Ch eze 2017) and, in particular, do not require additivity (Aumann and Dombb 2015). However, no finite algorithm can find an exactly equitable allocation (Procaccia and Wang 2017), though approximately equitable allocations can be computed in near-linear time (Cechl arov a and Pill arov a 2012). For indivisible items, EQx allocations were first shown to exist for monotone additive valuations (Gourv es, Monnot, and Tlilane 2014; Freeman et al. 2020). This existential guarantee was obtained via an efficient greedy algorithm. For additive valuations that are strictly positive, allocations that are both EQx and Pareto optimal are known to exist (Freeman et al. 2019). When the agents have identical valuations, EFx and EQx allocations coincide. Hence, under identical valuations, existential guarantees obtained for EFx allocations extend to EQx as well. In particular, for identical monotone (nondecreasing) valuations, EFx allocations were shown to exist using the leximin++ construct (Plaut and Roughgarden 2020a). This work also showed that even for two agents with identical submodular valuations, finding an EFx allocation requires an exponential number of queries. This problem is also PLS-complete (Goldberg, Høgh, and Hollender 2023). For objective identical valuations, the existence of EFx allocations was shown through a modification of the leximin construct (Chen and Liu 2020). For additive identical valuations, EFx existence, as well as efficient computation, was obtained by Aziz and Rey 2020. Finally, a number of recent papers have also studied the loss of efficiency for (near) equitable and near equitable allocations (Caragiannis et al. 2012; Aumann and Dombb 2015; Freeman et al. 2019, 2020; Sun, Chen, and Doan 2023; Bhaskar et al. 2023).

2 Notation and Preliminaries A fair division instance (N, M, V) consists of a set N = {1, 2, . . . , n} of agents, a set M of indivisible items, with m = |M|, and a valuation function vi V for each agent i N. The valuation vi : 2M Z specifies agent i s value for every subset of the items. We will assume, throughout, that vi( ) = 0, and all the agents values are integral.5 For notational convenience, for single items x M, we use vi(x) and vi(S x) to denote vi({x}) and vi(S {x}), respectively. Let Vmax := maxi [n] vi(M).

5The integrality assumption holds without loss of generality for rational values, since we can multiply the rational numbers by the product of their denominators to get integral ones. Note that under such a scaling, the size of the input only increases polynomially.

A valuation v is monotone nondecreasing if v(S x) v(S) for all subsets S M and all items x M. Similarly, valuation v is monotone nonincreasing if v(S x) v(S) for all S M and x M. Function v is additive if v(S) = P x S v(x), for all subsets S M. We will say that a fair division instance has objective valuations if for each item x M (i) either vi(S x) vi(S) for all agents i and subsets S M, (ii) or vi(S x) vi(S) for all agents i and subsets S M. Under (i), the item x is referred to as a good, and when case (ii) holds (and the inequality is strict for some agent i and subset S), we say that x is a chore. We will mainly address objective valuations and, hence, every item is unequivocally either a good or a chore.6 We will typically use g to denote a good and c to denote a chore. Under objective valuations vi, for each good g the value vi(g) 0 and for each chore c we have vi(c) 0. An allocation A := (A1, . . . , An) is a partition of items M into n pairwise disjoint subsets. Here, subset of items Ai M is assigned to agent i (also called agent i s bundle). At times (such as when analyzing the interim allocations obtained by our algorithms), we may also consider partial allocations wherein not all items are assigned among the agents, i.e., for the pairwise disjoint bundles we have n i=1Ai M. Given an allocation A, we say an agent p is poorest if vp(Ap) = mini N vi(Ai), and agent r is richest if vr(Ar) = maxi N vi(Ai). Equitability and Envy-Freeness. An allocation A is equitable if vi(Ai) = vj(Aj) for all agents i, j N. An allocation is said to be envy-free if vi(Ai) vi(Aj) for all agents i, j N. Hence, equity requires that all agents have equal value, while envy-freeness requires that each agent values her bundle more than that of any other agent. As mentioned, even in simple examples of a single good and two agents both equitable and envy-free allocations do not exist. Hence, we consider relaxations of these notions. Specifically, an allocation A = (A1, . . . , An) is said to be equitable up to any item (EQx) if (1) For every pair of agents i, j and for each good g Aj, we have vj(Aj \ {g}) vi(Ai), and (2) For every pair of agents i, j and for each chore c Ai, we have vi(Ai \ {c}) vj(Aj). That is, in an EQx allocation, for each agent, the removal of any good assigned to her makes her a poorest agent, and the removal of any chore assigned to her must make her a richest agent. Our results for monotone nondecreasing valuations (when all items are goods) are detailed in Section 3. Section 4 presents our results for nonmonotone additive valuations.

3 Monotone Valuations

In this section, all items have nonnegative marginal values. That is, vi(S x) vi(S) for all items x M, agents i N, and subsets S M. Hence, all items are goods in this section. We assume a standard value-oracle access to the

6The main exception here is the example given in Theorem 6, which shows that if the valuations are not objective, then EQx allocations may fail to exist.

The Thirty-Eighth AAAI Conference on Artiﬁcial Intelligence (AAAI-24)

valuations, that given any agent i N and subset S M, returns vi(S) Z 0. For monotone valuations, we establish strong positive results towards the existence of EQx allocations. Our primary result shows that, for general monotone valuations, EQx allocations always exist, and for a broad class of valuations termed weakly well-layered (WWL) valuations such fair allocations can be found in polynomial time.

Definition 1 ((Goldberg, Høgh, and Hollender 2023)). A valuation function v : 2M Z 0 is said to be weakly well-layered if for any set M M the sets S0, S1, . . . obtained by the greedy algorithm (that is, S0 = and Si = Si 1 {xi}, where xi arg maxx M \Si 1 v(Si 1 x), for i |M |) are optimal, in the sense that v(Si) = max S M :|S|=i v(S) for all i |M |.

WWL valuations intuitively capture valuations where optimal sets can be obtained via a greedy algorithm. Several interesting and widely-studied classes of valuations are weakly well-layered, including gross substitutes (which include weighted matroid rank functions), budget-additive, well-layered, and cancelable valuations; Figure 1 in (Goldberg, Høgh, and Hollender 2023) is helpful in visualizing the relation between these classes. Notably, submodular functions are not weakly well-layered. This is an affirming observation, since it is known that, even for two agents with identical submodular valuations, obtaining an EFx (and, hence, EQx) allocation is PLS-complete and requires exponentially many value queries. Our results are obtained through a modification and careful analysis of the Add-and-Fix algorithm, earlier used for obtaining EFx under identical cost functions (i.e., when all items are chores) (Barman, Narayan, and Verma 2023). The modified version of Add-and-Fix uses a greedy selection criterion; see Algorithm 1. In each iteration, the algorithm identifies a poorest agent p N in the current allocation. Then, agent p selects goods greedily from the unassigned ones. That is, from among the unassigned goods, p iteratively selects goods with maximum marginal value, until it is no longer the poorest agent. This is the Add phase in the algorithm (Lines 4 to 6). If after adding these goods, the allocation obtained is not EQx, this must be because of the goods assigned to agent p. In the Fix phase (Lines 7 and 8), violating goods are iteratively removed from agent p s bundle, until the allocation is EQx. After each iteration, either the value of agent p increases, or the algorithm terminates (Claim 1). We differ from the original Add-and-Fix in two aspects: the original algorithm chose a richest agent in each iteration, since it dealt with chores, whereas we select a poorest agent. Secondly, and crucially for our results for efficient computation, the original algorithm assigned an arbitrary chore to the richest agent, while we select goods with maximum marginal contribution to the poorest agent. Also, note that the EFx guarantee in (Barman, Narayan, and Verma 2023) is obtained for identical costs functions, whereas the EQx result here holds for (monotone) non-identical valuations. In our proofs, an iteration of the outer while-loop is called an outer iteration. Note that in every outer iteration, the allo-

Algorithm 1: Greedy Add-and-Fix Input: Fair division instance (N, M, V) with value-oracle access to monotone, nondecreasing valuations. Output: EQx allocation A. 1: Initialize bundles Ai = for all agents i, and initialize U = M as the set of unassigned goods. 2: while U = do 3: Let p arg min i N vi(Ai) and p arg min i N\{p} vi(Ai).

{p and p are a poorest and second poorest agent.} {Add Phase: Lines 4 to 6} 4: while vp(Ap) vp (Ap ) and U = do 5: Let g arg maxg U(vp(Ap g) vp(Ap)). 6: Update Ap Ap {g } and U U \ {g }. {Fix Phase: Lines 7 and 8} 7: while there exists bg Ap such that vp(Ap \ {bg}) > vp (Ap ) do 8: Update Ap Ap \ {bg} and U U {bg}. 9: return Allocation A = (A1, . . . , An).

cation to every agent, other than p, remains unchanged. We will use the following claim.

Claim 1. After each outer iteration, (i) either the value of the selected agent p strictly increases such that p is no longer the poorest agent (and the values of the other agents remain unchanged), or (ii) all the remaining unassigned goods are allocated to agent p and the algorithm terminates.

Theorem 2. Given any fair division instance with monotone valuations, Algorithm 1 computes an EQx allocation in pseudo-polynomial time.

Proof. We first show that the algorithm terminates in pseudo-polynomial time. Claim 1 implies that the number of outer iterations is at most P i N vi(M) n Vmax, where Vmax := maxi vi(M). Each outer iteration consists of an Add phase (in which at most m goods are included in agent p s bundle) and a Fix phase (in which at most m goods are removed from agent p s bundle). Each execution of these phases requires at most m calls to the value oracle to find the required goods g and bg. Hence, it follows that the algorithm terminates in O(m2n Vmax) time. Next, we show that the allocation computed by the algorithm is indeed EQx; our proof is via induction on the number of outer iterations. Initially, the allocation is empty, which is trivially EQx. For the inductive step, fix any outer iteration and let p be the poorest agent selected in that iteration. Write A = (A1, . . . , An) for the allocation at the beginning of the outer iteration and B = (B1, . . . , Bn) for the allocation obtained after the outer iteration. Note that Bi = Ai for all agents i = p. This observation and the induction hypothesis imply that any EQx violation must involve agent p. Further, Claim 1 gives us vp(Bp) vp(Ap). To show that allocation B is EQx, we need to show that for any agent i N, the removal of any good g Bi makes i a poorest agent. This condition holds via the induction

The Thirty-Eighth AAAI Conference on Artiﬁcial Intelligence (AAAI-24)

hypothesis for all agents i = p; recall that Bi = Ai for all i = p, and vp(Bp) vp(Ap). For agent p, note that after the completion of the Fix phase, the removal of any good from p s bundle reduces its value to at most vp (Ap ) = vp (Bp ). Since p was the poorest and p was the second poorest agent in allocation A, this implies that the removal of any good from Bp would make agent p the poorest agent in B as well: vp(Bp\{g}) vj(Bj) for all j N and each good g Bp. The theorem stands proved.

3.1 Weakly Well-Layered Valuations The following theorem asserts that for WWL valuations, Algorithm 1 computes an EQx allocation in polynomial time.

Theorem 3. Given any fair division instance in which all the agents have monotone, weakly well-layered valuations, Algorithm 1 computes an EQx allocation in polynomial time.

Proof. The monotonicity of agents s valuations ensures that the allocation returned by Algorithm 1 is EQx (Theorem 2). Hence, it remains to prove that, under weakly well-layered (WWL) valuations, the algorithm terminates in polynomial time. Towards this, we will show that, in fact, the Fix phase never executes when all the valuations are WWL. Hence, in every outer iteration of Algorithm 1 the number of unassigned goods strictly decreases, and the algorithm terminates in polynomial time. We will show that the Fix phase never executes via an inductive argument. In the base case (i.e., in the very first outer iteration) we have Ai = for all agents i. Now, for the first iteration, write S to denote the subset of goods assigned to the selected agent p in the Add phase. Further, let g denote the last good assigned in the Add phase. Then, by the loopexecution condition in Line 4, we have vp(S \ {g }) = 0, since all other agents have value 0. Further, given that vp is WWL and the set S \ {g } is populated greedily, any set of goods of cardinality |S| 1 has value 0. Hence, upon the removal of any good g from S, agent p has value 0 for the remaining subset, since it has size |S| 1. Therefore, the Fix phase (Line 7) will not execute in the first outer iteration. For the inductive step, fix an outer iteration. Let A = (A1, . . . , An) be the allocation at the beginning of the iteration and U = M \ ( i Ai) be the set of unassigned goods. For the poorest agent p selected in the iteration, consider the bundle Ap and write S U to denote the subset of goods assigned to p in the Add phase of the iteration. In addition, let g S be the last good assigned in the Add phase. The following Claim asserts that all strict subsets T Ap S

have value vp(T) vp Ap S \ {g} .

Claim 4. For weakly well-layered valuation vp we have Ap S \ {g} arg max X Ap S vp(X).

We use Claim 4 to complete the inductive step. The execution criterion of the Add phase (Line 4) implies that before good g was included in the agent p s bundle its value was at most vp (Ap ), i.e., vp Ap S \ {g} vp (Ap ). Hence, via Claim 4, for every strict subset T Ap S we

have vp(T) vp (Ap ). The execution condition for the Fix phase will hence not be satisfied. This completes the proof of the theorem.

3.2 Approximate EQx Allocations

As mentioned previously, for general monotone valuations, computing an EQx allocation is a PLS-hard problem. Complementing this hardness result, this section establishes that an approximately EQx allocation can be computed efficiently. In particular, for parameter ε [0, 1], an allocation A is said to be an (1 ε)-EQx allocation if for every pair of agents i, j N and for each good g Ai we have (1 ε) vi(Ai\{g}) vj(Aj). Hence, in an (1 ε)-EQx allocation, removing any good from any agent i s bundle brings down i s value to below 1 1 ε times the minimum. Also, note that ε = 0 corresponds to an exact EQx allocation. We modify Algorithm 1 to obtain an approximately EQx allocation. We replace Lines 4 and 7 in Algorithm 1 with their approximate versions as follows:7

4: while (1 ε) vp(Ap) vp (Ap ) and U = do... 7: while there exists bg Ap such that (1 ε)vp(Ap\{bg}) > vp (Ap ) do... The following theorem provides our main approximation guarantee under monotone valuations. The proof of this result is similar to that of Theorem 2 and is omitted.

Theorem 5. Given parameter ε (0, 1) and any fair division instance with monotone valuations, a (1 ε)-EQx allocation can be computed in O m2n

ε log Vmax time.

4 Nonmonotone Valuations

We now present our results for nonmonotone valuations. We will focus primarily on additive valuations, and will show that even in this case, EQx allocations may not exist. Furthermore, EQx allocations can be hard to compute even if they do exist. It is known that an EQx allocation can be computed in polynomial time if all the agents have identical, additive valuations (Aziz and Rey 2020). Complementing this positive result, we next show that an EQx allocation may not exist among agents that have nonidentical (and nonmonotone) valuations. Our negative result holds even for two agents with additive, normalized valuations. The fair division instance demonstrating this nonexistence of EQx allocations is given in Table 2. In particular, the instance highlights that if there are items with positive value for one agent and negative value for another i.e., the valuations are subjective rather than objective then an EQx allocation may not exist. Further, in such instances, it is NP-hard to determine if an EQx allocation exists.

Theorem 6. An EQx allocation may not exist for two agents with nonmonotone, additive, normalised valuations. Further, in such instances, it is NP-hard to determine whether an EQx allocation exists or not.

7Recall that Lines 4 and 7 in Algorithm 1 check the execution condition for the Add and Fix phases, respectively.

The Thirty-Eighth AAAI Conference on Artiﬁcial Intelligence (AAAI-24)

x1 x2 x3 Agent 1 +1 1 +100 Agent 2 1 +1 +100

Table 2: Example showing nonexistence of EQx allocations in Theorem 6.

Algorithm 2: Two-Way Greedy Algorithm Input: Instance (N, M, V) with two agents and additive objective valuations. Output: EQx allocation A. 1: Initialize A = ( , . . . , ) and item set U := M. 2: while U = do 3: Write r arg max i N vi(Ai) and let p be the other agent

(p = r). 4: Set item g arg max g U G vp(g) and item

c arg min c U C vr(c). {g is most valuable good for

p and c is least valuable chore for r.} 5: if |vp(g )| > |vr(c )| then 6: Update Ap Ap {g } and U U \ {g }. 7: else 8: Update Ar Ar {c } and U U \ {c }. 9: return Allocation A = (A1, . . . , An).

The example for nonexistence is given in Table 2. The computational hardness is established (in the full version of the paper) via a reduction from PARTITION. Given that under subjective valuations EQx allocations are not guaranteed to exist, we will focus on objective additive valuations in the remainder of this section. We will use C to denote the set of chores and G to denote the set of goods. Since valuations are objective, M = G C. Further, given an allocation A, we say agent i has a goods violation if, for some good g Ai, we have vi(Ai \ {g}) > mink vk(Ak). Similarly, agent i has a chores violation if vi(Ai \ {c}) < maxk vk(Ak) for some chore c Ai.

4.1 Two Agents

Theorem 7. Given any fair division instance (N, M, V) with two agents that have additive objective valuations, Algorithm 2 computes an EQx allocation in polynomial time. Proof Sketch. The theorem is established via an inductive argument. A key property utilized in the analysis is that, if, in the iteration, item g is assigned to agent p, then any chore c assigned previously (i.e., in an earlier iteration) to the other agent r must have greater absolute value. Similarly, if c is assigned to agent r in the considered iteration, any good g assigned previously to the other agent p must have greater absolute value. Using these bounds we show that the EQx criterion is maintained as an invariant.

4.2 Identical Chore Valuations We now show that EQx allocations exist when the agents have additive, objective valuations and they value the chores c identically, i.e., vi(c) = vj(c) for all agents i, j N.

As noted, C denotes the set of chores, and G is the set of goods. For each chore c C, we will write vc < 0 to denote the common value of the chore among the agents. For intuition for the proof, consider an allocation A = (A1, . . . , An) that is not EQx. There are two possibilities. There could be a chores violation there exist agents i and j and a chore c Ai such that vi(Ai \ {c}) < vj(Aj). Here c is called the violating chore. Or, there could be a goods violation there exist agents i and j and a good g Aj such that vi(Ai) < vj(Aj \ {g}). Here g a violating good. Our proof is based on the observation that transferring c to Aj in case of a chores violation and g to Ai under a goods violation leads to a lexicographic improvement in the tuple of values. The lexicographic order here additionally incorporates the sizes of the assigned bundles and the agents indices for tie-breaking. Specifically, for any allocation X = (X1, . . . , Xn), we define permutation (ordering) σX Sn over the n agents such that (i) Agents i with lower values, vi(Xi), receive lower indices in σX . (ii) Among agents with equal values, agents i with lower bundle sizes, |Ai|, receive lower indices in σX , and (iii) Then, among agents with equal values and equal number of items, we order by index i. Plaut and Roughgarden 2020b used a similar idea in their proof of the existence of EFx allocations for identical valuations. They introduced the ++ comparison operator, which we detail in Algorithm 3. Unlike their work, we use the ++ operator to obtain existential guarantees for EQx allocations even when the valuations are nonidentical over the goods (but identical for chores). If two agents have the same value and the same number of items, then Plaut and Roughgarden s results hold for any arbitrary but consistent tie-breaking between agents. In the definition of ++ (see Algorithm 3), we use the index of each agent i [n] as a tie-breaker to compare two agents that are otherwise identical (have the same value for their own bundles and the same number of items).

Algorithm 3: ++ comparison operator Input: Allocations A and B. Output: True if A ++ B, else return False.

1: Let σA and σB be the defined permutations of the agents associated with allocations A and B, respectively. 2: for all ℓ [n] do 3: Set i = σA(ℓ) and set j = σB(ℓ). {i and j are the ℓth agents in the permutations.} 4: if vi(Ai) = vj(Bj) then 5: return vi(Ai) < vj(Bj). 6: else if |Ai| = |Bj| then 7: return |Ai| < |Bj|. 8: else if i = j then 9: return i < j.

Theorem 8 (Theorem 4.1, (Plaut and Roughgarden 2020b)). The comparison operator ++ induces a total order on the

The Thirty-Eighth AAAI Conference on Artiﬁcial Intelligence (AAAI-24)

set of all allocations.

We say an allocation A is a leximin++ allocation if B ++ A for all allocations B. Theorem 8 ensures that a leximin++ allocation is guaranteed to exist. The following theorem then establishes the existential guarantee for EQx allocations in the case of identicallyvalued chores.

Theorem 9. In a fair division instance if the agents have additive, objective valuations and they value the chores identically, then the leximin++ allocation is EQx.

4.3 Additive Goods and a Single Chore

We now show that in instances with additive objective valuations and a single chore c, EQx allocations exist. Note first that in the presence of even a single non-identical chore, the leximin++ allocation may no longer be EQx. Instead, our proof of existence is based on a careful analysis of a version of local search, and keeping track of the movement of the single chore. The local search algorithm (Algorithm 4) proceeds as follows. Write A to denote the current allocation. Further, let p be the agent that appears first in the permutation σA (as defined in the previous subsection) and r be the agent that appears last. Note that p and r are a poorest and a richest agent, respectively. If A is not EQx, then there must be either a goods violation or a chores violation. If there is a goods violation in A, then there exists an agent i and good g Ai with the property that vi(Ai \ {g}) > vp(Ap). In our algorithm, we resolve the goods violation by transferring good g to agent p. The algorithm resolves all goods violations, before addressing the chores violation. Now, if there is a chores violation, then for some some agent i and the chore c Ai it holds that vi(Ai \ {c}) < vr(Ar). The algorithm resolves the chores violation by transferring chore c to agent richest agent r. The algorithm repeats these steps resolving all goods violations and then the chores violation until there are no more violations. By design, the algorithm terminates only when the maintained allocation is EQx. To prove that the algorithm indeed terminates, we need the following notation. For an allocation A, we denote by κ(A) as the agent holding the unique chore c, i.e., c Aκ(A). We call the value v+(A) := vκ(A)(Aκ(A) \ c) as the cutoff value of the allocation A and of the agent κ(A). In case of a chores violation we have vκ(A)(Aκ(A) \ c) < vr(Ar). Write B to denote the allocation after transferring chore c to agent r. Note that such a chore transfer increases the cutoff value: under allocation A, the cutoff value is v+(A) = vκ(A)(Aκ(A)\c) and, under the updated allocation B, it is v+(B) = vr(Ar). In particular, v+(A) < v+(B). In our analysis, we will keep track of two progress measures separately: the lexicographic value of the allocation (according to the order ++ defined in Section 4.2) and the cutoff value of the allocation. We will show, in particular, that the cutoff value of the allocation is nondecreasing between successive chores violations, and strictly increases whenever a chores violation is resolved. Whenever a goods violation is

Algorithm 4: Algorithm to compute an EQx allocation Input: Fair division instance (N, M, V) with additive, objective valuations and a single chore c Output: EQx allocation A 1: Initialize A1 = M and Ai = for all agents i = 1. 2: while A = (A1, . . . , An) is not EQx do 3: p = σA(1). {p is the first agent according to σA.} 4: while there exists agent i N and good g Ai such that vi(Ai \ {g}) > vp(Ap) do 5: Update Ap Ap {g} and Ai Ai \ {g}. 6: Update p = σA(1). {After resolving all goods violations, check for chores violation.} 7: r σA(n). {r is the last agent according to σA.} 8: if v+(A) < vr(Ar) then 9: Update Aκ(A) Aκ(A) \{c} and Ar Ar {c}. 10: return A

resolved, we obtain a lexicographic improvement in the allocation; a chores violation may however result in a lexicographic decrease. Since both the cutoff value and the lexicographic value can only increase a finite number of times, the local search algorithm must terminate in finite time. Theorem 10. Given any fair division instance with additive objective valuations and a single chore, Algorithm 4 terminates in finite time and returns an EQx allocation.

5 Conclusion and Future Work Our work resolves fundamental questions regarding the existence of EQx allocations. We present sweeping positive results when all the indivisible items are goods; this includes universal existence of EQx allocations under general, monotone valuations and an accompanying pseudopolynomial time algorithm. For monotone valuations, we also provide a fully polynomial-time approximation scheme (FPTAS) for finding approximately EQx allocations. In addition, we show that under weakly well-layered valuations EQx allocations can be computed efficiently. For mixed items (goods and chores), we show that EQx allocations may not exist. For additively-valued goods and chores, our results present a mixed picture: existence and efficient computation for two agents, and existence either when each chore has the same value among the agents, or if there is a single chore. In fact, all our positive results hold if we interchange goods and chores. For instance, the results in Section 3 hold for monotone nonincreasing valuations (i.e., when all items are chores) as well, with suitably modified definitions. Formal statements are given in the full version of the paper (Barman et al. 2023). A number of significant open questions remain. First, the existence of EQx allocations under objective, additive valuations remains unresolved. Second, efficient algorithms for computing EQx allocations in this case (or even for goods and a single chore, or identical chores) appear challenging. Lastly, given the practical significance, truthful mechanisms for obtaining EQx allocations may prove useful.

The Thirty-Eighth AAAI Conference on Artiﬁcial Intelligence (AAAI-24)

Acknowledgments Siddharth Barman s research is supported by a SERB Core research grant (CRG/2021/006165). We thank Rohit Vaish for useful discussions regarding the problem, and suggestions for the paper.

References Aumann, Y.; and Dombb, Y. 2015. The efficiency of fair division with connected pieces. ACM Transactions on Economics and Computation (TEAC), 3(4): 1 16. Aziz, H.; and Rey, S. 2020. Almost Group Envy-free Allocation of Indivisible Goods and Chores. In Bessiere, C., ed., Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI 2020, 39 45. ijcai.org. Barman, S.; Bhaskar, U.; Pandit, Y.; and Pyne, S. 2023. Nearly Equitable Allocations Beyond Additivity and Monotonicity. ar Xiv:2312.07195. Barman, S.; Narayan, V. V.; and Verma, P. 2023. Fair Chore Division under Binary Supermodular Costs. In Agmon, N.; An, B.; Ricci, A.; and Yeoh, W., eds., Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2023, London, United Kingdom, 29 May 2023 - 2 June 2023, 2863 2865. ACM. Bhaskar, U.; Misra, N.; Sethia, A.; and Vaish, R. 2023. The Price of Equity with Binary Valuations and Few Agent Types. Co RR, abs/2307.06726. Caragiannis, I.; Kaklamanis, C.; Kanellopoulos, P.; and Kyropoulou, M. 2012. The Efficiency of Fair Division. Theory of Computing Systems, 50(4): 589 610. Cechl arov a, K.; Doboˇs, J.; and Pill arov a, E. 2013. On the existence of equitable cake divisions. Information Sciences, 228: 239 245. Cechl arov a, K.; and Pill arov a, E. 2012. On the computability of equitable divisions. Discrete Optimization, 9(4): 249 257. Chen, X.; and Liu, Z. 2020. The Fairness of Leximin in Allocation of Indivisible Chores. Co RR, abs/2005.04864. Ch eze, G. 2017. Existence of a simple and equitable fair division: A short proof. Mathematical Social Sciences, 87: 92 93. Dubins, L. E.; and Spanier, E. H. 1961. How to cut a cake fairly. The American Mathematical Monthly, 68(1P1): 1 17. Foley, D. K. 1966. Resource allocation and the public sector. Yale University. Freeman, R.; Sikdar, S.; Vaish, R.; and Xia, L. 2019. Equitable Allocations of Indivisible Goods. In Proceedings of the 28th International Joint Conference on Artificial Intelligence, 280 286. Freeman, R.; Sikdar, S.; Vaish, R.; and Xia, L. 2020. Equitable Allocations of Indivisible Chores. In Proceedings of the 19th International Conference on Autonomous Agents and Multi Agent Systems, 384 392. Gal, Y. K.; Mash, M.; Procaccia, A. D.; and Zick, Y. 2017. Which Is the Fairest (Rent Division) of Them All? J. ACM, 64(6): 39:1 39:22.

Goldberg, P. W.; Høgh, K.; and Hollender, A. 2023. The Frontier of Intractability for EFX with Two Agents. In Deligkas, A.; and Filos-Ratsikas, A., eds., SAGT 2023, volume 14238 of Lecture Notes in Computer Science, 290 307. Springer. Goldman, J.; and Procaccia, A. D. 2015. Spliddit: Unleashing Fair Division Algorithms. ACM SIGecom Exchanges, 13(2): 41 46. Gourv es, L.; Monnot, J.; and Tlilane, L. 2014. Near Fairness in Matroids. In Proceedings of the 21st European Conference on Artificial Intelligence, 393 398. Gourv es, L.; Monnot, J.; and Tlilane, L. 2014. Near Fairness in Matroids. In Schaub, T.; Friedrich, G.; and O Sullivan, B., eds., ECAI 2014, volume 263 of Frontiers in Artificial Intelligence and Applications, 393 398. IOS Press. Herreiner, D. K.; and Puppe, C. 2010. Inequality aversion and efficiency with ordinal and cardinal social preferences An experimental study. Journal of Economic Behavior & Organization, 76(2): 238 253. Herreiner, D. K.; and Puppe, C. D. 2009. Envy freeness in experimental fair division problems. Theory and decision, 67: 65 100. Kagan, J. 2021. Equitable Distribution: Definition, State Laws, Exempt Property. https://www.investopedia.com/ terms/e/equitable-division.asp. Accessed: 2023-08-12. Moulin, H. 2004. Fair division and collective welfare. MIT press. Plaut, B.; and Roughgarden, T. 2020a. Almost Envy Freeness with General Valuations. SIAM Journal on Discrete Mathematics, 34(2): 1039 1068. Plaut, B.; and Roughgarden, T. 2020b. Almost Envy Freeness with General Valuations. SIAM J. Discret. Math., 34(2): 1039 1068. Procaccia, A. D.; and Wang, J. 2017. A lower bound for equitable cake cutting. In Proceedings of the 2017 ACM Conference on Economics and Computation, 479 495. Sun, A.; Chen, B.; and Doan, X. V. 2023. Equitability and welfare maximization for allocating indivisible items. Autonomous Agents and Multi-Agent Systems, 37(1): 8. Varian, H. R. 1974. Equity, Envy, and Efficiency. Journal of Economic Theory, 9(1): 63 91.

The Thirty-Eighth AAAI Conference on Artiﬁcial Intelligence (AAAI-24)