Extending EFX Allocations to Further Multi-Graph Classes

Bhaskar, Umang; Pandit, Yeshwant

doi:10.4230/LIPIcs.FSTTCS.2025.15

Extending EFX Allocations to Further Multi-Graph Classes

Umang Bhaskar

Tata Institute of Fundamental Research, Mumbai, India Yeshwant Pandit

Tata Institute of Fundamental Research, Mumbai, India

Abstract

The existence of EFX allocations is one of the most significant open questions in fair division. Recent work by Christodoulou, Fiat, Koutsoupias, and Sgouritsa (“Fair allocation in graphs,” EC 2023) establishes the existence of EFX allocations for graphical valuations, when agents are vertices in a graph, items are edges, and each item has zero value for all agents other than those at its endpoints. Thus, in this setting, each good has non-zero value for at most two agents, and there is at most one good valued by any pair of agents. This marks one of the few cases when an exact and complete EFX allocation is known to exist for more than three agents.

In this work, we partially extend these results to multi-graphs, when each pair of vertices can have more than one edge between them. The existence of EFX allocations in multi-graphs is a natural open question given their existence in simple graphs. We show that EFX allocations exist, and can be computed in polynomial time, for agents with cancelable valuations in the following cases: (i) bipartite multi-graphs, (ii) multi-trees with monotone valuations, and (iii) multi-graphs with girth $(2t-1)$ , where $t$ is the chromatic number of the multi-graph. The existence of EFX in cycle multi-graphs follows from (i), (iii), and the known existence of EFX for three agents.

Keywords and phrases:

Fair Division, EFX, Multi-graphs

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Algorithmic game theory

Related Version:

arXiv version: https://arxiv.org/abs/2412.06513

Funding:

Both authors acknowledge the support of the Department of Atomic Energy, Government of India, under project no. RTI4001.

DOI:

10.4230/LIPIcs.FSTTCS.2025.15

Event:

45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025)

Editors:

C. Aiswarya, Ruta Mehta, and Subhajit Roy

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

In discrete fair division, we are given a set of indivisible items and a set of agents, with the goal of allocating the items fairly among the agents. Various formalisations of fairness have been studied in the literature, of which the most popular is envy-freeness, which requires that no agent prefers another’s allocation to its own. However, envy-free allocations may not always exist, leading to extensive work on relaxations of envy-freeness. In this paper, we study the existence and computation of allocations that are envy-free up to any item, or EFX, in instances that can be represented as multi-graphs. The question of whether EFX allocations exist in general instances is possibly the most tantalizing open question in the fair allocation of resources, and many recent papers have focused on this question, leading to proofs of its existence in ever-larger classes of instances.

In our work, a fair division instance consists of a set of items that is to be allocated to a set of agents, with each item allocated to a single agent. Each agent has a monotone nondecreasing value function over the set of items. Given an allocation, agent $i$ envies agent $j$ if agent $i$ ’s value for its own allocation is less than its value for the set of items allocated to $j$ . An envy-free allocation is one where no agent envies another. Envy-free allocations do not exist in general, and the closest relaxation then studied is envy-freeness up to any good, or EFX. An EFX allocation allows an agent to envy another, but the removal of any item from the envied agent’s allocation should eliminate the envy as well.

EFX allocations were first studied by Caragiannis et al. [14], who established its relation to other notions of fairness, but left the question of existence open. If all agents have the same valuation, then an EFX allocation exists [25]. This can be extended to show the existence for two agents with distinct valuations. This was extended to multiple agents with two distinct additive valuations [24], then to three agents when at least one has an MMS-feasible valuation [3, 16], and recently to multiple agents with three distinct additive valuations [21]. A number of papers also study partial EFX allocations, when some items may remain unallocated, e.g., [17, 10], as well as approximately EFX allocations [5, 6, 15, 25].

Another widely studied relaxation of envy-freeness, weaker than EFX, is envy-freeness up to one item (EF1), which requires that any envy be resolved by removing some item from the envied agent’s bundle [13, 23]. Unlike EFX, EF1 allocations are known to exist for both monotone and for some non-monotone valuations [23, 7, 12, 9, 11]. Other fairness notions have also been extensively studied in the literature [4].

Given the difficulties in establishing the existence of EFX allocations, researchers study special cases of structured valuations. EFX allocations are known to exist if agents have lexicographic preferences [20]. Another such class of structured valuations is graphical valuations, when the instance can be represented as a graph [18]. Here the agents correspond to the vertices and each item is an edge. The restriction is that each item has nonzero marginal value for only the agents at its end-points, and has zero value for all other agents. Thus if $e=\{i,j\}$ , then for every other agent $k$ , and any subset $S$ of items, $v_{k}(S\cup\{e\})=v_{k}(S)$ . Further, the graph is simple, and thus there is at most one good valued by every pair of agents. For this case, when agents have monotone valuations over incident edges, Christodoulou et al. [18] show that EFX allocations exist, marking one of the rare cases where EFX allocations are shown to exist for more than three agents.

As mentioned in [18], graphical valuations model real-world scenarios with geographical constraints, where an item is only valued by nearby agents. For example, fishing rights in waters that are adjacent to two nations are such an item, valuable to the two nations but useless to others. Afshinmehr et al. [1] give the example of football matches in various formats; each match must be played at the home of one of the two teams in the match, and hence can be thought of as an item to be allocated to one of the two teams playing.

A natural question with graphical valuations is if an EFX orientation exists – an EFX allocation where goods are only allocated to agents at their endpoints. Christodoulou et al. [18] show that an EFX orientation may not exist, and it is NP-hard to determine if a given instance has an EFX orientation. Zeng and Mehta [28] characterize graphs that permit EFX orientations. Zhou et al. [29] study variants of EFX in the graphical setting, where an edge may be valued positively or negatively by its endpoints.

Given the existence of EFX in simple graphs, a natural question is if these results extend to multi-graphs when there are multiple edges between vertices (thus, pairs of agents can value multiple goods). Here a $2/3$ -approximate EFX allocation exists [5], beating the earlier bound of $0.618$ for general additive valuations [6]. EFX allocations also exist in multi-graphs with symmetrical additive valuations, i.e., when agents have additive valuations, and both agents at the endpoints of a good have the same value for the good [22]. In independent and concurrent work, Afshinmehr et al. [1, 2] show that exact EFX allocations exist in bipartite multi-graphs and cycle multi-graphs. They also characterize when EFX orientations exist in bipartite graphs, and show it is NP-hard to decide if a given instance admits an EFX orientation. Sgouritsa and Sotiriou [26] also independently present a number of results for multi-graphs when agents have general monotone valuations over their incident goods. We discuss these papers in Section 1.2.

1.1 Our Contribution

We study EFX allocations in multi-graphs and show that EFX allocations exist in large and important subclasses of multi-graphs. Our results are algorithmic, and for agents with cancelable valuations (defined in the next section), we show that an EFX allocation in these subclasses can be obtained in polynomial time. A feature of our algorithms is that they are iterative and fairly simple to state, based on the well-known cut-and-choose paradigm. While the algorithms are natural, the analysis is complicated and somewhat subtle.

1.

Firstly, we show that for bipartite multi-graphs with cancelable valuations, an EFX allocation can be obtained in polynomial time.
2.

Secondly, we show that for multi-trees, EFX allocations exist for general monotone valuations. Since multi-trees are also bipartite multi-graphs, for multi-trees with cancelable valuations, a polynomial time algorithm exists from the previous result.
3.

Lastly, we generalize the result for bipartite multi-graphs, and show that for multi-graphs with girth at least $(2t-1)$ , where $t$ is the chromatic number of the graph, EFX allocations can be obtained in polynomial time for agents with cancelable valuations, given the colour classes.¹¹1Note that approximating the chromatic number of a graph within $n^{1-\epsilon}$ for all $\epsilon>0$ is NP-hard [30]. Our algorithm here is a natural extension of the algorithm for bipartite multi-graphs, though the analysis is significantly more complicated.

Note that the chromatic number of a cycle multi-graph is $2$ for even cycles and $3$ for odd cycles. The existence of EFX allocations in even-length cycle multi-graphs follows from Result 1. The existence of EFX allocations in cycle multi-graphs of length 3 follows from prior work [16]. Result 1 implies the existence of EFX allocations in odd-length cycle multi-graphs of lengths at least 5. Hence, our work also shows the existence of EFX allocations for cycle multi-graphs of all lengths.

1.2 Comparison with Recent Work

Here, we compare our results with recent work on EFX existence in multi-graphs.

As noted earlier, Afshinmehr et al. [1, 2] independently and concurrently show the existence of EFX allocations in bipartite and cycle multi-graphs under additive valuations. Similar to earlier work [18], their algorithm for bipartite multi-graphs operates in two phases: the first constructs an EFX orientation with certain properties, and the second transforms it into a complete allocation using “safe” vertices. While their approach and analysis are somewhat involved, we present a simpler and efficient algorithm with a more straightforward analysis for cancelable valuations, which generalize additive valuations. Moreover, our algorithm for bipartite multi-graphs naturally extends to show the existence of EFX allocations in multi-graphs with chromatic number $t$ and girth at least $2t-1$ . This extension avoids the challenging case – highlighted in Section 5 of [1, 2] – where there are two envied vertices with the multi-edge between them unallocated, which poses a key difficulty in extending results to general multi-graphs. In contrast, the algorithm, as stated in Afshinmehr et al., does not immediately lend itself to any such natural extension beyond bipartite multi-graphs. Afshinmehr et al. also establish the existence of EFX in cycle multigraphs, which follows as a special case of our result for $t$ -chromatic multigraphs with girth at least $2t-1$ .

