EF1 and EFX Orientations

1 Introduction

The allocation of a set of indivisible goods to a set of agents in a way that is considered to be "fair" is a problem that has been studied since ancient times. Since envy-free allocations - no agent prefers the bundle of any other agent over their own - for indivisible goods are not always guaranteed to exist, in recent decades mathematicians, economists, and computer scientists formally studied the problem and have proposed several different fairness solution concepts [Lipton et al., 2004; Bouveret and Lang, 2008; Budish, 2011; Caragiannis et al., 2019b].

Arguably, EF1 and EFX are the two solution concepts that have received the majority of attention in the literature and have created a long stream of work. An allocation is EF1, if it is envy-free up to one good, i.e., any envy from one agent i to some agent j is eliminated by removing a specific item from the bundle of agent j. On the other hand, an allocation is EFX if it is envy-free up to any good, i.e., any envy towards agent j is eliminated by removing any item from j's bundle. While EFX is a stronger fairness notion, it is unknown whether it always exists; this is one of the main open problems in fair division. On the other hand, EF1 allocations are always guaranteed to exist and in fact, we can efficiently compute such an allocation via the envy-cycle elimination algorithm [Lipton et al., 2004].

However, both EF1 and EFX allow for allocations that can be considered "counterintuitive" in the best case, or wasteful in the worst. Consider for example the case where we have two agents, X and Y , and three items, a, b, and c. The valuations of X for a, b, c are 1, 1, 0.2 respectively, while the valuations of Y are 0, 1, 0. Observe now that the allocation that gives X item a and Y items b and c is both EFX and EF1. Still, giving item c to agent Y seems rather unreasonable since item c is "irrelevant" to agent Y ! Luckily for us, this issue can be fixed by giving item c to X instead. But is such a "fix" always possible? In other words, does a fair allocation always exist under the constraint that every agent gets goods from a restricted set, i.e., a subset of goods that they approve? This is the question we answer in this paper.

Our work is inspired by the recent paper of Christodoulou et al. [2023] that studies valuations on graphs. In that model, an instance of the problem is represented via a graph whose vertices correspond to agents with additive utilities and the edges correspond to goods. There, each agent had positive utility only for the goods that corresponded to edges incident to their vertex, i.e., only those goods were relevant to them. The value of an agent for every other good, non-incident to their vertex, was zero.

Christodoulou et al. studied the existence and complexity of finding EFX allocations and EFX orientations. An orientation is an allocation where every agent gets only edges adjacent to them, i.e., every edge is "oriented" towards the incident agent that gets it. Christodoulou et al. showed something really interesting. They have shown that albeit EFX allocations always exist for this model and they can be computed in polynomial time, EFX orientations fail to exist and in fact, the corresponding problem is NP-complete even for binary, additive and symmetric valuations for the agents.

1.1 Our contribution

Our contribution is twofold: (a) we initiate the study of EF1 orientations; (b) we examine EFX orientations through the lens of parameterized complexity.

Our main result is to prove that an EF1 orientation always exists when the valuations of the agents are monotone! In fact, we prove our result for a more general model than the one from Christodoulou et al. [2023], where instead of graphs, we consider hypergraphs, i.e., the goods now correspond to hyperedges. In other words, each agent has a subset of goods that are relevant to them. We prove our result algorithmically (Theorem 1). The base of our algorithm is the well-known envy-cycle elimination algorithm [Lipton et al., 2004], although it requires two careful modifications to indeed produce an orientation. The first modification is almost straightforward: every item is allocated to an agent that is incident to it. The second modification is required after we swap the bundles of some agents when we resolve an envy cycle. After the swap, an agent might get goods that are not relevant to them. If this is the case, we remove any irrelevant items from all the bundles of the partial allocation and we redistribute them. However, a priori it is not clear whether this procedure will ever terminate. As we prove via a potential argument, the procedure indeed terminates, albeit in pseudopolynomial time.

Then, we derive polynomial-time bounds for several different valuation classes as direct corollaries of our main theorem, or via a slight modification of the algorithm. Namely, our base algorithm finds an EF1 orientation in polynomial time if every agent has a constant number of relevant items (Corollary 1), or when there exists a constant number of "local" item-types (Corollary 2). In addition, via straightforward modifications of the base algorithm, we can efficiently compute EF1 orientations for identical valuations (Theorem 2), or when the relevant items of the agents form laminar sets (Corollary 3).

