Fairly Allocating Goods and (Terrible) Chores

1 Introduction

Fair division of indivisible items has provided a rich mathematical framework for studying computational and axiomatic aspects of fairness in a variety of settings ranging from assigning students to courses [Budish, 2011] and distributing food donations [Aleksandrov et al., 2015] to assigning papers to reviewers [Shah, 2022; Payan and Zick, 2022] and distributing medical equipment and vaccines [Schmidt et al., 2021; Aziz and Brandl, 2021; Pathak et al., 2021]. In these applications, the preferences of agents over items may be subjective, that is, some agents may consider an item as a good (with non-negative utility) while others may see the same item as a chore (with negative utility). For instance, in peer reviewing, reviewers may consider a paper to be a chore if it is outside of their immediate expertise while another subset of reviewers consider it as a good due its proximity to their own field. Thus, an emerging line of work has focused on fair allocation of mixture of goods and chores [Aziz et al., 2022; Bérczi et al., 2020; Kulkarni et al., 2021].

When distributing indivisible items, a prominent fairness notion, envy-freeness (EF) [Foley, 1967; Gamow and Stern,

1958], may not always exist. Its most compelling relaxation, envy-freeness up to any item (EFX) [Caragiannis et al., 2019], states that any pairwise envy is eliminated if we remove any single item that is considered as a good in the envied agent's bundle or is seen as a chore in the envious agent's bundle. A slightly weaker notion is envy-freeness up to one item (EF1) [Lipton et al., 2004; Budish, 2011], which requires that any pairwise envy can be eliminated by the removal of some single item from the bundle of one of the two agents. These relaxations gave rise to several challenging open problems, particularly when dealing with chores: the existence of EFX and, for mixed or even chores-only settings, the existence and computation of EF1 in conjunction with efficiency notions such as Pareto optimality (PO). To gain insights into structural and computational boundaries of achieving these fairness notions, several recent efforts have considered a variety of restricted domains such as limiting the number of agents [Chaudhury et al., 2020; Mahara, 2021], the item types [Aziz et al., 2023; Nguyen and Rothe, 2023], or the valuations (binary, bi-valued valuations, or identical) [Halpern et al., 2020; Garg et al., 2022; Bérczi et al., 2020]. One such natural restriction are lexicographic preferences-a subdomain of additive preferences-which provides a compact representation of preferences, and has been studied in voting [Lang et al., 2018], object allocation [Saban and Sethuraman, 2014; Hosseini and Larson, 2019], and fair division [Nguyen, 2020; Ebadian et al., 2022].

In this domain, it was recently shown that an EFX allocation may not always exist for mixed instances [Hosseini et al., 2023b]. Moreover, while weaker fairness notions such as EF1 and maximin share (MMS) are guaranteed to exist for mixed items, their computation along with PO remains unknown even for objective instances where all agents agree on whether an item is a good or a chore.

The non-existence of EFX for mixed items crucially relies on a set of highly undesirable chores (or terrible chores). Without these chores (i.e., if a single agent considers a good as its most important item), under lexicographic preferences an EFX and PO allocation can be computed in polynomial time [Hosseini et al., 2023b]. This observation raises several important questions: Can we efficiently decide whether an EFX allocation exists even in the presence of terrible chores? Can we efficiently compute an EF1 (or MMS) allocation in conjunction with PO?

1.1 Contributions

We focus on the allocation of mixtures of goods and chores in the lexicographic domain and resolve several open computational problems pertaining to the well-studied fairness notions of EFX, EF1, and MMS. 1

EFX. We show that determining the existence of an EFXallocation is NP-complete under lexicographic mixed instances even for objective preferences, i.e., when all agents agree on whether an item is a good or a chore (Theorem 1). To the best of our knowledge, this finding is the first computational intractability result for EFX over every preference extension containing lexicographic (and as a result additive) preferences. Subsequently, we discuss that deciding whether an EFX and PO allocation exist is NP-hard (Corollary 1).

EFX+PO. Given the possible non-existence of an EFX allocation even for objective mixed instances, and the computational hardness of determining its existence, we identify a natural variation of lexicographic preferences, called separable lexicographic preferences for which positive results can be obtained. In particular, we show that EFX and PO allocations always exist even in separable instances with terrible chores (Theorem 2) and further prove that under separable lexicographic preferences an EFX and PO allocation can be computed efficiently (Corollary 2).

