A Complete Landscape of EFX Allocations of Mixed Manna on Graphs
Yu Zhou Tianze Wei Minming Li Bo Li

[
    [
    September 9, 2024
=====================



§ ABSTRACT 
    We study envy-free up to any item (EFX) allocations on graphs where vertices and edges represent agents and items respectively. 
    An agent is only interested in items that are incident to her and all other items have zero marginal values to her. 
    Christodoulou et al. [EC, 2023] first proposed this setting and studied the case of goods.
    We extend this setting to the case of mixed manna where an item may be liked or disliked by its endpoint agents.
    In our problem, an agent has an arbitrary valuation over her incident items such that the items she likes have non-negative marginal values to her and those she dislikes have non-positive marginal values. 
    
    We provide a complete study of the four notions of EFX for mixed manna in the literature, which differ by whether the removed item can have zero marginal value. 
    We prove that an allocation that satisfies the notion of EFX where the virtually-removed item could always have zero marginal value may not exist and determining its existence is NP-complete, while one that satisfies any of the other three notions always exists and can be computed in polynomial time.     
    
    We also prove that an orientation (i.e., a special allocation where each edge must be allocated to one of its endpoint agents) that satisfies any of the four notions may not exist, and determining its existence is NP-complete. 




§ 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 <cit.>, 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 <cit.>: “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. 
For the case of goods where every item is liked by every agent, <cit.> showed that EFX allocations exist when there are only two agents. 
<cit.> and <cit.> complemented this result by showing the existence of EFX allocations when there are only three agents, and when the number of goods is at most three greater than the number of agents, respectively. 
<cit.> also showed that EFX allocations exist when the valuations are identical or additive with identical ordering. 
<cit.> extended this result by showing the existence of EFX allocations when the valuations are bi-valued. 
Other restricted valuations for which EFX allocations always exist include submodular dichotomous valuations where the marginal value of any item is either 0 or 1 <cit.>, and lexicographic valuations where the value of a single item is greater than the total value of all items that are less preferred <cit.>. 
For the case of chores where every item is disliked by every agent, even less is known. For example, <cit.> and <cit.> showed that EFX allocations exist for ordered instances and leveled preference instances, respectively. 

Recently, <cit.> 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 <cit.>, 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. 
<cit.> 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, <cit.> 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. 
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.  
<cit.>'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.



 §.§ Our Problem and Results

In this work, we extend the model of <cit.> 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., _0^0, ^0_-, ^+_0, and ^+_-, 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 <cit.>, 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 <ref>. 
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 these simple graphs, ^+_0 or ^+_- orientations always exist and can be computed in polynomial time. 
Although ^0_0 or ^0_- orientations may not exist, determining their existence is 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 <ref>. 
Specifically, we show that an ^0_0 allocation may not exist and determining its existence is NP-complete. In contrast, an allocation that satisfies any of the other three notions always exists and can be computed in polynomial time. 





 §.§ More Related Works

Mixed Manna.
Since initiated by <cit.>, there has been a rapidly growing interest in fair allocation of 
mixed manna in recent years. 
<cit.> proposed a polynomial-time algorithm named double round-robin that computes an envy-free up to one item (EF1) allocation for any instance with additive valuations. 
<cit.> extended this result by computing EF1 allocations for instances with general valuations. 
Their algorithm is based on the envy-cycle procedures and also runs in polynomial time. 
<cit.> gave a polynomial-time algorithm that computes an EFX and Pareto-Optimal (PO) allocation for instances with identical and additive valuations. 
In their definition of EFX, the removed item must not have a value of zero, which as we will see, is the weakest one among the notions of EFX that we study in this paper. 
Other fairness notions studied for mixed manna include proportionality up to one item (PROP1) <cit.> and maximin share (MMS) <cit.>. 
We refer the readers to the survey by <cit.> for more details on this topic. 

Fair Allocation on Graphs. 
There are many other works that study fair allocation of indivisible items on graphs, whose settings whereas, are quite different from ours and <cit.>'s. 
<cit.> 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 <cit.>. 
<cit.> considered the same model and quantified the loss of fairness when imposing the connectivity constraint, i.e., price of connectivity. 
<cit.> studied a similar model where each agent must receive a compact bundle of items that are “closely related”. 
Different from this line of works, <cit.> 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. 
<cit.> 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. 



§ 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 = {a_1, …, a_n} 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 (a_i, a_j) and e_i, j to represent the edge between a_i and a_j. 
Each agent a_i ∈ N has a valuation v_i: 2^M→ℝ over the edges and v_i(∅) = 0. 
We also write v_i(e) to represent v_i({e}). 


For an agent a_i, each item e ∈ M is classified as a good (if it has strictly positive marginal values to a_i, i.e., v_i(S ∪{e}) > v_i(S) for any S ⊆ M∖{e}), a chore (if it has strictly negative marginal values to a_i, i.e., v_i(S ∪{e}) < v_i(S) for any S ⊆ M∖{e}), or a dummy (if it has zero marginal value to a_i, i.e., v_i(S ∪{e}) = v_i(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 E_i be the set of all edges that are incident to a_i, E_i^≥ 0⊆ E_i be the subset of non-chores for a_i, and E_i^>0⊆ E_i be the subset of goods for a_i. 
Note that in our setting, all edges that are not incident to a_i (i.e., M ∖ E_i) are dummies for a_i. 


An allocation 𝐗 = (X_1, …, X_n) is an n-partition of M such that X_i contains the edges allocated to agent a_i ∈ N, where X_i ∩ X_j = ∅ for any a_i, a_j ∈ N and ⋃_a_i ∈ NX_i = M. 
An orientation is a restricted allocation where each edge must be allocated to one of its endpoint agents. 
An allocation 𝐗 is partial if ⋃_a_i ∈ NX_i ⊊ M. 



 §.§ Fairness Notions

Given an allocation 𝐗, we say agent a_i envies agent a_j if v_i(X_j) > v_i(X_i). 
The allocation is envy-free (EF) if no agent envies the others, i.e., for every two agents a_i, a_j ∈ N, v_i(X_i) ≥ v_i(X_j). 
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 <cit.>, namely, _0^0, ^0_-, ^+_0, and ^+_-. 
_0^0 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, 


    An allocation 𝐗 = (X_1, …, X_n) is ^0_0 if for every two agents a_i, a_j ∈ N such that a_i envies a_j, both of the following conditions hold: 
    
        
  * for any e ∈ X_j such that v_i(X_j ∖{e}) ≤ v_i(X_j), v_i(X_i) ≥ v_i(X_j ∖{e});
        
  * for any e ∈ X_i such that v_i(X_i ∖{e}) ≥ v_i(X_i), v_i(X_i ∖{e}) ≥ v_i(X_j). 
    


^0_- differs from _0^0 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 v_i(X_i ∖{e}) > v_i(X_i). 
^+_0 differs from _0^0 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 v_i(X_j ∖{e}) < v_i(X_j). 
^+_- differs from _0^0 in that the item removed from the envied agent's and the envious agent's bundles cannot be a dummy. 
Formally,  


    An allocation 𝐗 = (X_1, …, X_n) is ^0_- if for every two agents a_i, a_j ∈ N such that a_i envies a_j, both of the following conditions hold: 
    
        
  * for any e ∈ X_j s.t. v_i(X_j ∖{e}) ≤ v_i(X_j), v_i(X_i) ≥ v_i(X_j ∖{e}); 
        
  * for any e ∈ X_i s.t. v_i(X_i ∖{e}) > v_i(X_i), v_i(X_i ∖{e}) ≥ v_i(X_j). 
    



    An allocation 𝐗 = (X_1, …, X_n) is ^+_0 if for every two agents a_i, a_j ∈ N such that a_i envies a_j, both of the following conditions hold: 
    
        
  * for any e ∈ X_j s.t. v_i(X_j ∖{e}) < v_i(X_j), v_i(X_i) ≥ v_i(X_j ∖{e}); 
        
  * for any e ∈ X_i s.t. v_i(X_i ∖{e}) ≥ v_i(X_i), v_i(X_i ∖{e}) ≥ v_i(X_j). 
    



    An allocation 𝐗 = (X_1, …, X_n) is ^+_- if for every two agents a_i, a_j ∈ N such that a_i envies a_j, both of the following conditions hold: 
    
        
  * for any e ∈ X_j s.t. v_i(X_j ∖{e}) < v_i(X_j), v_i(X_i) ≥ v_i(X_j ∖{e}); 
        
  * for any e ∈ X_i s.t. v_i(X_i ∖{e}) > v_i(X_i), v_i(X_i ∖{e}) ≥ v_i(X_j). 
    


Obviously, any ^0_0 allocation is also ^0_- or ^+_0, and any ^0_- or ^+_0 allocation is also ^+_-. 



  
Goods and Chores Instances.
Goods instances have been well studied in <cit.>, and we will see that our results provide alternative approaches.
For chores instances, we provide a discussion in Appendix <ref>. 
In the subsequent sections, we shall focus on the general case of mixed manna.



§ EFX ORIENTATIONS

In this section, we elaborate on EFX orientations. 
Firstly, we have the following proposition. 


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


    Consider a connected graph where there are more edges than vertices and each edge is a chore for both its endpoint agents. 
    Since each edge must be allocated to one of its endpoint agents, there exists an agent who receives at least two chores in any orientation. 
    Even after removing one chore from her own bundle, this agent still receives a negative value and envies the agents who are not her neighbors. 


Due to this negative result, we turn to studying the complexity of determining the existence of EFX orientations. 
The result by <cit.> (see Theorem 2 in their paper) directly implies that determining the existence of ^0_- 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 ^0_- orientation is also ^0_0.
Therefore, we have the following corollary. 


    Determining whether an ^0_0 or ^0_- orientation exists or not is NP-complete. 




 §.§ ^+_- Orientations

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


    Determining whether an ^+_- orientation exists or not is NP-complete, even for additive valuations[Valuation v_i is additive if v_i(S) = ∑_e ∈ S v_i(e) for any S ⊆ M.]. 

To prove Theorem <ref>, we reduce from (3, B2)-SAT problem to the ^+_- orientation problem. 
A (3, B2)-SAT instance contains a Boolean formula in conjunctive normal form consisting of n variables {x_i}_i ∈ [n] and m clauses {C_j}_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 NP-complete <cit.>. 

Our reduction uses a gadget to ensure that a specific agent must receive a chore if the orientation is ^+_-. 
One such gadget is shown in Figure <ref>. 
In this example, agent a_i must receive (a_i, a_1^Δ) if the orientation is ^+_-. 
Otherwise, one of the other three agents must receive at least two chores and envy a_i even after removing one chore. 



Given a (3, B2)-SAT instance ({x_i}_i ∈ [n], {C_j}_j ∈ [m]), we construct a graph as follows:

    
  * For each variable x_i, create two vertices a^T_i, a^F_i and one edge (a^T_i, a^F_i) with a value of 2 to both a^T_i and a^F_i. 
    
  * For each clause C_j, create one vertex a_j^C. 
    Besides, if C_j contains a positive literal x_i, create one edge (a_j^C, a^T_i) with a value of 1 to both  a_j^C and a^T_i. 
    If C_j contains a negative literal x_i, create one edge (a_j^C, a^F_i) with a value of 1 to both  a_j^C and a^F_i. 
    
  * 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 (a_i^T, a_1^Δ) and (a_i^F, a_1^Δ). 
    For each j ∈ [m], create one edge (a_j^C, 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 (x_1 ∨ x_2 ∨ x_3) ∧ (x_1 ∨ x_2 ∨ x_3) ∧ ( x_1 ∨ x_2 ∨ x_3) ∧ ( x_1 ∨ x_2 ∨ x_3) in Figure <ref>. 



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


    For ease of presentation, for each variable x_i, we denote by C_j^i, T, 1, C_j^i, T, 2 the two clauses that contain the positive literal x_i and by C_j^i, F, 1, C_j^i, F, 2 the two clauses that contain the negative literal x_i. 
    
    For one direction, we assume that the (3, B2)-SAT instance has a satisfying assignment and use the assignment to create an _-^+ 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 x_i that is set to True, allocate (a_i^T, a_i^F) to a_i^T, 
        (a_i^T, a_j^i, T, 1^C) to a_j^i, T, 1^C, (a_i^T, a_j^i, T, 2^C) to a_j^i, T, 2^C, and (a_i^F, a_j^i, F, 1^C), (a_i^F, a_j^i, F, 2^C) to a_i^F.  
        
  * For each variable x_i that is set to False, allocate (a_i^T, a_i^F) to a_i^F, 
        (a_i^F, a_j^i, F, 1^C) to a_j^i, F, 1^C, (a_i^F, a_j^i, F, 2^C) to a_j^i, F, 2^C, and (a_i^T, a_j^i, T, 1^C), (a_i^T, a_j^i, T, 2^C) to a_i^T.  
    
    Next, we show that the above orientation is _-^+. 
    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 x_i that is set to True, agent a_i^T 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 a_i^F receives three edges with values of 1, 1, -1, respectively. 
    The only incident edge that she does not receive is (a_i^T, a_i^F), which is allocated to a_i^T and has a value of 2. 
    After removing the edge with a value of -1 from her own bundle or (a_i^T, a_i^F) from a_i^T's bundle, a_i^F does not envy a_i^T. 
    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 a_j^C receives at least one edge with a value of 1. 
    For example, if the clause C_j contains a positive literal x_i that is evaluated to True, a_j^C receives the edge (a_i^T, a_j^C). 
    Since each of a_j^C's incident edges that she does not receive has a value of 1, a_j^C 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 _-^+ orientation and use the orientation to create a satisfying assignment as follows: for each variable x_i, if the edge (a_i^T, a_i^F) is allocated to agent a_i^T, then set x_i to True; otherwise, set x_i to False. 
    Next, we show that the assignment is satisfying. 
    First, since the orientation is _-^+, 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 x_i, if the edge (a_i^T, a_i^F) is allocated to agent a_i^T, both (a_i^F, a_j^i, F, 1^C) and (a_i^F, a_j^i, F, 2^C) must be allocated to agent a_i^F. 
    Otherwise, a_i^F will envy a_i^T even after removing (a_i^F, a_1^Δ) from her own bundle. 
    For a similar reason, if the edge (a_i^T, a_i^F) is allocated to a_i^F, both (a_i^T, a_j^i, T, 1^C) and (a_i^T, a_j^i, T, 2^C) must be allocated to a_i^T. 
    For each clause C_j, agent a_j^C must receive at least one edge with a value of 1. 
    Otherwise, a_j^C 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 _0^+ if and only if it is _-^+, since no agent receives an edge with a value of zero. 
Therefore, the hardness of determining the existence of _-^+ orientations also applies to _0^+ orientations. 



    Determining whether an ^+_0 orientation exists or not is NP-complete, even for additive valuations. 




 §.§  Orientations on Simple Graphs

Due to the above hardness results for general graphs, we also study EFX orientations on some simple graphs such as trees, stars and paths. 
For these simple graphs, ^+_0 or ^+_- orientations always exist and can be computed in polynomial time. 
Although ^0_0 or ^0_- orientations may not exist, determining their existence is in polynomial time. 



  
Trees
We first consider trees and have the following result. 

    For trees, ^+_0 or ^+_- orientations always exist and can be computed in polynomial time. 

    
Since any ^+_0 orientation is also ^+_-, it suffices to compute ^+_0 orientations. 
To achieve this, we first traverse the tree using the breadth-first search (BFS) algorithm and label each vertex with its layer number during the BFS algorithm. 
We then allocate each edge to the endpoint agent at the upper layer if the edge is a good for that agent, and to the endpoint agent at the lower layer otherwise. 
The formal description is provided in Algorithm <ref>. 




    Clearly, Algorithm <ref> runs in polynomial time. 
    It suffices to show that the computed orientation is ^+_0. 
    Observe that for each agent a_i, the edge between herself and an agent at one higher layer is the only edge that is a good for her but is allocated to another agent, or the only edge that is not a good for her but is allocated to her. 
    For the first case, after removing the edge from the other agent's bundle, a_i does not envy that agent. 
    For the second case, after removing the edge from her own bundle, a_i does not envy others. 
    Therefore, the orientation is ^+_0. 


Note that stars and paths are also trees, Theorem <ref> holds for stars and paths. 
However, ^0_0 or ^0_- orientations may not exist even for a simple tree that is also a star and a path. 



    There exists a simple tree that is also a star and a path, for which no allocation is ^0_0 or ^0_-. 


    Consider the simple tree illustrated in Figure <ref>, which is also a star and a path. 
    Notice that the edge e_2, 3 must be allocated to a_2. 
    Otherwise, a_3 will envy whoever receives e_1, 2 even after removing e_1, 2 from the agent's bundle. 
    Moreover, e_1, 2 must also be allocated to a_2. 
    Otherwise, a_2 will envy a_1 even after removing e_2, 3 from her own bundle. 
    Since a_1 envies a_2 even after removing e_2, 3 from a_2's bundle, no orientation is ^0_0 or ^0_-. 






The good news is that for stars and a specific type of path, we can determine whether ^0_0 or ^0_- orientations exist or not in polynomial time. 



  
Stars
We then consider stars and have the following result. 

    For stars, determining whether an ^0_0 or ^0_- orientation exists or not is in polynomial time. 


    If there is only one edge, allocating the edge to one of its endpoint agents gives an ^0_0 and ^0_- orientation. 
    In the following, we assume that there are at least two edges. 
    Observe that if an edge is a chore for its satellite agent, the edge must be allocated to the center in any ^0_0 or ^0_- orientation. 
    To see this, let the edge be e_i, j such that a_j is the satellite and a_i is the center and suppose that e_i, j is allocated to a_j. 
    Let another edge be e_i, k. 
    Since e_i, k is a dummy for a_j, no matter who receives e_i, k, a_j will envy her even after removing e_i, k from her bundle.
    Thus, e_i, j must be allocated to a_i in any ^0_0 and ^0_- orientation.  
    Also, observe that if the center receives an edge, each edge that is a good for its satellite agent must be allocated to the satellite. 
    Otherwise, the satellite will envy the center even after removing the edge that the center has received. 
    We consider the following two cases: 

    Case 1: Each edge is not a chore for its satellite agent. 
    In this case, we simply allocate each edge to its satellite agent, and it is easy to see that the orientation is ^0_0 and ^0_-. 

    Case 2: There exists an edge that is a chore for its satellite agent. 
    In this case, as we have seen, the edges that are chores for their satellite agents must be allocated to the center in any ^0_0 and ^0_- orientation.
    Moreover, the edges that are goods for their satellite agents must be allocated to their satellites. 
    For the edges that are dummies for their satellite agents, it does not matter how they are allocated since the orientation is always envy-free for their satellites. 
    Thus, if they are not goods for the center, we allocate them to their satellites and otherwise we allocate them to the center. 
    Therefore, by checking whether the orientation is ^0_0 (resp. ^0_-) for the center, we can determine whether there exists any ^0_0 (resp. ^0_-) orientation. 




  
Paths We next consider a specific type of paths and have the following result. 

    For paths where each edge is either a good or a chore for both its endpoint agents, determining whether an ^0_0 or ^0_- orientation exists or not is in polynomial time. 


    In the paths we focus on, ^0_0 and ^0_- are equivalent since no edge is a dummy for any of its endpoint agents. 
    Thus, in the following, we only consider ^0_-. 

    If there is only one edge or each edge is a good for both its endpoint agents, we can obtain an ^0_- orientation by allocating each edge to the right endpoint agent. 
    If there are only two edges and at least one is a chore for both its endpoint agents, an ^0_- orientation does not exist, which is easy to see by the same reasoning we made in the proof of Proposition <ref>. 
    It remains to consider the cases where there are at least three edges and at least one is a chore for both its endpoint agents. 
    
    We first observe that for each edge that is a chore for both its endpoint agents, its neighboring vertices and edges follow the same pattern if there exists an ^0_- orientation. 
    Let one such edge be e_i_0, i_1 that is a chore for both a_i_0 and a_i_1, the two neighboring edges on its right are e_i_1, i_2, e_i_2, i_3, and the two neighboring edges on its left are e_i_-2, i_-1, e_i_-1, i_0. 
    We claim that if there exists an ^0_- orientation, one of the following two conditions holds:
    
        
  * e_i_1, i_2 is a good for both a_i_1 and a_i_2, e_i_2, i_3 is a good for both a_i_2 and a_i_3, v_i_1({e_i_0, i_1}∪{e_i_1, i_2}) ≥ 0, v_i_2(e_i_1, i_2) ≤ v_i_2(e_i_2, i_3); 
        
  * e_i_-1, i_0 is a good for both a_i_-1 and a_i_0, e_i_-2, i_-1 is a good for both a_i_-2 and a_i_-1, v_i_0({e_i_0, i_1}∪{e_i_-1, i_0}) ≥ 0, v_i_-1(e_i_-1, i_0) ≤ v_i_-1(e_i_-2, i_-1). 
    
    To see this, first consider the case if e_i_0, i_1 is allocated to a_i_1. 
    If e_i_1, i_2 is not a good for a_i_1 or v_i_1({e_i_0, i_1}∪{e_i_1, i_2}) < 0, a_i_1 gets a negative value and will envy whoever gets an edge that is not incident to her even after removing that edge. 
    Therefore, in any ^0_- orientation, e_i_1, i_2 must be a good for a_i_1, v_i_1({e_i_0, i_1, e_i_1, i_2}) ≥ 0 and e_i_1, i_2 must be allocated to a_i_1. 
    Furthermore, if e_i_2, i_3 is not a good for a_i_2 or v_i_2(e_i_1, i_2) > v_i_2(e_i_2, i_3), a_i_2 will envy a_i_1 after removing e_i_0, i_1 from her bundle. 
    Therefore, in any ^0_- orientation, e_i_2, i_3 must be a good for a_i_2, v_i_2(e_i_1, i_2) ≤ v_i_2(e_i_2, i_3) and e_i_2, i_3 must be allocated to a_i_2. 
    An analogous statement holds if e_i_0, i_1 is allocated to a_i_0. 

    We are now ready to determine whether an ^0_- orientation exists or not. 
    We consider three cases: 

    Case 1:
    If there exists an edge such that it is a chore for both its endpoint agents but its neighboring vertices and edges on neither of its two sides follow the pattern we observed (i.e., satisfy the above two conditions), we can assert that there does not exist any ^0_- orientation. 

    Case 2:
    If for each edge that is a chore for both its endpoint agents, the neighboring vertices and edges on both its two sides follow the pattern, we allocate each edge that is a chore to the left endpoint agent and each other edge to the right one. 
    It is easy to verify that the orientation is ^0_-. 

    Case 3:
    If there exists an edge that is a chore for both its endpoints, and its neighboring vertices and edges on only one of its two sides follow the pattern, we know how these edges must be allocated in any ^0_- orientation. 
    Take the edge e_i_0, i_1 for example, if only the first condition holds, e_i_0, i_1 and e_i_1, i_2 must be allocated to a_i_1, and e_i_2, i_3 must be allocated to a_i_2. 
    Therefore, we can delete these three edges and a_i_1 and a_i_2 from the path. 
    It is easy to see that the original path has an ^0_- orientation if and only if all reduced paths have ^0_- orientations. 
    By repeating the above reduction, either in some sub-path, Case 1 occurs and we can assert that there does not exist any ^0_- orientation; or in all sub-paths, either Case 2 occurs or each edge is a good for both its endpoint, then we can conclude that an ^0_- orientation exists. 




§ EFX ALLOCATIONS

In this section, we elaborate on EFX allocations. 



 §.§ _0^0 Allocations


We start with the strongest one among those four notions, i.e., ^0_0. 
We say an edge e is priceless to an agent a_i if for any S_1, S_2 ⊆ M such that e∉ S_1 and e∈ S_2, we have v_i(S_1) < v_i(S_2).
Notice that an agent envies whoever receives her priceless edge no matter which edges she herself receives and doe not envy others as long as she receives it. 
We have the following proposition, which provides some characterization of _0^0 allocations on some graphs with priceless edges.


    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 _0^0 allocation. 


    First, consider priceless edges. 
    Let (a_i, a_j) be one priceless edge and assume for the sake of contradiction that it is allocated to agent a_k who is not a_i or a_j. 
    In this case, a_k is envied by a_i and a_j, and thus cannot receive her priceless edge since it is a dummy for a_i and a_j. 
    Otherwise, a_i and a_j will envy a_k even after removing the dummy from a_k's bundle. 
    Moreover, a_k envies whoever receives her priceless edge even after removing (a_i, a_j) from her own bundle, which is a dummy for her, thus the allocation is not ^0_0. 

    Then, assume that each priceless edge is allocated to one of its endpoint agents and consider non-priceless edges. 
    Observe that each agent either envies the agent who receives the edge that is priceless to her, or is envied by that agent if she receives that priceless edge. 
    Each envied agent cannot receive any other edge since every edge is either a good or a dummy for the agent who envies her. 
    Otherwise, after removing the other edge from the envied agent's bundle, the envious agent still envies the envied agent, thus the allocation is not ^0_0. 
    Each agent who envies others cannot receive any edge that is not incident to her since it is a dummy for her. 
    Otherwise, after removing the dummy from her own bundle, the envious agent still envies others, thus the allocation is not ^0_0. 
    Therefore, each non-priceless edge must also be allocated to one of its endpoint agents. 


We first show that ^0_0 allocations may not exist. 



    There exist graphs for which no allocation is ^0_0. 


    Consider the graph illustrated in Figure <ref>. 
    Notice that the graph satisfies the three properties in Proposition <ref>. 
    Therefore, each edge must be allocated to one of its endpoint agents in any ^0_0 allocation. 
    Without loss of generality, assume that e_1, 2 is allocated to a_1, e_3, 4 to a_3, and e_1, 3 to a_1. 
    Since a_2 envies a_1 even after removing e_1,3 from a_1's bundle, the allocation is not ^0_0. 




We next study the complexity of determining the existence of ^0_0 allocations and have the following result. 


    Determining whether an _0^0 allocation exists or not is NP-complete, even for additive valuations. 




To prove Theorem <ref>, we reduce from Circuit-SAT problem to the _0^0 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 <cit.>. 



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 <ref>). 
It is easy to see that Proposition <ref> applies to all these four gadgets. 
That is, in any _0^0 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 <ref>), edges (a_1, a_1^') and (a_2, a_2^') represent the two inputs of the OR gate, edge (a_3, a_3^') represents the output. 
The following claim shows that the OR gadget correctly simulates the OR gate. 


    In every _0^0 allocation on the OR gadget, edge (a_3, a_3^') is allocated to a_3 if and only if edge (a_1, a_1^') is allocated to a_1 or edge (a_2, a_2^') is allocated to a_2.


    We first show that if (a_1, a_1^') is allocated to a_1, (a_3, a_3^') must be allocated to a_3. 
    Since (a_1, a_1^') is priceless to a_1^' but is allocated to a_1, a_1^' envies a_1. 
    Hence, (a_1, a_3^') must be allocated to a_3^'. 
    Otherwise, a_1^' still envies a_1 after removing (a_1, a_3^') from a_1's bundle. 
    Moreover, (a_3, a_3^') must be allocated to a_3.
    Otherwise, a_3 still envies a_3^' after removing (a_1, a_3^') from a_3's bundle. 
    By symmetry, it holds that if (a_2, a_2^') is allocated to a_2, (a_3, a_3^') must be allocated to a_3.

    We then show that when (a_1, a_1^') is allocated to a_1 and (a_3, a_3^') is allocated to a_3, no matter which endpoint agent (a_2, a_2^') is allocated to, there exists an _0^0 allocation. 
    When (a_2, a_2^') is allocated to a_2, we construct an _0^0 allocation as follows: allocate each priceless edge to the upper endpoint agent, i.e., (a_i, a_i^') to a_i for every i ∈{1, 2, 3} and (b_i, b_i^') to b_i 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^', a_3) to b_2^', (a_1, a_3^') to a_3^', (a_2, a_3^') to a_3^'. 
    Since each agent has a positive value for each edge she receives, to verify that the allocation is _0^0, it suffices to consider the agents who receive more than one edge (only a_3^' in the above allocation). 
    Since both a_1 and a_2 receive their priceless edges, neither of them envies a_3^' and thus the allocation is _0^0.
    When (a_2, a_2^') is allocated to a_2^', we construct an _0^0 allocation as follows: 
    allocate each priceless edge except (a_2, a_2^') and (b_1, b_1^')  to the upper endpoint, i.e., (a_i, a_i^') to a_i for every i ∈{1, 3}, (b_i, b_i^') to b_i for every i ∈{2, 3}, (a_2, a_2^') to a_2^', (b_1, 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^', a_3) to b_2^', (a_1, a_3^') to a_3^', (a_2, a_3^') to a_2. 
    In the above allocation, only b_2^' and b_3^' receive more than one edge. 
    For b_2^', neither b_1^' nor a_3 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 _0^0. 
    By symmetry, when (a_2, a_2^') is allocated to a_2 and (a_3, a_3^') is allocated to a_3, no matter which endpoint agent (a_1, a_1^') is allocated to, there exists an _0^0 allocation.

    We next show that if both (a_1, a_1^') and (a_2, a_2^') are allocated to their lower endpoint agents, (a_3, a_3^') must be allocated to a_3^'. 
    It suffices to show that (b_2^', a_3) must be allocated to a_3. 
    This is because if both (a_3, a_3^') and (b_2^', a_3) are allocated to a_3, a_3^' will envy a_3 even after removing (b_2^', a_3) from a_3's bundle. 
    If (b_2, b_2^') is allocated to b_2^', (b_2^', a_3) must be allocated to a_3 and we have done, since otherwise b_2 will envy b_2^' even after removing (b_2^', a_3) from b_2^''s bundle. 
    Therefore, it remains to consider the case when (b_2, b_2^') is allocated to b_2. 
    Since (a_1, a_1^') is allocated to a_1^', (a_1^', b_1^') must be allocated to b_1^' since otherwise a_1 will envy a_1^' even after removing (a_1^', b_1^') from a_1^''s bundle. 
    Furthermore, (b_1, b_1^') must be allocated to b_1. 
    By the same reasoning, (a_2^', b_3^') must be allocated to b_3^' and (b_3, b_3^') must be allocated to b_3. 
    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^', a_3) must be allocated to a_3. 
    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^', a_3) any more. 

    Lastly, we show that when all of (a_1, a_1^'), (a_2, a_2^') and (a_3, a_3^') are allocated to their lower endpoint agents, there exists an _0^0 allocation. 
    We allocate each priceless edge except (b_1, b_1^') and (b_3, b_3^') to the lower endpoint agent, i.e., (a_i, a_i^') to a_i^' for every i ∈{1, 2, 3}, (b_2, b_2^') to b_2^', and (b_i, b_i^') to b_i 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^', a_3) to a_3, (a_1, a_3^') to a_1, (a_2, a_3^') to a_2. 
    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 _0^0. 


In the NOT gadget (see Figure <ref>), edge (a_1, a_1^') represents the input of the NOT gate, and edge (a_2, a_2^') represents the output. 
The following claim shows that the NOT gadget correctly simulates the NOT gate. 


    In every _0^0 allocation on the NOT gadget, edge (a_2, a_2^') is allocated to a_2^' if and only if edge (a_1, a_1^') is allocated to a_1.


    If (a_1, a_1^') is allocated to a_1, (a_1, a_2) must be allocated to a_2 since otherwise a_1^' will envy a_1 even after removing (a_1, a_2) from a_1's bundle. 
    Furthermore, (a_2, a_2^') must be allocated to a_2^'. 
    By symmetry, if (a_1, a_1^') is allocated to a_1^',  (a_2, a_2^') must be allocated to a_2. 
    When (a_1, a_1^') is allocated to a_1 and (a_2, a_2^') is allocated to a_2^', allocating the edges clockwise produces an _0^0 allocation. 
    When (a_1, a_1^') is allocated to a_1^' and (a_2, a_2^') is allocated to a_2, allocating the edges counterclockwise produces an _0^0 allocation. 


In the WIRE gadget (see Figure <ref>), edge (a_1, a_1^') represents the input of the wire of a circuit, and edge (a_2, a_2^') represents the output. 
Since the only difference between the NOT gadget and the WIRE gadget is that the labels of a_2 and a_2^' are exchanged, we have the following claim that shows the WIRE gadget correctly simulates the wire in the circuit. 


    In every _0^0 allocation on the WIRE gadget, edge (a_2, a_2^') is allocated to a_2 if and only if edge (a_1, a_1^') is allocated to a_1.


In the TRUE terminator gadget (see Figure <ref>), edge (a_2, a_2^') is allocated to a_2 in every _0^0 allocation. 


    In every _0^0 allocation on the TRUE terminator gadget, edge (a_2, a_2^') is allocated to a_2.


    For the sake of contradiction, suppose that (a_2, a_2^') is allocated to a_2^'. 
    In this case, (a_1, a_2^') must be allocated to a_1, and (a_1^', a_2^') must be allocated to a_1^'. 
    Otherwise, a_2 will envy a_2^' even after removing one edge except (a_2, a_2^') from a_2^''s bundle. 
    Then neither a_1 nor a_1^' can receive  (a_1, a_1^'), a contradiction. 
    This is because the endpoint agent that receives (a_1, a_1^') will be envied by the other even after removing one edge except (a_1, a_1^') from her bundle. 
    When (a_2, a_2^') is allocated to a_2, allocating (a_1, a_1^') to a_1, (a_1^', a_2) and (a_1^', a_2^') to a_1^', (a_1, a_2^') to a_2^' produces an _0^0 allocation. 


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 <ref> shows the graph constructed from a simple circuit with one AND gate, two inputs and one final output.
Note that Proposition <ref> still applies to the graph we construct. 

Up to now, it is not hard to see the correctness of Theorem <ref>. 


    To prove Theorem <ref>, we show that the circuit has a satisfying assignment if and only if the constructed graph has an ^0_0 allocation. 
    For one direction, we assume that there exists an assignment of the inputs such that the final output of the circuit is True and use the assignment to create an allocation as follows: for each input, if it is set to True in the assignment, allocate the corresponding edge to the upper endpoint; otherwise, allocate the edge to the lower endpoint. 
    Allocate the edge that simulates the final output to the upper endpoint. 
    Allocate the remaining edges in each gadget according to Claims <ref> to <ref>. 
    Clearly, the allocation is _0^0. 
    
    For the other direction, we assume that there exists an _0^0 allocation in the constructed graph and use the allocation to create an assignment as follows: for each input, if the corresponding edge is allocated to the upper endpoint, set the input to True; otherwise, set the input to False. 
    By Claim <ref>, the edge that simulates the final output must be allocated to the upper endpoint. 
    Therefore, by Claims <ref> to <ref>, the assignment makes the final output of the circuit True. 





    Our reduction borrows an idea from the reduction by <cit.> (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. 




 §.§ _-^0 Allocations


We next study _-^0 and have the following theorem. 

    For any graph, an _-^0 allocation always exists and can be computed in polynomial time. 

 
We first introduce some notations. 
Given a (partial) allocation 𝐗  = (X_1, …, X_n), let R(𝐗) denote the set of unallocated edges, i.e., R(𝐗) = M ∖⋃_a_i ∈ NX_i.
We say an agent a_j is safe for another agent a_i if a_i does not envy a_j even if a_j receives all her unallocated incident edges that are not chores for her, i.e., v_i(X_i) ≥ v_i(X_j ∪ (E_i^≥ 0∩ R(𝐗))). 
We next introduce some properties of allocations. 


    We say that a (partial) allocation 𝐗 satisfies
    
        

        
  * property (1) if for every agent a_i, the value of her bundle is at least the largest value among her unallocated incident edges that are not chores for her. That is, v_i(X_i) ≥ v_i(e) for every edge e ∈ E_i^≥ 0∩ R(𝐗);
        

        
  * property (2) if for every envied agent a_i, the value of her bundle is at least the value of all her unallocated incident edges that are not chores for her. That is, v_i(X_i) ≥ v_i(E_i^≥ 0∩ R(𝐗)); 
        

        
  * 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_i^≥ 0 for any a_i ∈ N and e ∈ X_i; 
        

        
  * property (5) if every envied agent a_i receives exactly one edge, i.e., |X_i| = 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 a_i_0← a_i_1←⋯← a_i_s such that a_i_l envies a_i_l-1 for every l ∈ [s] and i_0 = i_s; 
        

        
  * property (8) if for any sequence of agents a_i_0← a_i_1←⋯← a_i_s such that  a_i_l envies a_i_l-1 for every l ∈ [s] and a_i_s is non-envied, we have that a_i_l is safe for a_i_0 for every l ∈ [s].
        

    


We obtain an ^0_- allocation in two parts. 

Part 1. 
In the first part, we compute a (partial) ^0_- orientation that satisfies properties (1)-(8) in Definition <ref>. 
Our algorithms in this part are adapted from those by <cit.>. 
There are two differences between our algorithms and <cit.>'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 <cit.> 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 algorithms and proofs can be seen in Appendix <ref>. 


    For any graph, a (partial) ^0_- orientation that satisfies properties (1)-(8) in Definition <ref> 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: 

    

    
  * G_1 contains each edge that has at least one non-envied endpoint agent for whom the edge is not a chore;
    

    
  * G_2 contains each edge that has two envied endpoints; 
    

    
  * G_3 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; 
    

    
  * G_4 contains the edges that have not been included in G_1, G_2, G_3. 
    Notice that each edge in G_4 is a chore for both its endpoint agents. 
    




We will allocate the unallocated edges from G_1 to G_4 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 ^0_- during the allocation process. 
Specifically, 
 
    

    
  * For each edge in G_1, we allocate it to the non-envied endpoint agent for whom it is not a chore.
    

    
  * For each edge in G_2, we allocate it to the non-envied agent who is safe for both its endpoint agents. 
    

    
  * For each edge e_i, j in G_3, we consider three cases. 
    Without loss of generality, let a_i be the endpoint agent for whom e_i, j is not a chore and a_j be the other one for whom it is a chore. 
    First, a_i becomes non-envied. Similar to the allocation of G_1, we allocate the edge to a_i. 
    Second, there exists a non-envied agent a_k ≠ a_j who is safe for a_i. Similar to the allocation of G_2, we allocate e_i, j to a_k. 
    Third, a_j is the only non-envied agent who is safe for a_i. 
    By property (8), it must be the case that there exists a sequence of agents a_i_0← a_i_1←⋯← a_i_s such that  a_i_l envies  a_i_l-1 for every l ∈ [s], a_i_0 is a_i and a_i_s is a_j. 
    For this case, we allocate e_i, j to a_i_s-1. 
    

    
  * For G_4, 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 a_i and a_j such that a_i is envied by a_j and a_j is non-envied. 
    We allocate the edges in G_4 that are incident to a_j (i.e., E_j ∩ G_4) to a_i, and the other edges in G_4 (i.e., G_4 ∖ E_j) to a_j.
    



We have the following lemma in Part 2. 


    For any graph, given a (partial) ^0_- orientation that satisfies properties (1)-(8) in Definition <ref>, we can compute an ^0_- allocation in polynomial time. 


    Each edge in G_1 is allocated to the non-envied endpoint agent for whom the edge is not a chore.
    This does not incur new envy, since the other endpoint agent of the edge prefers her own bundle to the edge by property (1). 
    Each edge in G_2 is allocated to a non-envied agent who is safe for both its two endpoint agents. 
    By property (3), such a non-envied agent exists. 
    Since the non-envied agent is safe for both the two endpoint agents, no new envy occurs, either. 
    Moreover, during the allocation of G_1 and G_2, no agent receives an edge that is a chore for her and no envied agent receives an edge, thus the new (partial) allocation is still ^0_- and retains properties (4)-(7). 
    Since no agent gets worse off and no allocated edge becomes unallocated, properties (1) and (2) are retained. 
    Furthermore, since no edge that was allocated to some agent is reallocated to another agent, an agent who is safe for some agent is always safe for that agent and thus properties (3) and (8) are retained. 

    For each edge e_i, j in G_3, without loss of generality, let a_i be the endpoint agent for whom e_i, j is not a chore and a_j be the other one for whom e_i, j is a chore.
    There are three cases: 
    
    
        

        
  * First, a_i now becomes non-envied. For this case, we allocate e_i, j to a_i. 
        By the same reasoning we made when allocating the edges in G_1, the new (partial) allocation is still ^0_- and does not break properties (1)-(8). 
        

        
  * Second, there exists a non-envied agent a_k ≠ a_j who is safe for a_i. 
        For this case, similarly to the allocation of G_2, we allocate e_i, j to a_k. 
        Although a_k may not be safe for a_j, allocating e_i, j to a_k does not make a_j envy a_k since e_i, j is a chore for a_j. 
        Therefore, by the same reasoning we made when allocating the edges in G_2, the new (partial) allocation is still ^0_- and does not break properties (1)-(8). 
        

        
  * Third, a_j is the only non-envied agent who is safe for a_i. 
        Since there is no envy cycle among the agents by property (7), there exists a sequence of agents a_i_0← a_i_1←⋯← a_i_s such that  a_i_l envies  a_i_l-1 for every l ∈ [s], a_i_s is non-envied and a_i_0 is a_i. 
        Then a_i_s must a_j. 
        Otherwise, by property (8), a_i_s is safe for a_i, which contradicts the assumption of this case. 
        For this case, we allocate e_i, j to a_i_s-1. 
        Clearly, property (4) still holds. 
        By property (8), a_i_s-1 is safe for a_i. 
        Besides, since e_i, j is a chore for a_j, allocating e_i, j to a_i_s-1 does not incur new envy. 
        Notice that although a_i_s-1 is envied, allocating e_i, j to her does not make the (partial) allocation not ^0_- since she is only envied by a_j by property (6) and e_i, j is a chore for a_j. 
        Therefore, the new (partial) allocation is still ^0_- and retains properties (6) and (7). 
        Since no agent gets worse off and no allocated edge becomes unallocated, properties (1) and (2) are retained. 
        Furthermore, since no edge that was allocated to some agent is reallocated to another agent, an agent who is safe for some agent is always safe for that agent and thus properties (3) and (8) are retained. 
        

    

    At last, we allocate the edges in G_4, each of which is a chore for both its endpoint agents. 
    If no agent is envied in the new (partial) allocation, we allocate each edge in G_4 to an agent who is not its endpoint and obtain an envy-free allocation. 
    If some agent is envied, we first find two agents a_i and a_j such that a_i is envied by a_j and a_j is non-envied. 
    We are able to find such two agents since there is no envy cycle among the agents by property (7). 
    Since no new envy occurs during the allocation of G_1, G_2 and G_3, a_j envied a_i in the (partial) orientation computed in Part 1 and thus e_i, j was allocated to a_i in Part 1 and is not in G_4. 
    We allocate the edges in G_4 that are incident to a_j (i.e., E_j ∩ G_4) to a_i, and the other edges (i.e., G_4 ∖ E_j) to a_j. 
    Although a_i is envied, she can receive the edges in E_j ∩ G_4 since she is only envied by a_j according to property (6) and these edges are chores for their endpoint agents (including a_j).
    a_j can receive the edges in G_1 ∖ E_j since she is non-envied and these edges are not incident to her and thus are dummies for her. 
    Therefore, the final allocation is still ^0_-. 
    Clearly, the whole allocation process runs in polynomial time and we complete the proof. 


By Lemmas <ref> and <ref>, it is clear that Theorem <ref> holds. 











 §.§ _0^+ Allocations


Finally, we study _0^+ and have the following theorem. 

    For any graph, an _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 envy-free 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 _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 a_i, each edge she receives is a good for her, and at most one edge that each other agent a_j receives is a good for her.
After removing the good from a_j's bundle, a_i does not envy a_j. 
Thus, the allocation is _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 _0^+ for the agent we find. 
When there exists an agent a_i to whom the total value of her incident edges is non-negative (i.e., v_i(E_i) ≥ 0), we let a_i 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 a_i receives all her incident edges whose total value is non-negative, the allocation is _0^+ for her. 

However, when the total value of the incident edges is negative to every agent (i.e., v_i(E_i) < 0 for every a_i), we cannot simply allocate all incident edges to an agent as above, since the allocation may not be _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 e_i, j that is not a chore for a_i, 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 a_i 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 a_j receive all her unallocated incident edges that are goods for her, as well as a_i'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 above allocation process is provided in Algorithm <ref>. 



Now we are ready to prove Theorem <ref>. 


    Clearly, Algorithm <ref> runs in polynomial time. 
    It remains to show that the computed allocation is _0^+. 
    We consider two cases: 

    Case 1: there exists an agent a_i such that v_i(E_i) ≥ 0.
    
    In this case, no edge remains unallocated at the end of the algorithm. 
    To see this, the incident edges of a_i, as well as those that are not incident to a_i and are not goods for any of their endpoint agents, are allocated to a_i.
    The remaining edges are goods for at least one of their endpoint agents and are allocated to those endpoint agents. 
    
    For agent a_i, she receives a non-negative value since she receives all her incident edges whose total value is non-negative to her and other edges she receives are not incident to her and are dummies for her. 
    Thus, each other agent receives a bundle that has a value of 0 to a_i and a_i does not envy them. 
    For each a_j ≠ a_i, each edge that she receives is a good for her (if exists) and each other agent receives at most one edge that is a good for her. 
    Thus a_j does not envy others after removing the good from their bundles and the allocation is ^+_0. 

    Case 2: v_i(E_i) < 0 for every agent a_i.
    
    In this case, no edge remains unallocated at the end of the algorithm, either. 
    To see this, the edges that are incident to a_i and are not chores for a_i, as well as those that are not incident to a_i and are not goods for any of their endpoint agents, are allocated to a_i. 
    The edges that are incident to a_i but are not goods for any of their endpoint agents are allocated to a_j. 
    The remaining edges are goods for at least one of their endpoint agents and are allocated to those endpoint agents. 

    For agent a_i, she receives a non-negative value since she only receives her incident edges that are not chores for her and other edges she receives are not incident to her and are dummies for her. 
    Thus, each other agent receives a bundle that has a non-positive value to a_i and a_i does not envy them. 
    For each agent a_k ≠ a_i or a_j, each edge that she receives is a good for her (if exists) and each other agent receives at most one edge that is a good for her. 
    Therefore, the allocation is ^+_0 for a_k. 
    It remains to consider agent a_j. 
    a_j does not envy each agent a_k ≠ a_i or a_j, since a_j does not receive any edge that is a chore for her and thus receives a non-negative value, and a_k does not receive any edge that is a good for a_j and thus her bundle has a non-positive value to a_j. 
    If the edge (a_i, a_j) is a chore for a_j, a_j does not envy a_i, either, since a_i does not receive any edge that is a good for a_j. 
    If (a_i, a_j) is not a chore for a_j, the tie-breaking rule implies that each edge in the graph either is not a chore for any of its endpoint agents, or is a chore for both its endpoint agents. 
    Thus, all a_j's incident edges that are chores for a_j are allocated to a_i. 
    Since v_j(E_j) < 0, a_i's bundle has a negative value to a_j and a_j does not envy a_i. 
    Therefore, the allocation is ^+_0. 


Since any _-^0 or _0^+ allocation is also ^+_-, we have the following corollary. 

    For any graph, an ^+_- allocation always exists and can be computed in polynomial time. 




§ 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. 

plainnat




§ APPENDIX




§ A DISCUSSION ON GOODS AND CHORES INSTANCES

 
There are two variants of EFX for goods instances in the literature, i.e., ^0 and ^+, which require that any envy could be eliminated after virtually removing any item from the envied agent's bundle that has a non-negative or a strictly positive marginal value to the envious agent, respectively. 
Formally, 

    An allocation 𝐗 = (X_1, …, X_n) is ^0 if for every two agents a_i, a_j ∈ N such that a_i envies a_j and any e ∈ X_j such that v_i(X_j ∖{e}) ≤ v_i(X_j), 
    we have v_i(X_i) ≥ v_i(X_j ∖{e}). 



    An allocation 𝐗 = (X_1, …, X_n) is ^+ if for every two agents a_i, a_j ∈ N such that a_i envies a_j and any e ∈ X_j such that v_i(X_j ∖{e}) < v_i(X_j), we have v_i(X_i) ≥ v_i(X_j ∖{e}). 


For goods instances, <cit.> studied ^0 in their work and proved that determining whether ^0 orientations exist or not is NP-complete. 
Our reduction in Theorem <ref> provides an alternative proof to this result.
It is easy to compute an ^+ orientation by allocating each edge to one of its endpoint agents. 
Since for each agent, she receives a non-negative value and each other agent receives at most one of her incident edges, the orientation is ^+. 
<cit.> also showed that an ^0 allocation always exists and can be computed in polynomial time, which also holds for ^+ allocations since any ^0 allocation is also ^+. 

There are also two variants of EFX for chores instances in the literature, i.e., _0 and _-, which require that any envy could be eliminated after virtually removing any item from the envious agent's bundle that has a non-positive or a strictly negative marginal value to her. 
Formally, 

    An allocation 𝐗 = (X_1, …, X_n) is _0 if for every two agents a_i, a_j ∈ N such that a_i envies a_j and and any e ∈ X_i such that v_i(X_i ∖{e}) ≥ v_i(X_i), we have v_i(X_i ∖{e}) ≥ v_i(X_j). 



    An allocation 𝐗 = (X_1, …, X_n) is _- if for every two agents a_i, a_j ∈ N such that a_i envies a_j and any e ∈ X_i such that v_i(X_i ∖{e}) > v_i(X_i), we have v_i(X_i ∖{e}) ≥ v_i(X_j). 


For chores instances, an _0 or _- orientation may not exist. 
Consider a connected graph where there are more edges than vertices and each edge is a chore for both its two endpoint agents. 
By the pigeonhole principle, there must exist an agent who receives more than one edge. 
After removing one edge from her own bundle, she still receives a negative value and envies the other endpoint agents of the edges she receives.  
We next show that we can determine whether an _- orientation exists or not in polynomial time. 
To achieve this, we first allocate each edge to an endpoint agent for whom it is a dummy (if exists) and remove these edges from the graph. 
We can do this since _- does not consider dummies in the envious agent's bundle. 
After this step, each unallocated edge is a chore for both its endpoint agents. 
We then compare the number of unallocated edges and agents in each connected component of the graph. 
If there exists a connected component where the number of unallocated edges is larger than that of agents, we can conclude that there does not exist an _- orientation. 
This is because by the pigeonhole principle, at least one agent receives more than one chore. 
If the number of unallocated edges is at most that of agents for every connected component, we can compute an _- orientation by allocating at most one chore to each agent. 
We note that whether the existence of an _- orientation can be determined in polynomial time remains as an open problem. 
We conjecture that it is NP-complete. 
At last, an envy-free allocation can be computed by allocating each edge to an agent who is not its endpoint, which is also _0 and _-. 



§ COMPUTING A (PARTIAL) ^0_- ORIENTATION THAT SATISFIES PROPERTIES (1)-(8) IN DEFINITION <REF>


In this section, we show how to compute a (partial) ^0_- orientation that satisfies properties (1)-(8) in Definition <ref>. 
We achieve this in two steps. 



 §.§ Step 1: Computing an Initial (Partial) Orientation 𝐗^1


We first construct an initial (partial) orientation 𝐗^1 by letting each agent pick one incident edge (if it exists) that she values the most among those that have not been allocated and are not chores for her. 
Once an agent picks an edge, the other endpoint agent of the edge will be the next to pick an edge.
The formal description is provided in Algorithm <ref>. 
It is easy to see that the following claim holds. 


    The initial (partial) orientation 𝐗^1 computed in Step 1 is ^0_- and satisfies properties (1) and (4)-(7) in Definition <ref>. 
    Moreover, it is computed in polynomial time. 


    Clearly, Algorithm <ref> runs in polynomial time. 
    Since each agent receives at most one incident edge that is not a chore for her, 𝐗^1 is ^0_- and satisfies properties (4)-(6). 
    Since each agent picks the edge that she values the most among those that have not been allocated and are not chores for her, 𝐗^1 satisfies properties (1) and (7). 




After Step 1, either Step 2-1 or Step 2-2 will be executed, depending on whether 𝐗^1 satisfies properties (2) and (3). 



 §.§ Step 2-1: Computing the Desired (Partial) Orientation if 𝐗^1 does not Satisfy Property (2)




Since 𝐗^1 does not satisfy property (2), there exists an envied agent a_i, for whom her bundle is less valuable than the unallocated incident edges that are not chores for her (i.e., v_i(X_i^1) < v_i(E_i^≥ 0∩ R(𝐗^1))). 
We allocate all edges in E_i^≥ 0∩ R(𝐗^1) to a_i and release the edge she received in 𝐗^1, which may break property (1). 
In order to regain property (1), for any agent who prefers an unallocated incident edge to her current bundle, we allocate the unallocated edge to the agent and release all edges she received previously. 
We repeat the above process until property (2) is satisfied. 
The formal description is provided in Algorithm <ref>. 
We have the following claim. 




    Taking as input a (partial) orientation that is ^0_- and satisfies properties (1) and (4)-(7) in Definition <ref>, Algorithm <ref> computes a (partial) orientation that is ^0_- and satisfies properties (1)-(7) in polynomial time. 


    Clearly, no agent receives an edge that is a chore for her in Algorithm <ref>, thus property (4) always holds. 
    We next show by induction that properties (1) and (5)-(7) always hold at the end of each round of the outer while-loop.
    Assume that at the beginning of a round, these four properties hold. 
    Let a_i be the agent who makes the algorithm enter the outer while-loop and a_j be the agent who envies a_i. 
    
    By property (5), a_i only owned e_i, j at the beginning of the round. 
    In the outer while-loop, a_i receives all edges in E_i^≥ 0∩ R(𝐗^') and releases e_i, j. 
    Since the value of E_i^≥ 0∩ R(𝐗^') to a_i is larger than that of e_i, j, property (1) holds for a_i. 
    Besides, the other endpoint agents of the edges in E_i^≥ 0∩ R(𝐗^') do not envy a_i since property (1) was satisfied for them at the beginning of the round. 
    Since a_i gets better off, she does not envy the agents whom she did not envy previously. 
    Therefore, the new (partial) orientation retains properties (5)-(7) after a_i gets her new bundle. 
    
    After a_i releases e_i, j, property (1) does not hold for a_j, and the algorithm enters the inner while-loop. 
    In the inner while-loop, a_j receives e_i, j and releases the edges she owned previously. 
    The value of e_i, j to a_j is larger than the total value of the edges a_j owned previously, and is larger than the value of each of these edges since none of them are chores for a_j by property (4). 
    Furthermore, since property (1) held for a_j at the beginning of the round, the value of e_i, j to a_j is larger than the value of each of a_j's incident edges that were unallocated at the beginning of the round and are not chores for her. 
    Thus, property (1) holds for a_j. 
    Besides, no one envies a_j since she only receives the edge e_i, j and a_i now prefers her own bundle to e_i, j. 
    Since a_j gets better off, she does not envy the agents whom she did not envy previously. 
    Therefore, the new (partial) orientation retains properties (5)-(7) after a_j gets her new bundle. 
        
    If a_j was non-envied at the beginning of the round of the outer while-loop, each agent prefers her own bundle to the edge between herself and a_j that a_j releases. 
    Therefore, the round ends and properties (1) and (5)-(7) hold. 
    If a_j was envied by some agent, property (1) is not satisfied for that agent and the algorithm enters the inner while-loop again. 
    By the same reasoning, properties (1) and (5)-(7) hold after that round of the inner while-loop. 
    By induction, properties (1) and (5)-(7) hold at the end of the the round of the outer while-loop. 
    Therefore, by induction, properties (1) and (5)-(7) hold at the end of the algorithm. 

    Next, we show that properties (2) and (3) hold at the end of the algorithm. 
    Observe that the agents who receive new bundles during the algorithm become non-envied, and the agents who were non-envied previously are still non-envied since no new envy occurs during the algorithm. 
    Therefore, the algorithm can terminate in polynomial time, and we have property (2) at the end. 
    To see property (3), let a_k be the agent who makes the algorithm enter the last round of the outer while-loop and a_l be the agent involved in the first round of the inner while-loop in that round. 
    At the end of that round, both a_k and a_l are non-envied, and a_l only receives e_k, l. 
    By property (2), a_l is safe for all envied agents and property (3) holds. 

    The (partial) orientation is ^0_- since for each agent, the edges that she receives are not chores for her by property (4), and each other agent receives at most one of her incident edges. 
    Therefore, we complete the proof. 











 §.§ Step 2-2: Computing the Desired (Partial) Orientation if 𝐗^1 Satisfies Property (2) but not (3)


Since 𝐗^1 does not satisfy property (3), there exist two envied agents a_i and a_j such that no non-envied agent is safe for both of them. 
Let a_i_0← a_i_1←⋯← a_i_s be the sequence of agents such that a_i_0 is a_i, a_i_l envies a_i_l-1 for every l ∈ [s] and a_i_s is non-envied, which exists since there is no envy cycle among the agents by property (7). 
Similarly, let a_j_0← a_j_1←⋯← a_j_t be the sequence of agents such that a_j_0 is a_j, a_j_l envies a_j_l-1 for every l ∈ [t] and a_j_t is non-envied. 
We first consider the following case: 

Case 1: e_i, i_s is allocated to a_i_s in 𝐗^1. 

Since each agent receives at most one edge in 𝐗^1, a_i_s only receives e_i, i_s and does not receive any incident edge of a_j. 
Thus, a_j values a_i_s's bundle at zero and by property (2), a_i_s is safe for a_j.
According to our assumption, a_i_s is not safe for a_i; that is, v_i({e_i, i_s}∪ (E_i^≥ 0∩ R(𝐗^1))) > v_i(X_i^1). 
For this case, we allocate the edges in E_i^≥ 0∩ R(𝐗^1) as well as e_i, i_s to a_i, and e_i_l-1, i_l to a_i_l for every l ∈ [s]. 
Figure <ref> visualizes the allocation process. 
We have the following claim. 





    The (partial) orientation computed in Case 1 of Step 2-2 is ^0_- and satisfies properties (1)-(7) in Definition <ref>. 
    Moreover, it is computed in polynomial time. 


    Clearly, the allocation process runs in polynomial time. 
    The (partial) orientation is ^0_- and satisfies property (4) since for each agent, the edges that she receives are not chores, and each other agent receives at most one of her incident edges. 
    We then show that the (partial) orientation satisfies properties (1), (2) and (5)-(7). 
    Observe that the agents who receive new bundles in the allocation process become non-envied. 
    To see this, first consider a_i. 
    Since 𝐗^1 satisfies property (1), the other endpoint agents of the edges in E_i^≥ 0∩ R(𝐗^1) do not envy a_i. 
    Besides, a_i_s does not envy a_i, since she prefers the edge she owns currently (i.e., e_i_s-1, i_s) to e_i, i_s. 
    For each l ∈ [s], a_i_l is non-envied, since a_i_l-1 prefers her current bundle to e_i_l-1, i_l. 
    Also observe that these agents do not envy the agents who they did not envy previously since they get better off.
    These two observations give that the new (partial) orientation still satisfies properties (5)-(7). 
    Moreover, since no agent gets worse off and no edge that was allocated previously becomes unallocated, properties (1) and (2) are still satisfied. 
    Since a_i_1 receives only the edge between herself and a_i_0 who is non-envied, by property (2), she is safe for all envied agents. 
    Therefore, property (3) is also satisfied and we complete the proof. 


When e_j, j_t is allocated to a_j_t, we can also construct a (partial) orientation that is ^0_- and satisfies properties (1)-(7), following the same process as above. 
Therefore, it remains to consider the case where e_i, i_s is not allocated to a_i_s and e_j, j_t is not allocated to a_j_t. 
In this case, a_i values a_i_s's bundle at zero, and thus a_i_s is safe for her. 
This implies that a_i_s is not safe for a_j; that is, a_i_s receives e_j, i_s in 𝐗^1 and v_j({e_j, i_s}∪ (E_j^≥ 0∩ R(𝐗^1))) > v_j(X_j^1). 
Similarly, a_j_t is not safe for a_i, a_j_t receives e_i, j_t in 𝐗^1 and v_i({e_i, j_t}∪ (E_i^≥ 0∩ R(𝐗^1))) > v_i(X_i^1). 
Figure <ref> illustrates the initial (partial) orientation regarding these agents. 
We further consider the following two cases: 



Case 2: a_i prefers e_i, j to e_i, j_t or is indifferent between them

For this case, we let a_i receive the incident edge (if exists) that she values the most among those that are not allocated and are not chores for her (i.e., E_i^≥ 0∩ R(𝐗^1)). 
We then allocate e_i_l-1, i_l to a_i_l for every l ∈ [s] and release e_j, i_s. 
Figure <ref> illustrates the new (partial) orientation. 
Note that the new (partial) orientation may not satisfy property (2), since some agents who were non-envied are now envied by a_i and the incident edge e_i_s, j of a_j that was allocated now becomes unallocated. 
The good news is that we can prove that the new (partial) orientation is ^0_- and satisfies properties (1) and (4)-(7). 
Therefore, we can run Algorithm <ref> to obtain a (partial) orientation that is ^0_- and satisfies properties (1)-(7). 
We have the following claim. 




    The (partial) orientation computed in Case 2 of Step 2-2 is ^0_- and satisfies properties (1)-(7) in Definition <ref>. 
    Moreover, it is computed in polynomial time. 


    Recall that by Claim <ref>, the initial (partial) orientation 𝐗^1 is ^0_- and satisfies properties (1) and (4)-(7). 
    We first show that the new (partial) orientation as illustrated in Figure <ref> is also ^0_- and satisfies properties (1) and (4)-(7). 
    Since no agent receives an edge that is a chore for her in the allocation process, property (4) holds.
    Moreover, for each agent, each other agent receives at most one of her incident edges, thus the new (partial) orientation is ^0_-. 
    To see property (1), it suffices to consider agents a_i, a_j and a_i_l for l ∈ [s], since only a_i and a_i_l for l ∈ [s] receive a new bundle in the allocation process, and only a_j has an incident edge that was allocated previously but now becomes unallocated. 
    For a_i, if she does not receive an edge, then all her unallocated incident edges are chores for her, thus property (1) holds for her. 
    If she receives an edge, then the edge is the one she values the most among those in E_i^≥ 0∩ R(𝐗^1), thus property (1) also holds for her. 
    For each l ∈ [s-1], a_i_l does not get worse off and her unallocated incident edges do not change, thus property (1) also holds for a_i_l. 
    For the same reason, both a_i_s and a_j prefer their current bundles to each of their unallocated incident edges except e_i_s, j, which is the only edge that was allocated previously but is now unallocated. 
    For a_i_s, she prefers her current bundle to e_i_s, j since she envied a_i_s-1  previously and now owns the edge e_i_s-1, i_s. 
    For a_j, she prefers her current bundle to e_i_s, j since she did not envy a_i_s previously. 
    Thus, property (1) also holds for both of them. 
    
    Now consider properties (5)-(7), first observe that except a_i_1, the agents who receive new bundles are now non-envied (i.e., a_i and a_i_l for each l ∈ [s] ∖{1}). 
    To see this, since 𝐗^1 satisfies property (1), the other endpoint agent of the edge that a_i receives (if it exists) does not envy a_i. 
    For each l ∈ [s] ∖{1}, a_i_l is non-envied by since a_i_l-1 prefers her current bundle to e_i_l-1, i_l. 
    Since each agent receives at most one edge, properties (5) and (6) still hold. 
    For property (7), since a_i is the only agent who may become worse off, the only agents who were non-envied previously and now become envied and who were envied by some agent and are now envied by another agent are all a_i's neighbors. 
    Each of them is envied by a_i who is now non-envied, thus there is still no envy cycle among the agents and property (7) still holds. 
    
    Clearly, the allocation process for Case 2 of Step 2-2 runs in polynomial time. 
    If the new (partial) orientation satisfies property (2), it also satisfies property (3). 
    To see this, consider a_i and a_j_t. 
    Since the edge that a_i owns currently is the one she values the most among those in E_i^≥ 0∩ R(𝐗^1) (including e_i, j) and she prefers e_i, j to e_i, j_t, she does not envy a_j_t. 
    Moreover, since a_j_t only receives the edge between herself and a_i who is now non-envied, a_j_t is safe for all envied agents and property (3) holds. 
    If the new (partial) orientation does not satisfy property (2), we run Algorithm <ref> once. 
    By Claim <ref>, the final (partial) orientation is ^0_- and satisfies properties (1)-(7), and is computed in polynomial time. 


Case 3: a_i prefers e_i, j_t to e_i, j

For this case, we allocate all edges in E_j^≥ 0∩ R(𝐗^1) as well as e_j, i_s to a_j, e_j_l-1, j_l to a_j_l for every l ∈ [t], and e_i_l-1, i_l to a_i_l for every l ∈ [s]. 
We then release e_i, j_t and let a_i receive the incident edge (if it exists) that she values the most among those that are not allocated and are not chores for her. 
Figure <ref> illustrates the new (partial) orientation. 
Similar to Case 2, the new (partial) orientation may not satisfy property (2), since some agents who were non-envied are now envied by a_i. 
But we can prove that the new (partial) orientation is ^0_- and satisfies properties (1) and (4)-(7). 
Therefore, after running Algorithm <ref>, we can obtain a (partial) orientation that is ^0_- and satisfies properties (1)-(7). 
We have the following claim. 




    The (partial) orientation computed in Case 3 of Step 2-2 is ^0_- and satisfies properties (1)-(7) in Definition <ref>. 
    Moreover, it is computed in polynomial time. 


    The proof is similar to that of Claim <ref>. 
    We first show that the new (partial) orientation is ^0_- and satisfies properties (1) and (4)-(7). 
    Since no agent receives an edge that is a chore for her in the allocation process, property (4) holds.
    Moreover, for each agent, each other agent receives at most one of her incident edges, thus the new (partial) orientation is ^0_-. 
    To see property (1), first consider a_i. 
    If a_i does not receive an edge, then all her unallocated incident edges are chores for her, thus property (1) holds for her. 
    If she receives an edge, the edge is the one that she values the most among her unallocated incident edges that are not chores for her, thus property (1) also holds for her. 
    For each l ∈ [s], a_i_l gets better off and her unallocated incident edges do not change, thus property (1) holds for her. 
    For the same reason, property (1) also holds for a_j_l for each l ∈ [t-1]. 
    For a_j, all her incident edges that are not chores for her are allocated, thus property (1) holds for her. 
    For a_j_t, although e_i, j_t was allocated to her previously but is now unallocated, she prefers her current bundle to e_i, j_t since she envied a_j_t-1 and now owns the edge e_j_t, j_t-1. 
    Thus property (1) also holds for a_j_t. 
    Therefore, the new (partial) orientation retains property (1). 
    
    To see properties (5)-(7), first observe that except a_i_1, the agents who receive new bundles are now non-envied. 
    To see this, since 𝐗^1 satisfies property (1), the other endpoint agent of the edge that a_i receives (if it exists) does not envy a_i. 
    For each l ∈ [s] ∖{1}, a_i_l is non-envied since a_i_l-1 prefers her current bundle to e_i_l-1, i_l. 
    For the same reason, for each l ∈ [t], a_j_l is non-envied. 
    For a_j, a_i_s does not envy her since a_i_s prefers e_i_s-1, i_s to e_j, i_s. 
    The other endpoint agents of the edges in E_j^≥ 0∩ R(𝐗^1) do not envy her, either, since 𝐗^1 satisfies property (1). 
    Since only a_j receives more than one edge and she is now non-envied, properties (5) and (6) still hold.
    For property (7), since a_i is the only agent who may become worse off, the only agents who were non-envied previously and now become envied and who were envied by some agent and are now envied by another agent are all a_i's neighbors. 
    Each of them is envied by a_i who is now non-envied, thus there is still no envy cycle among the agents and property (7) still holds. 
    
    If the new (partial) orientation satisfies property (2), it also satisfies property (3). 
    To see this, consider a_j and a_j_1. 
    Since a_j_1 only receives the edge between herself and a_j who is non-envied, a_j_1 is safe for all envied agents and property (3) holds. 
    If the new (partial) orientation does not satisfy property (2), we run Algorithm <ref> once. 
    By Claim <ref>, the final (partial) orientation is ^0_- and satisfies properties (1)-(7), and is computed in polynomial time. 


Now we are ready to prove Lemma <ref>. 

    By Claims <ref>, <ref>, <ref>,  <ref>, <ref>, we know that a (partial) orientation that is ^0_- and satisfies properties (1)-(7) can be computed in polynomial time. 
    If it also satisfies property (8), then we have done. 
    
    If the (partial) orientation does not satisfy property (8), then there exists a sequence of agents a_i_0← a_i_1←⋯← a_i_s such that  a_i_l envies a_i_l-1 for every l ∈ [s] and a_i_s is non-envied, we have that a_i_l is not safe for a_i_0 for some l ∈ [s]. 
    By property (5), for each l ∈ [s-1], agent a_i_l only receives e_i_l, i_l+1 and does not receive any incident edge of a_i_0. 
    Thus by property (2), a_i_l is safe for a_i_0. 
    The only case that property (8) is not satisfied is that a_i_s receives e_i_s, i_0 and is not safe for a_i_0. 
    For this case, we run the same allocation process for Case 1 of Step 2-2, as illustrated in Figure <ref>. 
    Specifically, we allocate e_i_s, i_0 to a_i_0 as well as all her unallocated incident edges that are not chores for her, and allocate e_i_l-1, i_l to a_i_l for every l ∈ [s]. 
    The above allocation process is repeated until property (8) is satisfied. 
    By the same reasonings in the proof of Claim <ref>, all the involved agents become non-envied, and ^0_- and properties (1)-(7) in Definition <ref> are retained. 
    Therefore, the allocation process is repeated for polynomial times and gives a (partial) ^0_- orientation that satisfies properties (1)-(8). 