For EFX orientations, we begin by showing two strong negative results. Firstly, we show that it is NP-complete to decide whether an EFX orientation exists even on graphs with vertex cover of size 10, even when the valuations are additive and symmetric (Theorem 3). This result rules out the possibility of fixed-parameter algorithms for a large number of graph parameters. Furthermore, we show that if we consider multigraphs instead of graphs, i.e., we allow parallel edges, finding an EFX orientation is NP-hard even when we have 8 agents with symmetric and additive valuations (Theorem 4). We complement these intractability results with a fixed parameter algorithm, for which the analysis is rather involved, parameterized by the slim tree-cut width of the underlying graph; this is essentially the best result someone could hope for, given our previous results.

Due to space constraints, some details, marked with ⋆, are omitted and are available in the supplementary material.

1.2 RelatedWork

The recent survey by Amanatidis et al. [2023] provides a comprehensive coverage of work on fair division of indivisible goods. In this section, we direct the reader to some other papers, in particular, that study EFX or EF1 and restrict the instance in different ways.

As aforementioned, the question of whether EFX always exists is a well-known open question in Fair Division. Currently, we have that Plaut and Roughgarden [2020] prove EFX always exists for 2 agents. For 3 agents already this question is much harder, Chaudhury et al. [2024] prove that EFX exists for 3 agents but with additive valuations, and recently Akrami et al. [2024] prove a result for 3 agents where only 1 of these agents requires additive valuations (and the other 2 agents have MMS-feasible valuations). The paper by Goldberg et al. [2023] studies the intractability of EFX with just two agents. They find that even with a small instance like this, it quickly becomes intractable as the valuations become more general - namely computing an EFX allocation for two identical agents with submodular valuations is PLS-hard 1 . However, they propose an intuitive greedy algorithm for EFX allocations for weakly well-layered valuations; a class of valuations which they introduce. An example of relaxation of EFX that has been studied is EFkX, envy freeness up to k goods, Akrami et al. [2022] study EF2X and prove existence in some restricted settings. A recent paper by Zhou et al. [2024] studies EFX allocations in the mixed setting on graphs, where agents only have valuations for edges adjacent to them and these can be positive or negative. They treat orientations as a special case of their problem and show that deciding if an EFX orientation exists is NP-complete. The paper by Payan et al. [2023] also studies graph restrictions but these are subtly different to that of Christodoulou et al.. In this model, edges are not items but instead, they are where EFX (/other fairness notions) must apply, intuitively this aims to capture a model where we want envy freeness between an agent and some of their neighbors. Some studies look at EFX where we (may) decide to leave some items unallocated. We refer to this as EFX with charity, [Caragiannis et al., 2019a; Chaudhury et al., 2021], where not all items are allocated and these leftover items are said to be "given away to charity". Moreover, Caragiannis et al. [2019b] introduces EFX0 and Kyropoulou et al. [2020] studies this. An allocation satisfies EFX0 if for one agent i they are not envious of any other agent j's bundle after removing any item for which agent i doesn't have a positive value. Moreover, another model which may be of interest is that of connected fair division - originally introduced by Bouveret et al. [2017] and more recently Deligkas et al. [2021] studies this under the lens of parameterized complexity - in which there are some items which cannot be separated i.e. have some connectivity constraints.

2 Preliminaries

Throughout the paper we consider A = {a1, a2, . . . , am} to be a set of indivisible items and N = {1, 2, . . . , n} to be a set of agents. An allocation π = (π1, π2, . . . , πn) is a partition of the items into n (possibly empty) sets which we refer to as bundles. Thus, πi ∩ πj = ∅ for every i ̸= j and ⋃i∈N πi = A, where the bundle πi is allocated to agent i. For an item a ∈ A, we denote by π(a) the agent who receives item a in the allocation π. We refer to an allocation of a subset of items as a partial allocation.

Every agent i ∈ N has a valuation function Vi that assigns a value Vi(S) for every subset S ⊆ A, where Vi(∅) = 0. Vi is non-negative if for all S ⊆ A it holds Vi(S) ≥ 0; Vi is monotone if for all S′ ⊂ S it holds Vi(S′ ) ≤ Vi(S); Vi is additive if there exist non-negative values vi1, vi2, . . . , vim such that for every S ⊆ A it holds Vi(S) = ∑j∈S vij .

1 For the definition of PLS see Johnson et al. [1988].

For an allocation π and two agents i, j ∈ N, we say that i envies j or alternatively that there is envy from i towards j if Vi(πj) > Vi(πi). An allocation is fair if envy can be eliminated in some particular way.

Definition 1 (EF1). An allocation π is envy-free up to one item (EF1), if for every pair of agents i, j ∈ N there exists an item a ∈ πj such that Vi(πi) ≥ Vi(πj \ {a}).