Another independent and concurrent work by Sgouritsa and Sotiriou [26] proves EFX existence for certain multi-graph classes under monotone valuations. They show that EFX allocations exist for: (i) multi-graphs where each vertex has at most $\lceil\frac{n}{4}\rceil-1$ neighbours (where $n$ is the total number of vertices), and (ii) multi-graphs with girth at least $6$ . In follow-up work on Arxiv, they extend these results to bipartite multi-graphs [27]. These results extend many of ours to monotone valuations, except for multi-graphs with chromatic number $3$ and girth $5$ (i.e., $t=3$ ), where we establish EFX existence. As in other papers [18, 1, 2], the algorithms by Sgouritsa and Sotiriou follow a multi-phase approach: the first phase computes an initial allocation (orientation) satisfying certain properties, the second aims to reduce the number of envied vertices, and the third assigns the remaining unallocated bundles to non-envied (safe) vertices who value them at zero. Our algorithms offer a different and simpler approach to those proposed in these other papers.

2 Notation and Preliminaries

Multi-graphs.

A multi-graph $G=(V,E)$ is a graph with possibly multiple edges between each pair of vertices. A function $r$ maps each edge $e\in E$ to an unordered pair of vertices, which are its endpoints. We use $E_{u,w}$ for the set of parallel edges between the vertices $u$ , $w$ (hence $E_{u,w}=E_{w,u}$ ). We define $n:=|V|$ and $m:=|E|$ . For a vertex $u$ , $N_{u}$ is the set of neighbours $\{w\in V:\,\exists e\in E,\,r(e)=\{u,w\}\}.$

Given a multi-graph, we can define paths and cycles as in simple graphs without parallel edges. A path $P=(v_{1},\ldots,v_{k})$ is a sequence of distinct vertices so that each pair of consecutive vertices are neighbours. The length of a path is one less than the number of vertices. A cycle $C=(v_{1},\ldots,v_{k-1},v_{k})$ is a sequence of distinct vertices so that each pair of consecutive vertices are neighbours, and $v_{1}$ , $v_{k}$ are neighbours.

Fair division.

In a fair division instance on a multi-graph $G=(V,E)$ , each vertex $u\in V$ corresponds to an agent $u$ , and each edge $e$ corresponds to a good. Throughout this article, we will use the terms agents and vertices interchangeably, and the terms items and edges interchangeably. Each agent $u$ has a valuation function $v_{u}:2^{E}\rightarrow\operatorname*{\mathbb{Z}}_{+}$ that maps subsets of goods to an integer value. A bundle $S\subseteq E$ is simply a subset of goods.

The multi-graph restricts the valuation functions in the following way: Each agent $u\in V$ has zero marginal value for any good not adjacent to it. Thus for a good $g$ if $u\not\in r(g)$ , then for any subset of goods $S\subseteq E$ , $v_{u}(S\cup\{g\})=v(S)$ . We say that agent $u$ values a good $g$ if $u\in r(g)$ , i.e., the edge $g$ is adjacent to $u$ , else it does not value the good $g$ . Extending this definition, we say that agent $u$ values a bundle $S\subseteq E$ if $S$ contains some good that $u$ values, else $u$ does not value the bundle $S$ .

An allocation $A=(A_{u})_{u\in V}$ is a partition of the set of items (or edges) among the agents. A partial allocation is a partition of a subset of items. An allocation $A$ is envy-free (EF) if for all agents $u$ , $w$ , $v_{u}(A_{u})\geq v_{u}(A_{w})$ . An allocation $A$ is envy-free up to any good (EFX) if for all agents $u$ , $w$ , either $v_{u}(A_{u})\geq v_{u}(A_{w})$ , or $v_{u}(A_{u})\geq v_{u}(A_{w}\setminus\{x\})$ , for all $x\in A_{w}$ . An orientation is an allocation where each item is allocated to an agent that values it (thus if $r(e)=\{u,w\}$ , then $e\in A_{u}\cup A_{w}$ ).

Given an allocation $A$ (or a partial allocation), we can define an envy graph $G_{A}$ among the agents: The vertices of $G_{A}$ are the agents, and there is a directed edge $(u,w)$ if agent $u$ envies agent $w$ , i.e., $v_{u}(A_{u})<v_{u}(A_{w})$ . Note that an envy graph is simple.

Given an allocation $A$ and the corresponding envy graph $G_{A}$ , let $C=(u_{1},u_{2},\ldots,u_{k})$ be a directed cycle in the envy graph. We use the term resolving the envy cycle $C$ to refer to the modification that exchanges bundles along the cycle: agent $u_{k}$ gets the bundle currently allocated to $u_{1}$ , and each agent $u_{i}$ gets the bundle currently allocated to $u_{i+1}$ , for $i<k$ . The modified allocation is called $A^{C}$ .

Valuation functions.

We will be interested in a few different classes of valuation functions. A valuation function $v:2^{E}\rightarrow\operatorname*{\mathbb{Z}}_{+}$ is monotone nondecreasing (or just monotone) if for every $S\subseteq E$ and $g\in E$ , $v(S\cup\{g\})\geq v(S)$ .

A monotone valuation function is cancelable if for $S$ , $T\subseteq E$ and $g\not\in S\cup T$ , if $v(S)\geq v(T)$ then $v(S\cup\{g\})\geq v(T\cup\{g\})$ . These functions were defined in prior work on EFX allocations for four agents [10]. We only consider monotone cancelable functions, and hence say cancelable to mean monotone cancelable functions. We in particular need the following two properties of cancelable functions.

Proposition 1.

Let $v$ be a cancelable function. Then given disjoint sets of goods $S_{1}$ , $S_{2}$ , $T_{1}$ , $T_{2}$ , and $v(S_{1})\geq v(T_{1})$ , $v(S_{2})\geq v(T_{2})$ , it follows that $v(S_{1}\cup S_{2})\geq v(T_{1}\cup T_{2})$ .

Proof.

By cancelability, $v(S_{1}\cup S_{2})\geq v(T_{1}\cup S_{2})$ and $v(T_{1}\cup S_{2})\geq v(T_{1}\cup T_{2})$ , and hence $v(S_{1}\cup S_{2})\geq v(T_{1}\cup T_{2})$ . $\hfill\blacktriangleleft$

For two agents with monotone valuations, EFX allocations are known to exist [25]. However, even for two agents with submodular valuations, computing an EFX allocation is PLS-complete and requires an exponential number of queries [19]. For cancelable valuations, we can compute an EFX allocation in polynomial time [8, 19].²²2The actual result holds for the more general class of weakly well-layered valuations.

Proposition 2.

For two identical agents with cancelable valuations, an EFX allocation can be computed in polynomial time.

Cut and Choose.

Cut and choose is a standard procedure to obtain an EFX allocation for two agents. Given agents $u$ and $w$ and a set of items $S$ , one agent “cuts” and the other agent “chooses”. If agent $u$ “cuts”, we assume there are two identical agents with valuation function $v_{u}$ , and use the algorithm from Proposition 2 to obtain a partition $(S^{1},S^{2})$ of $S$ that is EFX for identical agents with valuation function $v_{u}$ . Then agent $w$ “chooses” the bundle with a higher value for it, while agent $u$ is assigned the other bundle. The allocation is clearly envy-free for agent $w$ , and is EFX for agent $u$ . Note that for two agents with cancelable valuations, this gives us a polynomial time algorithm to obtain an EFX allocation.

The cut-and-choose procedure is central to our algorithm. In Section 3, when we deal with bipartite multi-graphs $G=(L\cup R,E)$ , for allocating a set of parallel edges $E_{u,w}$ with $u\in L$ , $w\in R$ , agent $w\in R$ will always cut (thus the agent in the right bipartition always cuts). In Section 5, when we deal with $t$ -chromatic multi-graphs, and partition the vertex set $V=C_{1}\cup\ldots\cup C_{t}$ where vertices in $C_{i}$ are the same colour, we think of the vertices in $C_{i}$ as being to the left of $C_{i+1}$ . For a set of parallel edges $E_{u,w}$ , as in the bipartite case, the vertex to the right will always cut.

We use $\textsc{Cut}(u,S)$ to refer to the use the algorithm from Proposition 2 to obtain a partition $(S^{1},S^{2})$ of $S$ that is EFX for identical agents with valuation function $v_{u}$ .

3 EFX Allocations in Bipartite Multi-graphs

We first show that for bipartite multi-graphs and agents with cancelable valuations, an EFX allocation always exists, and can be computed in polynomial time. Let $V=L\cup R$ be the bipartition of the vertex set. We first define some notation we will use for this case.

Structures

For each vertex $u\in L$ , we define the structure $\textrm{St}_{u}$ as the subgraph induced by $u\cup N_{u}$ . Note that since $N_{u}\subseteq R$ , all edges in $\textrm{St}_{u}$ are between $u$ and vertices in $N_{u}$ . We say $u$ is the root of the structure. Each iteration in our algorithm will resolve the structure $\textrm{St}_{u}$ , for some $u\in L$ , by which we mean that it will assign all the edges in $\textrm{St}_{u}$ . We also say that a vertex $u$ is resolved to mean that $\textrm{St}_{u}$ is resolved.

For allocating a set of parallel edges $E_{u,w}$ with $u\in L$ , $w\in R$ , agent $w\in R$ will always cut (thus the agent in the right bipartition always cuts). For each $w\in N_{u}$ , let $(E_{u,w}^{1},E_{u,w}^{2})=\textsc{Cut}(w,E_{u,w})$ be the partition of $E_{u,w}$ returned when agent $w$ cuts. Define $S_{u,w}:=\arg\max\{v_{u}(E_{u,w}^{1}),v_{u}(E_{u,w}^{2})\}$ as the bundle preferred by $u\in L$ , and $T_{u,w}:=\arg\max\{v_{w}(E_{u,w}^{1}),v_{w}(E_{u,w}^{2})\}$ as the bundle preferred by $w$ . Ties are broken arbitrarily to ensure that $S_{u,w}$ and $T_{u,w}$ are single bundles. If either agent is indifferent between the two bundles, we break ties so that $S_{u,w}\neq T_{u,w}$ . Further, we define $\bar{S}_{u,w}=E_{u,w}\setminus S_{u,w}$ and $\bar{T}_{u,w}=E_{u,w}\setminus T_{u,w}$ .