EF1+PO. Given that an EFX allocation may not exist under general (not necessarily separable) lexicographic mixed preferences, we focus our attention on EF1 along with Pareto optimality. While an EF1 allocation always exists and can be computed efficiently [Bhaskar et al., 2021; Aziz et al., 2022], its existence and computation along with PO remains open even for additive chores-only instances. We identify a class of lexicographic mixed instances with sufficiently many common terrible chores for which an EF1 and PO allocation can be computed in polynomial time (Theorem 3) and discuss several technical challenges in extending this result.

MMS+PO. Despite the non-existence of EFX and challenges in achieving EF1+PO, we show that an MMS and PO allocation always exists for any mixed instance containing terrible chores (Theorem 4) and can be computed efficiently for any mixed instance (Corollary 3). Moreover, we show that when the efficiency is strengthened to rank-maximality (RM), deciding whether an instance admits an MMS and rank-maximal allocation is NP-complete (Theorem 5).

1.2 RelatedWork

The existence of EFX is a major open problem in goods-only and chores-only settings. Moreover, EFX is known to be incompatible with PO under non-negative valuations [Plaut and Roughgarden, 2020a]. An EFX allocation may fail to exist under non-monotone, non-additive, and identical valuation functions [Bérczi et al., 2020] and for mixed items with additive valuations [Hosseini et al., 2023b]. While the computation of EFX is known to be hard for submodular valuations [Plaut and Roughgarden, 2020b; Goldberg et al., 2023], for additive preferences, the computational complexity of determining whether an instance admits an EFX allocation has been an open question, which we answer in this paper.

1 Some proofs and examples are relegated to the full version of the paper [Hosseini et al., 2023a].

An EF1 allocation can be computed efficiently in goodsonly [Caragiannis et al., 2019; Lipton et al., 2004] and chores-only [Aziz et al., 2022; Bhaskar et al., 2021] settings. When considering economic efficiency, for goods-only instances EF1 is compatible with PO [Caragiannis et al., 2019] and can be computed in pseudo-polynomial time [Barman et al., 2018]. In contrast, for chores-only settings, it is not known whether EF1 and PO allocations exist under additive valuations. For mixed items, an EF1 allocation can still be computed efficiently when valuations are doubly monotonic (which includes additive valuations) [Bhaskar et al., 2021; Aziz et al., 2022] through a careful use of the envy-graph algorithm. However, achieving EF1 alongside PO (except for two agents [Aziz et al., 2022]) remains an open problem.

With additive valuations, an MMS allocation could fail to exist in both the goods-only [Kurokawa et al., 2018] and the chores-only [Aziz et al., 2017] settings. Due to this non-existence, several multiplicative [Aziz et al., 2017; Ghodsi et al., 2021; Garg and Taki, 2021] and ordinal approximations [Babaioff et al., 2019; Hosseini et al., 2022b] to MMS have been proposed for both goods-only and choresonly settings. For mixed items, no constant multiplicative [Kulkarni et al., 2021] or ordinal [Hosseini et al., 2022a] approximation of MMS may exist.

Domain Restriction. To circumvent the negative results and explore the computational boundary and their compatibility with other properties, much attention has been given to studying fairness in restricted domains. For goodsonly settings, an EFX allocation is guaranteed to exist when agents have identical monotone valuations [Plaut and Roughgarden, 2020a], submodular valuations with binary marginals [Babaioff et al., 2021; Viswanathan and Zick, 2023], or additive valuations with at most two distinct values [Amanatidis et al., 2021; Garg and Murhekar, 2021]. For chores-only instances, an EFX allocation can be efficiently computed when there are four agents with only two types of additive valuations over seven items [Bérczi and Gedefa Tolessa, 2022]. Under lexicographic preferences, an EFX and PO allocation always exists and can be computed in polynomial time for goods-only and chores-only settings [Hosseini et al., 2021] and can often be guaranteed along with strategyproofness and other desirable properties.

In chores-only settings, EF1 and PO allocations can be computed in polynomial time when preferences are restricted to bivalued additive valuations [Ebadian et al., 2022; Garg et al., 2022] or when there are only two types of chores [Aziz et al., 2023]. Similarly, MMS allocations are known to always exist for restricted domains such as personalized bivalued valuations, and can be computed efficiently along PO under factored bivalued valuations and weakly lexicographic valuations (allowing ties between items) [Ebadian et al., 2022].

2 Preliminaries

For every k ∈ N, let [k] = {1, . . . , k}. Let N := [n] be a set of n agents and M := {o1, . . . , om} be a set of m items. For each i ∈ N, Gi ⊆ M denotes the subset of items considered as goods and Ci := M \ Gi is the set of items considered as chores by agent i. Items that are goods (chores) for all agents are referred to as common goods (similarly, common chores) i.e., ¯G := ⋂i∈N Gi ( ¯ C := ⋂i∈N Ci).