Definition 2 (EFX). An allocation π is envy-free up to any item (EFX), if for every pair of agents i, j ∈ N and every a ∈ πj it holds that Vi(πi) ≥ Vi(πj \ {a}).

Relevant items. We say that an item a is relevant for an agent i if there is a set S of items such that Vi(S\a) < Vi(S). For every agent i, we will denote the set of items relevant to i by Ai. Similarly, for every item a, we let Na = {i ∈ N | a ∈ Ai} be the set of agents to which a is relevant, we will also call Na the agent list of a. We say that items a and b belong to the same group if Na = Nb. Throughout the paper we assume that the union of all relevant sets is the set of items or, in other words, every item is relevant for at least one agent.

Orientations. Using relevant items, we can define a subset of all possible allocations, that we call orientations. Formally, an allocation π = (π1, π2, . . . , πn) is called an orientation if πi ⊆ Ai for all i ∈ N. In other words, in an orientation, the bundle of an agent contains only relevant items. For ϕ ∈ {EF1, EFX}, we say that an allocation π is a ϕ orientation if it is an orientation and in addition, it satisfies the corresponding fairness definition.

Parameterized Complexity. An instance of a parameterized problem Q ⊆ Σ×N, where Σ is fixed and finite alphabet, is a pair (I, k), where I is an input of the problem and k is a parameter. The ultimate goal of parameterized algorithmics is to confine the exponential explosion in the running time of an algorithm for some NP-hard problem to the parameter and not to the instance size. The best possible outcome here is the so-called fixed-parameter algorithm with running time f(k) · |I|O(1) for any computable function f. That is, for every fixed value of the parameter, we have a polynomial time algorithmwhere the degree of the polynomial is independent of the parameter. For a more comprehensive introduction to parameterized complexity, we refer to the monograph of Cygan et al. [2015].

3 EF1 Orientations for Monotone Valuations

In this section we establish the existence of EF1 orientations when agents have monotone valuations via the construction of a pseudopolynomial-time algorithm and we identify several sub-classes of valuation functions for the agents where our algorithm, or a slight modification of it, finds an EF1 orientation in polynomial time.

Let Vi be a valuation function of an agent. The maximal range of Vi is the number of different values of a bundle assigned by Vi, i.e., |{Vi(S) | S ⊆ A}|.

Theorem 1. When agents have monotone valuations, an EF1 orientation always exists and can be computed in time O (mn3 r) where r is the maximal range size of Vi, i ∈ N.

Algorithm 1 EF1 orientations for monotone valuations

Input: Set of items A, set of agents N, valuations Vi, sets of relevant items Ai, i ∈ N, agent lists Na, a ∈ A

Output: EF1 orientation π

• 1: Let π = (π1, . . . , πn) such that πi = ∅ for all i ∈ N.
• 2: Let Gπ = (N, ∅) be a directed graph ( an "envy-graph" of π)
• 3: while ∃ item a that is not in any πi do
• 4: Let i ∈ Na be an agent such that i is a source-vertex in G[Na].
• 5: Let πi = πi ∪ {a}
• 6: for j ∈ Na \ {i} do
• 7: if Vj(πj) < Vj(πi) then
• 8: Add the edge from j to i if it does not exist.
• 9: end if
• 10: end for
• 11: Call Algorithm2 with π andGπ to eliminate all cycles in Gπ .
• 12: end while
• 13: return π

Algorithm 2 Eliminating cycles in the envy-graph

Input: partial allocation π with an envy-graph Gπ Output: partial allocation π′ with Vi(π′i ) ≥ Vi(πi), i ∈ N, such that Gπ′ does not contain directed cycles

• 1: while ∃ a directed cycle C = (i1, i2, . . . , iℓ) in Gπ do
• 2: for all j ∈ [ℓ - 1] do
• 3: Let π′ij = πij+1 ∩Aij
• 4: end for
• 5: π′iℓ = πi0 ∩Aiℓ
• 6: Let π = π′
• 7: Recompute Gπ
• 8: end while
• 9: return π

Proof. A full pseudo-code of the algorithm is given in Algorithm 1. The algorithm is inspired by the envy-cycle elimination algorithm by Lipton et al. [2004]. Similarly to that algorithm, we are computing the allocation π iteratively starting from an empty (partial) allocation keeping an envy graph Gπ, which is a graph whose vertex set is precisely the set of agents N and there is a directed edge from i to j if in the allocation π the agent i envies the agent j. In addition, we will be preserving that π is an EF1 (partial) allocation such that πi ⊆ Ai for all i ∈ N. For the ease of the presentation of the proof, we will say that a pair of agents i, j satisfy EF1property if Vi(πj) ≤ Vi(πi) or there exists a ∈ πj such that Vi(πj \ {a}) ≤ Vi(πi).

