A Complete Landscape of EFX Allocations on Graphs: Goods, Chores and Mixed Manna

1 Introduction

Fair allocation of indivisible items has been broadly studied in the research fields of computer science, economics, and mathematics in the past few decades. One of the most compelling and natural fairness notions is envy-freeness (EF), which requires that every agent prefers her own bundle to any other agent's bundle. Though envy-freeness can always be satisfied for divisible items [Aziz and Mackenzie, 2016; Dehghani et al., 2018], it is too demanding for indivisible items. An EF allocation does not exist even for the simple instance where there are two agents and one indivisible item with non-zero marginal values to both agents.

The fact that envy-freeness is hard to satisfy necessitates the study of its relaxations, the most popular one among which is envy-freeness up to any item (EFX). EFX requires that any envy could be eliminated by virtually removing any item that the envious agent likes from the envied agent's bundle or any item that the envious agent dislikes from her own bundle. As remarked by [Caragiannis et al., 2019]: "Arguably, EFX is the best fairness analog of envy-freeness for indivisible items." Despite significant effort in the literature, the existence of EFX allocations still remains an open problem for indivisible items. Only a few special cases are known to admit EFX allocations [Plaut and Roughgarden, 2020; Chaudhury et al., 2020; Amanatidis et al., 2021; Hosseini et al., 2021; Li et al., 2022].

Recently, [Christodoulou et al., 2023] studied EFX allocations on graphs where vertices correspond to agents and edges correspond to indivisible goods. An agent (vertex) is only interested in the goods (edges) that are incident to her and all other edges have zero marginal values to her. Thus, each good is liked by exactly two agents in their setting. As motivated in [Christodoulou et al., 2023], a direct application of this setting is the allocation of geographical resources, for instance, natural resources among countries on the boundaries, working offices among research groups, and public areas among communities in a region, etc. [Christodoulou et al., 2023] proved that EFX allocations always exist and can be computed in polynomial time for arbitrary graphs. Remarkably, this is one more rare case with more than three agents for which an EFX allocation is guaranteed to exist. They also considered a more restricted scenario where each edge must be allocated to one of its endpoint agents. In this scenario, an allocation is also called an orientation. Unfortunately, [Christodoulou et al., 2023] proved that an EFX orientation may not exist, and determining whether it exists or not is NP-complete.

Besides goods, recent years have seen a rapidly growing interest in the case of mixed manna in the literature of fair division [Aziz et al., 2022; Aleksandrov and Walsh, 2019; Liu et al., 2023]. A mixed manna contains items that are goods for some agents but chores for others. Practically, the setting of mixed manna can model the scenarios where agents have different opinions on items. Many real-world scenarios involve the allocation of mixed manna. For example, when the items are paid jobs, they are goods for some people because completing them can bring extra revenue; however, they can be chores for some people who do not care much about this amount of money and would like to save time for other matters. The case of mixed manna is also a typical setting where the valuations are not monotone. [Christodoulou et al., 2023]'s graphic nature also appears in the setting of mixed manna. For example, in sports games, each match (that can be viewed as an item) involves two teams (that can be viewed as the agents) and has to be hosted by one of them (i.e., home or away). Hosting a match might be a good for some teams as they can make profit and might be a chore as they cannot cover the expenses. Furthermore, the graph orientation setting can use the topology to indicate who are capable of completing what jobs (edges), so that the jobs can only be allocated to people (incident vertices) who are able to do them. The allocation setting can model the case when people really do not have any cost or benefit on the items they are not incident to.

1.1 Our Problem and Results

In this work, we extend the model of [Christodoulou et al., 2023] to the case of mixed manna, where an edge may be liked or disliked by its endpoint agents. We consider the four variants of EFX for mixed manna in the literature, i.e., EFX00 , EFX0-, EFX+0 , and EFX+-, where the super and sub scripts indicate the items removed from the envied agent's and the envious agent's bundles respectively, +/- means an item with a strictly positive or negative margin and 0 means an item with a possibly zero margin.

Similar as [Christodoulou et al., 2023], we first study the setting where each edge must be allocated to one of its endpoint agents, i.e., orientations. The main results are summarized in the second column of Table 1. Specifically, we show that an orientation that satisfies any of the four EFX notions may not exist, and determining its existence is NP-complete. Due to the hardness results for orientations, we also study some simple graphs such as trees, stars and paths, for which the existence of orientations that satisfy the four notions can be determined in polynomial time.