Preferences. We consider lexicographic preferences over all possible subsets of mixed items, through a linear order that specifies an importance ordering of items for each agent. That is, for each agent i ∈ N there is an associated importance ordering ▷i which is a linear order over M. Thus, an importance profile is simply denoted by ▷ := (▷1, . . . , ▷n). We use "+" (or "-") in superscript to denote that an item is a good (or a chore) in an importance ordering. For example,

means that agent i considers o1 and o3 as goods and o2 as a chore. For a subset of items X ⊆ M, let ▷i(k, X) denote the k-th most important item in X according to an ordering ▷i. When X = M, we will simply write ▷i(k) for brevity.

Agent i's lexicographic preference ≻i is a strict linear order over all possible subsets of items, which is defined based on its importance ordering ▷i as follows: For every nonidentical X, Y ⊆ M, we say that X ≻i Y if and only if ▷i(1,X△Y ) ∈ (X ∩ Gi) ∪ (Y ∩ Ci), where △ denotes a symmetric difference (formally, A△B = (A ∪ B) \ (A ∩ B) for every sets A and B). In other words, X is preferred to Y if and only if the most important item on which they differ is either a good in X or a chore in Y . For every X, Y ⊆ M, we will write X ⪰i Y if X ≻i Y or X = Y . For instance, based on agent i's importance ordering stated above in (1), we have {o+1 , o+3 } ≻i {o+1 } ≻i {o+1 , o-2 , o+3 } ≻i {o+1 , o-2 } ≻i {o+3 } ≻i ∅ ≻i {o-2 , o+3 } ≻i {o-2 }.

Terrible Chores and Separable Preferences. For disjoint subsets X, Y ⊆ M, we use a shorthand notation X ▷i Y to say that for every x ∈ X and y ∈ Y it holds that x▷i y. A set of terrible chores is a set of chores more important than any good, i.e., a maximal set C ∗ i ⊆ Ci such that C ∗ i ▷i Gi (note that, if Gi = ∅, then C ∗ i = Ci). An importance ordering ▷i is separable if either Ci ▷i Gi or Gi ▷i Ci. In other words, in a separable ordering either all chores are terrible or every good is more important than every chore.

Instance. An instance of the allocation problemwith mixed items (a mixed instance) is a four-tuple (N,M,G,▷), where G := (Gi)i∈N and ▷ := (▷i)i∈N . An instance is goods-only if G = M, chores-only if G = ∅, and is objective if Gi = Gj for every i, j ∈ N. An instance (N,M,G,▷) is separable if the importance orderings are separable. Note that separable instances can be seen as a special extension of lexicographic preferences over mixed items with the assumption that for every agent either chores are more important than goods or goods than chores. On the other hand, lexicographic preferences can be seen as a special case of additive preferences in which the magnitude of valuations grow exponentially in the importance ordering. Figure 1 illustrates the inclusion relation between different lexicographic extensions.

A mixed instance with terrible chores is a (possibly objective) instance in which C ∗ i ̸= ∅ for every i ∈ N. The following example illustrates such an instance.

Example 1. Consider a mixed instance with three agents, six items and a profile as follows. The set of common goods is ¯G = {o+5 , o+6 }, and the set of common chores is ¯ C = {o-1 , o-2 }. This mixed instance contains terrible chores because every agent has a top item as a chore, i.e., ▷i(1) ∈ Ci. In fact, it is a separable instance as well.

1 : o-1 ▷ o-2 ▷ o-3 ▷ o+4 ▷ o+5 ▷ o+6

2 : o-1 ▷ o-2 ▷ o-3 ▷ o-4 ▷ o+5 ▷ o+6

3 : o-1 ▷ o-2 ▷ o+3 ▷ o+4 ▷ o+5 ▷ o+6

(underline denotes an allocation described in Section 3.1).

Allocations. An allocation A := (Ai)i∈N is a partition of M such that Ai ⊆ M is agent i's bundle. An allocation is complete if all items in M are assigned, i.e., ⋃i∈N Ai = M and is partial otherwise. Unless explicitly stated, we assume that an allocation is complete.

Envy-freeness. Given a pair of agents i, j ∈ N, agent i envies j if Aj ≻i Ai. Allocation A is envy-free (EF), if for every pair of agents i, j ∈ N, we have Ai ⪰i Aj . Allocation A is envy-free up to one item (EF1), if for every i, j ∈ N such that i envies j, there is g ∈ Gi ∩Aj such that Ai ⪰i Aj \{g} or there is c ∈ Ci ∩Ai such that Ai \ {c} ⪰i Aj. Allocation A is envy-free up to any item (EFX), if for every i, j ∈ N such that i envies j, it holds that for every g ∈ Gi ∩ Aj we have Ai ⪰i Aj \ {g} and for every c ∈ Ci ∩ Ai we have Ai \ {c} ⪰i Aj .