While the algorithm by Lipton et al. greedily picks any source-vertex i in Gπ (that is a vertex without any edge pointing towards it; so no agent in N envies agent i for its bundle in π) and allocates to i an arbitrary item, this would not work for us, as the remaining items might not be relevant for the source vertices of Gπ. Instead, we first pick an unassigned item a that needs to be assigned and give it to an agent i that is a source in the subgraph of Gπ induced by the agents in the set Na that are allowed to receive that item. Hence, the item a is irrelevant for any agent j that envies i before allocating the item a. Therefore, these steps preserve both that πi ⊆ Ai for all i ∈ N and that for all i, j ∈ N the pair i, j satisfies EF1-property.

Furthermore, in order to always find a source-vertex in this induced subgraph of the envy graph, we also need to be able to eliminate cycles in Gπ. An algorithm for eliminating all cycles in Gπ is described in Algorithm 2. Let C = (i1, i2, . . . , iℓ) be a cycle such that the agent ij envies the bundle of the agent ij+1 for j ∈ [ℓ - 1] and the agent iℓ envies the bundle of the agent i1. Similarly to Lipton et al., we shift the bundles in the opposite direction of the cycle, which is known to eliminate the envy on the cycle and does not create any new envy. However, after we execute this shift of bundles, the bundle of an agent i on the cycle could contain some items that are not in the set Ai of their relevant items. So we remove from the bundle of the agent i any item that is not relevant for them. Note that this does not change the valuation of i for its bundle. Let us denote by π the allocation before the cycle-elimination step and by π′ the allocation after the cycle-elimination step. As we already discussed, for all i ∈ N we have Vi(π′i ) ≥ Vi(πi) (the value either increased or the bundle did not change). Now let i, j ∈ N. We know that for all j ∈ N, the pair i, j satisfies EF1-property in π. It follows that if π′j = πj, then i, j satisfies EF1-property as well. Else π′j ⊆ πk for some k ∈ N. It follows from monotonicity of the valuation that Vi(π′j ) ≤ Vi(πk) and Vi(π′j \ a) ≤ Vi(πk \ a) for all a ∈ πk and so the pair i, j also satisfies the EF1-property in π′ .

It follows from the above discussion and from the fact that Algorithm 1 stops only when all items have been allocated that whenever Algorithm 1 stops it returns an EF1 orientation. It only remains to show that the algorithm terminates.

Let us consider the vector W π = (V1(π1), V2(π2)), . . . , Vn(πn)). By definition, each coordinate W π i of the vector W π has at most r ≤ 2m many possible values. In addition, in each cycle-elimination step all the coordinates corresponding to the agents on the cycle strictly increase and the remaining coordinates of W π do not change. Similarly, adding item a to agent i on line 5 of Algorithm 1 does not decrease any of the coordinates because of the monotonicity of the valuations. Since every coordinate can increase its value only r - 1 times, it follows that there are less than n · r many cycle elimination steps in total, each can be executed in O(nm) time. Between any two cycle-eliminations we can only add less than m items after each addition of an item, we need to update Gπ and check whether a cycle is created, which can be easily done in O(|V (Gπ)| + |E(Gπ)|) = O (n2 ) time. Putting everything together, Algorithm 1 runs in O (nr · (nm+mn2 )) = O (mn3 r)) time.

Note that if the number of relevant items for each agent is constant and bounded by some ℓ ∈ N, then the number of possible bundles for each agent and hence the range r of its valuation function Vi is bounded by 2ℓ . Therefore, Theorem 1 immediately implies the following corollary.

Corollary 1. For monotone valuations, computing an EF1 orientation is fixed-parameter tractable parameterized by the number of relevant items per agent, l and can be computed in time O (mn3 · 2l ).

3.1 Local item-types

While in Corollary 1, the number of relevant items per agent is small, our algorithm provided in Theorem 1 can be applied to compute an EF1 orientation in polynomial time in much more general settings. For instance, if the range of each valuation has size at most md for some constant d, the running time is upper-bounded by O (md+1n3 ).

One natural example of such valuations is as follows. Assume that each agent subdivides all items relevant to them into d groups (which we will refer to as local item-types) and only distinguishes items that are in different groups. In this case, the valuation each agent has for their bundle depends only on the number of received items from each local itemtype. Since each of the d groups contains at most m items, there are at most md possibilities for their value.