We then study the setting where the edges can be allocated to any agent. The main results are summarized in the third column of Table 1. Specifically, we show that an EFX00 allocation may not exist and determining its existence is NPcomplete. In contrast, an allocation that satisfies any of the other three notions always exists and can be computed in polynomial time.

1.2 More RelatedWorks

There are many other works that study fair allocation of indivisible items on graphs, whose settings whereas, are quite different from ours and [Christodoulou et al., 2023]'s. [Bouveret et al., 2017] formalized the problem that there is an underlying graph whose vertices are indivisible items and each agent must receive a connected component of the graph. They considered several fairness notions such as proportionality, envy-freeness, maximin share, and gave hardness results for general graphs and polynomial-time algorithms for special graphs. Many following works investigated the same problem with different fairness notions or graph structures [Bil`o et al., 2022; Suksompong, 2019; Igarashi and Peters, 2019]. [Bei et al., 2022] considered the same model and quantified the loss of fairness when imposing the connectivity constraint, i.e., price of connectivity. [Madathil, 2023] studied a similar model where each agent must receive a compact bundle of items that are "closely related". Different from this line of works, [Hummel and Hetland, 2022] used a graph to reflect conflicts between items. Each vertex on the graph is an item and each edge means that its two endpoint items have a conflict. They require that two items that have a conflict cannot be allocated to the same agent. In other words, the bundle allocated to each agent must be an independent set of the graph. [Payan et al., 2023] studied fair allocation on graph where vertices are agents (as in our setting). The graph was used to relax fairness notions such that fairness only need to be satisfied for the endpoint agents of the edges.

2 Preliminaries

For any positive integer k, let [k] = {1, . . . , k}. In an instance of our problem, there is a graph G = (N,M) where N = {a1, . . . , an} is the vertex set and M is the edge set. Each vertex corresponds to an agent and each edge corresponds to an indivisible item. We use vertex and agent, edge and item, interchangeably. We also write both (ai, aj) and ei,j to represent the edge between ai and aj. Each agent ai ∈ N has a valuation vi : 2M → R over the edges and vi(∅) = 0. We also write vi(e) to represent vi({e}).

For an agent ai, each item e ∈ M is classified as a good (if it has strictly positive marginal values to ai, i.e., vi(S ∪ {e}) > vi(S) for any S ⊆ M \ {e}), a chore (if it has strictly negative marginal values to ai, i.e., vi(S ∪ {e}) < vi(S) for any S ⊆ M \ {e}), or a dummy (if it has zero marginal value to ai, i.e., vi(S ∪ {e}) = vi(S) for any S ⊆ M \ {e}). Accordingly, an instance is called a goods instance (if no item is a chore for any agent), a chores instance (if no item is a good for any agent), or a mixed instance (if an item may be a good, a chore, or a dummy for any agent). Let Ei be the set of all edges that are incident to ai, E≥0 i ⊆ Ei be the subset of non-chores for ai, and E>0 i ⊆ Ei be the subset of goods for ai. Note that in our setting, all edges that are not incident to ai (i.e., M \ Ei) are dummies for ai.

An allocation X = (X1, . . . ,Xn) is an n-partition of M such that Xi contains the edges allocated to agent ai ∈ N, where Xi ∩Xj = ∅ for any ai, aj ∈ N and ⋃ai∈N Xi = M. An orientation is a restricted allocation where each edge must be allocated to one of its endpoint agents. An allocation X is partial if ⋃ai∈N Xi ⊊ M.

2.1 Fairness Notions

Given an allocation X, we say agent ai envies agent aj if vi(Xj) > vi(Xi). The allocation is envy-free (EF) if no agent envies the others, i.e., for every two agents ai, aj ∈ N, vi(Xi) ≥ vi(Xj). As we have seen, envy-freeness is too demanding for indivisible items. Thus, in this paper, we focus on its relaxation envy-free up to any item (EFX).

For the case of mixed manna, there are four variants of EFX in the literature [Aziz et al., 2022; Aleksandrov and Walsh, 2020; B´erczi et al., 2020], namely, EFX00 , EFX0-, EFX+0 , and EFX+-. EFX00 requires that any envy could be eliminated by removing any item that is not a chore for the envious agent from the envied agent's bundle or any item that is not a good from the envious agent's own bundle. Formally,

Definition 1 (EFX00 ). An allocation X = (X1, . . . ,Xn) is EFX00 if for every two agents ai, aj ∈ N such that ai envies aj, both of the following conditions hold:

EFX0- differs from EFX00 in that the item removed from the envious agent's bundle cannot be a dummy. More concretely, the item e considered in the second condition is subject to vi(Xi \ {e}) > vi(Xi). EFX+0 differs from EFX00 in that the item removed from the envied agent's bundle cannot be a dummy, i.e., the item e considered in the first condition is subject to vi(Xj \ {e}) < vi(Xj). EFX+- differs from EFX00 in that the item removed from the envied agent's and the envious agent's bundles cannot be a dummy. The formal definitions of EFX0-, EFX+0 and EFX+- can be seen in the full version.

Obviously, any EFX00 allocation is also EFX0- or EFX+0 , and any EFX0- or EFX+0 allocation is also EFX+-.

Goods and Chores Instances. Goods instances have been well studied in [Christodoulou et al., 2023], and we will see that our results provide alternative approaches. For chores instances, we provide a discussion in the full version of this paper. In the subsequent sections, we shall focus on the general case of mixed manna.

3 EFXOrientations

In this section, we elaborate on EFX orientations. Firstly, we have the following proposition, whose proof can be seen in the full version of this paper.

Proposition 1. There exist graphs for which no orientation satisfies any of the four notions of EFX.

Due to this negative result, we turn to studying the complexity of determining the existence of EFX orientations. The result by [Christodoulou et al., 2023] (see Theorem 2 in their paper) directly implies that determining the existence of EFX0- orientations is NP-complete. In the graphs constructed in their reduction, each edge is a good for both its endpoint agents. For such graphs, any EFX0- orientation is also EFX00 . Therefore, we have the following corollary.

Corollary 1. Determining whether an EFX00 or EFX0- orientation exists or not is NP-complete.

In the following, we prove the below theorem for EFX+-.

Theorem 1. Determining whether an EFX+- orientation exists or not is NP-complete, even for additive valuations 1 .

To prove Theorem 1, we reduce from (3,B2)-SAT problem to the EFX+- orientation problem. A (3,B2)-SAT instance contains a Boolean formula in conjunctive normal form consisting of n variables {xi}i∈[n] and m clauses {Cj}j∈[m]. Each variable appears exactly twice as a positive literal and exactly twice as a negative literal in the formula, and each clause contains three distinct literals. Determining whether a (3,B2)-SAT instance is satisfiable or not is NPcomplete [Berman et al., 2007].

Our reduction uses a gadget to ensure that a specific agent must receive a chore if the orientation is EFX+-. One such gadget is shown in Figure 1. In this example, agent ai must receive (ai, a∆1 ) if the orientation is EFX+-. Otherwise, one of the other three agents must receive at least two chores and envy ai even after removing one chore.

Given a (3,B2)-SAT instance ({xi}i∈[n], {Cj}j∈[m]), we construct a graph as follows:

• For each variable xi, create two vertices aTi , aFi and one edge (aTi , aFi ) with a value of 2 to both aTi and aFi .
• For each clause Cj, create one vertex aCj . Besides, if Cj contains a positive literal xi, create one edge (aCj , aTi ) with a value of 1 to both aCj and aTi . If Cj contains a negative literal ¬xi, create one edge (aCj , aFi ) with a value of 1 to both aCj and aFi .
• Create three vertices a∆1 , a∆2 , a∆3 and three edges (a∆1 , a∆2 ), (a∆2 , a∆3 ), (a∆1 , a∆3 ). Besides, for each i ∈ [n], create two edges (aTi , a∆1 ) and (aFi , a∆1 ). For each j ∈ [m], create one edge (aCj , a∆1 ). Each of these edges has a value of -1 to both its endpoint agents.
• Each vertex has an additive valuation.

To visualize the above reduction, we show the graph constructed from the formula (x1 ∨ x2 ∨ x3) ∧ (x1 ∨ x2 ∨ ¬x3) ∧ (¬x1 ∨ ¬x2 ∨ ¬x3) ∧ (¬x1 ∨ ¬x2 ∨ x3) in Figure 2.

We now prove that a (3,B2)-SAT instance is satisfiable if and only if the constructed graph has an EFX+- orientation.

1 Valuation vi is additive if vi(S) = ∑e∈S vi(e) for any S ⊆ M.