For a structure $\textrm{St}_{u}$ , we further define a favourite neighbour $f_{u}$ as follows:

f_{u}:=\arg\max_{w\in N_{u}}v_{u}(S_{u,w})\,.

We break ties arbitrarily to ensure that $f_{u}$ is a single vertex. Then $f_{u}$ is a neighbour who offers $u$ the highest-value bundle after cutting the adjacent edges. The other neighbours are simply called ordinary neighbours.

Our algorithm is then simple to describe, and is formally given as Algorithm 1. We consider the vertices in $L$ in turn. For vertex $u\in L$ , we consider the structure $\textrm{St}_{u}$ and resolve it, as follows. Each neighbour $w\in N_{u}$ cuts the bundle $E_{u,w}$ . Each ordinary neighbour $w\neq f_{u}$ gets their higher-value bundle $T_{u,w}$ . Let $\operatorname*{LO}_{u}=\bigcup_{w\in N_{u}\setminus\{f_{u}\}}\bar{T}_{u,w}$ be the union of the left-over goods from the ordinary neighbours of $u$ . For the favourite neighbour $f_{u}$ , if $S_{u,f_{u}}\neq T_{u,f_{u}}$ – both $u$ and $f_{u}$ prefer different bundles when $f_{u}$ cuts $E_{u,f_{u}}$ – then $u$ gets $S_{u,f_{u}}\cup\operatorname*{LO}_{u}$ , and $f_{u}$ gets $T_{u,f_{u}}$ . In this case, everyone gets their largest value bundle, and there is no envy. On the other hand, if $S_{u,f_{u}}=T_{u,f_{u}}$ – both $u$ and $f_{u}$ prefer the same bundle when $f_{u}$ cuts $E_{u,f_{u}}$ – then $u$ is offered the choice of $S_{u,f_{u}}$ or $\bar{S}_{u,f_{u}}\cup\operatorname*{LO}_{u}$ . If $u$ prefers the former, then it gets $S_{u,f_{u}}$ , and $f_{u}$ gets $\bar{S}_{u,f_{u}}\cup\operatorname*{LO}_{u}$ . In this case, $f_{u}$ may envy $u$ , but this is EFX. If $u$ prefers $\bar{S}_{u,f_{u}}\cup\operatorname*{LO}_{u}$ , it gets this bundle, and $f_{u}$ gets $S_{u,f_{u}}(=T_{u,f_{u}})$ . Again, in this case, there is no envy.

Algorithm 1 Bipartite-EFX.

We note the following properties of the algorithm. In each iteration of the outer for loop, a vertex $u\in L$ is chosen, and the goods in $\textrm{St}_{u}$ are assigned to the agents in $\textrm{St}_{u}$ . The allocation to all other agents remains unchanged. Since $\textrm{St}_{u}$ does not contain any agent from $L$ other than $u$ , an agent $u^{\prime}\in L$ has no allocated goods until it is resolved, and the allocation to agent $u^{\prime}$ is not changed after it is resolved. Finally, no goods are removed from an agent once assigned.

Theorem 3.

Algorithm 1 runs in polynomial time, and returns an EFX allocation.

The polynomial running time is easily seen, and is because the procedure $\textsc{Cut}(u,S)$ runs in polynomial time for cancelable valuations. The EFX property follows immediately from the next lemma.

Lemma 4.

Fix an agent $u\in L$ . Let $A$ be the partial allocation after resolving $\textrm{St}_{u}$ . Then the only possible envy in allocation $A$ is that a resolved agent $u^{\prime}\in L$ is envied by its favourite agent $f_{u^{\prime}}$ . Further, the partial allocation $A$ is EFX.

Proof.

The proof is by induction on the iterations of the outer for loop. The claim is clearly true for the initial empty allocation. Let $\hat{A}$ be the allocation before $u$ is resolved. Then by the induction hypothesis, since $u$ is not yet resolved in $\hat{A}$ , no agents in $\textrm{St}_{u}$ are envied.

In the current iteration, when $\textrm{St}_{u}$ is resolved, only agents in $\textrm{St}_{u}$ get goods, while agents not in $\textrm{St}_{u}$ retain their allocation. Hence, any new envy edges must be to agents in $\textrm{St}_{u}$ . Further since only agents in $\textrm{St}_{u}$ value the goods in $\textrm{St}_{u}$ , any new envy edges must also be from agents in $\textrm{St}_{u}$ .

Suppose agent $w$ envies agent $w^{\prime}\not\in\textrm{St}_{u}$ in $\hat{A}$ (as established, agents in $\textrm{St}_{u}$ are not envied in $\hat{A}$ ). Thus $v_{w}(\hat{A}_{w})<v_{w}(\hat{A}_{w^{\prime}})$ . In the current iteration, the allocation to $w^{\prime}$ does not change, while $w$ does not lose any goods. Hence any such envy remains EFX. Thus to prove the lemma, we only need to show that any new envy between agents in $\textrm{St}_{u}$ is from $f_{u}$ to $u$ , and is EFX.

Consider first an ordinary neighbour $w$ . Of the goods allocated in this iteration, $w$ only values $E_{u,w}$ . Of this set, it gets its preferred partition $T_{u,w}$ . Then since $w$ did not envy anyone in $\textrm{St}_{u}$ earlier, for any agent $z\in\textrm{St}_{u}$ , $v_{w}(\hat{A}_{w})\geq v_{w}(\hat{A}_{z})$ . Then

v_{w}(A_{w})=v_{w}(\hat{A}_{w}\cup T_{u,w})\geq v_{w}(\hat{A}_{z}\cup\bar{T}_{% u,w})\geq v_{w}(A_{z})\,.

The first inequality is because valuations are cancelable, and $w$ prefers $\hat{A}_{w}$ to $\hat{A}_{z}$ , and $T_{u,w}$ to $\bar{T}_{u,w}$ . The second inequality is because in this iteration, any agent other than $w$ either does not receive any good valued by $w$ , or receives the bundle $\bar{T}_{u,w}$ .

Consider $f_{u}$ , agent $u$ ’s favourite neighbour. Again of the goods allocated in this iteration, $f_{u}$ is only interested in $E_{u,f_{u}}$ . Of this set, it either gets its preferred bundle $T_{u,f_{u}}$ (in either Line 14 or in Line 17), or it gets the bundle $\bar{S}_{u,f_{u}}$ in Line 11. In the former case, since the valuations are cancelable and agent $f_{u}$ did not earlier envy any agent in $\textrm{St}_{u}$ , agent $f_{u}$ does not envy any agent in $\textrm{St}_{u}$ in allocation $A$ either. In the latter case, $f_{u}$ gets the bundle $\bar{S}_{u,f_{u}}$ , and hence may envy $u$ since agent $u$ gets $S_{u,f_{u}}=T_{u,f_{u}}$ . But note that then $A_{u}=S_{u,f_{u}}$ , and this is an EFX partition since $f_{u}$ cuts the set of items $E_{u,f_{u}}$ . Thus, the only possible new envy edge from $f_{u}$ is to $u$ , and this is EFX.

Lastly, consider agent $u$ . We show that $u$ will not envy any agent in $\textrm{St}_{u}$ . If $u$ gets $S_{u,f_{u}}\cup\operatorname*{LO}_{u}$ (Line 17), then by definition $S_{u,f_{u}}$ is preferred over all the other bundles allocated to the other agents in $\textrm{St}_{u}$ , and $u$ additionally gets all the left-over bundles. Otherwise, $u$ gets a choice between $S_{u,f_{u}}$ and $\bar{S}_{u,f_{u}}\cup\operatorname*{LO}_{u}$ ; the other bundle is given to $f_{u}$ . Then clearly $u$ does not envy $f_{u}$ . The bundle $S_{u,f_{u}}$ has a higher value for $u$ than $T_{u,w}$ for any neighbour $w$ . Since $u$ chooses the bundle with the highest value, $u$ does not envy any ordinary neighbour either. $\hfill\blacktriangleleft$

4 EFX Allocations for Monotone Valuations in Tree Multi-graphs

We now show that for monotone valuations, an EFX allocation exists in tree multi-graphs. Note that even for two agents with monotone submodular valuations, computing an EFX allocation is PLS-complete [19], and hence a polynomial-time algorithm for tree multi-graphs may not exist. Since trees are also bipartite, a polynomial time algorithm for cancelable valuations follows from the previous section.

Our algorithm for trees is recursive and again utilizes the procedure $\textsc{Cut}(v,S)$ , that obtains an EFX partition $(S^{1},S^{2})$ of $S$ for two identical agents with valuation $v$ . Let $T=(V,E)$ be the tree multi-graph, and $\ell$ be a leaf with parent $p$ . Then $E_{\ell,p}$ are the edges between $\ell$ and $p$ , and no other agent values these goods. Inductively, let $A^{\prime}$ be an EFX allocation of goods $E\setminus E_{\ell,p}$ to agents $V\setminus\{\ell\}$ . Our objective is then to extend $A^{\prime}$ to an EFX allocation of goods $E$ .

For this, let $(S^{1},S^{2})$ be the partition obtained when $p$ cuts $E_{\ell,p}$ . We define $A_{\ell}=\arg\max_{S\in\{S^{1},S^{2}\}}v_{\ell}(S)$ and $\bar{A}_{\ell}=E_{\ell,p}\setminus A_{\ell}$ . Note that ties are broken arbitrarily, ensuring that $A_{\ell}$ is a single bundle. Agent $\ell$ gets its preferred bundle $A_{\ell}$ . If $p$ is not envied in allocation $A^{\prime}$ , then it gets $\bar{A}_{\ell}$ , and the algorithm terminates. If $p$ is already envied in allocation $A^{\prime}$ , it cannot get additional goods. Let $s$ be a source in the envy graph for $A^{\prime}$ with a path to $p$ . We add $\bar{A}_{\ell}$ to agent $s$ ’s allocation. If $p$ does not envy $s$ now, the algorithm terminates. Else, there is an envy cycle where $p$ envies $s$ . Resolving the envy cycle gives us an EFX allocation.

