Paper deep dive
EFX Allocation In (Multi)Hypergraphs
Thanasis Lianeas, Alkmini Sgouritsa, Minas Marios Sotiriou
Intelligence
Status: not_run | Model: - | Prompt: - | Confidence: 0%
Entities (0)
Relation Signals (0)
No relation signals yet.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:We study fair allocations of indivisible goods among agents with heterogeneous monotone valuations. As fair we consider the allocations that are envy-free-up-to-any-good (EFX). Finding if EFX alloca- tions always exist, even for agents with additive valuations, is a major open problem in Fair Division. Christodoulou et al. (2023) introduced the (multi-hyper)graph setting, where agents and goods are represented by vertices and edges of a graph, respectively, and only the endpoints of an edge may have non-zero marginal value for it. We show that for hypergraphs with girth at least 4 and agents with general monotone valuations there always exists an EFX allocation and can be constructed in polynomial time. We generalize our approach to also show that multi-hypergraphs with girth (on the simple hypergraph) at least 4 always admit an EFX allocation, as long as there exists a single vertex whose incident edges have multiplicity at most the size of that edge minus 2; our construction in this case needs pseudo-polynomial time.
Tags
Links
- Source: https://arxiv.org/abs/2608.03171v1
- Canonical: https://arxiv.org/abs/2608.03171v1
Trouble viewing inline? Open PDF directly →
Full Text
63,279 characters extracted from source content.
Expand or collapse full text
EFX ALLOCATION IN (MULTI)HYPERGRAPHS Thanasis Lianeas University of West Attica Greece Alkmini Sgouritsa Athens University of Economics and Business Archimedes/Athena RC Greece Minas Marios Sotiriou Athens University of Economics and Business Archimedes/Athena RC Greece ABSTRACT We study fair allocations of indivisible goods among agents with heterogeneous monotone valuations. As fair we consider the allocations that are envy-free-up-to-any-good (EFX). Finding if EFX alloca- tions always exist, even for agents with additive valuations, is a major open problem in Fair Division. Christodoulou et al. (2023) introduced the (multi-hyper)graph setting, where agents and goods are represented by vertices and edges of a graph, respectively, and only the endpoints of an edge may have non-zero marginal value for it. We show that for hypergraphs with girth at least 4 and agents with general monotone valuations there always exists an EFX allocation and can be constructed in polynomial time. We generalize our approach to also show that multi-hypergraphs with girth (on the simple hypergraph) at least 4 always admit an EFX allocation, as long as there exists a single vertex whose incident edges have multiplicity at most the size of that edge minus 2; our construction in this case needs pseudo-polynomial time. arXiv:2608.03171v1 [cs.GT] 4 Aug 2026 1 Introduction Fair division of resources among agents is an important topic, from dividing inheritance, to allocating computational resources to training models. Many situations fall under the category of fair division of indivisible goods, which is the central theme of this paper. There are sites (e.g. http://w.spliddit.org/) that provide mechanisms for such applications, based on theoretical results. The research of fair division dates back to almost 80 years ago [39]. A well studied and established notion of fair allocations are envy-free allocations, where nobody envies another agent [26,25,41], which always exists for divisible resources [40,42,7]. However, envy-free allocations may not always exist regarding indivisible goods; consider for instance the case of two agents and a valued good, where whoever gets the good is envied by the other agent. Since the envy-free condition is too strict in this case, two natural relaxations were defined. The first notion is envy-freeness up to one good (EF1) [14]. Such an allocation always exists and can be computed in polynomial time [35], even when agents have arbitrarily heterogeneous (monotone) valuations over the sets of goods. The second notion, which is the one considered here, is envy-freeness up to any good (EFX) [16, 27] and it is stricter than EF1. In contrast to EF1, it is unknown if EFX allocations always exist, and this problem has been described as “Fair Division’s Most Enigmatic Question” [37]. An EFX allocation is known to exist only in special cases: for 2 agents with heterogeneous monotone valuations [36], for 3 agents with additive valuations or a slightly more general class of valuations [17,4], and for many agents with identical monotone valuations [36]. Other results limit the valuation function of the agents or consider limited types of agents (e.g., [5, 30, 28, 8]). Christodoulou et al. [20]introduced a restriction on the valuations by relying on a graphical structure. More precisely, agents and edges are represented by vertices and edges, respectively, and only the agents that are the endpoints of an edge/good may consider it valuable. The motivation behind the graph setting is about instances where multiple agents find valuable a “neighboring” good but not all of them (e.g. geographic settings between neighboring countries, or allocation of work space between research labs). Moreover, the multi-hypergraph setting is basically the unrestricted setting, therefore, exploring ways of coping with graph settings may be proven useful for solving the general problem. Christodoulou et al. [20]showed that it is not always possible to construct an EFX allocation by orienting the edges of the graph, i.e., by allocating each edge to one of its endpoints, even for 4 agents, however, they showed that EFX allocations always exist. There have been several follow-up works considering the existence of EFX allocations in graph settings: Kaviani et al. [34]showed existence of EFX allocations for the multigraph setting when agents have restricted additive valuations, 1 and there is a line of works showing existence of EFX allocations in multigraphs for more general valuations under restrictions on the graph structure [3,12,38]; a common restriction that appears in all those works is about the girth of the underlying simple graph. Our results is in the same direction and focus on the existence of EFX allocations in hypergraph and multi-hypergraph setting with girth at least 4. We note that for hypergraphs with girth at least 3, the best known result is only an approximation of the EFX guarantee ( √ 2 2 −EFX existence) for subadditive valuations [34]; we manage to show exact EFX guarantees for general monotone valuations by slightly relaxing the restriction on the girth. 1.1 Our Results. We show that an EFX allocation always exists for hypergraphs of girth at least 4, when agents have general heterogeneous monotone valuations. We do this by constructing this allocation in polynomial time. The following theorem describes this first result. Theorem 1. Instances on hypergraphs of girth at least 4 always admit an EFX allocation that can be constructed in polynomial time to the number of agents and goods. We generalize our result, by considering a multi-hypergraph of girth at least 4: such a graph may contain multiple edges of the same subset of vertices, i.e., each edge may have multiplicity more than 1, but the simple underlying hypergraph (by considering multiplicity 1 for all edges) has girth at least 4. We remark that with no further restriction, the existence of EFX allocations in such a setting reduces to the general problem of EFX existence: consider a single edge containing all vertices of multiplicity equal to the number of goods. In our second result we prove the existence of EFX allocation in multi-hypergraphs of girth at least 4 as long as there exists a single vertex whose incident edges have multiplicity at most the size of that edge minus 2; our construction in this case needs pseudo-polynomial time. We justify the importance of this restriction by showing that if we slightly relax this restriction, the problem of EFX existence with at most one unallocated good reduces to the problem we try to solve; this problem is considered quite difficult and it is solved only for the case of 4 agents [11]. Our second result is summarized in the next theorem. 1 In restrictive additive valuations each agent values each goodgby either a fixed valuev g for goodg, or0. Then, the valuation for any set equals the sum of the values for each good in the set. 2 Theorem 2. For multi-hypergraphs with girth at least 4 where there exists a vertex whose incident edges have multiplicity at most the edge’s size minus 2, there exists an EFX allocation constructed in pseudo-polynomial time. Our approach.It is well known that EFX orientations may not exist even in simple graphs (see the counterexample in [20] regarding the existence of EFX orientations), hence, it may be the case that in an EFX allocation some edges are allocated to vertices that are not endpoints of those edges. Our approach anticipates this fact and initially chooses an arbitrary vertex (vertex0in our analysis) to serve as the vertex to “park" those edges. One such vertex is sufficient in the case of simple hypergraphs (Theorem 1), however when we consider edges of higher multiplicity than 1 (Theorem 2), more such vertices may be needed, and for that we employ the neighbors of vertex 0 to play such a role. 1.2 Further Related Work. EFX in Multigraphs and hypergraphs. Christodoulou et al. [20]introduced the graph setting and showed the existence of EFX allocation when the graph is simple and the items are goods. This result was extended to the case of mixed manna, where items may be both goods and chores [44]. Kaviani et al. [34]showed that multigraphs where agents have restricted additive valuations always admit an EFX allocation. Afshinmehr et al. [3], and Bhaskar and Pandit[12]proved that bipartite multigraphs where agents have additive and cancelable valuations, respectively, admit EFX allocations. In parallel, Sgouritsa and Sotiriou[38]showed that multigraphs with girth at least 6, or multigraphs where each vertex is connected with roughly at most a quarter of the other vertices, admit EFX allocations for agents with general monotone valuations, and Bhaskar and Pandit[12]showed thattcolored multigraphs with girth at least 2t− 1for agents with cancelable valuations admit EFX allocations. Subsequently, Afshinmehr et al. [1]showed that triangle-free multigraphs (girth≥ 4) always admit EFX allocations for general monotone valuations. Recently, in parallel two papers in different approaches showed existence of EFX allocation on multigraphs with cancelable valuations [22, 2]. Approximate EFX-allocations have also been studied in multigraphs and hypergraphs. Amanatidis et al. [6]showed that 2 3 −EFX allocations always exist in multigraphs when agents have additive valuations, which was recently improved to a √ 2 2 −EFX [33]. Kaviani et al. [34]showed that for hypergraphs with girth at least 3 (meaning that any two agents share at most one edge), √ 2 2 -EFX allocations always exist when agents have subadditive valuations. In the graph and multigraph setting the existence of EFX orientations, i.e., allocations where edges may only be allocated to one of the endpoints, has also been considered. Christodoulou et al. [20]showed that EFX orientations need not exist by giving a counterexample in aK 4 graph, and they further showed that even deciding if an EFX orientation exists is NP-complete; it was later shown that this result holds even if the vertex cover of the graph has size 8, or in multigraphs with only 10 vertices [23], which was later improved to a vertex cover of size 4 or multigraphs with as few as 4 vertices by [32]. Zeng and Mehta[43]showed that EFX orientations may not exist in graphs with chromatic number greater than 3, and they always exist when the chromatic number is at most 2. The complexity of orientations has been further explored, e.g., [29, 3, 13]. Another fairness criterion known as maximin share (MMS) has also been explored in multigraphs [21, 24]. EFX with charity. The concept of (partial) EFX allocation with unallocated goods, known also as EFX allocation with charity, was introduced by Caragiannis et al. [15]. Chaudhury et al. [19]showed that EFX allocations always exist, even with general monotone valuations, if at mostn− 1goods are donated to charity, wherenis the number of agents, and moreover nobody envies the charity. The size of the charity was then improved ton− 2, and to one for the case of 4 agents with valuations slightly more general than additive [11]. For hypergraphs with girth at least 3, the size of the charity was reduced to⌊ n 2 ⌋− 1for general monotone valuations [34]. Finally, the number of unallocated goods was subsequently improved to sublinear by [18, 4, 9, 31], but for approximate EFX. 2 Preliminaries We consider a setting where there is a setNofnagents and a setMofmindivisible goods, and each agentihas a valuation functionv i : 2 M →R ≥0 , over the subsets of goods, i.e.,v i (S)denotes the valuation of agentifor the subsetSof goods. The valuation functions are considered to be monotone, i.e., for anyS ⊆ T ⊆ M, it holds that v i (S) ≤ v i (T), and normalized, i.e.,v i (∅) = 0. For simplicity, for the valuation ofifor some goodg, we write v i (g)instead ofv i (g). An allocationX = (X 1 , . . . , X n )is a partition of a subset of goods intondisjoint bundles X 1 , . . . , X n , where each agentireceivesX i . An allocation is complete if it allocates all the goods, and partial if not. Throughout, for k ∈N + , we let [k] :=1, 2, . . . , k. 3 Envy - EFX allocation. Given an allocationX = (X 1 , . . . , X n ), an agentienvies an agentj(or alternatevlyX j ), if v i (X i ) < v i (X j ). An allocationX = (X 1 , . . . , X n ) is EFX if for any pair of agents i, j it holds that: v i (X i )≥ v i (X j \g) ,∀g ∈ X j . In other words, in an EFX allocation, no agent envies a proper subset of what is allocated to any other agent. We assume that the setting is modeled on hypergraphs. A hypergraph is a pairG = (V, E)whereVis a set of vertices andEis a set of subsets ofV, called hyperedges or simply edges. The size of an edge is the number of vertices it contains. For an edgee∈ Eand a vertexi∈ ewe say thateis incident toiandiis incident toe, oriis an endpoint of e. If vertices i and j belong to some edge e (i.e., i, j ∈ e), we say that i and j share e and we call i and j neighbors. Cycles [10] - Girth. For a hypergraphG, a cycle of length k is defined by a sequence(x 1 , e 1 , x 2 , e 2 , . . . , x k , e k , x k+1 ) such that: (i)x 1 , x 2 , . . . , x k are distinct vertices andx k+1 = x 1 , (i)e 1 , e 2 , . . . , e k are distinct edges and (i) x i , x i+1 ∈ e i ,∀i ∈ [k]. A hypergraphGhas girthk, ifG’s shortest cycle has lengthk; if there is no cycle inGthe girth is infinity. Hypergraph setting. In the hypergraph setting, we let agents correspond to vertices of a hypergraphG = (V, E), and goods correspond to edges ofG. For ease, we refer to the agents as vertices and to goods as edges. The edges that are not incident to some vertexiare irrelevant to it, i.e., for anyS ⊆ Eand anye∈ Esuch thati /∈ e,v i (S∪e) = v i (S). Note that this implies that for e∈ E irrelevant to i∈ V : v i (e) = v i (∅) = 0. We call an edge e relevant to i, if i∈ e. Orientation. An allocationX is an orientation if for any allocated edge e, if e∈ X i , then i is an endpoint of e. Unallocated edges. Given a partial allocationX, an edgeeis unallocated ife /∈ X i , for alli∈ V. We denote byU(X) the set of unallocated edges inX. For each vertexi, we defineU i (X)to be the set of all the unallocated edges that are relevant to i. We give the following two observations for hypergraphs with girth at least3and at least4. For hypergraphs with girth at least3, any two vertices may share at most one edge, and for hypergraphs with girth at least4, any two vertices of an edge e do not share any other common neighbor outside e. Observation 2.1. In hypergraphs with girth at least 3, any two vertices may share at most one edge. Proof. On the contrary, leti, jbe two vertices that both belong to edges, say,e 1 ande 2 . Starting with vertexi, following edgee 1 to reachjand then following edgee 2 to reachiwe get a cycle of length 2, i.e., the cycle(i, e 1 , j, e 2 , i), contradicting the hypothesis that the girth is at least 3. Observation 2.2. In hypergraphs with girth at least 4, any two vertices of an edgeedo not share any other common neighbor outside e. Proof.On the contrary, let verticesx, ybelong in some edgeeand letvbe one of their common neighbors outsidee. Lete x be an edge thatxandvshare. By Observation 2.1ycannot belong ine x , or elsexandywould shareeande x . Let e y be an edge that y and v share. The cycle (x, e x , v, e y , y, e, x) has length 3, which is a contradiction. Multi-hypergraph setting. In Section 4 we allow for a more general hypergraph setting. In the multi-hypergraph setting the edge setEis allowed to have edges of the same set of vertices. Such edges correspond to different goods, with possibly different impact on the valuation functions of the vertices/agents. For an edgeethat appearsktimes inEwe say thatehas multiplicityk. For a multi-hypergraphG = (V, E)we define the girth ofGto be the girth of G ′ = (V, E ′ ), where E ′ is derived from E if we delete all repetitions of the edges of E. 3 EFX on Hypergraphs For ease of presentation we will rename/reorder the vertices using numbers from0ton− 1. Pick an arbitrary vertex and let it be vertex0. Letn 0 be the number of neighbors that vertex0has. Arbitrarily, name the neighbors of0with numbers from1ton 0 and the remaining vertices with numbers fromn 0 + 1ton− 1. Throughout the runs of the presented algorithms, vertices will be prioritized based on their names-labels, in a decreasing order. We next repeat the main theorem of the section whose proof is built up by the use of several lemmas. Theorem 1. Instances on hypergraphs of girth at least 4 always admit an EFX allocation that can be constructed in polynomial time to the number of agents and goods. 4 Algorithm 1 FixProp3 Input: An allocationX satisfying Property (1) Output: An allocationX satisfying Properties (1) and (3). 1: while∃ j ∈ V, e∈ U(X): v j (e) > v j (X j ) do 2:Let j be the maximum vertex with this property for some e 3:X j ←arg max e∈U j (X) v j (e) 4: end while 5: returnX The proof is constructive and is described in the following subsections. At each time we preserve an EFX allocation by satisfying additional properties. Our intermediate goal, achieved by Algorithm 2, is to achieve a partial allocation by orienting edges that satisfies the following four Properties. 1.X is a (partial) EFX orientation. 2.Vertex0is non-envied and any neighboriof vertex0may be envied only if it is allocated the edge that it shares with 0. 3. For any vertex i and e∈ U i (X), v i (X i )≥ v i (e). 4. For any envied vertex i, v i (X i )≥ v i (U i (X)). Properties(1)-(2)are preserved throughout Algorithm 2, and Algorithm FixProp3 therein guarantees Property(3). At the end of Algorithm 2, a stronger property for the envied vertices than(3)is satisfied, namely Property(4). In Algorithm 3 and Lemma 3.5 we show how those properties are used in order to construct a complete EFX allocation. Proof of Theorem 1. For the proof of Theorem 1 it suffices to run in series Algorithms 2 and 3. By Lemmas 3.2, 3.3, 3.4 and 3.5 we show that if the instance is a hypergraph of girth at least 4, the final allocation will be a complete EFX allocation. In Lemma 3.6 we show that those algorithms run in polynomial time, which completes the proof. 3.1 Orienting edges. Algorithm FixProp3 is called in order to ensure that no unallocated edge is preferred by any vertex over its bundle. Lemma 3.1. When FixProp3 is called for an EFX orientation, it outputs an EFX orientation satisfying Property (3). Proof.First note that FixProp3 will terminate since the bundles (and thus the values) that a vertex may get are finite, and at every execution of the while-loop, the value of some vertex for the updated allocation strictly increases. To see that Property(3)is satisfied in the resulting allocation, see that the condition of the while-loop is the negation of Property (3), so FixProp3 terminates by satisfying it. Clearly, the allocating step of line 3 orients a single (unallocated) edge to one of its incident vertices. This keeps the allocation an orientation. This allocation further remains an EFX allocation after each execution of the while-loop, since for the new bundle/edge allocated in line 3, removing the single edge it contains will leave it empty and thus non-envied. Also the value of the vertices may only increase during the execution of FixProp3; thus, no further envy may appear in the future and the EFX property will not break. Algorithm 2 starts by assigning each vertex, in decreasing order, its most valuable unallocated edge (one call of FixProp3). It continues by repeatedly offering envied vertices all their incident unallocated edges in place of their current bundle. If an envied vertex prefers all its incident unallocated edges to its currently allocated bundle, it is allocated those edges, it releases its bundle, followed by one call of FixProp3, i.e., repeatedly, any unallocated single edge is offered to vertices, in decreasing order, until no vertex prefers an unallocated edge. This algorithm is similar to Algorithm 2 in [20], but edges might have size greater that 2, and an order is added when offering a single unallocated edge, to make sure that Property (2) is satisfied. Lemma 3.2. After the termination of Algorithm 2, Properties (1), (3) and (4) are satisfied. Proof. Algorithm 2 will terminate since both FixProp3 and the allocating step of line 4 only strictly increase the value that a vertex gets and the bundles (and thus the values) that a vertex may get are finite. The condition of the while-loop of Algorithm 2 is the negation of Property(4). Since the condition of the while-loop must be false for the algorithm 5 Algorithm 2 Orienting Edges Input: A hypergraph G of girth at least 4. Output: An allocationX satisfying Properties (1)-(4). 1: LetX be the all empty allocation. 2: FixProp3(X) 3: while ∃ envied i∈ V : v i (U i (X)) > v i (X i ) do 4:X i ← U i (X) 5:FixProp3(X) 6: end while to terminate, Property(4)will hold. Additionally, since the algorithm ends with a call of FixProp3, by Lemma 3.1, Properties (1) and (3) will also be satisfied as long as Property (1) was satisfied before the call of FixProp3. It remains to show that Property(1)was satisfied before any call of FixProp3. The empty allocation clearly satisfies Property(1), so it is satisfied before the call of FixProp3 at line 2. Suppose that Properties(1)and(3)are satisfied before an execution of any round of the while-loop, which is the case before the first execution of the while-loop. It suffices to show that the allocating step of line 4 does not break the EFX property (it clearly gives an orientation); this would guarantee that Property(1)is satisfied before FixProp3, and by Lemma 3.1, Properties(1)and(3)would be indeed satisfied before the next round of the while-loop. Consider a vertexithat will get its bundle changed by the allocating step of line 4. By Observation 2.1, for any other vertexj,U i (X)contains at most one edge, saye, relevant to j. By Property(3), vertexjdoes not prefere, if it exists, i.e.,v j (X j )≥ v j (e) = v j (U i (X))and thusjwill not envyi. Also the value of the vertices may only increase during the execution of Algorithm 2, and therefore no further envy may appear and the EFX property will not break. We will prove that Algorithm 2 will output an allocation also satisfying Property (2) in the next two lemmas. Lemma 3.3. Vertex 0 is non-envied throughout the execution of Algorithm 2. Proof.Initially it isX 0 =∅and thus0is non-envied. Any time that FixProp3 is called, in order for0to be considered for a change in its bundle, it must be that all other vertices do not prefer any of the unallocated edges, since all of them have higher index from0. This directly implies that if0is allocated some edge by FixProp3, no other vertex will envy it and thus, since the values of the vertices may only increase,0remains non-envied. Hence, vertex0is never considered in the while-loop of Algorithm 2, and overall, it remains non-envied throughout the execution of Algorithm 2. Lemma 3.4. After the termination of Algorithm 2, any neighboriof vertex0may only be envied if it is allocated the edge that it shares with 0. Proof. Consider any vertexi ∈ [n 0 ], i.e., a neighbor of0, and the bundleX i allocated toiafter the termination of Algorithm 2. If|X i | = 0, obviouslyiis non-envied. If|X i | > 1, theniis still non-envied due to Property(1): Consider any other vertexjand letebe the edge, if any, that it shares withi; by Observation 2.1,iandjmay share at most one edge. Ife /∈ X i , obviouslyv j (X i ) = 0, andjdoesn’t envyi. Ife∈ X i , since|X i | > 1, lete ′ ̸= ebe some other edge inX i . Then, by Property(1)it should be thatjdoes not preferX i \e ′ ⊇eto the bundle allocated toj. Sinceeis the only valuable edge for j in X i , j does not envy i. In the case that|X i | = 1, letebe the edge assigned toiand suppose thateis not the edge thatiand0share. Since Algorithm 2 only orients edges,eis relevant toi. We first show thatecannot be relevant to any other neighbor of0, and therefore none of them envyi. Letj ∈ [n 0 ]be some neighbor of0belonging to the edge that0andishare. By Observation 2.1,eis irrelevant toj. Letj ∈ [n 0 ]be some neighbor of0not belonging to the edge that0andishare. Due to Observation 2.2, verticesi, jcannot both belong in the same edge, saye ′ , or else they would have vertex0as a common neighbor outside e ′ . Thus, e is irrelevant to j. Vertices indexed higher thann 0 did not envyiat the time it receivedX i during the execution of Algorithm 2: If X i =ewas allocated toiin a run of FixProp3, vertexiwas considered as the highest indexed vertex that preferred eto what it got allocated, implying that all vertices with index higher thanipreferred their bundles over every single unallocated edge, soeas well. IfX i was allocated toiin the while-loop of Algorithm 2, then Property(3)(from the previous FixProp3 run) guarantees that nobody enviediat that point. Note thatiremains non-envied until the termination of Algorithm 2, since the vertices’ value may only increase. 6 Algorithm 3 Complete allocation Input: The allocationX returned by Algorithm 2. Output: A complete EFX allocationX. 1: while ∃e∈ U(X) containing a non-envied vertex j do 2:X j ← X j ∪e 3: end while 4: X 0 ← X 0 ∪ U(X) 3.2 Complete EFX allocation. In Algorithm 3 we allocate in two steps the remaining edges (if any) to reach a complete EFX allocation. Unallocated edges incident to a non-envied vertex are oriented towards some non-envied vertex and the rest are allocated to 0. Lemma 3.5. IfX is the allocation returned by Algorithm 2, then Algorithm 3 returns a complete EFX allocation. Proof.There are two steps in Algorithm 3 for allocating the remaining edges, one in line 2, and the other in line 4. We will show that at each of them no further envy is created. In line 2, each unallocated edge containing a non-envied vertex is oriented towards one of its non-envied vertices. This keeps the allocation EFX. To see this, first note that when an edgeeis allocated to a vertexiin this way, only vertices incident toemay envyi, andewill be the only edge that they share withi(Observation 2.1). SinceXis an orientation, this implies that for any of these vertices, sayj, v j (e) = v j (X i ∪e). Yet, due to Property(3),jprefers its bundle overe, i.e.,v j (X j ) ≥ v j (e) = v j (X i ∪ e), and thus it will not envy i. Note that at the end of the while-loop, the allocation is still an orientation and Properties(1)-(4)are still satisfied. Additionally, the remaining unallocated edges have all their incident vertices envied. For the rest of the proof,X represents the updated allocation after the while-loop. It remains to show that allocating the rest of the unallocated edges to0will not create any envy towards0. Since all those edges are relevant only to envied vertices, we will show that any envied vertexiwill not envy vertex0after the allocation in line 4. Ifiis a neighbor of vertex0, due to Property(2),ihas received the shared edge with0, and thereforeihas no value forX 0 . The same holds ifiis not a neighbor of vertex0, since after the while-loop, the allocation is still an orientation. Therefore, in both cases, due to Property(4),v i (X i )≥ v i (U i (X)) = v i (X 0 ∪ U(X)), and so i does not envy vertex 0 in the final allocation. 3.3 Poly-time EFX construction. To complete the proof of Theorem 1, we show that the construction of the EFX allocation needs polynomial time. Lemma 3.6. The construction of the EFX allocation by running Algorithms 2, and 3 needs polynomial time complexity on the number of edges and vertices. Proof.Algorithm 2 uses FixProp3 as a subroutine, which runs in timeO(n 4 ): Each while-loop needs at mostn 2 checks to find an appropriate vertex (since each vertex has degree at mostn− 1), and if those checks follow the priority of the vertices, no extra time is needed to find the maximum vertex (at line 2). Each vertex may update its allocation, i.e., be considered in the while, at mostntimes (it has at mostnrelevant edges and any time it strictly increases its value). So, overall the while-loop may be executed at most n 2 times and each execution needs O(n 2 ) time. Regarding Algorithm 2, the vertex picked in the while is changed from envied to non-envied (in line 4). We remark that in FixProp3, a non-envied vertex may turn to an envied one, however the value each vertex has for its allocated bundle always strictly increases when it updates her bundle. Therefore, each vertex may turn from non-envied to envied at mostntimes, since every envied vertex receives a single edge andnis an upper bound of its degree. Therefore, the while-loop may be executed at most n 2 times. Overall, the time complexity of Algorithm 2 is O(n 6 ). Algorithm 3 allocates at mostmedges, each in timeO(n), which is the time needed to identify if there exists a non-envied endpoint. Therefore, the time complexity of Algorithm 3 isO(nm). Hence, the construction of an EFX allocation needs overall polynomial time on n and m. 7 4 EFX on Multi-hypergraphs In this section we generalize our approach so it can be applied to the more general setting of multi-hypergraphs. We next repeat the main theorem of this section whose proof is built up by the use of several lemmas. Theorem 2. For multi-hypergraphs with girth at least 4 where there exists a vertex whose incident edges have multiplicity at most the edge’s size minus 2, there exists an EFX allocation constructed in pseudo-polynomial time. Before proceeding to the proof of Theorem 2 we show the necessity of the additional restriction, in the sense that dropping it makes our problem at least as hard as a difficult problem in the literature. More precisely, we construct an instance of a multi-hypergraph with girth at least 4, where there is no vertex whose all incident edges have multiplicity at most the edge’s size minus 2, and there exists a vertex that violates this condition only for one of its incident edges, for which the multiplicity is its size minus 1. We show that the general problem of EFX existence with at most one unallocated good reduces to finding an EFX allocation in that instance. We stress out that the problem of EFX existence with at most one unallocated good is considered a hard problem (see Section 1.2). Lemma 4.1. Consider any instanceIofnagents andm≥ ngoods, where agents have arbitrary monotone positive valuations. Then, there exists an instanceI ′ on a multi-hypergraph withn + 1vertices,m + 1edges and girth at least 4, where there is no vertex whose all incident edges have multiplicity at most that edge’s size minus 2, and there exists a vertex with a single incident edge of multiplicity equal its size minus 1, and an EFX allocation inI ′ implies an EFX allocation with at most one unallocated good inI. Proof.LetN = [n] = 1, . . . , nandM = e 1 , . . . e m be the set of agents and goods, respectively, inI. We construct a multi-hypergraph instanceI ′ with vertex setN ′ = N ∪0, and edge setM ′ = M ∪e 0 , where e 0 =0, 1, ande j = [n]for alle j ∈ M, i.e., each edge apart frome 0 contains all the vertices but0. Note that in this example there is no cycle (the girth is infinity) and there is no vertex whose incident edges have multiplicity at most that edge’s size minus 2 and vertex0has a single incident edge of multiplicity equal its size minus 1. For any vertexi̸= 0, the valuation functionv i overM, coincide with the valuation that they have inI. The valuation for vertex1for any set Scontaininge 0 is0, ifS =e 0 , and greater thanv 1 (M)(its value for all edges excepte 0 ), otherwise. Vertex0has some positive value for e 0 . We argue that in any EFX allocation inI ′ , vertex0is allocatede 0 and at most one other edge. First note that if onlye 0 was allocated to any vertexi̸= 0,ihas value0, and some vertexj ≥ 1would be allocated at least 2 edges fromM. Since vertexivalues positively any of those edges, the EFX condition would be violated foriagainstj. Therefore, if e 0 was allocated to some vertexi̸= 0in any EFX allocation, vertexishould receive at least one more edge. In that case, vertex0would envy vertexiafter the removal of that edge (since vertex0values positively onlye 0 ), and the EFX condition would again be violated. So, we have established that in any EFX allocation,e 0 should be allocated to vertex 0. If vertex0was allocated at least two more edges, after the removal of any of those, vertex1would still envy vertex0, which is again a violation of the EFX condition. Hence, overall, in any EFX allocation vertex0is allocatede 0 and at most one other edge. In any such EFX allocation, the EFX condition is satisfied between the vertices inN, and their allocation gives an EFX allocation of the instanceI with at most one unallocated good, namely the good that is possibly given to vertex 0 apart from e 0 . We now proceed to the proof of Theorem 2. The proof is constructive and generalizes the EFX construction for simple hypergraphs (Section 3). Similarly, our intermediate goal here is the construction of a (partial) EFX allocation that satisfies four properties. The first two properties are as in Section 3 and the other are more generalized to handle the allowance of repetitions of edges. For that we need the following definition regarding multiple appearances of edges. Definition 4.2. For a setEof edges where repetitions are allowed,P e is the set of edges containing all the appearances ofeinE(i.e., edges with the same incident vertices); we refer toP e as the patch fore. If some edges ofEare allocated byX,U e (X)denotes the subset ofP e that contains all the unallocated edges ofP e underX, i.e.U e (X) = U(X)∩P e . Below we state the four properties for the multi-hypergraph setting. Property(3)differs from the corresponding property in simple hypergraphs in expressing no envy towards the whole unallocated set of any patch; in simple hypergraphs this was just a single edge. Property(4)is extended to consider all vertices (apart from the special vertex0) and not only the envied ones as in the case of simple hypergraphs; the reason is that we may not be able to orient all edges incident to non-envied vertices, so we need to guarantee that EFX doesn’t break when those are allocated to non-incident vertices. 2 The four properties are used in Algorithm 6 and Lemma 4.8 to construct a complete EFX allocation. 2 We remark that we could transform Algorithm 2 for simple hypergraphs to satisfy this more extended Property(4), however this was not necessary and so we kept only the necessary steps. 8 Algorithm 4 FixProp3Gen Input: An allocationX satisfying Property (1). Output: An allocationX satisfying Properties (1) and (3). 1: while ∃ i∈ V , e∈ E: v i (X i ) < v i (U e (X)) do 2:Z = Subroutine 7 (L = e, S = U e (X)). 3:k = arg max j v j (Z) > v j (X j ) 4:X k ← Z 5: end while 6: returnX 1.X is a (partial) EFX orientation. 2.Vertex0is non-envied and any neighboriof vertex0may be envied only if it is allocated some edge(s) that it shares with 0. 3. For any vertex i and any e∈ U i (X), v i (X i )≥ v i (U e (X)). 4. For any vertex i̸= 0, v i (X i )≥ v i (U i (X)). Before we delve deep into the proof of Theorem 2 we give a high-level proof sketch. Proof sketch.We keep a similar approach to Section 3: we employ an algorithm that outputs an allocation satisfying the four properties, and an algorithm that completes the EFX allocation. We define the vertices’ labels as in Section 3 by setting the special vertex whose incident edges have the restricted multiplicity as vertex 0. Algorithm 5 that satisfies the four properties is the same with Algorithm 2, by substituting the Algorithm FixProp3 with the more generalized Algorithm FixProp3Gen.FixProp3Gen basically applies ruleU 1 of [19] to each patch separately: It checks if there is a setZof unallocated edges in a single patch such that there exists a vertexkthat values it more than its bundle, while for the other vertices the EFX condition is satisfied ifkreceivesZ, i.e., they do not envy any proper subset ofZ. As long as such a vertexkand setZexist, the algorithm allocatesZtoi(without breaking EFX), while prioritizing vertices with a higher index to preserve Property(2). This Algorithm satisfies Property(3), as long as Property(1)was initially satisfied. Algorithm 5 initially calls FixProp3Gen to guarantee Properties(1)-(3), and then each vertex, except vertex0, is offered its relevant unallocated edges resulting in satisfying Property(4); the Algorithm FixProp3Gen is executed any time an offer is accepted so that Property(3)is preserved. Algorithm 5 terminates with all four properties satisfied. The final allocation (Algorithm 6) differs from the one in Section 3 because now there may be unallocated edges with non-envied endpoints that cannot be oriented. In Section 3, the unallocated edges that could not be oriented were given to vertex0without causing envy towards0, since all vertices that had positive value for those edges either were not neighbors to vertex0or they had received the single edge shared with vertex0(Property(2)); in both cases this meant that they had zero value forX 0 . In the multi-hypergraph setting, it may be that for vertices that value positivelyX 0 there are unallocated edges incident to them that cannot be oriented. In that case, no property guarantees that allocating those edges to vertex0would not create envy towards0. For those vertices, we find alternative vertices to “park" their relevant unallocated edges. Next we describe how we do that. IfX 0 =∅at this phase, we allocate all unallocated edges to vertex 0, and due to Property(4)no envy will be created. If X 0 ̸=∅, thenX 0 ⊆P e , for somee∈ E, asi = 0is not considered in line 3 of Algorithm 5. Since|P e |is no more than the size ofeminus 2 (by Theorem 2’s assumption), there would be two verticesj 1 , j 2 ∈ ethat are not allocated any edge fromP e . By Property(2), those two vertices are non-envied, and by Observations 2.1 and 2.2, each of the j 1 , j 2 is allocated edges that are irrelevant to any vertex ofeand their neighbors. So, allocatingU i (X)toj 1 , for any i∈ edifferent fromj 1 and0, andU j 1 (X)toj 2 , creates no further envy due to Properties(3)-(4). For any other vertex i /∈ e, X 0 is irrelevant for i, and so allocating U i (X) to vertex 0 again creates no further envy due to Property (4). 4.1 Construction of the EFX allocation. The complete EFX allocation is derived by the sequential execution of Algorithms 5 and 6. Algorithm 5 calls FixProp3Gen (Algorithm 4) to maintain Property(3). To succeed this, FixProp3Gen makes use of Subroutine 7 that returns a minimal setZof same patch edges that a vertex prefers to its bundle, meaning that no other vertex envies any proper subset ofZ. Subroutine 7 is the same with Algorithm 3 from [19]; we give Subroutine 7 in Appendix A for completeness. 9 Algorithm 5 Orienting Edges Input: A multi-hypergraph G of girth at least 4, where edges related to vertex 0 have multiplicity at most that edge’s size minus 2. Output: An allocationX satisfying Properties (1)-(4). 1: FixProp3Gen(X) 2: while ∃ vertex i̸= 0: v i (U i (X)) > v i (X i ) do 3:X i ← U i (X) 4:FixProp3Gen(X) 5: end while Lemma 4.3. When FixProp3Gen is called for an EFX orientation outputs an EFX orientation satisfying Property(3). Proof.First note that FixProp3Gen will terminate since the bundles (and thus the values) that a vertex may get are finite, and at every execution of the while, the value of some vertex for the updated allocation strictly increases. To see that Property(3)is satisfied in the resulting allocation, observe that the condition of while is the negation of Property (3), so FixProp3Gen terminates by satisfying it. The allocating step of line 4 orients a set of unallocated edges to one of its adjacent vertices; this is because the setZ returned by Subroutine 7 (line 2) is a subset ofU e (X), andkdefined in line 3 belongs toesincev k (Z) > v k (X k )≥ 0. This keeps the allocation an orientation. This allocation further remains an EFX allocation after each execution of the while, since no vertex envied a proper subset ofZand also the value of the vertices may only increase during the execution of FixProp3Gen, and therefore no further envy may appear in the future. Algorithm 5 extends Property (3) to Property (4) for all vertices but 0, while preserving Properties (1) and (2). Lemma 4.4. After the termination of Algorithm 5, Properties (1)-(4) are satisfied. Proof.Lemma 4.4 is proven by combining the following three lemmas. Lemma 4.5 shows that Properties (1) and(4) hold for the allocation that Algorithm 5 returns, then Lemmas 4.6 and 4.7 show that Property(2)hold for vertex 0, and any neighbor of vertex 0, respectively. Moreover, since Algorithm 5 terminates with a call of FixProp3Gen, by Lemma 4.3, Property (3) is also satisfied. Lemma 4.5. After the termination of Algorithm 5, Properties (1) and (4) are satisfied. Proof. Algorithm 5 will terminate since both FixProp3Gen and the allocating step of line 3 only strictly increase the value that a vertex gets and the bundles (and thus the values) that a vertex may get are finite. The condition of the while loop of Algorithm 5 is the negation of Property(4). Since the condition of the while loop must be false in order for the algorithm to terminate, it means that Property (4) will hold. It remains to show that Property(1)holds when Algorithm 5 terminates. First thing to note is that FixProp3Gen outputs an orientation if its input is an orientation and the allocating step of line 3 orients edges (towards one of its adjacent vertices), and thus the resulting allocation is an orientation (since the initial allocation is the empty allocation which is trivially an orientation). To see that the allocation remains EFX it suffices to show that the allocating step of line 3 does not break the EFX property, since by Lemma 4.3 FixProp3Gen does not break the EFX property. Consider a vertexithat gets its bundle changed by the allocating step of line 3. For any other vertexj, eitherjis noti’s neighbor, so will not envy i for receiving U i (X), or by Observation 2.1, U i (X) contains exactly one patch relevant to j, sayP e . Since FixProp3Gen terminated right before the update of line 3, vertexjdoes not prefer the unallocated set of that patch, i.e.,v j (X j )≥ v j (U e (X)) = v j (U i (X)), and thusiwill be non-envied. Also the value of the vertices may only increase during the execution of Algorithm 5, and therefore no further envy may appear and the EFX property will not break. Lemma 4.6. After the termination of Algorithm 5 vertex 0 is non-envied. Proof.Initially it isX 0 =∅and thus vertex0is non-envied. Note that vertex0may only change its allocated bundle during the procedure FixProp3Gen. Any time that FixProp3Gen is called, in order for vertex0to be considered for a change in its bundle it must be that all other vertices do not prefer the set of the edges that vertex0is allocated, since all of them have higher index than0. This directly implies that if vertex0is allocated a set of edges during FixProp3Gen no vertex will envy vertex 0 and thus, since the values of the vertices only increase, vertex 0 remains non-envied. 10 Algorithm 6 Complete allocation Input: The allocationX returned by Algorithm 5. Output: A complete EFX allocationX. 1: if X 0 ̸=∅ then 2:Let e be the edge such that X 0 ⊆P e . 3:Let j 1 , j 2 ∈ e be two non-envied vertices where X j ∩P e =∅, for j ∈j 1 , j 2 . 4:for every i∈ e\j 1 , 0 do 5:X j 1 ← X j 1 ∪ U i (X) 6:end for 7:X j 2 ← X j 2 ∪ U j 1 (X) 8: end if 9: X 0 ← X 0 ∪ U(X) Lemma 4.7. After the termination of Algorithm 5, any neighboriof vertex0may only be envied if it is allocated some edge(s) that it shares with 0. Proof.Consider any vertexi∈ [n 0 ], i.e., a neighbor of vertex0, and the bundleX i allocated toiafter the termination of Algorithm 5. IfX i = ∅, theniis trivially non-envied, otherwise we distinguish between the casesX i is a subset of a single patch or not. Consider first the case thatX i contains edges from at least two different patches, theniis non-envied due to Property(1). To see this suppose on the contrary thatiis envied by some vertexj. Sinceireceives only relevant edges to itself,jshould bei’s neighbor. By Observation 2.1,iandjshare only one patch; let it beP e . Sincejenviesi, it holds thatv j (X i ∩P e ) > v j (X j ), and sinceX i contains edges from at least two different patches, it holds thatX i e is not empty. So, after the removal of any edge fromX i e ,jwould still envyi, which violates the EFX condition and therefore Property (1). Hence, in this case, i is not envied. Suppose now thatX i contains edges from only one patch, soX i ⊆P e , for some edgee, and suppose thatP e is not the patch thatishares with vertex0. Since Algorithm 5 only orients edges,X i is relevant toi. We next show thatP e (and soX i ) cannot be relevant to any other neighbor of vertex0, and therefore none of them may envyi. Letj ∈ [n 0 ]be some neighbor of0belonging to the patch that0andishare. By Observation 2.1,P e is irrelevant toj. Letj ∈ [n 0 ]now be some neighbor of 0 not belonging to the patchiand0share. Due to Observation 2.2, verticesi, jcannot both belong in the same edge, let’s saye ′ , or else they would have vertex0as a common neighbor outsidee ′ . Thus,P e is irrelevant tojin that case as well. Vertices indexed higher thann 0 did not envyiat the time it receivedX i during the execution of Algorithm 5: IfX i was allocated toiin a run of FixProp3Gen, vertexiwas considered as the highest indexed vertex that preferredX i to what it got, implying that all vertices with index higher thanipreferred their bundles over every set of unallocated edges in some patch, which includesX i . IfX i was allocated toiin the while of Algorithm 5, then Property(3)(from the previous FixProp3Gen run) guarantees that nobody enviediat that point. Note thati remains non-envied until the termination of the Algorithm 5, since the vertices’ value may only increase. Algorithm 6 allocates any unallocated edges from the allocation of Algorithm 5. IfX 0 = ∅, then all remaining unallocated edges are allocated toX 0 . IfX 0 ̸=∅, we carefully select two non-envied neighbors of vertex0and the unallocated edges are allocated among those two vertices and 0 in such a way that no further envy is created. Lemma 4.8. LetXbe the allocation returned by Algorithm 5. Then, if Algorithm 6 takesXas input, it returns a complete EFX allocation. Proof.IfX 0 =∅at this phase, then we allocate all unallocated edges to vertex 0, and due to Property(4)no further envy will be created. For the case thatX 0 ̸=∅, we first establish that verticesj 1 , j 2 (line 3) exist. Note that vertex0may be only allocated edges from a single patch, so supposeX 0 ⊆P e , for some edgee∈ E. Since|P e |is no more than the size ofeminus 2 (by Theorem 2’s assumption), there would be two verticesj 1 , j 2 ∈ e, different from vertex0, that are not allocated any edge fromP e . By Property (2) those two vertices are non-envied. We next show thatj 1 will not be envied after the execution of lines 4-6. We show this by arguing that any vertex that finds relevant any edge allocated toj 1 during this procedure, foundX j 1 (as it was prior the execution of lines 4-6) irrelevant. Consider some vertexkthat finds relevant some of the edge(s) ofU i (X), for somei∈ e\j 1 , 0. If k ∈ ethen by Observation 2.1,kandj 1 do not share any other edge butP e , thereforev k (X j 1 ) = 0. Otherwise,k /∈ e is some neighbor of vertexi. By Observation 2.2,iandj 1 do not have any common neighbor outsidee, therefore, kis notj 1 ’s neighbor and so,kfindsX j 1 irrelevant, i.e.,v k (X j 1 ) = 0, in this case as well. Therefore, allocating 11 ∪ i∈e\j 1 ,0 U i (X)toj 1 do not make any vertexk ̸= 0envious towardsj 1 due to Property(4). Regarding vertex0, note that by Observation 2.1 vertex0do not share any other edge apart fromP e with any other vertexi ∈ e, so the relevant edges for vertex0in∪ i∈e\j 1 ,0 U i (X)are theU e (X); due to Property 3, vertex0will also not envyj 1 after the execution of lines 4-6. The same arguments hold for the allocation at line 7; no envy would be created towards vertexj 2 . Regarding the allocation at line 9, for any other vertexi /∈ e,X 0 is irrelevant fori, since vertex0is allocated edges only from patch P e , and so allocating U i (X) to vertex 0 creates no further envy due to Property (4). The running time of Subroutine 7 is polynomial on the number of different values of the social welfare, yet, this number can be exponential to the size of the input. Lemma 4.9. The construction of the EFX allocation by running Algorithms 5 and 6 needs pseudo-polynomial time. Proof.We first argue that each iteration of the while of the Procedure FixProp3Gen needs polynomial time. Checking the condition of the while needs time complexityO(n 2 ), as it needs to check for each of thenvertices, at mostn− 1 different patches (there at mostn− 1relevant patches for each vertex which coincides with its degree in the underlying simple hypergraph). Inside the while of FixProp3Gen, the Subroutine 7 is executed for a subset of vertices and edges and according to [19] it needs O(mn) time. Therefore, each execution of the while needs time O((m + n)n). We next argue that each iteration of the while of Algorithm 5, excluding the call of FixProp3Gen, needs polynomial time. Indeed, checking the condition of the while needs time complexityO(n), as it performs one comparison per vertex. Note that any time the while of FixProp3Gen is executed the sum of the vertices’ value (social welfare) strictly increases. The same holds in line 3 of the while of Algorithm 5. Therefore, after polynomially many steps an increment on the social welfare happens. Following the analysis of [19], that also used the social welfare as the potential of their algorithm, Algorithm 5 needs pseudo-polynomial time. Since Algorithm 6 allocates at mostmedges, while it requires timeO(n)to findj 1 , j 2 , the time complexity isO(m+n). Hence, overall, executing Algorithms 5 and 6 needs pseudo-polynomial time. 5 Conclusion Our results build upon the existing literature on graph setting based on the definition of [20], and push the state-of-the-art even further towards the general problem of EFX existence, which is equivalent to the multi-hypergraph setting without any restrictions. We introduce a different angle on the approach of the problem by designating from the start special vertices to allocate non-oriented edges. We remark that our approach is quite general and is applied to arbitrarily heterogeneous monotone valuations, and any restrictions come merely from the structure of the multi-hypergraph. Future directions include lifting the restrictions in the structure of the multi-hypergraph, or even improve complexity for restricted cases. 6 Acknowledgements The research project is implemented in the framework of H.F.R.I call “Basic research Financing (Horizontal support of all Sciences)” under the National Recovery and Resilience Plan “Greece 2.0” funded by the European Union- NextGenerationEU (H.F.R.I. Project Number:15635). This work has been partially supported by project MIS 5154714 of the National Recovery and Resilience Plan Greece 2.0 funded by the European Union under the NextGenerationEU Program. References [1]Mahyar Afshinmehr, Arash Ashuri, Pouria Mahmoudkhan, and Kurt Mehlhorn. 2025. EFX Allocations Exist on Triangle-Free Multi-Graphs. arXiv:2512.21644 [cs.GT] https://arxiv.org/abs/2512.21644 [2] Mahyar Afshinmehr, Arash Ashuri, Pouria Mahmoudkhan, Kurt Mehlhorn, and Amir Mohammad Shahrezaei. 2026. EFX Allocations Exist on Multi-Graphs. In Proceedings of the 27th ACM Conference on Economics and Computation (Rome, Italy). 12 [3]Mahyar Afshinmehr, Alireza Danaei, Mehrafarin Kazemi, Kurt Mehlhorn, and Nidhi Rathi. 2025. EFX Allocations and Orientations on Bipartite Multi-graphs: A Complete Picture. In AAMAS. International Foundation for Autonomous Agents and Multiagent Systems / ACM, 32–40. [4]Hannaneh Akrami, Noga Alon, Bhaskar Ray Chaudhury, Jugal Garg, Kurt Mehlhorn, and Ruta Mehta. 2023. 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, Kevin Leyton-Brown, Jason D. Hartline, and Larry Samuelson (Eds.). ACM, 61. doi:10.1145/3580507.3597799 [5]Georgios Amanatidis, Georgios Birmpas, Aris Filos-Ratsikas, Alexandros Hollender, and Alexandros A. Voudouris. 2021. Maximum Nash welfare and other stories about EFX. Theor. Comput. Sci. 863 (2021), 69–85.https: //doi.org/10.1016/j.tcs.2021.02.020 [6]Georgios Amanatidis, Aris Filos-Ratsikas, and Alkmini Sgouritsa. 2024. Pushing the Frontier on Approximate EFX Allocations. In Proceedings of the 25th ACM Conference on Economics and Computation, EC. [7]Haris Aziz and Simon Mackenzie. 2016. A discrete and bounded envy-free cake cutting protocol for four agents. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Daniel Wichs and Yishay Mansour (Eds.). ACM. https://doi.org/10.1145/2897518.2897522 [8] Moshe Babaioff, Tomer Ezra, and Uriel Feige. 2021. Fair and Truthful Mechanisms for Dichotomous Valuations. In Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2021, Thirty-Third Conference on Innovative Applications of Artificial Intelligence, IAAI 2021, The Eleventh Symposium on Educational Advances in Artificial Intelligence, EAAI 2021, Virtual Event, February 2-9, 2021. AAAI Press, 5119–5126. doi:10.1609/AAAI.V35I6. 16647 [9] Benjamin Aram Berendsohn, Simona Boyadzhiyska, and László Kozma. 2022. Fixed-Point Cycles and Approx- imate EFX Allocations. In 47th International Symposium on Mathematical Foundations of Computer Science, MFCS 2022, August 22-26, 2022, Vienna, Austria (LIPIcs, Vol. 241), Stefan Szeider, Robert Ganian, and Alexandra Silva (Eds.). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 17:1–17:13. doi:10.4230/LIPICS.MFCS.2022. 17 [10] Claude Berge. 1973. Graphs and Hypergraphs. North-Holland, Amsterdam. [11] Ben Berger, Avi Cohen, Michal Feldman, and Amos Fiat. 2022. Almost Full EFX Exists for Four Agents. In Thirty-Sixth AAAI Conference on Artificial Intelligence, AAAI 2022, Thirty-Fourth Conference on Innovative Applications of Artificial Intelligence, IAAI 2022, The Twelveth Symposium on Educational Advances in Artificial Intelligence, EAAI 2022 Virtual Event, February 22 - March 1, 2022. AAAI Press, 4826–4833. doi:10.1609/ AAAI.V36I5.20410 [12] Umang Bhaskar and Yeshwant Pandit. 2025. Extending EFX Allocations to Further Multi-Graph Classes. In 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025) (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 360), C. Aiswarya, Ruta Mehta, and Subhajit Roy (Eds.). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 15:1–15:18. doi:10.4230/LIPIcs.FSTTCS.2025.15 [13]Václav Blažej, Sushmita Gupta, M. S. Ramanujan, and Peter Strulo. 2025. Tractable Graph Structures in EFX Orientation. In Algorithmic Game Theory: 18th International Symposium, SAGT 2025, Bath, UK, September 2–5, 2025, Proceedings (Bath, United Kingdom). Springer-Verlag, Berlin, Heidelberg, 175–190. doi:10.1007/978-3-032-03639-1_10 [14]Eric Budish. 2010. The combinatorial assignment problem: approximate competitive equilibrium from equal incomes. In Proceedings of the Behavioral and Quantitative Game Theory - Conference on Future Directions, BQGT ’10, Newport Beach, California, USA, May 14-16, 2010, Moshe Dror and Greys Sosic (Eds.). ACM, 74:1. doi:10.1145/1807406.1807480 [15]Ioannis Caragiannis, Nick Gravin, and Xin Huang. 2019. Envy-Freeness Up to Any Item with High Nash Welfare: The Virtue of Donating Items. In Proceedings of the 2019 ACM Conference on Economics and Computation, EC 2019, Phoenix, AZ, USA, June 24-28, 2019, Anna R. Karlin, Nicole Immorlica, and Ramesh Johari (Eds.). ACM, 527–545. doi:10.1145/3328526.3329574 [16]Ioannis Caragiannis, David Kurokawa, Hervé Moulin, Ariel D. Procaccia, Nisarg Shah, and Junxing Wang. 2019. The Unreasonable Fairness of Maximum Nash Welfare. ACM Trans. Economics and Comput. 7, 3 (2019), 12:1–12:32. doi:10.1145/3355902 [17]Bhaskar Ray Chaudhury, Jugal Garg, and Kurt Mehlhorn. 2024. EFX Exists for Three Agents. J. ACM 71, 1 (2024), 4:1–4:27. doi:10.1145/3616009 13 [18]Bhaskar Ray Chaudhury, Jugal Garg, Kurt Mehlhorn, Ruta Mehta, and Pranabendu Misra. 2021. Improving EFX Guarantees through Rainbow Cycle Number. In EC ’21: The 22nd ACM Conference on Economics and Computation, Budapest, Hungary, July 18-23, 2021, Péter Biró, Shuchi Chawla, and Federico Echenique (Eds.). ACM, 310–311. doi:10.1145/3465456.3467605 [19]Bhaskar Ray Chaudhury, Telikepalli Kavitha, Kurt Mehlhorn, and Alkmini Sgouritsa. 2021. A Little Charity Guarantees Almost Envy-Freeness. SIAM J. Comput. 50, 4 (2021), 1336–1358. doi:10.1137/20M1359134 [20]George Christodoulou, Amos Fiat, Elias Koutsoupias, and Alkmini Sgouritsa. 2023. Fair allocation in graphs. In Proceedings of the 24th ACM Conference on Economics and Computation, EC 2023, London, United Kingdom, July 9-12, 2023, Kevin Leyton-Brown, Jason D. Hartline, and Larry Samuelson (Eds.). ACM, 473–488. doi:10. 1145/3580507.3597764 [21]George Christodoulou and Symeon Mastrakoulis. 2026. Exact and Approximate Maximin Share Allocations in Multi-Graphs. In Fortieth AAAI Conference on Artificial Intelligence, Thirty-Eighth Conference on Innovative Applications of Artificial Intelligence, Sixteenth Symposium on Educational Advances in Artificial Intelligence, AAAI 2026, Singapore, January 20-27, 2026, Sven Koenig, Chad Jenkins, and Matthew E. Taylor (Eds.). AAAI Press, 16761–16769. doi:10.1609/AAAI.V40I20.38719 [22] Giorgos Christodoulou, Symeon Mastrakoulis, Alkmini Sgouritsa, and Minas Marios Sotiriou. 2026. EFX allocations on multigraphs. In Proceedings of the 27th ACM Conference on Economics and Computation (Rome, Italy). [23]Argyrios Deligkas, Eduard Eiben, Tiger-Lily Goldsmith, and Viktoriia Korchemna. 2025. EF1 and EFX Orien- tations. In Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-25. International Joint Conferences on Artificial Intelligence Organization, 8. doi:10.24963/ijcai.2025/7Main Track. [24] Uriel Feige. 2025. From multi-allocations to allocations, with subadditive valuations. arXiv:2506.21493 [cs.GT] https://arxiv.org/abs/2506.21493 [25] Duncan Karl Foley. 1966. Resource allocation and the public sector. Yale University. [26]G. Gamow and M. Stern. 1958. Puzzle-math. Viking Press.https://books.google.gr/books?id= _vdytgAACAAJ [27]Laurent Gourvès, Jérôme Monnot, and Lydia Tlilane. 2014. Near Fairness in Matroids. In ECAI 2014 - 21st European Conference on Artificial Intelligence, 18-22 August 2014, Prague, Czech Republic - Includ- ing Prestigious Applications of Intelligent Systems (PAIS 2014) (Frontiers in Artificial Intelligence and Ap- plications, Vol. 263), Torsten Schaub, Gerhard Friedrich, and Barry O’Sullivan (Eds.). IOS Press, 393–398. doi:10.3233/978-1-61499-419-0-393 [28]Hadi Hosseini, Sujoy Sikdar, Rohit Vaish, and Lirong Xia. 2021. Fair and Efficient Allocations under Lex- icographic Preferences. In Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2021, Thirty-Third Conference on Innovative Applications of Artificial Intelligence, IAAI 2021, The Eleventh Symposium on Educa- tional Advances in Artificial Intelligence, EAAI 2021, Virtual Event, February 2-9, 2021. AAAI Press, 5472–5480. doi:10.1609/AAAI.V35I6.16689 [29]Kevin Hsu. 2024. EFX Orientations of Multigraphs. arXiv:2410.12039 [cs.GT]https://arxiv.org/abs/ 2410.12039 [30]Vishwa Prakash Hv, Pratik Ghosal, Prajakta Nimbhorkar, and Nithin Varma. 2025. EFX Exists for Three Types of Agents. In Proceedings of the 26th ACM Conference on Economics and Computation (Stanford University, Stanford, CA, USA) (EC ’25). Association for Computing Machinery, New York, NY, USA, 101–128. doi:10. 1145/3736252.3742509 [31]Shayan Chashm Jahan, Masoud Seddighin, Seyed Mohammad Seyed Javadi, and Mohammad Sharifi. 2023. Rainbow Cycle Number and EFX Allocations: (Almost) Closing the Gap. In Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, IJCAI 2023, 19th-25th August 2023, Macao, SAR, China. ijcai.org, 2572–2580. doi:10.24963/IJCAI.2023/286 [32] Sotiris Kanellopoulos, Edouard Nemery, Christos Pergaminelis, Minas Marios Sotiriou, and Manolis Vasilakis. 2025. EF(X) Orientations: A Parameterized Complexity Perspective. arXiv:2512.25033 [cs.DS]https: //arxiv.org/abs/2512.25033 [33]Alireza Kaviani, Alireza Keshavarz, Masoud Seddighin, and AmirMohammad Shahrezaei. 2025. Improved Approximate EFX Guarantees for Multigraphs. arXiv:2506.09288 [cs.GT]https://arxiv.org/abs/2506. 09288 14 [34]Alireza Kaviani, Masoud Seddighin, and AmirMohammad Shahrezaei. 2024. Almost Envy-Free Allocation of Indivisible Goods: A Tale of Two Valuations. In WINE (Lecture Notes in Computer Science, Vol. 15534). Springer, 261–276. [35]Richard J. Lipton, Evangelos Markakis, Elchanan Mossel, and Amin Saberi. 2004. On approximately fair allocations of indivisible goods. In EC. ACM, 125–131. [36]Benjamin Plaut and Tim Roughgarden. 2020. Almost Envy-Freeness with General Valuations. SIAM J. Discret. Math. 34, 2 (2020), 1039–1068. doi:10.1137/19M124397X [37]Ariel D. Procaccia. 2020. An answer to fair division’s most enigmatic question: technical perspective. Commun. ACM 63, 4 (2020), 118. doi:10.1145/3382131 [38]Alkmini Sgouritsa and Minas Marios Sotiriou. 2025. On the Existence of EFX Allocations in Multigraphs. In Proceedings of the 24th International Conference on Autonomous Agents and Multiagent Systems (Detroit, MI, USA) (AAMAS ’25). International Foundation for Autonomous Agents and Multiagent Systems, 2735–2737. [39] Hugo Steinhaus. 1948. The problem of fair division. Econometrica 16 (1948), 101–104. [40]Walter R. Stromquist. 1980. How to Cut a Cake Fairly. Amer. Math. Monthly 87 (1980), 640–644.https: //doi.org/10.1080/00029890.1980.11995109 [41]Hal R Varian. 1974. Equity, envy, and efficiency. Journal of Economic Theory 9, 1 (1974), 63–91. doi:10.1016/ 0022-0531(74)90075-1 [42]D.R Woodall. 1980. Dividing a cake fairly. J. Math. Anal. Appl. 78, 1 (1980), 233–247. doi:10.1016/ 0022-247X(80)90225-5 [43]Jinghan A. Zeng and Ruta Mehta. 2025. On the Structure of EFX Orientations on Graphs. In AAMAS. International Foundation for Autonomous Agents and Multiagent Systems / ACM, 2309–2316. [44]Yu Zhou, Tianze Wei, Minming Li, and Bo Li. 2024. A Complete Landscape of EFX Allocations on Graphs: Goods, Chores and Mixed Manna. In IJCAI. 3049–3056. A Subroutine 7 (Algorithm 3 of [19]) Subroutine 7 Finding an inclusion-wise minimal envied subset from a patch (Algorithm 3 [19]) Input: A set of agents L, and a set of goods S Output: A set that none envies a proper subset of it. 1: Z = S 2: for every agent i∈ L do 3:for every good g ∈ Z do 4:if v i (X i ) < v i (Z\g) then 5:Z ← Z\g 6:end if 7:end for 8: end for 9: return Z 15