Proof of Theorem 1. For ease of presentation, for each variable xi, we denote by Cj i,T,1,Cj i,T,2 the two clauses that contain the positive literal xi and by Cj i,F,1,Cj i,F,2 the two clauses that contain the negative literal ¬xi.

For one direction, we assume that the (3,B2)-SAT instance has a satisfying assignment and use the assignment to create an EFX+- orientation as follows:

• Allocate (a∆1 , a∆2 ) to a∆1 , (a∆2 , a∆3 ) to a∆2 , and (a∆3 , a∆1 ) to a∆3 . Allocate each other edge that is incident to a∆1 to the endpoint that is not a∆1 .
• For each variable xi that is set to True, allocate (aTi , aFi ) to aTi , (aTi , aCj i,T,1) to aCj i,T,1, (aTi , aCj i,T,2) to aCj i,T,2, and (aFi , aCj i,F,1), (aFi , aCj i,F,2) to aFi .
• For each variable xi that is set to False, allocate (aTi , aFi ) to aFi , (aFi , aCj i,F,1) to aCj i,F,1, (aFi , aCj i,F,2) to aCj i,F,2, and (aTi , aCj i,T,1), (aTi , aCj i,T,2) to aTi .

Next, we show that the above orientation is EFX+-. For agents

a∆1 , a∆2 , a∆3 , each of them receives one edge with a value of -1 and all edges received by other agents have non-positive values to them. After removing the edge from their bundles, they do not envy others. For each variable xi that is set to True, agent aTi does not envy others since she receives a total value of 1 and each of her incident edges that she does not receive has a value of 1. Agent aFi receives three edges with values of 1, 1,-1, respectively. The only incident edge that she does not receive is (aTi , aFi ), which is allocated to aTi and has a value of 2. After removing the edge with a value of -1 from her own bundle or (aTi , aFi ) from aTi 's bundle, aFi

does not envy aTi . We have an analogous argument for each variable that is set to False. It remains to consider the agents that correspond to clauses. Since the assignment is satisfying, each clause contains at least one literal that is evaluated to True. This implies that each agent aCj receives at least one edge with a value of 1. For example, if the clause Cj contains a positive literal xi that is evaluated to True, aCj receives the edge (aTi , aCj ). Since each of aCj 's incident edges that she does not receive has a value of 1, aCj does not envy other agents after removing the edge with a value of -1 from her own bundle or the edge with a value of 1 from other agents' bundles.

For the other direction, we assume that the constructed graph has an EFX+- orientation and use the orientation to create a satisfying assignment as follows: for each variable xi, if the edge (aTi , aFi ) is allocated to agent aTi , then set xi to True; otherwise, set xi to False. Next, we show that the assignment is satisfying. First, since the orientation is EFX+-, each agent that corresponds to a variable or a clause must receive the edge between herself and a∆1 that has a value of -1. For each variable xi, if the edge (aTi , aFi ) is allocated to agent aTi , both (aFi , aCj i,F,1) and (aFi , aCj i,F,2) must be allocated to agent aFi . Otherwise, aFi will envy aTi even after removing (aFi , a∆1 ) from her own bundle. For a similar reason, if the edge (aTi , aFi ) is allocated to aFi , both (aTi , aCj i,T,1) and (aTi , aCj i,T,2) must be allocated to aTi . For each clause Cj , agent aCj must receive at least one edge with a value of 1. Otherwise, aCj will envy the agents who receive her incident edges that have a value of 1 even after removing the edge with a value of -1 from her own bundle. This implies that each clause has a literal that is evaluated to True.

Notice that in the graphs constructed in the above reduction, each edge has non-zero values to both its endpoint agents. For such graphs, an orientation is EFX+0 if and only if it is EFX+-, since no agent receives an edge with a value of zero. Therefore, the hardness of determining the existence of EFX+- orientations also applies to EFX+0 orientations.

Corollary 2. Determining whether an EFX+0 orientation exists or not is NP-complete, even for additive valuations.

SimpleGraphs. To bypass the hardness results in Corollaries 1, 2 and Theorem 1 for general graphs, in the full version of this paper, we also study EFX orientations on some simple graphs such as trees, stars and paths. For these simple graphs, though orientations that satisfy the four notions may not exist, their existence can be determined in polynomial time.

4 EFXAllocations

In this section, we elaborate on EFX allocations.

4.1 EFX00 Allocations