Algorithm 2 Tree-EFX.

Theorem 5.

Given a tree multi-graph, $T=(V,E)$ with monotone valuations, Algorithm Tree-EFX returns an EFX allocation $A$ .

Proof.

By induction, assume that $A^{\prime}$ is an EFX allocation on $T^{\prime}=(V\setminus\{\ell\},E\setminus E_{\ell,p})$ . Note that given an EFX allocation, resolving envy cycles does not destroy this property, since each agent’s value does not decrease, and bundles are merely reassigned. Hence, the partial allocation in Line 11 is EFX for agents $V\setminus\{\ell\}$ , and $A_{\ell}=\emptyset$ .

On allocating $A_{\ell}$ to agent $\ell$ , clearly $\ell$ does not envy any agent. The only agent that could envy $\ell$ is agent $p$ , since only agents $p$ and $\ell$ value the bundle $A_{\ell}$ . Further, since $p$ gets to cut the bundle $E_{\ell,p}$ , as long as $p$ possesses a bundle with value at least $v_{p}(\bar{A}_{\ell})$ , its envy towards $\ell$ will be EFX.

If $p$ is a source in the envy graph, then the condition in Line 14 is satisfied and gets the bundle $\bar{A}_{\ell}$ . No agent will envy $p$ , since agents $V\setminus\{p,\ell\}$ do not value the bundle $\bar{A}_{\ell}$ , and $\ell$ already gets its preferred bundle. Thus the allocation $A$ is EFX.

If $p$ is not a source, then since the envy-graph is acyclic (and $\ell$ does not envy any agent), there is a source $s$ with a path to $p$ in the envy graph. Let $P$ be this path. We assign $\bar{A}_{\ell}$ to agent $s$ . The only agent that could now envy $s$ is $p$ . If $p$ envies $s$ , there is an envy cycle, which we resolve. We claim that the resulting allocation is EFX. This is because agent $\ell$ continues to not envy any agent. Agent $p$ ’s value for its bundle is now at least $v_{p}(\bar{A}_{\ell})$ , and hence any envy towards agent $\ell$ is EFX. Further agent $p$ ’s value for its bundle is also at least its earlier value; since resolving the cycle only shifted bundles around, any envy towards agents $V\setminus\{\ell\}$ is also EFX by induction. Finally, for other agents, their value does not decrease, and any envy is unaffected by the shifting of bundles. Hence the allocation is EFX. $\hfill\blacktriangleleft$

5 EFX Allocations in $𝒕$ -Chromatic Multi-graphs with Girth at Least $(2t-1)$

We now extend our algorithm and analysis to show that EFX allocations exist for agents with cancelable valuations in multi-graphs with girth at least $2t-1$ , where $t$ is the chromatic number of the graph. A multi-graph is $t$ -chromatic if $t$ is the minimum number of colours required to colour the vertices, so no edge has both end-points the same colour. The girth of a multi-graph is the length of the shortest simple cycle, without using parallel edges. For example, bipartite multi-graphs are 2-chromatic with girth at least 4, while the Petersen graph (with parallel edges) is 3-chromatic with girth 5. We will assume that we are given a $t$ -colouring of the multi-graph.

Our algorithm proceeds as follows. Given a multi-graph $G=(V,E)$ coloured with $t$ colours, let $c(u)\in[t]$ be the colour of each vertex $u\in V$ . Let $C^{i}=\{u:c(u)=i\}$ be the independent set consisting of all vertices coloured $i$ . We think of the vertices as ordered from left to right by their colour, and say a vertex $u$ is to the left of $w$ if $c(u)<c(w)$ . For $i=1,\ldots,t-1$ , define $L^{i}:=C^{i}$ , and $R^{i}:=C^{i+1}\cup\ldots\cup C^{t}$ .

We proceed in phases. In phase $i$ , we consider the bipartite multi-graph $G^{i}=(V^{i}=L^{i}\cup R^{i},E^{i})$ where an edge $e\in E$ is in $E^{i}$ if $|r(e)\cap L^{i}|$ $=|r(e)\cap R^{i}|=1$ , i.e., each edge is from a vertex in $L^{i}$ to a vertex in $R^{i}$ . Note that each vertex $u\in V\setminus C^{t}$ appears in a left bipartition in exactly one phase, when we consider all edges to vertices to the right of $u$ . Thus each edge appears in exactly one phase.

Now in phase $i$ , we run Algorithm 1 on the bipartite multi-graph $G^{i}$ . The only change we make is that in Algorithm 1, initially all vertices – in particular, vertices $u\in L$ – had empty allocations. This may not be the case in the current algorithm in the second phase onwards. Hence, we remove Line 1 from Algorithm 1, which initializes the allocation, within the outer for loop. Further in Lines 16 and 19 in Algorithm 3, agent $u\in L^{i}$ retains its earlier allocation. In Line 13, when $u\in L^{i}$ is possibly envied by $f_{u}$ , its earlier allocation passes to $f_{u}$ . Algorithm 3 formally states the algorithm.

Algorithm 3

t

-Chromatic-EFX.

A phase is an iteration of the outer loop. In phase $i$ , the vertices in $C^{i}$ are picked sequentially in the inner for loop.

Structures

For our analysis, we slightly need to redefine structures. For a vertex $u\in C^{i}$ , we now define the structure $\textrm{St}_{u}$ as the subgraph induced by $u\cup(N_{u}\cap R^{i})$ . That is, a structure now consists of the subgraph induced by $u$ and all neighbours to its right. As before, $u$ is the root of the structure. Now each iteration in phase $i$ of our algorithm resolves the structure $\textrm{St}_{u}$ for some $u\in C^{i}$ , and thus assigns all the edges in $\textrm{St}_{u}$ . A vertex $u$ is resolved if $\textrm{St}_{u}$ is resolved.

Fix agent $u\in C^{i}$ . As before, for each $w\in(N_{u}\cap R^{i})$ , $(E_{u,w}^{1},E_{u,w}^{2})=\textsc{Cut}(w,E_{u,w})$ is the partition of $E_{u,w}$ returned when agent $w$ cuts. Define $S_{u,w}:=\arg\max\{v_{u}(E_{u,w}^{1}),v_{u}(E_{u,w}^{2})\}$ as the bundle preferred by $u$ , and $T_{u,w}:=\arg\max\{v_{w}(E_{u,w}^{1}),v_{w}(E_{u,w}^{2})\}$ as the bundle preferred by $w$ . As earlier, ties are broken arbitrarily to ensure that $S_{u,w}$ and $T_{u,w}$ are single bundles. If either agent is indifferent between the two bundles, we break ties so that $S_{u,w}\neq T_{u,w}$ . Further, for $S\subseteq E_{u,w}$ , we define $\bar{S}=E_{u,w}\setminus S$ . Then $u$ ’s favourite neighbour $f_{u}:=\arg\max_{w\in N_{u}\cap R_{i}}v_{u}(S_{u,w})$ , with ties broken arbitrarily.
This is the right neighbour that offers $u$ the highest-value bundle after cutting the adjacent edges. The other right neighbours are simply called ordinary neighbours.

We note the following properties of our algorithm. In phase $i$ of the algorithm, the inner for loop picks an agent $u\in C^{i}$ , and resolves $\textrm{St}_{u}$ . The goods in $\textrm{St}_{u}$ are assigned to the agents in $\textrm{St}_{u}$ . The allocation to other agents is unchanged. Hence in particular, the allocation to a resolved agent does not change subsequently. Furthermore, while $\textrm{St}_{u}$ is resolved, agents in $\textrm{St}_{u}$ do not lose any goods, except possibly $u$ itself. Agent $u$ may however give its entire set of goods to its favourite neighbour $f_{u}$ (Line 13). However, in this case, agent $u$ gets $S_{u,f_{u}}$ , which it prefers over its earlier allocation and all the left-over goods. Thus, the value of each agent for its bundle is nondecreasing.

Much of our effort is towards proving Lemma 11, which shows that any envy is within a structure, and is from a favourite neighbour $f_{u}$ to the root $u$ . In particular, we want to avoid the following. Say for some interim allocation $A$ , agent $u^{\prime}$ values goods in both $A_{u}$ and $A_{f_{u}}$ . Then if $A_{u}$ is transferred to $f_{u}$ in Line 13, agent $u^{\prime}$ should not envy $f_{u}$ .

We show this by contradiction: that if agent $u^{\prime}$ does indeed start envying $f_{u}$ , then it must have short paths to both $u$ and $f_{u}$ , and hence, taken with any edge between $u$ and $f_{u}$ , there is a cycle of length less than $2t-1$ . We do this in two steps: Claim 7 shows that if $u^{\prime}$ envies the bundle of goods $A_{u}\cup A_{f_{u}}$ , then these must contain a good from $\textrm{St}_{u^{\prime}}$ . Claims 9 and 10 then establish bounds on the distance from $u^{\prime}$ for $u$ and $f_{u}$ .

Next, we state the claims required to prove Lemma 11. Our first claim is that an unresolved agent does not envy the entire set of goods held by all other unresolved vertices.

Claim 6.

Let $A$ and $\operatorname*{Res}$ be the allocation and the set of resolved vertices at Line 5. Let $z$ be an unresolved agent. Then

v_{z}(A_{z})\geq v_{z}\left(\bigcup_{w\not\in\operatorname*{Res},\,w\neq z}A_{% w}\right)\,.

Proof.