Maximin Share. The maximin share (MMS) of an agent, i ∈ N, is the most preferred bundle it can guarantee by creating an n-partition and receiving the worst one. Formally, MMSi := maxA∈Πn min{A1, . . . ,An}, where Πn is the set of all n-partitions of M, and max and min denote the most preferred and the least preferred bundles according to ≻i, respectively. An allocation A satisfies maximin share, if for all i ∈ N it holds that Ai ⪰i MMSi. In our setting EFX implies both EF1 and MMS, but the converse is not true. Also, EF1 and MMS do not imply each other [Hosseini et al., 2023b].

Economic Efficiency. A (possibly partial) allocation A Pareto dominates allocation B if A assigns the same set of items as B, i.e., ⋃i∈N Ai = ⋃i∈N Bi, and Ai ⪰i Bi for every i ∈ N and there exists i ∈ N such that Ai ≻i Bi. Allocation A is Pareto optimal (PO), if it is not Pareto dominated by any other allocation. In Section 5, we also consider rank maximality (RM), which is a stronger efficiency notion. Intuitively, it means that each item is given to an agent that values it the most. We give a formal definition in the full version of the paper.

We note that EFX and PO allocations always exist and can be efficiently computed in every instance without terrible chores, i.e., when at least one agent sees its most important item as a good [Hosseini et al., 2023b]. Thus, we primarily focus on instances with terrible chores.

Serial Dictatorship. An ordering of agents is a sequence σ = (σ1, . . . , σn) such that σi ∈ N denotes the i-th agent in the sequence. A quota vector q = (q1, . . . , qn) is a vector of nonnegative integers that we assign to each agent. A serial dictatorship mechanism, prescribed by an ordering σ and a quota q, proceeds as follows: starting from some partial (possibly empty) allocation A, in each step, i ∈ [k], if there are still unallocated items, we take the qσi most preferred ones by agent σi (i.e., the most important goods and then the least important chores if there are not enough goods left) and add them to the bundle of this agent.

3 Envy-Freeness up to Any Item (EFX)

Recall that an EFX allocation may fail to exist for mixed instances [Hosseini et al., 2023b]. This non-existence crucially relies on a set of chores that are at the top of the importance orderings of the agents, i.e., the terrible chores. Otherwise, if there is at least one agent with the top item as a good, an EFX and PO allocation can be computed efficiently under lexicographic preferences. Thus, we focus on mixed instances with terrible chores and show that deciding whether an EFX allocation exists is computationally hard under lexicographic preferences, which subsequently implies hardness for additive preferences with mixed items.

Theorem 1. The problem of deciding whether there exists an EFX allocation for a given lexicographic mixed instance is NP-complete.

Proof (sketch). We prove the hardness by a reduction from EXACT COVER BY 3-SETS (X3C). In an X3C instance, we have a universe U = {u1, . . . , um} and a family of its threeelement-subsets, S = {S1, . . . , Sn}. The problem, which is known to be NP-complete [Johnson and Garey, 1979], is to decide whether there exists an exact cover K ⊂ S of size k, such that ⋃Sj∈K Sj = U.

For every such X3C instance, we construct a corresponding objective mixed items instance (N,M,G,▷) as follows. For every element ui ∈ U, we take 2n common chores ci,1, . . . , ci,2n. We add to it k common goods g1, . . . , gk (the assignment of which will correspond to the choice of subsets in K), which gives us |M| = 2mn + k items in total. Next, for every subset Sj ∈ S we take two agents 2j -1 and 2j and we give them identical importance orderings, i.e., ▷2j-1 = ▷2j. Specifically, their importance ordering consists of three "blocks": first there are all chores corresponding to elements ui such that ui ̸∈ Sj, then there are k goods g1, . . . , gk, and at the end there are all chores corresponding to elements ui ∈ Sj. For example, if we had Sj = {u1, u2, u3}, then the importance ordering of agents 2j - 1 and 2j would be c4,1 ▷ · · · ▷ cm,2n ▷ g1 ▷ · · · ▷ gk ▷ c1,1 ▷ · · · ▷ c3,2n.

We prove that there is a cover in an X3C instance, if and only if, there is an EFX allocation in the corresponding mixed item instance. If there is a cover, without loss of generality we assume that K = {S1, . . . , Sk} and show that allocation A = (A1, . . . , A2n), where

