On the Number of Almost Envy-Free Allocations

Abstract

Envy-freeness is a standard benchmark of fairness in resource allocation. Since it cannot always be satisfied when the resource consists of indivisible items even when there are two agents, the relaxations envy-freeness up to one item (EF1) and envy-freeness up to any item (EFX) are often considered. We establish tight lower bounds on the number of allocations satisfying each of these benchmarks in the case of two agents. In particular, while there can be as few as two EFX allocations for any number of items, the number of EF1 allocations is always exponential in the number of items. Our results apply a version of the vertex isoperimetric inequality on the hypercube and help explain the large gap in terms of robustness between the two notions.

References in corpus (8)

• Multiple Birds with One Stone: Beating $1/2$ for EFX and GMMS via Envy Cycle Elimination
• Maximum Nash Welfare and Other Stories About EFX
• Fairly Allocating Contiguous Blocks of Indivisible Items
• The Price of Fairness for Indivisible Goods
• Democratic Fair Allocation of Indivisible Goods
• Fair Division Under Cardinality Constraints
• The Price of Connectivity in Fair Division
• EFX Exists for Three Agents

Cited by in corpus (6)

• Maximum Nash Welfare and Other Stories About EFX
• Almost Envy-Freeness in Group Resource Allocation
• The Price of Fairness for Indivisible Goods
• Closing Gaps in Asymptotic Fair Division
• Fair allocation of a multiset of indivisible items
• Fairly Allocating Many Goods with Few Queries