Corollary 2. For monotone valuations, computing an EF1 orientation is XP parameterized by d, the number of local item-types per agent, and can be computed in time O (md+1n3 ).

In general, when the range size of Vi is unbounded, we still can distinguish some settings for which the described algorithm (or its slight modification) is polynomial.

3.2 Identical valuations

While strictly speaking, identical valuations would mean that all items have to be relevant for all agents, we relax this notion slightly to better fit with the intended meaning of the relevant items as a restriction of the item an agent is allowed to receive.

Definition 3. A set of agents have identical valuations if there exists a function V such that for every agent i their valuation function is defined by Vi(B) = V(B ∩ Ai) for every B ⊆ S.

Similarly to the standard setting where agents with identical valuations cannot create envy cycles, we can show that the same is the case even with this relaxed definition of identical valuations and we obtain the following theorem.

Theorem 2. An EF1 orientation can be computed in linear time when agents have identical monotone valuations.

Proof. We will show that it is not possible to have a cycle in the envy graph. That is that when we run Algorithm 1, then whenever Algorithm 2 is called as a subroutine, the condition on line 1 in Algorithm 2 is always false and it returns the same partial allocation.

For the sake of a contradiction, assume that C = (i1, i2, . . . , iℓ) is a cycle in the envy-graph for some partial allocation π such that πi ⊆ Ai. That is the agent ij envies the agent ij+1 for all j ∈ [ℓ-1] and the agent iℓ envies the agent i1. Let V be the function such that for all i ∈ N and for all B ⊆ A we have V⟩(B) = V(B ∩ Ai). Since, πi ⊆ Ai for all i ∈ N it follows that Vi(πi) = V(πi) for all i ∈ N and Vi(πj) = V(πj ∩ Ai) and by monotonicity Vi(πj) ≤ V(πj). It follows that

which is a contradiction. Therefore, Algorithm 1 only has to assign every item a once to a source-vertex in Gπ[Na], without ever running Algorithm 2 which takes linear time O(mn).

3.3 Laminar agent lists

The final setting for which we get a polynomial time algorithm is when items are arranged in some kind of hierarchical structure, where the most common items can be assigned to any agent and then we have more and more specialized items that only a smaller and smaller group of agents can get. One can think about it like this: agents need to undergo some training and which items you are allowed to receive depends on your specialization and on the amount of training you already received.

Definition 4. We say that agent lists Na, a ∈ A, are laminar if for any two items a1 and a2 it holds that either Na1 ∩Na2 = ∅ or one of the sets is a subset of another, i.e. Na1 ⊆ Na2 or Na2 ⊆ Na1

Corollary 3. For the monotone valuations with laminar agent lists, an EF1 orientation can be computed in time O (m2n).

Proof. Recall that the algorithm described in the proof of Theorem 1 picks undistributed items in random order. Here, instead of this, if the agent lists are laminar, we order the items in a tuple (a1, . . . , am) so that either Nj ∩ Nk = ∅ or Nk ⊆ Nj whenever 1 ≤ j < k ≤ m. In the algorithm, we will pick items exactly in this order. Consider the moment when a new item a is allocated. Then shifting items along the cycle in Ga will never result in allocating illegal items. Indeed, if some item b was moved to agent i ∈ Na, then Na ∩ Nb ̸= ∅. Since b was allocated before a, we conclude that Na ⊆ Nb and hence i ∈ Nb.

Therefore, each item is moved from not distributed to distributed precisely once, and potential cycle elimination afterwards takes time at most O(mn), so the EF1 orientation is computed in time at most O (m2n).

4 EFXOrientations

The paper by Christodoulou et al. [2023] proves that it is NP-complete to decide if an EFX orientation exists. We strengthen this result, by showing it is NP-hard even when the graph has constant vertex cover.

Theorem 3. Deciding whether an EFX orientation exists on graph G is weakly NP-hard even when G has a vertex cover of constant size.