Fix an unresolved agent $z$ . We prove this by induction on the iterations of the inner loop. Initially, the allocation is empty, and the claim is trivially satisfied. Assume this is true prior to the loop when a vertex $u$ is resolved. Let $\hat{A}$ , $\widehat{\operatorname*{Res}}$ be the allocation and set of resolved vertices before $u$ is resolved, and $A$ , $\operatorname*{Res}=\widehat{\operatorname*{Res}}\cup\{u\}$ be the allocation and set of resolved vertices after. Note that the allocation to resolved agents does not change subsequently. Hence if $z$ now envies the set of goods held by unresolved agents, new goods that $z$ values must be allocated to unresolved agents.

In this loop, only the allocation to agents in $\textrm{St}_{u}$ is modified. Further, none of the agents in $\textrm{St}_{u}$ are resolved prior to the loop, i.e., $\textrm{St}_{u}\cap\widehat{\operatorname*{Res}}=\emptyset$ . Hence $v_{z}(\hat{A}_{z})\geq v_{z}\left(\cup_{u^{\prime}\in\textrm{St}_{u},\,u^{% \prime}\neq z}\hat{A}_{u^{\prime}}\right)$ by the induction hypothesis. Now if $z\not\in\textrm{St}_{u}$ , then no additional goods it values are allocated in this loop. Hence the claim holds by induction. Thus, since $z\neq u$ (since $z$ is unresolved after the loop), it must be that $z$ is a neighbour to the right of $u$ . Of the goods allocated in this loop, $z$ only values $E_{u,z}$ .

If $z$ is an ordinary neighbour, then $z$ additionally gets its preferred bundle $T_{u,z}$ , while the bundle $\bar{T}_{u,z}$ is allocated to other agents. Hence, since valuations are cancelable, the claim remains true. On the other hand, if $z=f_{u}$ , then $z$ could lose its preferred bundle $T_{u,z}$ to agent $u$ . But in this case agent $u$ is resolved, hence $u\not\in\operatorname*{Res}$ . Since $z$ additionally gets $\bar{T}_{u,z}$ and does not lose any goods, the claim remains true after the loop also. $\hfill\vartriangleleft$

The next claim builds on the previous claim to show that if any vertex $z$ envies the union of goods held by some set $S$ of unresolved agents, then $z$ must be resolved, and some agent in $S$ must hold a good from $\textrm{St}_{z}$ .

Claim 7.

Let $A$ and $\operatorname*{Res}$ be the allocation and the set of resolved vertices at Line 5. Let $z$ be any agent, and $S$ is a subset of unresolved vertices so that

v_{z}(A_{z})<v_{z}\left(\bigcup_{w\in S,z\not\in S}A_{w}\right)\,.

Then $z$ is resolved, and for some agent $w\in S$ , $A_{w}$ contains some good $g\in\textrm{St}_{z}$ .

Proof.

By Claim 6, if $z$ is unresolved, then $v_{z}(A_{z})$ $\geq v_{z}\left(\cup_{w\in S,\,w\neq z}A_{w}\right)$ . Hence $z$ must in fact be resolved. We prove the contrapositive by induction, that if a subset of unresolved agents $S$ do not hold any good from $\textrm{St}_{z}$ , then $v_{z}(A_{z})\geq v_{z}(\cup_{w\in S}A_{w})$ . Clearly, the claim holds in any iteration before $z$ is resolved.

Consider the iteration where $z$ is resolved. Every agent in $\textrm{St}_{z}$ receives goods from $\textrm{St}_{z}$ , hence, we only consider subsets $S$ consisting of agents not in $\textrm{St}_{z}$ . But the allocation for these agents does not change, and $z$ ’s value for its bundle is nondecreasing, hence the claim holds in this iteration.

Consider any later iteration, where an agent $u\neq z$ is resolved. Then $u\not\in S$ , since $u$ is resolved. Let $\hat{A}$ be the allocation before resolving $\textrm{St}_{u}$ , and $A$ the allocation after. Again, only the allocation for agents in $\textrm{St}_{u}$ changes, hence by induction we only need to consider subsets $S$ that contain agents in $\textrm{St}_{u}$ . Note that since agent $z$ is already resolved, $z$ does not value any goods in $\textrm{St}_{u}$ . Hence the allocation of goods in $\textrm{St}_{u}$ does not affect the right hand side of the inequality in the claim.

Other than the allocation of goods in $\textrm{St}_{u}$ , the only change that happens in the algorithm is that the prior bundle $\hat{A}_{u}$ may be transferred to $f_{u}$ . Thus if $\hat{A}_{u}$ is not transferred to $f_{u}$ , or $f_{u}\not\in S$ , then $z$ ’s value for the aggregate bundle $\cup_{w\in S}A_{w}$ is unchanged, and the claim holds.

Thus, $f_{u}\in S$ , $u\not\in S$ , and the only relevant change that occurs in the iteration is that the bundle $\hat{A}_{u}$ is transferred to agent $f_{u}$ . Note that since $f_{u}\in S$ , $f_{u}$ does not hold any goods from $\textrm{St}_{z}$ , and hence $\hat{A}_{u}$ does not contain any goods from $\textrm{St}_{z}$ . Now in the allocation $\hat{A}$ , consider the subset $\hat{S}=S\cup\{u\}$ . Then

	$\displaystyle v_{z}(A_{z})=v_{z}(\hat{A}_{z})$	$\displaystyle\geq v_{z}\left(\bigcup_{w\in\hat{S}}\hat{A}_{w}\right)\quad\text% {(by the induction hypothesis)}$
		$\displaystyle=v_{z}\left(\hat{A}_{u}\cup\bigcup_{w\in S}\hat{A}_{w}\right)% \nobreak\ =v_{z}\left(\bigcup_{w\in S}A_{w}\right)\,,$

proving the claim. $\hfill\vartriangleleft$

Proposition 8.

For an agent $u$ , let $\hat{A}$ and $A$ be the allocations before and after $\textrm{St}_{u}$ is resolved. If for some agent $z$ and good $g$ , $g\in\hat{A}_{z}$ but $g\not\in A_{z}$ , then $z=u$ and $g\in A_{f_{u}}$ . Thus in a phase, any good allocated before the phase began can only be transferred from the root of a structure to its favourite neighbour.

Proof.

As noted, when $\textrm{St}_{u}$ is resolved, the goods in the structure are allocated to the agents in the structure. If Line 13 is executed, then additionally the bundle $A_{u}$ is transferred to agent $f_{u}$ (and agent $u$ gets the bundle $S_{u,f_{u}})$ . Thus the only way that a good that is assigned to an agent before $\textrm{St}_{u}$ is resolved can be moved, is if it was assigned to $u$ and then is transferred to agent $f_{u}$ . The proposition follows.

Since a root only appears once in a phase, a good once transferred in a phase cannot be transferred again, and hence any good allocated prior to a phase can only be transferred once, from the root of a structure to its favourite neighbour. $\hfill\blacktriangleleft$

The next few results show that a good valued by an agent $z$ cannot be very far from $z$ .

Claim 9.

Let $A$ be the allocation at Line 5. If agent $z$ values a good $g$ and $g\in A_{w}$ , then $\operatorname*{dist}(z,w)\leq c(w)$ along allocated edges.

Proof.

By Proposition 8, a good can only be transferred rightward, from an agent being resolved to its favourite neighbour. If $c(w)=1$ , then once $\textrm{St}_{w}$ is resolved, $w$ ’s allocation does not change. Thus if $g\in A_{w}$ and $c(w)=1$ , $w$ received this good in phase 1 when $\textrm{St}_{w}$ was resolved. Since $z$ values $g$ , $z$ must be in $N_{w}$ , and there is a path of length 1 between $z$ and $w$ along the edge set $E_{w,z}$ satisfying the claim.

Now suppose $c(w)\geq 2$ . Consider the phase when $g$ is initially allocated, say to an agent $w^{\prime}$ when $\textrm{St}_{u}$ is resolved. Since $z$ values $g$ , $z\in\textrm{St}_{u}$ . Hence $z$ and $w^{\prime}$ have a path of length 2 along the edges of $\textrm{St}_{u}$ . From Proposition 8, in each subsequent phase, $g$ is transferred from the root of a structure to its favourite neighbour. Suppose $g$ is allocated to $w$ in phase $k$ . Then $w$ must be a right neighbour for the agent being resolved, and hence the colour $c(w)\geq k+1$ . There are at most $k-1$ phases after the phase $g$ is initially allocated. Thus there is a path of length $k-1+2\leq c(w)$ along allocated edges from $w$ to $z$ . $\hfill\vartriangleleft$

If $z$ not only values $g$ , but $g\in\textrm{St}_{z}$ and is held by agent $w$ , then we can get a tighter bound on $\operatorname*{dist}(z,w)$ .

Claim 10.

Let $A$ be the allocation at Line 5. Let there be agents $z$ , $w$ , and good $g\in\textrm{St}_{z}\cap A_{w}$ . Then $\operatorname*{dist}(z,w)\leq c(w)-c(z)$ along allocated edges.

Proof.

Since $g\in\textrm{St}_{u}$ , when $\textrm{St}_{u}$ is resolved, it is assigned either to $u$ or to a neighbour to the right. Further any reassignment of $g$ transfers it to a neighbour further to the right. Hence if $u\neq w$ , then $w$ must be to the right of $u$ , hence $c(w)>c(u)$ .

Now when $g$ is initially allocated in phase $c(u)$ , it is allocated to an agent $w^{\prime}$ at a distance 1 from $u$ along the edges $E_{u,w^{\prime}}$ . Suppose $g$ is allocated to agent $w$ in phase $k$ . Then $c(w)>k$ , and there are at most $k-c(u)$ phases after the phase when $g$ is initially allocated. Thus there is a path of length $k-c(u)+1\leq c(w)-c(u)$ along allocated edges from $u$ to $w$ . $\hfill\vartriangleleft$

We now prove our main lemma.

Lemma 11.

