Almost EFX in Hypergraphs DOI: XXXXXXX.XXXXXXX Conference: Make sure to enter the correct conference title from your rights confirmation email; June 03–05, 2018; Woodstock, NY ISBN: 978-1-4503-XXXX-X/2018/06 CCS: Theory of computation Algorithmic game theory

Ioannis Kakatelis, Thanasis Lianeas, Alkmini Sgouritsa, Minas Marios Sotiriou · 2026

Read Almost EFX in Hypergraphs DOI: XXXXXXX.XXXXXXX Conference: Make sure to enter the correct conference title from your rights confirmation email; June 03–05, 2018; Woodstock, NY ISBN: 978-1-4503-XXXX-X/2018/06 CCS: Theory of computation Algorithmic game theory by Ioannis Kakatelis, Thanasis Lianeas, Alkmini Sgouritsa, Minas Marios Sotiriou (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-26948.txt.

Introduction

Ioannis Kakatelis, Thanasis Lianeas, Alkmini Sgouritsa, and Minas Marios Sotiriou study fair division of indivisible goods arranged on a hypergraph. Agents value bundles of goods; an allocation is EFX if no agent envies another after removing any single good from the other's bundle. In the hypergraph setting, goods are edges and only their endpoints can value them. Full EFX allocations may not exist, so approximations matter.

The authors simplify and extend earlier constructions. For graphs without short cycles, a construction guarantees each agent at least a fixed strong fraction of the EFX standard under additive valuations. Weaker envy guarantees with more slack goods removed are proven to exist always in special cases. All constructions run in polynomial time. The results push the frontier of provably fair sharing in network-structured settings.

Catalog record

CREATORIoannis Kakatelis, Thanasis Lianeas, Alkmini Sgouritsa, Minas Marios Sotiriou
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE113 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2606.26948

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Almost EFX in Hypergraphs DOI: XXXXXXX.XXXXXXX Conference: Make sure to enter the correct conference title from your rights confirmation email; June 03–05, 2018; Woodstock, NY ISBN: 978-1-4503-XXXX-X/2018/06 CCS: Theory of computation Algorithmic game theory Ioannis Kakatelis, Thanasis Lianeas, Alkmini Sgouritsa, Minas Marios Sotiriou Abstract . We study the existence of envy-free-up-to-any-good (EFX) allocations of indivisible goods among agents with heterogeneous monotone valuations. 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. Our work simplifies and extends previous results of ( 42 ) in this domain. First, we provide a simpler construction of EF2X allocation for general monotone valuations in hypergraphs with girth at least 3. We extend our ideas when the multiplicity of each edge is 2 and show that an EF3X allocation always exists for additive valuations. Both results can be constructed in polynomial time. Regarding EFX approximations, we provide a simpler construction for 2 2 \frac{\sqrt{2}}{2} -EFX allocations in hypergraphs of girth at least 3 under subadditive valuations. We push the state-of-the-art by establishing the existence of 2 3 \frac{2}{3} -EFX allocations for additive valuations when the edge multiplicity is 2. Both of the latter results can be constructed in pseudo-polynomial time. By addressing these multi-hypergraph settings, our work contributes to the ongoing effort to resolve the existence of EFX in increasingly general and applicable domains. \declaretheorem [name= Theorem ]thm 1. Introduction The problem of fair division involves allocating a set of indivisible goods among multiple agents in a manner that ensures fairness. While the roots of fair resource allocation trace back to antiquity, the field formally emerged in the late 1940s with the work of 52 and later the works of ( 35 ; 34 ; 53 ) . Today, fair division represents a rich interdisciplinary field intersecting economics, social choice theory, mathematics, and computer science ( 6 ; 17 ; 18 ; 50 ) . In the last decade, research has focused on minimizing envy among agents in diverse applications such as auctions, business partnerships, and course scheduling ( 19 ) . However, eliminating envy is often impossible with indivisible items; for instance, if two agents both desire a single indivisible good, any allocation necessarily creates envy. This reality has necessitated the study of envy-freeness relaxations. The first major relaxation is Envy-freeness up to one good (EF1) introduced by 20 , which requires that envy can be eliminated by removing a prespecified single good from the envied agent’s bundle. 44 proved that EF1 allocations are guaranteed to exist even for general monotone valuations and can be computed efficiently. A more rigorous and “enigmatic” relaxation is Envy-freeness up to any good (EFX) as mentioned in ( 49 ) and was introduced by 23 and 36 . In an EFX allocation an agent should not envy another agent after the hypothetical removal of any single good from the envied agent’s bundle. Whether EFX allocations always exist remained one of the most significant open problems in fair division for several years. Very recently, 4 answered negatively the question of EFX existence by giving a counterexample in the case of n\geq 3 agents and m\geq n+5 goods. In the case of n=3 and m=8 , where agents have general monotone valuations, this result was extended to show non-existence even for submodular valuations ( 45 ) . The question still remains open for more specialized valuation functions, such as additive, and more restrictive but realistic settings. Known existence results are limited to specific cases: when there are two agents with general monotone valuations and for any number of agents, provided that all agents have identical valuations ( 48 ) and also for three agents with additive valuations ( 27 ) . The case of three agents was extended to nice-cancelable valuations by 14 and generalized further by 3 to the case where two agents have arbitrary monotone valuations and at least one agent has MMS-feasible valuation. For n agents, known results involve cases where agents have additive bi-valued valuations ( 7 ; 21 ) , all agents have one of two general valuations or when the number of items is at most n+3 ( 46 ) , when the valuations are submodular with binary marginals ( 11 ) , and when there are at most three distinct additive valuations ( 38 ) . The attention of the research community has also turned into graphical valuations, where the relationship between agents and goods is captured by a graph G=(V,E) . In this setting, agents are represented by vertices and goods by edges; an edge/good may have positive value only for its endpoints ( 29 ) . 29 proved that EFX allocations always exist on simple graphs and they noted that EFX orientations, i.e., allocations where each edge is given to one of its endpoints may not always exist and are NP-complete to decide their existence. Our work focuses on multigraph and hypergraph settings, where a single good may be relevant to more than two agents and multiple goods may connect the same set of agents. These structures are more complex but offer deeper insights into real-world applications like territorial borders or shared research workspace. 1.1. Our Contribution We focus on hypergraphs of girth at least 3 (meaning that any two agents share at most one good/edge) and relax the EFX requirement in two directions, searching for EF2X allocations, i.e., allocations under which removing any two goods from any envied agent’s bundle eliminates the envy towards the agent, and approximate EFX allocations. In both directions we recover best-known results via simpler constructions. We further extend these findings to multi-hypergraph instances of girth at least 3 and multiplicity 2, i.e., instances where any subset of agents may share more than one but up to two common goods. Notably the only prior work that considers multiplicity greater than 1 is by 43 , who showed EFX existence for girth at least 4. In contrast, our focus on girth at least 3 introduces significantly more complex agent connectivity, resulting in a more challenging setting. In Section 3 we aim for EF2X allocations and provide a simple polynomial time algorithm that returns an EF2X allocation for hypergraphs of girth at least 3 and general monotone valuations (Theorem 3.1 ), thus reproving a result of 42 with a much simpler and polynomial time construction. The algorithm, in a first step, by employing ideas of 43 and prioritizing the agents, creates first a partial EFX allocation with specific properties, and in a second step it assigns, in one pass, the unallocated goods to reach a complete EF2X allocation. Next, moving one step forward, we focus on multi-hypergraphs of girth at least 3 and multiplicity 2. For such instances, we provide a polynomial time algorithm that returns an EF3X allocation for additive valuations (Theorem 3.1 ), i.e., any agent does not envy any other bundle after removing 3 goods from it. In Section 4 we turn into finding approximate EFX allocations. For simple hypergraphs of girth at least 3 we extend ideas used by Amanatidis et al. ( 8 ) and show that

Read the complete text