Understanding EFX Allocations: Counting and Variants
This work addresses fundamental fairness questions in resource allocation for multi-agent systems, offering incremental progress by solving specific open problems and introducing new variants.
The paper tackles the problem of counting EFX allocations in fair division of indivisible goods, focusing on instances where goods slightly outnumber agents, and extends analysis to weighted EFX and a new variant called EFX+. It resolves open problems by proving polynomial-time computability for weighted EFX under binary additive valuations and providing a constant-factor approximation for two agents.
Envy-freeness up to any good (EFX) is a popular and important fairness property in the fair allocation of indivisible goods, of which its existence in general is still an open question. In this work, we investigate the problem of determining the minimum number of EFX allocations for a given instance, arguing that this approach may yield valuable insights into the existence and computation of EFX allocations. We focus on restricted instances where the number of goods slightly exceeds the number of agents, and extend our analysis to weighted EFX (WEFX) and a novel variant of EFX for general monotone valuations, termed EFX+. In doing so, we identify the transition threshold for the existence of allocations satisfying these fairness notions. Notably, we resolve open problems regarding WEFX by proving polynomial-time computability under binary additive valuations, and establishing the first constant-factor approximation for two agents.