is EFX (and also PO). If there is no cover, we analyze the number of "uncovered" chores in an allocation, i.e., chores received by an agent that are more important than every good it received. We show that EFX would imply that there can be at most 2n-1 such chores, but no set cover implies that there are at least 2n of them-a contradiction.

In the proof of Theorem 1, we show that the allocation defined in equation (2) (i.e., an EFX allocation that exists when there is a set cover in an X3C instance) is not only EFX but also PO. This implies that deciding whether there exists an allocation that is both EFX and PO is also NP-hard (since the problem of verifying if an allocation is PO in polynomial time remains open, we cannot claim NP-completeness).

Corollary 1. The problem of deciding whether there exists an EFX and PO allocation for a given lexicographic mixed instance is NP-hard.

The constructions in the proof of Theorem 1 only used objective instances, where all agents agree on whether an item is a chore or a good. Thus, these computational hardness results hold for all mixed instances and do not rely on subjective views of agents.

3.1 EFX and PO: Separable Preferences

An important feature of our construction in the proof of Theorem 1 is that each agent has some terrible chores and some other (non-terrible) chores that are separated by several goods in its importance ordering. In this section, we analyze the case where either all chores are terrible or all are less important than every good, i.e., the separable lexicographic preferences. We show that such a constraint enables us to devise an algorithm that computes an EFX and PO allocation for every separable instance.

Algorithm 1 finds one such allocation for every mixed instance with separable preferences that contains terrible chores. It extends the algorithm by Hosseini et al. [2023b] for EFX and PO allocations in instances in which the most important item of one of the agents is a good (in fact Phase 2 of our algorithm can be seen as running this algorithm on a smaller instance).

Algorithm 1. Fix any ordering of agents 1, . . . , n. The algorithm runs in two phases. In Phase 1, we allocate all common chores (items in ¯ C) and goods to agents that receive these chores. First, all common chores are allocated through a serial dictatorship with ordering (1, . . . , n) and quotas q, in which every agent, except possibly the first one, receives one item. Then starting from the last agent which received a common chore (i.e., the worst chore), say agent z, in the reverse Algorithm 1 Finding an EFX and PO allocation for separable lexicographic preferences Input: A mixed instance (N,M, G, ▷) with separable preferences

that contains terrible chores Output: An allocation A that is EFX and PO 1: A := (∅, . . . , ∅) ▷ PHASE 1: 2: assign common chores, ¯ C, by a serial dictatorship with ordering (1, . . . , n) and quotas q, where q1 = max(1, | ¯ C| - n + 1) and qi = 1, for i ∈ N \ {1} 3: N ′ := {i ∈ N : Ai = ∅}, H :=M \ ¯ C 4: z :=max{N \N ′ } 5: for i ∈ (z, z -1, . . . , 1) do 6: Ai ←Ai ∪ (Gi ∩H), H ←H \ Ai 7: end for ▷ PHASE 2: 8: for k ∈ (1, . . . , |M|) do 9: while there is i ∈ N ′ such that ▷i(k) ∈ H ∩Gi do 10: gi := ▷i(k), Ai ← {gi} 11: Ai ←Ai ∪ (H ∩Gi \ ⋃j∈N′\{i} Gj ) 12: N ′ ←N ′ \ {i}, H ←H \ Ai 13: end while 14: end for 15: return A

order, i.e., z, z - 1, . . . , 1, we add to each agent's bundle all the unassigned items that it considers as goods. At the end of Phase 1, all remaining items are considered as a good for at least one agent in N, but considered as a chore by all agents who received an item in Phase 1, i.e., agents in [z]. This is crucial for ensuring that the final allocation will be EFX. In Phase 2, we distribute the remaining items in such a way that each is assigned to an agent for which it is a good. Specifically, we move through the positions in importance orderings, one by one, starting from the first position with an unassigned item. For each position k, we find an agent, i ∈ N ′ , that has yet unassigned good at position k, and assign this good plus all remaining items that only i considers as goods (but no other remaining agent considers as goods). This process repeats until no item remains unassigned.

Example 2. Consider the mixed instance with separable preferences given in Example 1. Algorithm 1 starts by running a serial dictatorship with a fixed ordering of (1, 2, 3) to allocate all terrible common chores, i.e., {o-1 , o-2 }. Thus, agents 1 and 2 receive o-2 and o-1 respectively, while agent 3 receives nothing. Then, starting from agent 2, the last agent who received a chore (the worst chore), in the reverse ordering i.e., (2, 1), agents receive all their remaining goods (if any). Therefore, at the end of Phase 1, A1 = {o-2 , o+4 }, A2 = {o-1 , o+5 , o+6 } and A3 = ∅.

