On the number of almost envy-free allocations

DOI10.1016/J.DAM.2020.03.039zbMATH Open1444.91109arXiv2006.00178OpenAlexW3015881104MaRDI QIDQ777445FDOQ777445

Authors: Warut Suksompong 

Publication date: 7 July 2020

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/2006.00178

Recommendations

• Almost envy-freeness with general valuations
• Almost envy-freeness with general valuations
• Almost envy-freeness in group resource allocation
• On the existence of EFX allocations
• When do envy-free allocations exist?

zbMATH Keywords

resource allocationenvy-freeness

Mathematics Subject Classification ID

Resource and cost allocation (including fair division, apportionment, etc.) (91B32)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Almost envy-freeness with general valuations
• Envy-freeness in house allocation problems
• Almost envy-free allocations with connected bundles

Cited In (16)

• The price of fairness for indivisible goods
• Envy-freeness and relaxed stability for lower-quotas: a parameterized perspective
• Fair in the Eyes of Others
• An algorithm for identifying least manipulable envy‐free and budget‐balanced allocations in economies with indivisibilities
• Diverse fair allocations: complexity and algorithms
• Diverse fair allocations: complexity and algorithms
• Almost envy-freeness with general valuations
• Almost envy-freeness with general valuations
• Closing gaps in asymptotic fair division
• On the existence of EFX allocations
• Almost envy-freeness in group resource allocation
• Fair in the eyes of others
• Fairly allocating many goods with few queries
• Maximum Nash welfare and other stories about EFX
• Almost envy-free allocations with connected bundles
• Title not available (Why is that?)

This page was built for publication: On the number of almost envy-free allocations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q777445)