We start with the strongest one among those four notions, i.e., EFX00 . We say an edge e is priceless to an agent ai if for any S1, S2 ⊆ M such that e /∈ S1 and e ∈ S2, we have vi(S1) < vi(S2). We first have the following proposition, which provides some characterization of EFX00 allocations on some graphs with priceless edges. The proof can be seen in the full version of this paper.

Proposition 2. For graphs that satisfy (1) each edge is a good for both its endpoint agents, (2) each agent has one priceless incident edge and (3) each priceless edge is priceless to both its endpoint agents, we have that each edge must be allocated to one of its endpoint agents in any EFX00 allocation.

In the full version, we provide a graph with priceless edges, which proves the following proposition.

Proposition 3. There exist graphs for which no allocation is EFX00 .

We next study the complexity of determining the existence of EFX00 allocations and have the following result.

Theorem 2. Determining whether an EFX00 allocation exists or not is NP-complete, even for additive valuations.

To prove Theorem 2, we reduce from Circuit-SAT problem to the EFX00 allocation problem. Circuit-SAT problem determines whether a given Boolean circuit has an assignment of the inputs that makes the output True, which is well-known to be NP-complete [Karp et al., 1975].

We first show how to simulate the OR gate, the NOT gate, the wire in the circuit and how to force the final output to be True. To achieve this, we construct four graphs, named OR gadget, NOT gadget, WIRE gadget, TRUE terminator gadget, respectively (see Figure 3). It is easy to see that Proposition 2 applies to all these four gadgets. That is, in any EFX00 allocation on each of these gadgets, each edge must be allocated to one of its endpoint agents. This enables us to represent each input (or output) in the circuit as an edge in the gadgets and its value (True or False) as the orientation of the edge.

In the OR gadget (see Figure 3a), edges (a1, a′1 ) and (a2, a′2 ) represent the two inputs of the OR gate, edge (a3, a′3 ) represents the output. The following claim shows that the OR gadget correctly simulates the OR gate.

Claim 1. In every EFX00 allocation on the OR gadget, edge (a3, a′3 ) is allocated to a3 if and only if edge (a1, a′1 ) is allocated to a1 or edge (a2, a′2 ) is allocated to a2.

Proof. We first show that if (a1, a′1 ) is allocated to a1, (a3, a′3 ) must be allocated to a3. Since (a1, a′1 ) is priceless to a′1 but is allocated to a1, a′1 envies a1. Hence, (a1, a′3 ) must be allocated to a′3 . Otherwise, a′1 still envies a1 after removing (a1, a′3 ) from a1's bundle. Moreover, (a3, a′3 ) must be allocated to a3. Otherwise, a3 still envies a′3 after removing (a1, a′3 ) from a3's bundle. By symmetry, it holds that if (a2, a′2 ) is allocated to a2, (a3, a′3 ) must be allocated to a3.

We then show that when (a1, a′1 ) is allocated to a1 and (a3, a′3 ) is allocated to a3, no matter which endpoint agent (a2, a′2 ) is allocated to, there exists an EFX00 allocation. When (a2, a′2 ) is allocated to a2, we construct an EFX00 allocation as follows: allocate each priceless edge to the upper endpoint agent, i.e., (ai, a′i ) to ai for every i ∈ {1, 2, 3} and (bi, b′i ) to bi for every i ∈ {1, 2, 3}; allocate the middle four edges to the endpoint agents who are further away from b′2 , i.e., (a′1 , b′1 ) to a′1 , (b′1 , b′2 ) to b′1 , (b′2 , b′3 ) to b′3 , (b′3 , a′2 ) to a′2 ; allocate (b′2 , a3) to b′2 , (a1, a′3 ) to a′3 , (a2, a′3 ) to a′3 . Since each agent has a positive value for each edge she receives, to verify that the allocation is EFX00 , it suffices to consider the agents who receive more than one edge (only a′3 in the above allocation). Since both a1 and a2 receive their priceless edges, neither of them envies a′3 and thus the allocation is EFX00 . When (a2, a′2 ) is allocated to a′2 , we construct an EFX00 allocation as follows: allocate each priceless edge except (a2, a′2 ) and (b1, b′1 ) to the upper endpoint, i.e., (ai, a′i ) to ai for every i ∈ {1, 3}, (bi, b′i ) to bi for every i ∈ {2, 3}, (a2, a′2 ) to a′2 , (b1, b′1 ) to b′1 ; for the middle four edges, allocate (a′1 , b′1 ) to a′1 , (b′1 , b′2 ) to b′2 , (b′2 , b′3 ) to b′3 , (b′3 , a′2 ) to b′3 ; allocate (b′2 , a3) to b′2 , (a1, a′3 ) to a′3 , (a2, a′3 ) to a2. In the above allocation, only b′2 and b′3 receive more than one edge. For b′2 , neither b′1 nor a3 envies her since both of them receive their priceless edges. For b′3 , a′2 does not envy her since she receives her priceless edge, and b′2 does not envy her since she receives a value of ϵ1 + ϵ2 and thinks that b′3 receives a value of ϵ1. Therefore, the allocation is also EFX00 . By symmetry, when (a2, a′2 ) is allocated to a2 and (a3, a′3 ) is allocated to a3, no matter which endpoint agent (a1, a′1 ) is allocated to, there exists an EFX00 allocation.