In Phase 2, the only remaining item o3 is allocated to agent 3 who sees it as a good (while agents 1 and 2 consider o3 as a chore). The final allocation is underlined in Example 1.

The proof of the correctness of Algorithm 1 relies on the general result concerning the serial dictatorship mechanism (Lemma 1). Assume there is a PO partial allocation, B, and a set of common chores, H, such that for each agent H is more important than its current bundle and all its goods (so, chores in H are terrible for all agents). We show that extending B by allocating items in H through the serial dictatorship with arbitrary ordering and quotas will preserve PO. Since the order of allocating items does not affect the final allocation, Lemma 1 can be used to show the correctness of Algorithm 1.

Lemma 1. For every instance (N,M,G,▷), subset of common chores H ⊆ ¯ C, and partial allocation B of items in M \ H that is PO, if for each i ∈ N it holds that H ▷i (Gi ∪Bi), then every allocation A obtained by extending B by the serial dictatorship with an arbitrary ordering and quotas is PO.

Proof. Assume by contradiction that there exists A obtained by the serial dictatorship that is not PO. This means that there exists an allocation A′ that Pareto dominates A. Now, let us consider two cases based on whether A and A′ differ on assignment of chores in H. If this is true, then there exists a common chore, c ∈ H, that is assigned to different agents in A and A′ , i.e., there exists i ∈ N such that c ∈ A′i \ Ai. Let us take c and i such that, among all such chores, c was picked as the last one in the serial dictatorship leading to A. Observe that every chore c′ ∈ H ∩ Ai such that c′ ▷i c was picked by agent i after c was assigned (otherwise i would pick c instead). Hence, for every such c′ we have also c′ ∈ A′i (otherwise c would not be the last picked chore that is assigned to different agents in A and A′ ). Since H ▷i (Gi ∪ Bi), this implies that Ai ≻i A′i , which means that A′ does not Pareto dominate A-a contradiction.

Finally, consider the case in which A and A′ assign chores in H identically. By B′ let us denote the partial allocation obtained from A′ by removing chores in H. Since A′ Pareto dominates A, it means that B′ Pareto dominates B. But that contradicts the fact that B is PO.

Theorem 2. Given a mixed instance with separable preferences that contains terrible chores, an EFX and PO allocation always exists and can be computed in polynomial time.

When at least one agent's top item is a good, an EFX and PO allocations are guaranteed to exist and can be computed efficiently [Hosseini et al., 2023b]. Combining this with Theorem 2 we obtain the following computational and existence results for separable preferences.

Corollary 2. Given any mixed instance with separable preferences, an EFX and PO allocation always exists and can be computed in polynomial time.

4 EF1 and PO

Despite the non-existence of EFX and the computational hardness of deciding whether an instance admits such an allocation (Theorem 1), we identified a natural class of separable lexicographic preferences for which an EFX and PO allocation is always guaranteed to exist and can be computed efficiently (Theorem 2). This raises the question of whether focusing on weaker fairness notions, e.g., EF1 or MMS, enables us to escape these negative results for the more general mixed lexicographic (but not necessarily separable) preferences.

In this section, we focus on EF1 and discuss the technical challenges in satisfying it with PO. We then devise an efficient algorithm for finding EF1 and PO when there are sufficiently many common terrible chores, specifically, when there are at least n - 1 terrible chores shared by all agents.

Before presenting our main result in this section, let us discuss the technical challenges in achieving EF1 and PO for mixed lexicographic preferences. 2 For mixed instances, under additive or doubly monotone valuations, 3 an EF1 allocation (without PO) can be computed efficiently through either the double round robin algorithm [Aziz et al., 2022] or a variant of the envy-graph algorithm [Bhaskar et al., 2021]. However, both these approaches fail in satisfying PO even when preferences are restricted to the lexicographic domain.

Remark 1. Other naive approaches also fail to achieve the desired outcome. For instance, a good may have to be given to an agent that does not rank it as high as other agents. This observation immediately shows that approaches used for achieving EFX and PO under separable preferences (as described in Algorithm 1) or those proposed by [Hosseini et al., 2023b] that assign goods to agents having them high in the orderings fail. We illustrate this challenge in the next example.

Example 3. Consider a mixed instance with five agents, six items, and a profile as follows. The set of common chores is ¯ C = {o-2 , o-3 , o-4 , o-5 , o-6 }, the set of common goods is ¯G = {o+1 }, but the set of common terrible chores is empty.

In this instance, every EF1 and PO allocation must assign the only good, o+1 to agent 1; otherwise, either the allocation violates PO or it violates EF1. Note that all other agents rank o+1 higher in their importance ranking; yet, this common good must be allocated to agent 1.