Let $A$ be the allocation at Line 5. Then if $w$ envies $u$ , then $u$ is a resolved vertex, and $w=f_{u}$ (i.e., $w$ is $u$ ’s favourite vertex in $\textrm{St}_{u}$ ).

Proof.

We will prove the lemma by induction. For the base case, the initial allocation is empty and trivially satisfies the two properties. Now fix any vertex $u$ . Let $\hat{A}$ be the allocation before the structure rooted at $u$ is resolved, and $A$ be the allocation after resolving $\textrm{St}_{u}$ .

None of the vertices in $\textrm{St}_{u}$ are resolved in $\hat{A}$ , and hence by the induction hypothesis, none of these are envied in $\hat{A}$ . When $\textrm{St}_{u}$ is resolved, only the allocation to agents in $\textrm{St}_{u}$ is modified, while the allocation to other agents is unchanged. The value of agents in $\textrm{St}_{u}$ does not decrease. Hence, any new envy edge must be towards agents in $\textrm{St}_{u}$ .

Consider an ordinary neighbour $w$ in $\textrm{St}_{u}$ . Agent $w$ is not envied in $\hat{A}$ . It receives its preferred bundle $T_{u,w}$ ; this is only valued by $u$ and $w$ , hence no agent other than $u$ will envy $w$ . To see that $u$ also will not envy $w$ , we first claim that $v_{u}(\hat{A}_{w})=0$ , i.e., $u$ does not value $w$ ’s bundle in $\hat{A}$ . To prove this, assume for a contradiction that $u$ values $w$ ’s bundle. Then by Claim 9, there exists a $u$ - $w$ path along allocated edges of length at most $t$ . Including the (unallocated) edges $E_{u,w}$ , this gives a cycle of length $t+1$ . If $t=2$ , this gives us a 3-cycle, which would mean that the graph is not 2-colourable. If $t>2$ , then $t+1<2t-1$ , but the graph has girth at least $2t-1$ . In either case we get a contradiction. Thus, $v_{u}(\hat{A}_{w})=0$ .

Further, $v_{u}(A_{u})\geq v_{u}(T_{u,w})$ . This is because agent $u$ prefers $S_{u,f_{u}}$ over $T_{u,w}$ , and always has the choice of keeping $S_{u,f_{u}}$ . Hence, it ends up with a bundle of value at least that of $T_{u,w}$ . Then since $v_{u}(\emptyset)\geq v_{u}(\hat{A}_{w})$ and $v_{u}(A_{u})\geq v_{u}(T_{u,w})$ , since valuations are cancelable, $v_{u}(A_{u})\geq v_{u}(A_{w})$ . Thus, an ordinary neighbour $w\in\textrm{St}_{u}$ is not envied.

Now consider agent $u$ . As shown, agent $u$ is not envied in $\hat{A}$ . While resolving $\textrm{St}_{u}$ , the only goods agent $u$ can possibly receive are goods in $\textrm{St}_{u}$ , and hence no agent outside $\textrm{St}_{u}$ will envy $u$ . Within $\textrm{St}_{u}$ , all ordinary neighbours receive their preferred bundle, and hence will not envy $u$ . Thus the only agent that could possibly envy $u$ after resolving $\textrm{St}_{u}$ is $f_{u}$ .

Now if $f_{u}$ gets its preferred bundle $T_{u,f_{u}}$ (in Lines 16 and 19), it does not envy $u$ . If agent $f_{u}$ gets $\bar{T}_{u,f_{u}}$ (in Line 13), then this is an EFX partition for $f_{u}$ (since $f_{u}$ cut s $E_{u,f_{u}}$ ), and agent $u$ only gets $T_{u,f_{u}}$ . In this case, $f_{u}$ envies $u$ , but the envy is EFX.

Lastly, consider agent $f_{u}$ . This case is more complicated than the earlier cases, since the bundle $\hat{A}_{u}$ previously held by $u$ could be transferred to $f_{u}$ in Line 13. We will show however that no agent envies $f_{u}$ .

First, let’s consider agents in $\textrm{St}_{u}$ . Again, the ordinary neighbours $w$ did not envy $f_{u}$ earlier, and from the goods $E_{u,w}$ they get their preferred bundle $T_{u,w}$ . Hence, since valuations are cancelable, they will not envy $f_{u}$ .

Agent $u$ , as argued previously, by Claim 9, does not value $\hat{A}_{f_{u}}$ , else there is a cycle of length strictly smaller than $2t-1$ . Further agent $u$ gets a bundle of value at least that of $S_{u,f_{u}}$ , and hence will not envy $f_{u}$ .

For the last case, consider any agent $u^{\prime}\not\in\textrm{St}_{u}$ . In allocation $\hat{A}$ , $u^{\prime}$ does not envy $u$ or $f_{u}$ . Since $u^{\prime}$ does not value goods in $E_{u,f_{u}}$ , if it envies $A_{f_{u}}$ , clearly (i) it must value both $\hat{A}_{u}$ and $\hat{A}_{f_{u}}$ , and (ii) it must envy $\hat{A}_{u}\cup\hat{A}_{f_{u}}$ .

Suppose $c(u^{\prime})\geq 2$ . Then from Claim 7, either $u$ or $f_{u}$ holds a good from $\textrm{St}_{u^{\prime}}$ (say $u$ ). By Claim 10, $u$ is then at distance $c(u)-c(u^{\prime})$ from $u^{\prime}$ along allocated edges. From (i) in the previous paragraph, and Claim 9, $f_{u}$ is at distance at most $c(f_{u})$ from $u^{\prime}$ along allocated edges. Thus, there is $u$ - $f_{u}$ path along allocated edges (via $u^{\prime}$ ) of length $c(f_{u})+c(u)-c(u^{\prime})$ $\leq 2t-3$ (since $c(u)\leq t-1$ and $c(u^{\prime})\geq 2$ ). But then including the (unallocated) edges $E_{u,f_{u}}$ , there is a cycle of length $2t-2$ , which is a contradiction, since we assume the graph has girth at least $2t-1$ .

Finally, suppose $c(u^{\prime})=1$ . Then note that all the goods that $u^{\prime}$ values are in $\textrm{St}_{u^{\prime}}$ . Since both $u$ and $f_{u}$ possess goods that $u^{\prime}$ values, by Claim 10, they are at distance $c(u)-1$ and $c(f_{u})-1$ respectively from $u^{\prime}$ along allocated edges. Since $c(u)\leq t-1$ , there is a path of length $2t-3$ from $u$ to $f_{u}$ (via $u^{\prime}$ ) along allocated edges. But then including the (unallocated) edges $E_{u,f_{u}}$ , there is a cycle of length $2t-2$ , which is again a contradiction. Thus, agent $f_{u}$ is not envied in the allocation $A$ . This completes the proof. $\hfill\blacktriangleleft$

We now can easily prove that the allocation obtained is EFX.

Theorem 12.

Algorithm 3 obtains an EFX allocation for agents with cancelable valuations in polynomial time.

Proof.

The proof for the running time for Algorithm 3 is obtained easily, since for cancelable valuations $\textsc{Cut}(u,S)$ runs in polynomial time, and the other steps are straightforward.

We now show that the algorithm obtains an EFX allocation. As before, the proof is by induction on the iterations of the inner for loop. For the base case, the statement clearly holds for the empty allocation. Then consider an agent $u$ , and let $\hat{A}$ and $A$ be the allocations before and after $\textrm{St}_{u}$ is resolved.

Consider first an envy edge from agent $w$ to agent $u^{\prime}$ in allocation $\hat{A}$ . We will show that this envy remains EFX in allocation $A$ as well. By Lemma 11, agent $u^{\prime}$ must be resolved. No agent in $\textrm{St}_{u}$ is resolved in $\hat{A}$ , hence $u^{\prime}\not\in\textrm{St}_{u}$ . Since only agents in $\textrm{St}_{u}$ have their allocations modified, agent $u^{\prime}$ ’s allocation is not modified. Agent $w$ is either also not in $\textrm{St}_{u}$ (in which case its allocation also does not change), or is in $\textrm{St}_{u}$ (in which case its value does not decrease). In either case, either $w$ does not envy $u^{\prime}$ in $A$ , or the envy remains EFX.

By Lemma 11, the only envy edge that may be in $A$ but not in $A^{\prime}$ is from $f_{u}$ to $u$ . This happens in Line 11, when $u$ gets $S_{u,f_{u}}$ . But then agent $f_{u}$ gets $\bar{S}_{u,f_{u}}$ . Since agent $f_{u}$ cuts the bundle $E_{u,f_{u}}$ , and agent $u$ has no goods besides $S_{u,f_{u}}$ , the envy is EFX. $\hfill\blacktriangleleft$

Finally, we show that EFX allocations exist in cycle multi-graphs, from the earlier results.

Theorem 13.

For agents with cancelable valuations in a cycle multi-graph, EFX allocations exist.

Proof.

We consider three separate cases, depending on the length of the cycle. For even-length cycles, the result follows from Theorem 3, since such a cycle is a bipartite multi-graph. If the length is 3, then the result follows from EFX existence for three agents [16]. Finally, if the cycle has odd length of at least 5, the chromatic number is 3, and the existence follows from Theorem 12, setting $t=3$ , since the girth is least $5$ . $\hfill\blacktriangleleft$

6 Conclusion

Our paper extends the work on EFX existence to important classes of multi-graphs. We view our results as a significant extension over the work by Christodoulou et al. [18] since their results are for simple graphs. Our work also shows that the well-known cut-and-choose paradigm can be leveraged to obtain results in fairly general settings. Our algorithm is another tool in the toolbox for EFX allocations, different, for example, from the multiple-phase algorithms used in many other papers.

We note that if edges are chores instead of good, i.e., an edge is negatively-valued by both adjacent vertices, an envy-free allocation can be obtained by assigning each edge to a vertex other than its endpoints. The existence of EFX allocations for general multi-graphs with positively valued edges remains an open problem. We also find it interesting that the case of a cycle multi-graph with 3 agents does not yet have a simpler algorithm than for general 3 agents. Coming up with a simpler algorithm here may be crucial to extending our work to general multi-graphs.