We next show that if both (a1, a′1 ) and (a2, a′2 ) are allocated to their lower endpoint agents, (a3, a′3 ) must be allocated to a′3 . It suffices to show that (b′2 , a3) must be allocated to a3. This is because if both (a3, a′3 ) and (b′2 , a3) are allocated to a3, a′3 will envy a3 even after removing (b′2 , a3) from a3's bundle. If (b2, b′2 ) is allocated to b′2 , (b′2 , a3) must be allocated to a3 and we have done, since otherwise b2 will envy b′2 even after removing (b′2 , a3) from b′2 's bundle. Therefore, it remains to consider the case when (b2, b′2 ) is allocated to b2. Since (a1, a′1 ) is allocated to a′1 , (a′1 , b′1 ) must be allocated to b′1 since otherwise a1 will envy a′1 even after removing (a′1 , b′1 ) from a′1 's bundle. Furthermore, (b1, b′1 ) must be allocated to b1. By the same reasoning, (a′2 , b′3 ) must be allocated to b′3 and (b3, b′3 ) must be allocated to b3. Then consider the incident edges of b′2 that have not been allocated so far, i.e., (b′1 , b′2 ) and (b′2 , b′3 ). b′2 must receive one of these two edges, since otherwise she will envy b′1 even after removing (a′1 , b′1 ) from b′1 's bundle, and b′3 even after removing (a′2 , b′3 ) from b′3 's bundle. No matter which edge b′2 receives, (b′2 , a3) must be allocated to a3. To see this, let the edge that b′2 receives be (b′1 , b′2 ). Since b′1 receives a value of ϵ2 and thinks that b′2 receives a value of ϵ1 > ϵ2, she envies b′2 and thus b′2 cannot receive (b′2 , a3) any more.

Lastly, we show that when all of (a1, a′1 ), (a2, a′2 ) and

(a3, a′3 ) are allocated to their lower endpoint agents, there exists an EFX00 allocation. We allocate each priceless edge except (b1, b′1 ) and (b3, b′3 ) to the lower endpoint agent, i.e., (ai, a′i ) to a′i for every i ∈ {1, 2, 3}, (b2, b′2 ) to b′2 , and (bi, b′i ) to bi for every i ∈ {1, 3}; for the middle four edges, allocate (a′1 , b′1 ) and (b′1 , b′2 ) to b′1 , (b′2 , b′3 ) and (b′3 , a′2 ) to b′3 ; allocate (b′2 , a3) to a3, (a1, a′3 ) to a1, (a2, a′3 ) to a2. In the above allocation, only b′1 and b′3 receive more than one edge. For b′1 , neither a′1 nor b′2 envies her since both of them receive their priceless edges. By the same reasoning, neither b′2 nor a′2 envies b′3 . Therefore, the allocation is EFX00 .

We can also prove that the other three gadgets correctly simulate the corresponding elements of a circuit. The formal claims and proofs can be seen in the full version of this paper.

Given a circuit, we first substitute each AND gate with three NOT gates and one OR gate, and get an equivalent circuit without AND gates. For the new circuit, we construct a priceless edge with a value of +∞ for each input, and the corresponding gadget for each gate and wire. We then construct a True terminator gadget to force the final output to be True. Figure 4 shows the graph constructed from a simple circuit with one AND gate, two inputs and one final output. Note that Proposition 2 still applies to the graph we construct.

Up to now, it is not hard to see the correctness of Theorem 2, whose formal proof can be seen in the full version.

Remark 1. Our reduction borrows an idea from the reduction by [Christodoulou et al., 2023] (see Theorem 2 in their paper) and generalizes their reduction. Our reduction can imply their result, while theirs cannot carry over to our problem since it relies on the orientation model.