Note that if the preferences of agents 3, 4, and 5 were identical to those of agent 1 (instead of 2), then o+1 would need to be allocated to agent 2 to guarantee EF1 and PO. In the full version of the paper, we give additional examples to illustrate the complexity of this problem.

Given the aforementioned challenges, we show that for lexicographic mixed instances that contain at least n-1 common terrible chores, an EF1 and PO allocation always exists and can be computed efficiently. Formally, the set of common terrible chores contains all chores that are terrible for all agents, i.e., ¯ C ∗ = ⋂i∈N C ∗ i . We describe an algorithm that finds an EF1 and PO allocation for every mixed instance with at least n-1 common terrible chores, i.e., | ¯ C ∗ | ≥ n-1 (we present its pseudocode in the full version of the paper).

2 The existence and computation of EF1 and PO allocations remain open even for additive chores-only instances.

3 Doubly (or item-wise [Chen and Liu, 2020]) monotone is a broad valuation class where each agent can partition items into those with non-negative (goods) or negative (chores) marginal utility.

Algorithm 2. Fix any ordering of agents 1, . . . , n. We start by giving agent 1 all items it considers as goods. To each next agent, in the order 2, . . . , n, we give everything it considers as goods from the set of unassigned items (or nothing if there are no such items left). The remaining items are necessarily common chores. Next, we start from agent n, and assign to it all of its non-terrible chores. To each next agent, in the reversed order, i.e., n - 1, . . . , 1, we give all its non-terrible chores that remain (if any). The only remaining items are common terrible chores. Such partial allocation is PO, but it can be very unfair (agent 1 got all its goods and agent n all its non-terrible chores). To ensure fairness, we assign the remaining common terrible chores using serial dictatorship with ordering σ such that the last agent, σn, is not envied by any other agent (since the partial allocation is PO there surely is such σ). In this way, every agent (except possibly σn) receives at least one common terrible chore, which results in an EF1 allocation (and by Lemma 1 it is still PO).

Example 4. Consider a mixed instance with three agents, eight items, and a profile as follows. The set of common chores is ¯ C = {o-1 , o-2 , o-3 , o-5 }.

Suppose the ordering is (1, 2, 3). the algorithm starts by assigning {o+4 , o+6 , o+8 } and {o+7 } to agents 1 and 2, respectively. Then in the reverse ordering (3, 2, 1), agents get their common non-terrible chores (out of the remaining items), resulting in agent 3 receiving o-5 (and nothing for others). Since agent 3 is not envied (such an agent always exists), the algorithm allocates all common terrible chores ({o-1 , o-2 , o-3 }) by running a serial dictatorship with the ordering of (1, 2, 3) and single quota. The final allocation is underlined.

Theorem 3. Given a lexicographic mixed instance with at least n-1 common terrible chores, an EF1 and PO allocation always exists and can be computed in polynomial time.

Given the theorem above, one may wonder whether a similar approach can be utilized for instances with potentially fewer than n - 1 common terrible chores. In the full version of the paper, we show that even extending to n - 2 (if possible) requires new techniques with a rather complicated analysis to guarantee Pareto optimality.

5 MMS and Efficiency

Despite the challenges in satisfying EF1 and PO for lexicographic mixed instances that contain terrible chores, we show that an MMS and PO allocation always exists and can be computed in polynomial time. Note that while an MMS allocation can be computed efficiently [Hosseini et al., 2023b], its computation along with economic efficiency notions such as PO and rank maximality was open even for objective instances. We build on the characterization of maximin share of an agents which is specified by its most important item: if the top item of an agent is a chore, its MMS is this top item and

Algorithm 3 Finding an MMS and PO allocation

Input: Amixed instance (N,M,G,▷) with terrible chores

Output: An allocation A that is MMS and PO 1: A := (∅, . . . , ∅), c∗ := ▷n(1) 2: for i ∈ (1, . . . , n) do 3: Ai ←Gi \ ⋃j∈[i-1] Aj 4: end for 5: An ←An ∪ ¯ C \ {c∗ } 6: if for every i ∈ N it holds that ▷i(1) = c∗ then 7: A1 ←A1 ∪ {c∗ } 8: else if c∗ ∈ ¯ C then 9: i∗ :=max{i ∈ [n] : ▷i(1) ̸= c∗ } 10: Ai∗ ←Ai∗ ∪ {c∗ } 11: end if 12: return A

all items it considers as goods; otherwise its MMS is the set of all items that it considers as a good without the first n- 1 goods according to its importance ordering (or the empty set if its importance ordering contains fewer than n goods).