Proof. We show a reduction from the NP-complete problem PARTITION. An instance of partition consists of a multiset S of positive integers. Let T be the number of elements in S. Let ∑Tt=1 St = 2B. Given S we want to decide if the elements can be divided into two subsets S1 and S2 such that the sum of elements in S1 is equal to that of S2. Given an instance of PARTITION, we will construct a graph G = (V, E). We start by constructing a bipartite graph such that there is a vertex (i.e. an agent) for every element in S on one side, call them x1, · · · , xT , and two additional vertices i and j on the other. Now we will create the edges, where |E| = m, the number of items and weights on edges are the valuation of that item for the agents on both endpoints. For all vertices xv ∈ {x1, x2..., xT } we create an edge (i, xv) of weight Sv and an edge (j, xv) of weight Sv. We create two copies of gadget X, we will call these X1 and X2. Gadget X is a clique on 4 vertices based on Example 1. in [Christodoulou et al., 2023] that has no EFX orientation on its own. Let the vertices in the gadget Xh be Xh1 to Xh4 . Edges (Xh1,Xh2) and (Xh3,Xh4) have weight B. All other edges in Xh have weight 1. Finally, we create edges (i,X11) and (j,X21) of weight B. This completes the construction, see Figure 1.

One can now show that in order to get an EFX orientation, the edges (i,X11) and (j,X21) have to be allocated to X11 and X21, respectively. In addition, the only way to satisfy all the remaining agents in the gadgets X1 and X2, both X11 and X21 need to receive additional edge of value 1. Hence in order for both i and j to be satisfied, they each need to value their bundle at least B. Since to achieve this both i and j need to receive more than just one edge, each of agents xk for k ∈ [T ] has to receive at least one of its incident edges. Therefore, the only way for the graph G to admit EFX orientation is if the elements associated with the edges allocated to i and the elements associated with the edges allocated to j form a partition of S.

Theorem 4 (⋆). Deciding whether an EFX orientation exists on a multigraph G is weakly NP-hard even when G has a constant number of vertices.

Proof Sketch. We begin with a construction very similar to that of Theorem 3. The only difference is that instead of creating a set of vertices x1 · · · xT we will create T many edges between vertices i and j, see Figure 2.

4.1 Slim tree-cut width and the FPT algorithm

Examining the hardness of Christodoulou et al., we can see that their reduction can be made to work on graphs with constant maximum degree. In combination with Theorem 3, this shows that efficient algorithms for deciding the existence of EFX orientations are unlikely already for very restricted settings. In this section, we show an efficient algorithm for a setting that is basically on the limit of tractability from the point of view of parameterized complexity (in a sense, that more general parameters studied so far would contain some of the hard instances).

As follows from our reduction, deciding whether EFX orientation exists in the graph setting is hard, even when the underlying graph has constant vertex cover and tree-cut width. In particular, this rules out most of the vertex-separator based parameters. However, we show that the recently introduced parameter slim tree-cut width (also equivalent to super edgecut width, see [Ganian and Korchemna, 2024]) allows us to achieve tractability.

For simplicity, here we work with super edge-cut width. For a graph G and a spanning tree T of G, let the local feedback edge set at v ∈ V be EG,T loc (v) = {uw ∈ E(G)\E(T) | the unique path between u and w in T contains v}.

Definition 5. The edge-cut width of the pair (G, T) is ecw(G, T) = 1+maxv∈V |EG,T loc (v)|, and the edge-cut width of G (denoted ecw(G)) is the smallest edge-cut width among all possible spanning trees T of G.

If in the last definition, we allow to choose the spanning tree in any connected supergraph of G, this leads to the notion of super edge-cut width (denoted by sec(G)):

Super edge-cut width is a strictly more general parameter than degree+treewidth and feedback edge number, but it is more restrictive than tree-cut width [Ganian and Korchemna, 2024].

Theorem 5 (⋆). Deciding whether an EFX orientation exists for a given graph G is fixed-parameter tractable if parameterized by the slim tree-cut width of G.

4.2 Proof of Theorem 5

Let H be the supergraph of G with the spanning tree T such that sec(G) = ecw(H, T) = k. For the rest of the proof, we root T in some arbitrary fixed vertex. We begin by recalling some basic properties of the super edge-cut width, in particular, we adapt the related notion of the boundary of a vertex, firstly introduced in [Ganian and Korchemna, 2021] for a weaker parameter.

For v ∈ V (T), let Tv be the subtree of T rooted at v, let Vv = V (G∩ Tv), and let ¯ Vv = NG(Vv) ∪ Vv. We define the boundary δ(v) of v to be the set of endpoints of all edges in G with precisely one endpoint in Vv (observe that the boundary can never have a size of 1). A vertex v of T is called closed if |δ(v)| ≤ 2 and open otherwise.

Observation 1 ([Ganian and Korchemna, 2021]). Let v be a vertex of T . Then:

1. δ(w) = {v,w} for every closed child w of v in T, and vw is the only edge between Vw and V \ Vw in G.
2. |δ(v)| ≤ 2k +2.
3. Let {vi|i ∈ [t]} be the set of all open children of v in T. Then t ≤ 2k and δ(v) ⊆ ∪ti=1 δ(vi) ∪ {v} ∪ NG(v).