4.2 EFX0- Allocations

We next study EFX0- and have the following theorem.

Theorem 3. For any graph, an EFX0- allocation always exists and can be computed in polynomial time.

We first introduce some notations. Given a (partial) allocation X = (X1, . . . ,Xn), let R(X) denote the set of unallocated edges, i.e., R(X) = M \ ⋃ai∈N Xi. We say an agent aj is safe for another agent ai if ai does not envy aj even if aj receives all her unallocated incident edges that are not chores for her, i.e., vi(Xi) ≥ vi(Xj ∪ (E≥0 i ∩ R(X))). We next introduce some properties of allocations.

Definition 2 (Properties of a (Partial) Allocation). We say that a (partial) allocation X satisfies

• property (1) if for every agent ai, the value of her bundle is at least the largest value among her unallocated incident edges that are not chores for her. That is, vi(Xi) ≥ vi(e) for every edge e ∈ E≥0 i ∩R(X);
• property (2) if for every envied agent ai, the value of her bundle is at least the value of all her unallocated incident edges that are not chores for her. That is, vi(Xi) ≥ vi(E≥0 i ∩R(X));
• property (3) if for every two envied agents, there exists a non-envied agent who is safe for both of them;
• property (4) if no agent receives an edge that is a chore for her. That is, e ∈ E≥0 i for any ai ∈ N and e ∈ Xi;
• property (5) if every envied agent ai receives exactly one edge, i.e., |Xi| = 1.
• property (6) if every envied agent is envied by exactly one agent;
• property (7) if there is no envy cycle among the agents. That is, there does not exist a sequence of the agents ai0 ← ai1 ← · · · ← ais such that ail envies ail-1 for every l ∈ [s] and i0 = is;
• property (8) if for any sequence of agents ai0 ← ai1 ← · · · ← ais such that ail envies ail-1 for every l ∈ [s] and ais is non-envied, we have that ail is safe for ai0 for every l ∈ [s].

We obtain an EFX0- allocation in two parts.

Part 1. In the first part, we compute a (partial) EFX0- orientation that satisfies properties (1)-(8) in Definition 2. Our algorithms in this part are adapted from those by [Christodoulou et al., 2023]. There are two differences between our algorithms and [Christodoulou et al., 2023]'s. First, since there is one more requirement in our problem that agents cannot envy others after removing a chore from their own bundles, we need to carefully allocate the edges that are chores for their endpoint agents. Second, the algorithms by [Christodoulou et al., 2023] cannot guarantee property (8) and our algorithms need to deal with the case where property (8) is not satisfied.

We have the following lemma. The detailed algorithms and proofs can be seen in the full version.

Lemma 1. For any graph, a (partial) EFX0- orientation that satisfies properties (1)-(8) in Definition 2 can be computed in polynomial time.

Part 2. In the second part, we allocate the edges that are not allocated in Part 1. We first categorize the unallocated edges into four disjoint groups:

• G1 contains each edge that has at least one non-envied endpoint agent for whom the edge is not a chore;
• G2 contains each edge that has two envied endpoints;
• G3 contains each edge that has one non-envied endpoint agent for whom the edge is a chore and one envied endpoint agent for whom it is not a chore;

• G4 contains the edges that have not been included in G1, G2, G3. Notice that each edge in G4 is a chore for both its endpoint agents.

We will allocate the unallocated edges from G1 to G4 such that no agent will receive an edge that is a chore for her and thus property (4) will be retained. Besides, no agent will get worse off and no allocated edge will become unallocated, which will ensure that properties (1) and (2) are retained. Moreover, no new envy will occur, which will ensure that properties (6) and (7) are retained. Furthermore, no allocated edge will be reallocated to another agent, which will ensure that an agent who is safe for some agent is always safe for that agent and thus properties (3) and (8) are retained. We will also see that the (partial) allocation is always EFX0- during the allocation process. Specifically,