Proposition 1. [Hosseini et al., 2023b] Given a mixed instance (N,M,G,▷), for every agent i ∈ N, if ▷i(1) ∈ Ci, it holds that MMSi = {▷i(1)} ∪ Gi. Otherwise, if ▷i(1) ∈ Gi, it holds that MMSi = ∅, if |Gi| < n, or MMSi = Gi \ ⋃k∈[n-1] {▷i(k,Gi)}, if |Gi| ≥ n.

Algorithm 3. Fix any ordering of agents 1, . . . , n. We start by allocating to each agent, in the ordering 1, . . . , n, all remaining unassigned items that it considers as goods (or nothing if there are no such items left). The remaining items will be common chores. We give all of them to agent n, with the exception of the most important item for n, which we denote by c∗ . Now, the choice of which agent should receive c∗ depends on whether c∗ is the most important item for all agents. If it is the case, we give it to agent 1. Otherwise, i.e., if there is at least one agent for which there is more important item than c∗ , we give it to the last such agent in the ordering.

Example 5. We revisit the instance given in Example 4.

For this instance, the allocation returned by Algorithm 2 is not MMS. The outcome for agent 3 was {o-1 , o-5 }, to which agent 3 strictly prefers its MMS (MMS3 = {o-1 , o+4 , o+6 , o+8 }). Suppose the ordering is (1, 2, 3). Algorithm 3 starts by assigning {o+4 , o+6 , o+8 } and {o+7 } to agents 1 and 2, respectively. Then, agent 3 receives all common chores, except its most important item c∗ = o-1 . Lastly, since c∗ is the most important item for every agent, it is allocated to the first agent. The final allocation is underlined.

Let us prove the correctness of our algorithm.

Theorem 4. Given a lexicographic mixed instance with terrible chores, an MMS and PO allocation always exists and can be computed in polynomial time.

Proof (sketch). Since (N,M,G,▷) is an instance with terrible chores, by Proposition 1, maximin share of every agent consists of its most important chore and all goods. The first agent, agent 1, is the only one that can receive its most important chore in our algorithm. However, since apart from that it receives all of its goods, the output allocation is MMS.

For PO, consider two agents i < j ∈ [n]. Observe that j does not have any item that i considers as a good. Hence, the only Pareto improvement between these two agents is possible if i received c∗ (Pareto improvement can involve more than two agents, but we do not consider such in this sketch). Then, i can potentially offer c∗ to j, bundled with less important for i goods. However, if i was assigned c∗ , this means that c∗ is the most important item for j. Hence, j would not accept any exchange in result of which it gets c∗ .

Combining Theorem 4 with the existence and computation results when there are no terrible chores [Hosseini et al., 2023b], we obtain the following general conclusion.

Corollary 3. Given a lexicographic mixed instance, an MMS and PO allocation always exists and can be computed in polynomial time.

Corollary 3 ensures that an MMS and PO allocation always exists. From Corollary 1 we know however that if we strengthen MMS to EFX, then an EFX and PO allocation may not exist and deciding if such an allocation exists is computationally hard. A natural question is whether one can strengthen the efficiency to rank maximality. We show that deciding whether there exists an MMS and RM allocation is computationally hard, which stands in sharp contrast to the goods-only and chores-only settings.

Theorem 5. The problem of deciding whether there exists an MMS and RM allocation for a given lexicographic mixed instance is NP-complete.

The proof follows a reduction from SET COVER problem and shares some similarities with the proof of Theorem 1 (instance is objective and chores correspond to elements of the universe, agents to subsets, and assignment of goods to subsets chosen to the cover). However, there are important differences. For instance, more emphasis is put on the positions of items in the importance orderings. To this end, we introduce additional dummy goods and chores and two auxiliary agents that restrict the set of possible rank maximal allocations.

6 Concluding Remarks

By focusing on the restricted domain of lexicographic preferences, we identified instances with terrible chores for which EFX is hard to compute, thus, providing the first ever computational hardness result for EFX. Nonetheless, we identified a natural class of separable lexicographic preferences for which EFX and PO allocations are efficiently computable (and always exist). Moreover, we showed that MMS and PO allocations always exist and can be computed efficiently for any lexicographic mixed instance.

For EF1 and PO, the main remaining challenge is how to deal with (possibly subjective) mixed instances that contain fewer than n - 1 common terrible chores. Steps towards addressing this problem could potentially lead to novel techniques for more general preferences, including and beyond, the additive domain.

Acknowledgments

Hadi Hosseini acknowledges support from NSF grants #2144413 (CAREER), #2052488, and #2107173. We thank the anonymous reviewers for their helpful comments.