References

[1] Mahyar Afshinmehr, Alireza Danaei, Mehrafarin Kazemi, Kurt Mehlhorn, and Nidhi Rathi. EFX allocations and orientations on bipartite multi-graphs: A complete picture. CoRR, abs/2410.17002, 2024. doi:10.48550/arXiv.2410.17002.
[2] Mahyar Afshinmehr, Alireza Danaei, Mehrafarin Kazemi, Kurt Mehlhorn, and Nidhi Rathi. EFX allocations and orientations on bipartite multi-graphs: A complete picture. In Proceedings of the 24th International Conference on Autonomous Agents and Multiagent Systems, pages 32–40, 2025. doi:10.5555/3709347.3743514.
[3] Hannaneh Akrami, Noga Alon, Bhaskar Ray Chaudhury, Jugal Garg, Kurt Mehlhorn, and Ruta Mehta. EFX: A simpler approach and an (almost) optimal guarantee via rainbow cycle number. In Proceedings of the 24th ACM Conference on Economics and Computation, EC 2023, London, United Kingdom, July 9-12, 2023, page 61. ACM, 2023. doi:10.1145/3580507.3597799.
[4] Georgios Amanatidis, Haris Aziz, Georgios Birmpas, Aris Filos-Ratsikas, Bo Li, Hervé Moulin, Alexandros A Voudouris, and Xiaowei Wu. Fair division of indivisible goods: Recent progress and open questions. Artificial Intelligence, 322:103965, 2023. doi:10.1016/J.ARTINT.2023.103965.
[5] Georgios Amanatidis, Aris Filos-Ratsikas, and Alkmini Sgouritsa. Pushing the frontier on approximate EFX allocations. In Dirk Bergemann, Robert Kleinberg, and Daniela Sabán, editors, Proceedings of the 25th ACM Conference on Economics and Computation, EC 2024, New Haven, CT, USA, July 8-11, 2024, pages 1268–1286. ACM, 2024. doi:10.1145/3670865.3673582.
[6] Georgios Amanatidis, Evangelos Markakis, and Apostolos Ntokos. Multiple birds with one stone: Beating 1/2 for efx and gmms via envy cycle elimination. Theoretical Computer Science, 841:94–109, 2020. doi:10.1016/J.TCS.2020.07.006.
[7] Haris Aziz, Ioannis Caragiannis, Ayumi Igarashi, and Toby Walsh. Fair allocation of indivisible goods and chores. In Proceedings of the 28th International Joint Conference on Artificial Intelligence, pages 53–59, 2019. doi:10.24963/IJCAI.2019/8.
[8] Siddharth Barman, Umang Bhaskar, Yeshwant Pandit, and Soumyajit Pyne. Nearly equitable allocations beyond additivity and monotonicity. In Thirty-Eighth AAAI Conference on Artificial Intelligence, AAAI 2024, February 20-27, 2024, Vancouver, Canada, pages 9494–9501. AAAI Press, 2024. doi:10.1609/AAAI.V38I9.28804.
[9] Kristóf Bérczi, Erika R. Bérczi-Kovács, Endre Boros, Fekadu Tolessa Gedefa, Naoyuki Kamiyama, Telikepalli Kavitha, Yusuke Kobayashi, and Kazuhisa Makino. Envy-free relaxations for goods, chores, and mixed items. Theor. Comput. Sci., 1002:114596, 2024. doi:10.1016/J.TCS.2024.114596.
[10] Ben Berger, Avi Cohen, Michal Feldman, and Amos Fiat. Almost full EFX exists for four agents. In Thirty-Sixth AAAI Conference on Artificial Intelligence, AAAI 2022, February 22 - March 1, 2022, pages 4826–4833. AAAI Press, 2022. doi:10.1609/AAAI.V36I5.20410.
[11] Umang Bhaskar, Gunjan Kumar, Yeshwant Pandit, and Rakshitha. Towards envy-freeness relaxations for general nonmonotone valuations. In Proceedings of the 24th International Conference on Autonomous Agents and Multiagent Systems, pages 298–306, 2025. doi:10.5555/3709347.3743543.
[12] Umang Bhaskar, A. R. Sricharan, and Rohit Vaish. On approximate envy-freeness for indivisible chores and mixed resources. In Mary Wootters and Laura Sanità, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2021, volume 207 of LIPIcs, pages 1:1–1:23. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021. doi:10.4230/LIPICS.APPROX/RANDOM.2021.1.
[13] Eric Budish. The Combinatorial Assignment Problem: Approximate Competitive Equilibrium from Equal Incomes. Journal of Political Economy, 119(6):1061–1103, 2011.
[14] Ioannis Caragiannis, David Kurokawa, Hervé Moulin, Ariel D Procaccia, Nisarg Shah, and Junxing Wang. The unreasonable fairness of maximum nash welfare. ACM Transactions on Economics and Computation, 7(3):12, 2019.
[15] Hau Chan, Jing Chen, Bo Li, and Xiaowei Wu. Maximin-aware allocations of indivisible goods. In Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems, AAMAS ’19, pages 1871–1873, 2019. URL: http://dl.acm.org/citation.cfm?id=3331947.
[16] Bhaskar Ray Chaudhury, Jugal Garg, and Kurt Mehlhorn. EFX exists for three agents. J. ACM, 71(1):4:1–4:27, 2024. doi:10.1145/3616009.
[17] Bhaskar Ray Chaudhury, Telikepalli Kavitha, Kurt Mehlhorn, and Alkmini Sgouritsa. A little charity guarantees almost envy-freeness. SIAM J. Comput., 50(4):1336–1358, 2021. doi:10.1137/20M1359134.
[18] George Christodoulou, Amos Fiat, Elias Koutsoupias, and Alkmini Sgouritsa. Fair allocation in graphs. In Kevin Leyton-Brown, Jason D. Hartline, and Larry Samuelson, editors, Proceedings of the 24th ACM Conference on Economics and Computation, EC 2023, London, United Kingdom, July 9-12, 2023, pages 473–488. ACM, 2023. doi:10.1145/3580507.3597764.
[19] Paul W. Goldberg, Kasper Høgh, and Alexandros Hollender. The frontier of intractability for EFX with two agents. In Algorithmic Game Theory - 16th International Symposium, SAGT 2023, Egham, UK, September 4-7, 2023, Proceedings, volume 14238 of Lecture Notes in Computer Science, pages 290–307. Springer, 2023. doi:10.1007/978-3-031-43254-5_17.
[20] Hadi Hosseini, Sujoy Sikdar, Rohit Vaish, and Lirong Xia. Fair and efficient allocations under lexicographic preferences. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 5472–5480, 2021. doi:10.1609/AAAI.V35I6.16689.
[21] Vishwa Prakash HV, Pratik Ghosal, Prajakta Nimbhorkar, and Nithin Varma. EFX exists for three types of agents. CoRR, abs/2410.13580, 2024. doi:10.48550/arXiv.2410.13580.
[22] Alireza Kaviani, Masoud Seddighin, and AmirMohammad Shahrezaei. Almost envy-free allocation of indivisible goods: A tale of two valuations. In Web and Internet Economics - 20th International Conference, WINE 2024, Proceedings. Springer, 2024.
[23] Richard J Lipton, Evangelos Markakis, Elchanan Mossel, and Amin Saberi. On approximately fair allocations of indivisible goods. In Proceedings of the 5th ACM Conference on Electronic Commerce, pages 125–131, 2004. doi:10.1145/988772.988792.
[24] Ryoga Mahara. Existence of EFX for two additive valuations. Discret. Appl. Math., 340:115–122, 2023. doi:10.1016/J.DAM.2023.06.035.
[25] Benjamin Plaut and Tim Roughgarden. Almost envy-freeness with general valuations. SIAM J. Discret. Math., 34(2):1039–1068, 2020. doi:10.1137/19M124397X.
[26] Alkmini Sgouritsa and Minas Marios Sotiriou. On the existence of EFX allocations in multigraphs. In Proceedings of the 24th International Conference on Autonomous Agents and Multiagent Systems, pages 2735–2737, 2025. doi:10.5555/3709347.3743995.
[27] Alkmini Sgouritsa and Minas Marios Sotiriou. On the existence of EFX allocations in multigraphs. CoRR, abs/2502.09777, 2025. doi:10.48550/arXiv.2502.09777.
[28] Jinghan A Zeng and Ruta Mehta. On the structure of EFX orientations on graphs. In Proceedings of the 24th International Conference on Autonomous Agents and Multiagent Systems, pages 2309–2316, 2025. doi:10.5555/3709347.3743871.
[29] Yu Zhou, Tianze Wei, Minming Li, and Bo Li. A complete landscape of EFX allocations on graphs: goods, chores and mixed manna. In Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence, pages 3049–3056, 2024. URL: https://www.ijcai.org/proceedings/2024/338.
[30] David Zuckerman. Linear degree extractors and the inapproximability of max clique and chromatic number. In Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, pages 681–690, 2006. doi:10.1145/1132516.1132612.

[bib.bib1] [1] Mahyar Afshinmehr, Alireza Danaei, Mehrafarin Kazemi, Kurt Mehlhorn, and Nidhi Rathi. EFX allocations and orientations on bipartite multi-graphs: A complete picture. CoRR, abs/2410.17002, 2024. doi:10.48550/arXiv.2410.17002.

[bib.bib2] [2] Mahyar Afshinmehr, Alireza Danaei, Mehrafarin Kazemi, Kurt Mehlhorn, and Nidhi Rathi. EFX allocations and orientations on bipartite multi-graphs: A complete picture. In Proceedings of the 24th International Conference on Autonomous Agents and Multiagent Systems, pages 32–40, 2025. doi:10.5555/3709347.3743514.