• For each edge in G1, we allocate it to the non-envied endpoint agent for whom it is not a chore.
• For each edge in G2, we allocate it to the non-envied agent who is safe for both its endpoint agents.
• For each edge ei,j in G3, we consider three cases. Without loss of generality, let ai be the endpoint agent for whom ei,j is not a chore and aj be the other one for whom it is a chore. First, ai becomes non-envied. Similar to the allocation of G1, we allocate the edge to ai. Second, there exists a non-envied agent ak ̸= aj who is safe for ai. Similar to the allocation of G2, we allocate ei,j to ak. Third, aj is the only non-envied agent who is safe for ai. By property (8), it must be the case that there exists a sequence of agents ai0 ← ai1 ← · · · ← ais such that ail envies ail-1 for every l ∈ [s], ai0 is ai and ais is aj. For this case, we allocate ei,j to ais-1 .
• For G4, we consider two cases. First, if no agent is envied, we allocate each edge to an agent who is not its endpoint. Second, if some agent is envied, we find two agents ai and aj such that ai is envied by aj and aj is non-envied. We allocate the edges in G4 that are incident to aj (i.e., Ej ∩ G4) to ai, and the other edges in G4 (i.e., G4 \ Ej) to aj.

We have the following lemma in Part 2, whose proof can be seen in the full version of this paper.

Lemma 2. For any graph, given a (partial) EFX0- orientation that satisfies properties (1)-(8) in Definition 2, we can compute an EFX0- allocation in polynomial time.

By Lemmas 1 and 2, it is clear that Theorem 3 holds.

4.3 EFX+0 Allocations

Finally, we study EFX+0 and have the following theorem.

Theorem 4. For any graph, an EFX+0 allocation always exists and can be computed in polynomial time.

First recall that for chores instances where each edge is a chore for both its endpoint agents, we can compute an envyfree allocation by allocating each edge to an agent who is not its endpoint. Thus in the following, we only consider graphs where there exists an edge that is not a chore for at least one of its endpoint agents.

To get some intuitions about how to compute an EFX+0 allocation, consider the graphs where each edge is a good for at least one of its endpoint agents. For these graphs, we can simply allocate each edge to the endpoint agent for whom it is a good. For any agent ai, each edge she receives is a good for her, and at most one edge that each other agent aj receives is a good for her. After removing the good from aj's bundle, ai does not envy aj. Thus, the allocation is EFX+0 .

The trickier graphs to deal with are those with edges that are not goods for any of their endpoint agents. For these graphs, we want to find an agent who can receive all such edges, so that we can simply allocate each remaining edge to one of its endpoint agents as above. At the same time, the allocation should be EFX+0 for the agent we find. When there exists an agent ai to whom the total value of her incident edges is non-negative (i.e., vi(Ei) ≥ 0), we let ai receive all her incident edges as well as all edges that are not goods for any of their endpoint agents. We then allocate each remaining edge to one of its endpoint agents for whom it is a good. Since ai receives all her incident edges whose total value is non-negative, the allocation is EFX+0 for her.

However, when the total value of the incident edges is negative to every agent (i.e., vi(Ei) < 0 for every ai), we cannot simply allocate all incident edges to an agent as above, since the allocation may not be EFX+0 for her. For this case, we let an agent receive all her incident edges that are not chores for her and allocate her other incident edges to another agent. More concretely, we first choose an edge ei,j that is not a chore for ai, breaking the tie by giving priority to the edges that are not chores for one endpoint agent and are chores for the other. We then let ai receive all her incident edges that are not chores for her, as well as all edges that are not incident to her but are not goods for any of their endpoint agents. Next, we let aj receive all her unallocated incident edges that are goods for her, as well as ai's unallocated incident edges that are not goods for any of their endpoint agents. At last, we allocate each remaining unallocated edge to one of its endpoint agents for whom it is a good. The formal description of the allocation process and the formal proof of Theorem 4 can be seen in the full version.

Since any EFX0- or EFX+0 allocation is also EFX+-, we have the following corollary.

Corollary 3. For any graph, an EFX+- allocation always exists and can be computed in polynomial time.

5 Conclusion

In this paper, we give a complete computational study of EFX allocations on graphs when the items are a mixture of goods and chores. There are some future directions. In our setting, exactly two agents are interested in one common item that is incident to both of them. One immediate direction is to study the generalized setting with multi-edges where multiple edges exist between two agents or hypergraphs where more than two agents are interested in one common item. Another direction is to study the setting where agents are also interested in the edges that are not very far away from them. To bypass the hardness results of EFX orientations, we have studied some simple graphs including trees, stars and paths. One can also study complex graphs for which the existence of EFX orientations can be determined in polynomial time.

Acknowledgements

This work is partly funded by the Hong Kong SAR Research Grants Council (No. PolyU 15224823) and Department of Science and Technology of Guangdong Province (No. 2023A1515010592).