We can now define the records that will be used in our dynamic program. Intuitively, these records will be computed in a leaf-to-root fashion and will store at each vertex v information about possible EFX orientations for the subtree of T rooted at v.

Let R be a binary relation on δ(v), and S a subset of δ(v).

Definition 6. We say that (R, S) is a record at vertex v if there exists an orientation D of G restricted to vertices in ¯ Vv and edges with at least one endpoint in Vv such that:

1. The partial allocation defined by D is EFX between any two vertices in Vv.
2. R is the set of all arcs of D that have precisely one endpoint in Vv.
3. For every w ∈ δ(v), if there is envy from some vertex u ∈ Vv towards w in D then w ∈ S.
4. The in-degree of every w ∈ S in D is equal to one.

We call such a digraph D a partial solution at v. We say that D is a witness of the record (R, S). Denote the set of all records for v by R(v), then |R(v)| ≤ 2O(k2 ) .

Intuitively, the set S in a record is intended to capture all the vertices of δ(v) towards which there can be envy in the resulting solution. This is why we require all the vertices in S to have the in-degree of one. Otherwise, there would be a possibility to remove items without changing the envy: note that the only relevant item for both agents is their shared edge.

Note that if vi is a closed child of v, then by Observation 1, R(vi) can contain only the records ({viv}, ∅), ({viv}, {v}), ({vvi}, ∅) and ({vvi}, {vi}). The root r of T contains at most one record (∅, ∅), which happens if and only if the instance is a YES instance (otherwise R(r) = ∅).

Observation 2 (⋆). Let vi be a closed child of v.

• If ({viv}, ∅) ∈ R(vi), then ({viv}, {v}) ∈ R(vi),
• if ({vvi}, {vi}) ∈ R(vi), then ({vvi}, ∅) ∈ R(vi).

Lemma 6 (⋆). Let v ∈ V (G) have c > 0 children in T , and assume we have computed R(vi) for each child vi of v. Then R(v) can be computed in time at most 2O(k3 ) · c.

Proof sketch. Without loss of generality, let the open children of v ∈ V (G) be v1, . . . , vt, then t ≤ 2k by Point 3 of Observation 1. Let C be the set of remaining (closed) children of v, i.e. C = {vt+1, . . . , vc}. Denote Vi = Vvi , ¯ Vi = ¯ Vvi , i ∈ [c], and V0 = δ(v) \ ∪ci=1Vi. Note that all Vi, i ∈ [c]0, are pairwise disjoint. If the record set of some child is empty, we conclude that R(v) = ∅. Otherwise, we branch over all choices of (Ri, Si) ∈ R(vi) for each individual open child vi of v. We also branch over all orientations R0 of edges {uv|u ∈ V0}.

Let R′ = ⋃j∈[t]0 Rj. We branch over subsets S0 of V0 \ {v} with precisely one incoming arc in R′ . Let S′ =

⋃j∈[t]0 Sj, if R′ is not anti-symmetric or contains two different arcs u1w and u2w for some w ∈ S′ , we discard this branch. We also discard it if Vi ∩ S′ ̸= Vi ∩ Si for some i ∈ [t]. Otherwise, we create a trial record (R, S), where R is the restriction of R′ to those arcs which have precisely one endpoint in Vv and S = S′ ∩ δ(v). We branch over 4 options for the in-neighbors of v in the partial solution, and in each case try to choose suitable records for the closed children.

Case 0: no in-neighbors. If v has no in-neighbors in R′ , and every closed child vi contains the record ({vvi}, {vi}) (or ({vvi}, ∅) if Vv({viv}) = 0 ), and every w ∈ NG(v) \ C with Vv({wv}) > 0 is in S′ , we add the record (R, S).

Case 1: one open in-neighbor. If there is precisely one incoming arc uv to v in R′ , and for every closed child vi of v, R(vi) contains the record ({vvi}, ∅), let s1 = Vv({uv}). If s1 < Vv({viv}) for some vi ∈ C, and R(vi) does not contain the record ({vvi}, {vi}), we discard this case. We also discard it if s1 < Vv({wv}) for some w ∈ NG(v) \ (C ∪ S′ ). Otherwise, we add the records (R, S) and (R, S ∪ {v}).

Case 1': one closed in-neighbor. If R′ has no incoming