[bib.bib3] [3] Hannaneh Akrami, Noga Alon, Bhaskar Ray Chaudhury, Jugal Garg, Kurt Mehlhorn, and Ruta Mehta. EFX: A simpler approach and an (almost) optimal guarantee via rainbow cycle number. In Proceedings of the 24th ACM Conference on Economics and Computation, EC 2023, London, United Kingdom, July 9-12, 2023, page 61. ACM, 2023. doi:10.1145/3580507.3597799.

[bib.bib4] [4] Georgios Amanatidis, Haris Aziz, Georgios Birmpas, Aris Filos-Ratsikas, Bo Li, Hervé Moulin, Alexandros A Voudouris, and Xiaowei Wu. Fair division of indivisible goods: Recent progress and open questions. Artificial Intelligence, 322:103965, 2023. doi:10.1016/J.ARTINT.2023.103965.

[bib.bib5] [5] Georgios Amanatidis, Aris Filos-Ratsikas, and Alkmini Sgouritsa. Pushing the frontier on approximate EFX allocations. In Dirk Bergemann, Robert Kleinberg, and Daniela Sabán, editors, Proceedings of the 25th ACM Conference on Economics and Computation, EC 2024, New Haven, CT, USA, July 8-11, 2024, pages 1268–1286. ACM, 2024. doi:10.1145/3670865.3673582.

[bib.bib6] [6] Georgios Amanatidis, Evangelos Markakis, and Apostolos Ntokos. Multiple birds with one stone: Beating 1/2 for efx and gmms via envy cycle elimination. Theoretical Computer Science, 841:94–109, 2020. doi:10.1016/J.TCS.2020.07.006.

[bib.bib7] [7] Haris Aziz, Ioannis Caragiannis, Ayumi Igarashi, and Toby Walsh. Fair allocation of indivisible goods and chores. In Proceedings of the 28th International Joint Conference on Artificial Intelligence, pages 53–59, 2019. doi:10.24963/IJCAI.2019/8.

[bib.bib8] [8] Siddharth Barman, Umang Bhaskar, Yeshwant Pandit, and Soumyajit Pyne. Nearly equitable allocations beyond additivity and monotonicity. In Thirty-Eighth AAAI Conference on Artificial Intelligence, AAAI 2024, February 20-27, 2024, Vancouver, Canada, pages 9494–9501. AAAI Press, 2024. doi:10.1609/AAAI.V38I9.28804.

[bib.bib9] [9] Kristóf Bérczi, Erika R. Bérczi-Kovács, Endre Boros, Fekadu Tolessa Gedefa, Naoyuki Kamiyama, Telikepalli Kavitha, Yusuke Kobayashi, and Kazuhisa Makino. Envy-free relaxations for goods, chores, and mixed items. Theor. Comput. Sci., 1002:114596, 2024. doi:10.1016/J.TCS.2024.114596.

[bib.bib10] [10] Ben Berger, Avi Cohen, Michal Feldman, and Amos Fiat. Almost full EFX exists for four agents. In Thirty-Sixth AAAI Conference on Artificial Intelligence, AAAI 2022, February 22 - March 1, 2022, pages 4826–4833. AAAI Press, 2022. doi:10.1609/AAAI.V36I5.20410.

[bib.bib11] [11] Umang Bhaskar, Gunjan Kumar, Yeshwant Pandit, and Rakshitha. Towards envy-freeness relaxations for general nonmonotone valuations. In Proceedings of the 24th International Conference on Autonomous Agents and Multiagent Systems, pages 298–306, 2025. doi:10.5555/3709347.3743543.

[bib.bib12] [12] Umang Bhaskar, A. R. Sricharan, and Rohit Vaish. On approximate envy-freeness for indivisible chores and mixed resources. In Mary Wootters and Laura Sanità, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2021, volume 207 of LIPIcs, pages 1:1–1:23. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021. doi:10.4230/LIPICS.APPROX/RANDOM.2021.1.

[bib.bib13] [13] Eric Budish. The Combinatorial Assignment Problem: Approximate Competitive Equilibrium from Equal Incomes. Journal of Political Economy, 119(6):1061–1103, 2011.

[bib.bib14] [14] Ioannis Caragiannis, David Kurokawa, Hervé Moulin, Ariel D Procaccia, Nisarg Shah, and Junxing Wang. The unreasonable fairness of maximum nash welfare. ACM Transactions on Economics and Computation, 7(3):12, 2019.

[bib.bib15] [15] Hau Chan, Jing Chen, Bo Li, and Xiaowei Wu. Maximin-aware allocations of indivisible goods. In Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems, AAMAS ’19, pages 1871–1873, 2019. URL: http://dl.acm.org/citation.cfm?id=3331947.

[bib.bib16] [16] Bhaskar Ray Chaudhury, Jugal Garg, and Kurt Mehlhorn. EFX exists for three agents. J. ACM, 71(1):4:1–4:27, 2024. doi:10.1145/3616009.

[bib.bib17] [17] Bhaskar Ray Chaudhury, Telikepalli Kavitha, Kurt Mehlhorn, and Alkmini Sgouritsa. A little charity guarantees almost envy-freeness. SIAM J. Comput., 50(4):1336–1358, 2021. doi:10.1137/20M1359134.

[bib.bib18] [18] George Christodoulou, Amos Fiat, Elias Koutsoupias, and Alkmini Sgouritsa. Fair allocation in graphs. In Kevin Leyton-Brown, Jason D. Hartline, and Larry Samuelson, editors, Proceedings of the 24th ACM Conference on Economics and Computation, EC 2023, London, United Kingdom, July 9-12, 2023, pages 473–488. ACM, 2023. doi:10.1145/3580507.3597764.

[bib.bib19] [19] Paul W. Goldberg, Kasper Høgh, and Alexandros Hollender. The frontier of intractability for EFX with two agents. In Algorithmic Game Theory - 16th International Symposium, SAGT 2023, Egham, UK, September 4-7, 2023, Proceedings, volume 14238 of Lecture Notes in Computer Science, pages 290–307. Springer, 2023. doi:10.1007/978-3-031-43254-5_17.

[bib.bib20] [20] Hadi Hosseini, Sujoy Sikdar, Rohit Vaish, and Lirong Xia. Fair and efficient allocations under lexicographic preferences. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 5472–5480, 2021. doi:10.1609/AAAI.V35I6.16689.

[bib.bib21] [21] Vishwa Prakash HV, Pratik Ghosal, Prajakta Nimbhorkar, and Nithin Varma. EFX exists for three types of agents. CoRR, abs/2410.13580, 2024. doi:10.48550/arXiv.2410.13580.

[bib.bib22] [22] Alireza Kaviani, Masoud Seddighin, and AmirMohammad Shahrezaei. Almost envy-free allocation of indivisible goods: A tale of two valuations. In Web and Internet Economics - 20th International Conference, WINE 2024, Proceedings. Springer, 2024.

[bib.bib23] [23] Richard J Lipton, Evangelos Markakis, Elchanan Mossel, and Amin Saberi. On approximately fair allocations of indivisible goods. In Proceedings of the 5th ACM Conference on Electronic Commerce, pages 125–131, 2004. doi:10.1145/988772.988792.

[bib.bib24] [24] Ryoga Mahara. Existence of EFX for two additive valuations. Discret. Appl. Math., 340:115–122, 2023. doi:10.1016/J.DAM.2023.06.035.

[bib.bib25] [25] Benjamin Plaut and Tim Roughgarden. Almost envy-freeness with general valuations. SIAM J. Discret. Math., 34(2):1039–1068, 2020. doi:10.1137/19M124397X.

[bib.bib26] [26] Alkmini Sgouritsa and Minas Marios Sotiriou. On the existence of EFX allocations in multigraphs. In Proceedings of the 24th International Conference on Autonomous Agents and Multiagent Systems, pages 2735–2737, 2025. doi:10.5555/3709347.3743995.

[bib.bib27] [27] Alkmini Sgouritsa and Minas Marios Sotiriou. On the existence of EFX allocations in multigraphs. CoRR, abs/2502.09777, 2025. doi:10.48550/arXiv.2502.09777.

[bib.bib28] [28] Jinghan A Zeng and Ruta Mehta. On the structure of EFX orientations on graphs. In Proceedings of the 24th International Conference on Autonomous Agents and Multiagent Systems, pages 2309–2316, 2025. doi:10.5555/3709347.3743871.

[bib.bib29] [29] Yu Zhou, Tianze Wei, Minming Li, and Bo Li. A complete landscape of EFX allocations on graphs: goods, chores and mixed manna. In Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence, pages 3049–3056, 2024. URL: https://www.ijcai.org/proceedings/2024/338.

[bib.bib30] [30] David Zuckerman. Linear degree extractors and the inapproximability of max clique and chromatic number. In Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, pages 681–690, 2006. doi:10.1145/1132516.1132612.

Extending EFX Allocations to Further Multi-Graph Classes

Abstract

Keywords and phrases:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

Funding:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

1.1 Our Contribution

1.2 Comparison with Recent Work

2 Notation and Preliminaries

Multi-graphs.

Fair division.

Valuation functions.

Proposition 1.

Proof.

Proposition 2.

Cut and Choose.

3 EFX Allocations in Bipartite Multi-graphs

Structures

Theorem 3.

Lemma 4.

Proof.

4 EFX Allocations for Monotone Valuations in Tree Multi-graphs

Theorem 5.

Proof.

5 EFX Allocations in 𝒕-Chromatic Multi-graphs with Girth at Least (𝟐⁢𝒕−𝟏)

Structures

Claim 6.

Proof.

Claim 7.

Proof.

Proposition 8.

Proof.

Claim 9.

Proof.

Claim 10.

Proof.

Lemma 11.

Proof.

Theorem 12.

Proof.

Theorem 13.

Proof.

6 Conclusion

References

5 EFX Allocations in $𝒕$ -Chromatic Multi-graphs with Girth at Least $(2t-1)$