Dividing Conflicting Items Fairly

1 Introduction

How can we allocate a resource fairly? This problem was first formalized by the pioneering work of [Steinhaus, 1949] and has since been extensively studied in the fields of economics, mathematics, and computer science under the umbrella of fair division. Applications of fair division arise in many real-life situations, including the allocation of courses among students [Budish et al., 2017], the division of family inheritance among family members [Goldman and Procaccia, 2014], and the division of household chores between couples [Igarashi and Yokoyama, 2023].

A central notion of fairness in fair division is envy-freeness, which requires that every agent is allocated their most preferred bundle in the allocation. However, such a fairness guarantee is impossible to achieve when dealing with indivisible resources, such as courses, houses, or tasks. Consequently, recent literature on discrete fair division has focused on approximate fairness, exploring various concepts and algorithmic results [Amanatidis et al., 2023]. One particular influential relaxation of envy-freeness is, envy-freeness up to one good (EF1), introduced by [Budish, 2011], allowing agents to remove one good from others' bundle to eliminate envy. This concept has garnered significant attention over the past decade. It is known that for general classes of monotone valuations, an EF1 allocation exists and can be computed efficiently [Lipton et al., 2004].

Most studies on fair division assume that any allocation is feasible. While this assumption may hold in some cases, many practical scenarios involve constraints that restrict the structure of allocations. For instance, consider the allocation of multiple offices among several people over different periods of time. If the time intervals associated with two offices overlap, they cannot be assigned to the same person. Similar constraints arise in job scheduling, where overlapping shifts cannot be allocated to the same employee. Another example is the allocation of players to sports teams. If two players have overlapping areas of expertise, it is preferable not to assign them to the same team. A versatile framework for modeling such constraints, explored in a series of recent papers [Chiarelli et al., 2023; Hummel and Hetland, 2022; Kumar et al., 2024], represents conflicts among indivisible resources using a graph structure, where vertices correspond to resources and edges represent conflicts.

Conflicting constraints introduce new challenges, as standard fairness and efficiency concepts often become unattainable. Notably, canonical efficiency concepts such as completeness and Pareto-optimality are incompatible with EF1 under these constraints. In fact, with conflicting constraints, a complete allocation that assigns all goods may not always exist. Furthermore, even if such an allocation exists, there are simple instances where a complete EF1 allocation is unattainable [Hummel and Hetland, 2022].

[Kumar et al., 2024] studied chore allocation under conflicting constraints, observing that even on a path, EF1 is incompatible with Pareto-optimality for two agents with identical additive valuations. 1 To address this limitation, they introduced the notion of maximality. A maximal allocation ensures that no unassigned item can be feasibly allocated to some agent. Kumar et al. showed that for interval graphs-a common structure in job scheduling-a maximal EF1 allocation among two agents always exists and can be efficiently found for monotone valuations. However, the existence of a maximal EF1 allocation for more general graph families remains unresolved, offering a rich avenue for further research.

1 In [Kumar et al., 2024], Pareto-optimality is defined with respect to maximal allocations.

Our contributions. We study the allocation of indivisible goods under conflicting constraints. Our goal is to identify conditions under which a maximal EF1 allocation exists and can be efficiently computed. Our main contributions are:

1. Two-Agent-Case: We significantly extend the result of [Kumar et al., 2024] by establishing that a maximal EF1 allocation exists for any graph when the agents have monotone valuations. Further, we develop efficient algorithms for finding such allocations, including a polynomial-time algorithm for additive valuations and a pseudo-polynomial-time algorithm for monotone valuations. Note that the two-agent case is of particular importance in fair division, with various applications, including inheritance division, house-chore division, and divorce settlements [Brams and Fishburn, 2000; Brams et al., 2014; Igarashi and Yokoyama, 2023].
2. Three orMoreAgents: We establish a sharp dichotomy from the two-agent case in terms of both existence and computational complexity. First, we provide an example where a maximal EF1 allocation fails to exist, even for three agents with monotone valuations. While [Hummel and Hetland, 2022] previously identified a counterexample for four agents, no such example was known for three agents. We also prove the NP-hardnesss of determining the existence of a maximal EF1 allocation for a fixed number n ≥ 3 of agents with monotone valuations.
3. Chore Allocation: Finally, we consider the problem of chore allocation, where each agent has a monotone nonincreasing valuation. We show that the existence of a maximal EF1 allocation under identical valuations directly translates from the goods case, establishing that all our results for goods hold for chores as well.