arcs uv to v, we model partial solutions where the unique inneighbor of v is one of its closed children. We branch over the choices of this closed child vi. For every fixed vi ∈ C such that R(vi) contains the record ({viv}, {v}), we compare si = Vv({viv}) with all the values sj over the rest of the closed children vj of v. If sj > si for some j and R(vj) does not contain the record ({vvj}, {vj}), we discard the case. We also discard it if for some j ̸= i, R(vj) does not contain ({vvj}, ∅). Otherwise, we compare si with Vv({wv}) for every w ∈ NG(v) \C. If for some w ̸∈ S′ the latter is larger, we discard the branch as well. Otherwise, we add the record (R, S ∪ {v}). If R(vi) contains the record ({viv}, ∅), we additionaly add (R, S).

Case 2: two or more in-neighbors. Finally, if v ̸∈ S′ , we model the subcase when v has more than one in-neighbor in a partial solution. For every closed child vi of v such that ({viv}, ∅) ̸∈ R(vi), vvi must be oriented towards vi. On the other hand, for every vi ∈ C such that R(vi) contains the record ({viv}, ∅), by monotonicity of Vv we can just greedily orient the edge vvi towards v. The corresponding value of v will be s = Vv({wv|wv ∈ R′ } ∪ {viv|vi ∈ C, ({viv}, ∅) ∈ R(vi)}. If there is a closed child vi such that s < Vv({viv}) and R(vi) does not contain the record ({vvi}, {vi}), we discard the branch. Moreover, if there is closed child vi such that ({viv}, ∅) ̸∈ R(vi) and ({vvi}, ∅) ̸∈ R(vi), we discard the branch. We also discard it if s < Vv({vw}) for some w ∈ NG(v) \ C such that w ̸∈ S′ . Otherwise, we add the record (R, S).

For the running time, note that we branch over the choice of at most 2k + 1 many binary relations Ri, and there are at most O(2(2k+2)2 ) ) options for every such relation, which dominates the number of possible choices of subsets Si of the boundaries. Therefore, we have at most O((2(2k+2)2 )2k+1 ≤ 2O(k3 ) branches. In each branch, we need at most linear in c time to traverse closed children of v. Hence, R(v) can be computed in time 2O(k3 ) · c.

To establish the correctness of the procedure described above, which we will refer to as CRC(v) (combining records of children of v), we prove the following two claims:

Claim 1 (⋆). If (R∗ , S∗ ) ∈ R(v), then CRC(v) adds it.

This concludes the proof of Lemma 6.

5 Discussion and Open Problems

The focus of this paper was the existence and complexity of EF1 and EFX orientations of goods, i.e., allocations that satisfy the corresponding fairness criterion and in addition, every agent gets items from their own predetermined set. In contrast to EFX orientations, which do not always exist and if they do it is almost always hard to find one, we have shown that EF1 orientations do exist and can be computed. Hence, EF1 orientations, in addition to fairness constraints, preserve some economic efficiency as well; however in Christodoulou et al. [2023] it was shown that EFX does not have the latter property, as in specific cases it has to give goods to agents that do not value them at all.

We conclude by highlighting some intriguing open problems that deserve further investigation.

From a purely theoretical point of view, the complexity of finding an EF1 orientation is open. Can we compute such an orientation in polynomial time? We currently do not know the answer even for three agents- for two agents the problem is easy. Alternatively, is the problem hard for some complexity class? Our proof indicates that the problem belongs to PLS, however, showing hardness is an intriguing question.

What about EF1 allocations that satisfy other types of constraints? Our results show existence under "approval" constraints for the agents. A different option would be to consider cardinality constraints for the agents, i.e., every agent should get a specific number of items. A version of this model was studied by Caragiannis and Narang [2024] and the existence of EF1 allocations is an open problem.

Moreover, in this paper we show weak NP-hard for EFX orientations where we have a small vertex cover. This leaves open whether we can compute if an EFX orientation exists when the weights are given in unary, i.e. can we find a pseudo-polynomial time algorithm? (However do note that, Caragiannis and Narang [2024] show that this is strongly NPhard even for instances with constant max degree.)

The definition of EFX that both Christodoulou et al. [2023] and this paper has adopted, assumes that the envy should be eliminated by removing any item from an envied bundle. However, someone can study the relaxed notion of EFX+; recall in EFX+ the envy should be eliminated by removing any item that changes the value of the envied bundle. Our preliminary investigation shows that indeed this is a promising direction. We have identified some classes of (graph-based) monotone valuations where a natural generalization of EFX+ always exists and can be computed efficiently. This raises the natural question about for which classes of valuation functions EFX+ allocations are guaranteed to exist.

Acknowledgements

Argyrios Deligkas acknowledges the support of the EPSRC grant EP/X039862/1.