Approximate Envy-Free Allocations up to any k k Goods

Aris Filos-Ratsikas, Georgios Kalantzis, Fangxiao Wang · 2026

Read Approximate Envy-Free Allocations up to any k k Goods by Aris Filos-Ratsikas, Georgios Kalantzis, Fangxiao Wang (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-2605-10371.txt.

Introduction

Aris Filos-Ratsikas, Georgios Kalantzis, and Fangxiao Wang study fair division of indivisible goods. Envy-freeness up to one good, or EFX, remains famously open. EFX demands that any agent's envy of another's bundle vanish after removing the least valuable good, from the envious agent's view. Their 2026 paper advances approximate and relaxed versions of that ideal.

For any k greater than 2, the authors show that (k+1)/(k+2)-approximate envy-free-up-to-any-k-goods allocations exist for any number of agents. They can be computed in polynomial time, via a generalization of the 3PA algorithm. A corollary gives 3/4-approximate EFX-up-to-2-goods allocations for any number of agents, while exact 2/3-approximate EFX was previously known only up to 7 agents. The authors extend that result to 8 agents. They also prove EFkX graph orientations need not exist, and that deciding existence is NP-complete.

Catalog record

CREATORAris Filos-Ratsikas, Georgios Kalantzis, Fangxiao Wang
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE119 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

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

Browse the full library · About the Tower of Babel

Full text

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

Approximate Envy-Free Allocations up to any k k Goods Aris Filos-Ratsikas, Georgios Kalantzis, Fangxiao Wang Abstract We study the problem of finding approximate envy-free allocations up to any k k goods ( α \alpha -EFkX), when agents have additive values over goods in a bundle. As our main result, we show that for any k > 2 k>2 , k + 1 k + 2 \frac{k+1}{k+2} -EFkX allocations exist for any number of agents, and can be computed in polynomial time, via an appropriate generalization of the 3PA algorithm of [ 6 ] . An immediate corollary of this result is that 3 / 4 3/4 -EF2X allocations exist for any number of agents; in contrast, 2 / 3 2/3 -EFX allocations are only known to exist for up to 7 agents. We improve this latter result by devising an algorithm that achieves 2 / 3 2/3 -EFX for 8 agents. We also consider EFkX graph orientations; we prove that such orientations do not always exist, and that deciding their existence is NP-complete, thereby generalizing the corresponding result of [ 15 ] for k = 1 k=1 . 1 Introduction The area of computational fair division studies the problem of allocating resources to agents in a fair manner, based on those agents’ heterogeneous and often contrasting preferences over how the resources should be allocated. Amongst its many variants, the one that is currently on the forefront of the associated literature is the existence of fair allocations of indivisible goods , also known as discrete fair division [ 4 ] . This literature has studied multiple notions of fairness for this setting, but arguably the most intriguing out of all those is that of envy-freeness up to one good (EFX) [ 13 ] ; this notion stipulates that the envy of one agent for another agent’s allocated bundle is eliminated, once we remove the least valuable good, from the envious agent’s perspective, from the bundle of the envied agent. The question of whether EFX allocations always exist, and, if they do, whether they can be computed in polynomial time, is still open. In fact, it would be fair to say that this is the most important question, or the “holy grail”, of this very active research area. In the absence of a definitive answer, the literature has produced a plethora of results on meaningful special cases, which can be seen as important building blocks towards tackling the main question. For example, in a breakthrough result, 14 showed the EFX allocations exist for three agents (strengthening a previous existence result for two agents due to 22 , see also [ 2 ] ). 5 showed the EFX allocations exist and can be computed in polynomial time on instances where agents can have one of two possible values for the goods, and 15 showed a corresponding result when the values can be represented by a graph. 22 showed an EFX existence result when the agents’ values induce the same ordering over goods. Achieving exact EFX allocations has proven to be quite challenging for settings that go beyond the aforementioned special cases. For this reason, the literature has applied further relaxations to the EFX notion, two of the most prominent of which are the following: - approximate-EFX or \alpha -EFX , i.e., a notion that stipulates that after the removal of any good from the envied agent’s bundle, the remaining envy is bounded multiplicatively by a factor \alpha . - EFkX , i.e., a notion that stipulates that the envy is eliminated after the removal of any k goods from the envied agent’s bundle. Obviously, when \alpha=1 and k=1 , we recover the definition of EFX allocations. The notion of \alpha -EFX was notably studied by 7 , who proved the (currently best known) approximation of \alpha=0.618 ; this bound was established also by 17 with a different algorithm. 21 improved the factor to \alpha=2/3 when all of the n agents agree on the n most valuable goods. In a work that is most relevant to us, 6 obtained 2/3 -EFX allocations for three important cases, namely when (i) there are at most 7 agents, or (ii) when the values can be represented by a multigraph, or (iii) when the agents have one of three possible values. The notion of EFkX allocations was defined by 3 , who, among other results, proved the existence of EF2X allocations for a rather restricted class of values (namely when each agent has a value in \{0,v_{g}\} for some good g ). Recently, 8 showed the EF2X allocations exist for up to 4 agents. To the best of our knowledge, prior to our work, results for k>2 were not known in the literature. 1.1 Our Contribution In this work, for the first time we combine the two aforementioned lines of investigation, and consider approximate-EFkX allocations . This combination allows us to achieve significant improvements to the approximation factor \alpha compared to the state-of-the-art results for EFX, without any restrictions on the number of agents or their values. Our main result is given by the following theorem, informally stated below. Informal Theorem 1 . For any k\geq 2 , and any number of agents with additive values, a \frac{k+1}{k+2} -EFkX allocation exists and can be computed in polynomial time. To put 1 in context, we compare its instantiation for k=2 with the aforementioned results of 3 and 8 , which establish the existence of EF2X allocations for rather restricted valuation classes, and only for 4 agents, respectively. By allowing an approximation of \alpha=3/4 , we are able to achieve (3/4) -EF2X allocations for any number of agents and any additive valuation functions. We state the corresponding corollary below. Informal Corollary 1 . For any number of agents with additive values, a (3/4) -EF2X allocation exists and can be computed in polynomial time. 1 does not apply when k=1 . For this case, we manage to improve on the result of [ 6 ] by showing the existence of 2/3 -EFX allocations for 8 agents. Although the improvement from 7 to 8 agents may not seem that significant at first glance, the extension reveals some of the inherent difficulties of moving beyond the case of 7 agents, and introduces new techniques to achieve that. We state the corresponding theorem informally below. Informal Theorem 2 . A 2/3 -EFX allocation exists and can be computed in polynomial time for instances with up to 8 agents. We also consider EFkX allocations on graphs, extending the setting introduced by 15 in the context of EFX allocations. In this setting, every good (corresponding to an edge of the graph) is positively valued by only two agents (the endpoints of the edge in the graph). We are particularly interested in orientations of the edges, i.e., allocations such that each good is assigned to one of the two agents that values it positively. 15 showed the EFX orientations may not exist, and deciding their existence is an NP-complete problem. We strengthen their results to EFkX orientations, for any meaningful value of k . Informal Theorem 3 . EFkX orientations on graphs do not always exist. Furthermore, given an instance of the problem, deciding whether it admits

Read the complete text