Related work. There is a growing body of research on fair division under constraints. For a comprehensive survey on the topic, see [Suksompong, 2021]. Conflicting constraints in the context of fair division were introduced by [Chiarelli et al., 2023] and have been further explored by [Hummel and Hetland, 2022; Kumar et al., 2024; Biswas et al., 2023; Li et al., 2021]. [Chiarelli et al., 2023] explored different fairness objectives from ours, focusing on partial allocations that maximize the egalitarian social welfare-defined as the value of a bundle received by the worst-off agent. [Hummel and Hetland, 2022] studied complete allocations satisfying fairness criteria such as EF1 and MMS (maximin fair share). [Biswas et al., 2023] generalized the model of [Hummel and Hetland, 2022], taking into account capacity of resources. [Li et al., 2021] and [Kumar et al., 2024] considered an interval scheduling problem, with the goal of achieving fairness concepts such as EF1 and MMS. While [Li et al., 2021] focused on goods allocation with flexible intervals, [Kumar et al., 2024] examined chore allocation.

A related type of constraints to conflicting constraints is the connectivity constraints of a graph [Bouveret et al., 2017;

Bil `o et al., 2022], where each agent receives a connected bundle of a graph. Note that while connectivity constraints imposed by a sparse graph such as a tree allow fewer feasible allocations, in our setting, sparsity implies greater flexibility, as it increases the number of feasible allocations.

2 Preliminaries

For any natural number s ∈ N, let [s] = {1, 2, . . . , s}.

Problem instance. We use M = [m] to denote the set of goods and N = [n] to denote the set of agents. Let G = (M, E) denote an undirected graph, where each vertex corresponds to a good and each edge corresponds to a conflict. Each agent i has a valuation function vi : 2M → R+; here, R+ is the set of non-negative reals. We assume that vi(∅) = 0. The valuation of a single good g ∈ M, vi({g}), is denoted by vi(g). An instance of our problem is given by the tuple (N,M, V, G) where V = (v1, v2, . . . , vn) denotes a valuation profile. We use Ks,t to denote a complete bipartite graph with a bipartition in which one part contains s vertices and another part includes t vertices.

Valuation function. A valuation function vi is monotone non-decreasing if vi(S) ≤ vi(T) for every S ⊆ T ⊆ M. Unless specified otherwise, we refer to such a function simply as monotone. It is additive if vi(S) = ∑g∈S vi(g) holds for every S ⊆ M and i ∈ N. A valuation profile V is called identical if every agent i ∈ N has the same valuation function; in this case, we denote this function by v. Let T(m) denote the time to compute valuation vi(S) for a given S ⊆ M.

Allocation. An allocation is an ordered subpartition A = (A1, . . . ,An) of M where for every pair of distinct agents i, j ∈ N, Ai ∩ Aj = ∅, ∪i∈NAi ⊆ M, and for each i ∈ N, Ai is an independent set of G, namely, there is no pair of goods in Ai that are adjacent to each other. The subset Ai is called the bundle of agent i. An allocation is complete if all goods are allocated, i.e., ∪i∈NAi =M.

Fairness and efficiency notions. An allocation is envy-free (EF) if for every pair of agents i, j ∈ N, we have vi(Ai) ≥ vi(Aj) [Gamow and Stern, 1958; Foley, 1967]. It is envy-free up to one good (EF1) if for every pair of agents i, j ∈ N, either Aj = ∅, or there exists some good g ∈ Aj such that vi(Ai) ≥ vi(Aj \ {g}) [Budish, 2011; Lipton et al., 2004].

As discussed in the Introduction, observe that a complete allocation may not always exist (e.g., consider a complete graph K2 with one agent). Further, even when a complete allocation exists, a complete EF1 allocation may not exist: For instance, in a setting with n agents and a star where the center has a value of 0 and each of the n+ 1 leaves has a value of 1, an agent receiving the center cannot receive any other good, while at least one agent receives two or more leaves.

Besides completeness, another commonly used notion of efficiency in fair division is Pareto-optimality. Similar to the chore setting, one can show that EF1 is incompatible with Pareto-optimality for goods instances. As in [Kumar et al., 2024], we therefore consider a relaxed efficiency notion of maximality. An allocation A is maximal if for every agent i ∈ N and every unallocated good g ∈ M \ ⋃i∈N Ai, g is adjacent to some good in Ai. Our goal is to achieve an allocation that simultaneously satisfies maximality and EF1.

3 Two Agents

In this section, we consider the case of two agents.

3.1 Cut-and-Choose Protocol

When there are two agents, we can use a well-known strategy called cut-and-choose protocol [Brams and Taylor, 1996].

Theorem 1. Suppose that a maximal EF1 allocation always exists and can be computed in τ time for instances with two agents and identical valuations. Then, a maximal EF1 allocation always exists and can be computed in τ +2T (m) time for instances with two agents.

Proof. Let (A1, A2) a maximal EF1 allocation in a hypothetical scenario that valuations of both agents are v1. Then, agent 2 chooses a preferred bundle, leaving the reminder for 1. The resulting allocation is maximal and EF1.

Now, the question is whether a maximal EF1 allocation exists for identical valuations. In subsections 3.2-3.5, we assume that the valuations are identical and monotone, and valuations for both agents are represented by v(S) (S ⊆ M).

3.2 Proof Strategy of Kumar et al.

To describe our proof strategy, let us (informally) review Kumar et al.'s proof of the existence of maximal EF1 allocation when G is a path. At a high level, the idea of the proof is to construct a chain of maximal allocations A(0) , . . . ,A(m-1) , as illustrated in Figure 1, satisfying the following two properties: (i) adjacent allocations only "differ slightly" and (ii) (A(0) 1 ,A(0) 2 ) = (A(m-1) 2 , A(m-1) 1 ). The latter implies that the signs of v(A(0) 1 ) -v(A(0) 2 ) and v(A(m-1) 1 ) - v(A(m-1) 2 ) are different. Therefore, there exists an i that the signs of v(A(i) 1 )-v(A(i) 2 ) and v(A(i+1) 1 )-v(A(i+1) 2 ) are different. At this point, they show that at least one of A(i) or A(i+1) must be EF1, which shows the existence of a maximal EF1 allocation. This concludes the proof overview of [Kumar et al., 2024] for path graphs. They also extended this method to interval graphs, although the construction of the chain of maximal allocations becomes significantly more involved. Indeed, as explained and formalized below, our main contribution is to give a construction of a chain for any graph.

3.3 Useful Definitions and Lemmata

Our construction will require several generalizations of definitions and lemmata from [Kumar et al., 2024]. We believe that these tools can be useful beyond the context of our work. Firstly, we use the following definition of "adjacency". Compared to [Kumar et al., 2024], our definition (Definition 2) is more relaxed, in that it does not place any requirement on |A′1 \ A1| and |A2 \ A′2 | whereas Kumar et al.'s enforces that these are at most one. Such a relaxation is crucial since our "chain" constructed below violates the aforementioned Kumar et al.'s condition.

Definition 2. A pair (A,A′ ) of allocations is ordered adjacent if |A1 \ A′1 | ≤ 1 and |A′2 \ A2| ≤ 1.

The following is the key lemma that enables to find an EF1 allocation at the point when v(A1)-v(A2) crosses from positive to negative.

Lemma 3. Let (A,A′ ) be any ordered adjacent pair of allocations. Further, assume that the following conditions hold:

Then, at least one of A or A′ must be EF1.

Proof. Suppose that the allocation A is not EF1. Since v(A1) ≥ v(A2), agent a2 envies agent a1 even if one good is removed from A1. Since |A1 \ A′1 | ≤ 1, we must have v(A1 ∩ A′1 ) = v(A1 \ (A1 \ A′1 )) ≥ v(A2). As a result,

where the first and third inequalities hold because v is monotone. Now, consider the allocation A′ :

• Since |A′2 \ A2| ≤ 1, (1) implies that agent 1 does not envy agent 2 after removing a good from A′2 .
• Agent 2 does not envy agent 1 since v(A′1 ) ≤ v(A′2 ).

Therefore, this allocation is EF1.

We generalize Kumar et al.'s method by defining a gapless chain, and prove that any gapless chain must contain an EF1 allocation. We stress again that our requirements are weaker than the chain used in Kumar et al.'s 2 , but still suffices to ensure EF1 for identical valuations.

Definition 4. A sequence of allocation A(0) , . . . ,A(k) is a gapless chain if it satisfies the following conditions:

2 Namely, we use a weaker adjacency notion and we only require the sign flip (first two conditions) whereas Kumar et al. require that (A(0) 1 ,A(0) 2 ) = (A(k) 2 ,A(k) 1 ).

1. (A(i-1) ,A(i) ) is ordered adjacent for every i ∈ [k].

Lemma 5. If A(0) , . . . ,A(k) is a gapless chain, there exists an i ∈ {0, . . . , k} that A(i) is EF1.

Proof. From the first two conditions, there exists i ∈ [k] that v(A(i-1) 1 ) ≥ v(A(i-1) 2 ) and v(A(i) 1 ) ≤ v(A(i) 2 ). Lemma 3 then implies that at least one of A(i-1) or A(i) is EF1.

Given Lemma 5, our main task is thus to (efficiently) construct a gapless chain of maximal allocations (for any graph G). We devote the remainder of this section to this task.

3.4 Proof of Existence

Now, we prove that, a maximal EF1 allocation always exists for two agents, as stated below.

Theorem 6. For n = 2 agents, any graph G and any monotone valuation v, there exists a maximal EF1 allocation.

Although we only claim the existence in the above theorem, we will in fact present an algorithm for finding such an allocation, as its running time will be discussed in the next section. Our algorithm is presented in Algorithm 1 where the input S can be any maximal independent set of G. To prove Theorem 6, we use one that maximizes v(S). In Figure 2, we provide an example of a chain constructed by the algorithm.

Algorithm 1 CHAINEF1(S; G = (M, E), v)

Require: S = {s1, . . . , sk} is a maximal independent of G.

1: for t ∈M \ S do 2: Γt := {i ∈ [k] | {si, t} ∈ E} ▷ Non-empty since S is a maximal independent set 3: pt =mini∈Γt i 4: qt =maxi∈Γt i 5: X1 ← ∅ 6: for t ∈M \ S in increasing order of qt do 7: if t has no neighbor in X1 then 8: X1 ← X1 ∪ {t} 9: X2 ← ∅ 10: for t ∈M \ S in decreasing order of pt do 11: if t has no neighbor in X2 then 12: X2 ← X2 ∪ {t} 13: for i = 0, . . . , k do 14: A(i) 1 = {si+1, . . . , sk} ∪ {t ∈ X1 | qt ≤ i} 15: A(i) 2 = {s1, . . . , si} ∪ {t ∈ X2 | pt > i} 16: if A(i) = (A(i) 1 ,A(i) 2 ) is EF1 then 17: return A(i) 18: return NULL

We now prove a couple of crucial lemmata. Starting with the fact that each allocation is valid and maximal:

Lemma 7. For every i ∈ {0, . . . , k}, A(i) is a valid maximal allocation.

Proof. First, we prove that the allocation is valid:

• No good is assigned to both agents. This is obvious for goods in S. For good t ∈ M \ S, since qt ≥ pt, at most one of the conditions qt ≤ i or pt > i can hold; thus, it is assigned to at most one agent.
• No adjacent goods are assigned to the same agent. Consider two goods g, g′ (g ̸= g′ ) that are assigned to agent 1 and consider the following cases:
• Both goods are in S. They are not adjacent because S is an independent set.
• Both goods are in M \ S. They are not adjacent because g, g′ ∈ X1 and X1 is an independent set.
• One good is from S and the other is from M \ S. Assume w.l.o.g. that g ∈ S and g′ ∈ M \ S. From this, we must have g ∈ {si+1, . . . , sk} and that qg′ ≤ i. By the definition of qg′ , this ensures that g, g′ are not adjacent.

Next, we prove maximality of A(i) , i.e., that no good in M \ (A(i) 1 ∪ A(i) 2 ) can be assigned to one of the agents. Let g ∈ M \ (A(i) 1 ∪ A(i) 2 ) be any unassigned good. Consider three following cases:

1. qg ≤ i. Since g is adjacent to sqg ∈ A(i) 2 , g cannot be assigned to agent 2. Moreover, since g /∈ A(i) 1 , it must be that g /∈ X1. From how X1 is constructed, there exists t ∈ X1 such that qt ≤ qg and t is adjacent to g. As t ∈ A(i) 1 , g cannot be assigned to agent 1.
2. pg > i. This case follows from an analogous argument to the first case.
3. pg ≤ i < qg. In this case, g is adjacent to spg ∈ A(i) 2 and sqg ∈ A(i) 1 . Thus, tj cannot be assigned.

Next, we show that A(0) , . . . ,A(k) is a gapless chain. However, this requires an additional requirement that v(S) is no smaller than v(X1), v(X2).

Lemma 8. If v(S) ≥ v(X1) and v(S) ≥ v(X2), then A(0) , . . . ,A(k) is a gapless chain.

Proof. Note that A(0) = (S,X2) and A(k) = (X1, S). Thus, the first two conditions are satisfied by our assumption v(S) ≥ v(X1), v(S) ≥ v(X2). Finally, for every i ∈ [k], we can see that A(i-1) 1 \ A(i) 1 = {si} and A(i) 2 \ A(i-1) 2 = {si}. Thus, (A(i-1) ,A(i) ) is ordered adjacent.

Lemmas 5, 7 and 8 together immediately imply the following:

Lemma 9. If v(S) ≥ v(X1) and v(S) ≥ v(X2), then Algorithm 1 outputs a maximal EF1 allocation.

Our main theorem of this section (Theorem 6) now then follows easily from Lemma 9 by choosing an appropriate S.

Proof of Theorem 6. Let S be a maximal independent set of G that maximizes v(S). Since X1,X2 are independent set and v is monotone, we have v(S) ≥ v(X1) and v(S) ≥ v(X2). Thus, Lemma 9 ensures that running Algorithm 1 on input S yields a maximal EF1 allocation.

3.5 Algorithm

Recall in the proof of Theorem 6 that we pick S to be a maximal independent set with largest valuation. Doing so trivially would require enumerating through all 2m subsets of M. In this section, we give a simple algorithm (Algorithm 2) that significantly improves upon this running time. In particular, it runs in polynomial-time for additive valuations and pseudopolynomial time for general monotone valuations.

Algorithm 2 SWAPEF1(G = (M, E), v)

• 1: g∗ ← argmaxg∈M v(g) 2: Si ← any maximal independent set of G containing g∗ 3: i ← 0 4: while True do 5: if CHAINEF1(Si ; G, v) ̸= NULL then 6: return CHAINEF1(S0 ; G, v) 7: Xi1 ,Xi2 ←X1,X2 in CHAINEF1(Si ;G, v) 8: ℓ ← argmaxℓ′∈{1,2} v(Xi ℓ′ ) 9: Si+1 ←any maximal independent set containing Xi ℓ 10: i ← i + 1

Our algorithm running time is stated below in Theorem 10. Note that in the second case, if the valuations v(S) are all integers, the running time is pseudo-polynomial.

Theorem 10. When there are n = 2 agents, there exists an algorithm that can find a maximal EF1 allocation and its running time is as follows:

• O(3m/3 · (m · T(m) + |E|)) for monotone valuations,
• O(B · (m · T (m) + |E|)) for monotone valuations such that the number of distinct values of v(S) is at most B (i.e. |{v(S) | S ⊆M}| ≤ B), and,
• O(m log m · (m · T (m) + |E|)) for additive valuations.

Proof. Observe that the preprocessing time and the running time of each loop is O(m · T(m) + |E|). Thus, it suffices to bound the number of iterations of the loop in each case.

• For monotone valuations, by Lemma 9, each loop either terminates or we must have v(Xi ℓ ) > v(Si ). This implies v(Si+1 ) > v(Si ). This means that S0 , S1 , . . . are all distinct maximal independent sets of G. Since there are at most 3m/3 maximal independent sets [Moon and Moser, 1965], the number of iterations is at most 3m/3 .
• Next, suppose that v(S) can take at most B distinct values. From the argument above, v(S0 ), v(S1 ), . . . are distinct. Thus, the number of iterations is at most B.
• Finally, suppose that v is additive. We claim that the following holds for each loop i that does not terminate:

Before we prove (2), let us first use it to bound the number of iterations. Notice that (2) implies that, after loop i, we must have v(Si+1 ) > ( m m-1 )i+1 · v(S0 ) ≥ ( m m-1 )i+1 · v(g∗ ). Moreover, our choice of g∗ ensures that v(Si+1 ) ≤ m·v(g∗ ). Thus, the number of iterations is at most logm/(m-1) m + 1 = O(m log m).

To see that (2) holds, first recall from Algorithm 1 that, if Algorithm 1 returns NULL, it has considered either (Si , Xi ℓ ) or (Xi ℓ , Si ) already and has determined that this is not EF1. Since v(Xi ℓ ) > v(Si ), this means that, for any good g ∈ Xi ℓ , we must have v(S) < v(Xi ℓ \{g}). When we pick g ∈ Xi ℓ with the largest v(g), we have

4 Three or More Agents

Negative Examples. While a maximal EF1 allocation always exists when there are two agents, it turns out that this is not the case for three agents or more.

Theorem 11. For n = 3 agents, there exists an instance with identical monotone valuations where no maximal EF1 allocation exists.

Proof Sketch. Consider the following instance with 7 goods. The graph consists of a complete bipartite graph K3,3 with bipartition X = {1, 2, 3} and Y = {4, 5, 6} together with two edges {1, 7} and {4, 7}. Each of the three agents has an identical monotone valuation v such that

• v(∅) = 0;
• v(S) = 1 if |S| = 1 and S ∈ {{1}, {4}};
• v(S) = 2 if |S| = 1 and S ̸∈ {{1}, {4}};
• v(S) = 3 if S is {2, 7}, {3, 7}, {5, 7}, or {6, 7};
• v(S) = 4 for any other S ⊆M.

Note that the symmetry on the graph and valuation holds: swapping 2 and 3, swapping 5, 6, and swapping {1, 2, 3} and {4, 5, 6} all lead to the same instance, and swapping the bundles of agents does not change whether the allocation is EF1. For this reason, there are only 6 maximal allocations to consider (refer to Figure 3). All of them are not EF1, because:

• Allocations #1, #4, #5, #6: one agent takes one good but but there is another agent who takes three goods.

• Allocation #2: v({5, 7}) = 3 but v({1, 2}), v({1, 3}), v({2, 3}) = 4.
• Allocation #3: v(4) = 1 but v(5) = v(7) = 2.

The instance constructed in the proof of Theorem 11 uses an identical monotone valuation. It remains an open question for three agents with (even identical) additive valuations.

For n ≥ 4 of agents, [Hummel and Hetland, 2022] presented an instance with identical additive valuations and a complete bipartite graph Kn-1,n-1 for which no complete EF1 allocation exists. In Kn-1,n-1, any maximal allocation is complete. Thus, this counterexample implies that achieving both EF1 and maximality is impossible for four agents with identical additive valuations. Here, we provide a smaller example using K3,n-1, which turns out to be smallest since for m ≤ n+1, there always exists a maximal EF1 allocation.

Proposition 12. For every number n ≥ 4 of agents, there is an instance with identical additive valuations, m = n + 2, and G = K3,n-1 where no maximal EF1 allocation exists.

Proposition 13. For n agents with monotone valuations and m ≤ n + 1 goods, there exists a maximal EF1 allocation.

NP-Hardness. Next, we show that it is NP-hard to decide whether a maximal EF1 allocation exists, as stated below.

Theorem 14. Given the graph and valuations, determining whether a maximal EF1 allocation exists is NP-hard for:

1. any fixed n ≥ 4, even for identical and additive valuation, and,
2. n = 3, even for identical and monotone valuation.

In fact, our proof can transform any negative example into an NP-hardness result, as stated more precisely below.

Lemma 15. Suppose that there exists an instance ˜ I = ([n], ˜M, ˜ v, ˜G = ( ˜M, ˜E)) (with identical valuation) where the number n of agents and the number | ˜M| of items are both constants, such that no maximal EF1 allocation exists. Then, it is NP-hard to decide whether a maximal EF1 allocation exists for n agents with identical valuations. Furthermore, if ˜ v is additive, then this applies even for additive valuations.

Theorem 14 is an immediate corollary of Lemma 15 where ˜ I is the instance from Proposition 12 or Theorem 11. Note that we state Lemma 15 in this generic form so that, if subsequent work finds such an instance ˜ I for additive valuation for n = 3, then the NP-hardness would follow as a corollary.

Reduction. We will reduce from the Independent Set (IS) problem, which is NP-hard [Karp, 1972]. In IS, we are given a graph H = (VH, EH) and a positive integer t, and the goal is to decide whether H contains an IS of size t.

At a high-level, our reduction starts from ˜ I and adds to it n copies of the graph H, where each good has the same value λ. Roughly speaking, we wish the i-th copy of H (denoted by Xi in the proof below) to give "extra goods" to the i-th agent, in case that agent envies some other agent by more than one good. The crux of the reduction is that such an agent can "catch up" (and thus satisfy EF1) iff there is a sufficiently large independent set in H. This is not yet a complete reduction since, H may not have a maximal independent set of a certain prescribed size. To alleviate this, we introduce "dummy goods" with zero value (denoted by Yi below) to ensure that we can pick any desired number of goods from each copy of H. Finally, some additional edges are also added to ensure that each agent selects goods from a single copy of H.

For the proof below, we will use the following notation: for any valuation v and set S of goods, let v-1 (S) := minj∈S v(S \ {j}) denote the value of S after its most valuable good is removed. We use the convention v-1 (∅) = 0.

Proof of Lemma 15. Recall ˜ I from the lemma statement. Let 3γ := min ˜ A maxi,i′∈[n] (˜ v-1 ( ˜ Ai) - ˜ v( ˜ Ai′)) where the outer minimum is over all maximal allocation ˜ A of ˜ I. By the assumption on ˜ I, we have γ > 0. Let λ := γ/t.

Let (H = (VH, EH), t) denote the IS instance. Our reduction constructs the instance I = ([n],M, v, G) as follows:

• Goods: M = ˜M ∪ X1 · · · ∪ Xn ∪ Y1 ∪ · · · ∪ Yn where Xi = {xi,w | w ∈ VH} and Yi = {yi,w | w ∈ VH} are sets (each of size |VH|) of additional goods.
• Graph: G contains the following edges:
• (i) All edges in ˜G,
• (ii) (xi,u, xi,w) for all i ∈ [n] and (u,w) ∈ VH,
• (iii) (xi,w, yi,w) for all i ∈ [n] and w ∈ VH,
• (iv) all pairs of vertices in (Xi ∪ Yi) × (Xi′ ∪ Yi′) for all distinct i, i′ ∈ [n].
• Valuation: For all S ⊆ M, let v(S) = ˜ v(S∩ ˜M)+λ|S∩ X| where X := X1 ∪ · · · ∪Xn. That is, the valuations on original goods remain the same, each good in X has value λ, and the goods in Y1 ∪ · · · ∪ Yn have value zero.

See Figure 4 for an illustration of the instance I.

It is clear that the reduction runs in polynomial time, and that, if ˜ v is additive, then v is also additive.

3 γ can be computed in O(1) time by bruteforce.

(YES) Suppose that H contains an IS of size t. Let ˜ A∗ be a maximal allocation of ˜ I such that maxi,i′∈[n] (˜ v-1 ( ˜ A∗i ) - ˜ v( ˜ A∗i′)) = γ. Assume w.l.o.g. that v-1 ( ˜ A∗1 ) ≥ v-1 ( ˜ A∗2 ), . . . , v-1 ( ˜ A∗n ). For each i ∈ [n], we construct A∗i as follows:

1. Let ci := ⌈max{0, ˜ v-1 ( ˜ A∗1 ) - ˜ v( ˜ A∗i )}/λ⌉ ≤ t.
2. Let Si be any (non-necessarily maximal) IS of size ci in H, which exists since H contains an IS of size t.

Observe that each good in Xi ∪ Yi can only belong to A∗i , and there is no edge between goods in A∗i . Thus, A∗ = (A∗1 , . . . ,A∗n ) is a valid allocation. To see that this is maximal, note that the goods from Yi (resp., Xi) together with type-(iii) edges ensure that no other goods in Xi (resp., Yi) can be added to A∗i . Since at least one good fromXi ∪ Yi is picked, type-(iv) edges ensure that no goods in Xi′ ∪ Yi′ for i′ ̸= i can be added to A∗i .

Finally, we argue that A∗ is EF1. To bound v-1 (A∗i ), note that v(A∗i ) = ˜ v( ˜ A∗i ) + ciλ. Consider two cases based on ci.

• If ci = 0, we have v-1 (A∗i ) = ˜ v-1 ( ˜ A∗i ) ≤ ˜ v-1 ( ˜ A∗1 ).
• If ci > 0, by definition of ci, we have v(A∗i ) < ˜ v-1 ( ˜ A∗1 )+λ. Thus, v-1 (A∗i ) ≤ v(A∗i )-λ < ˜ v-1 ( ˜ A∗1 ).

Thus, in both cases, we have v-1 (A∗i ) ≤ ˜ v-1 ( ˜ A∗1 ).

On the other hand, for any i′ ∈ [n], the definition of ci′ immediately implies v(A∗i′ ) ≥ ˜ v-1 ( ˜ A∗1 ).

By the two previous paragraphs, A∗ is EF1.

(NO) Suppose that H does not contain an IS of size t. Consider any maximal allocation A = (A1, . . . ,An) of I. Notice that the allocation ˜ A = (A1 ∩ ˜M, . . . ,An ∩ ˜M) is maximal w.r.t. ˜ I. Thus, there exist i, i′ ∈ [n] such that ˜ v-1 ( ˜ Ai) - ˜ v( ˜ Ai′) ≥ γ. Due to type-(iv) edges, at most one of Ai′ ∩X1, . . . ,Ai′ ∩Xn can be non-empty. Furthermore, type-(ii) edges imply that the non-empty set must correspond to an independent set in H. From our assumption, this implies |Ai′ ∩X| < t. As a result,

where (⋆) is due to our choice of λ. Thus, ˜ A is not EF1.

5 Chore Allocation

In this section, we consider the chore version of our problem, where each agent i has a monotone non-increasing valuation function vi. An allocation A = (A1, . . . ,An) is envy-free up to one chore (EF1 for chores) if for every pair of agents i, j ∈ N, either Ai = ∅, or vi(Ai \ {c}) ≥ vi(Aj) some c ∈ Ai [Aziz et al., 2022; Bhaskar et al., 2021]. For identical valuations, the existence of a maximal EF1 allocation is equivalent for goods and chores: An allocation A is EF1 for chores under valuation v iff A is EF1 for goods under -v.

.

Consider the case of two agents with monotone nonincreasing valuations. Theorem 1 holds in this case, so we can assume w.l.o.g. that the agents have identical valuations v. By combining the discussion above with the fact that -v is monotone non-decreasing, Theorem 6 guarantees the existence of a maximal EF1 allocation. Moreover, the algorithms presented in Theorem 10 remain applicable in this setting.

For three or more agents with monotone non-increasing valuations, there exist instances where a maximal allocation does not exist. In fact, the instances given in Theorem 12 and Proposition 11 use an identical valuation v, and the corresponding instance obtained by replacing v with -v yields no maximal allocation that is EF1 for chores. Also, determining whether a maximal EF1 allocation exists is NP-hard also for monotone non-increasing valuations. This follows from Theorem 14 since the constructed instance uses an identical monotone non-decreasing valuation.

6 Conclusion

While we give a nearly complete picture of the existence for maximal EF1 allocations, there are still a few open questions left. First, for n = 2, our algorithm (Theorem 10) runs in pseudo-polynomial time for general monotone valuations. Is there a polynomial-time (in m, T (m)) algorithm for this task?

It might also be worthwhile considering special cases, by restricting either the valuations or the graphs. Examples are:

• Additive valuations: The existence of maximal EF1 allocation remains open only for the case n = 3 since our lower bound in Theorem 11 requires non-additive valuations, but the lower bound for n ≥ 4 (Proposition 12) holds for additive (and identical) valuations.
• Uniform valuations: All n ≥ 3 remains open in this case as we are not aware of any lower bound that holds for uniform valuations (namely, all goods are equally valued 1). We also note that the well-known Hajnal-Szemer´edi theorem ([Hajnal and Szemer´edi, 1970]) is equivalent to stating that a maximal EF1 allocation exists when the graph has maximum degree at most n - 1. Thus, a positive answer to the question for arbitrary graphs will significantly generalize the theorem.

Acknowledgements

This work was partially supported by JST FOREST Grant Numbers JPMJPR20C1. We thank the anonymous IJCAI 2025 for their valuable comments.