On the number of almost envy-free allocations

DOI10.1016/J.DAM.2020.03.039MaRDI QIDQ777445zbMATH OpenOpenAlexFDO

Authors Warut Suksompong

Publication date 7 July 2020

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

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

zbMATH Keywords

resource allocationenvy-freeness

Mathematics Subject Classification ID

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

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.

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?

Cites work

• scientific article; zbMATH DE number 3957109 (Why is no real title available?)
• scientific article; zbMATH DE number 4100062 (Why is no real title available?)
• Almost envy-free allocations with connected bundles
• Almost envy-freeness with general valuations
• Envy-freeness in house allocation problems

Cited in

(17)

• 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
• Almost envy-freeness for groups: improved bounds via discrepancy theory
• 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
• scientific article; zbMATH DE number 6850473 (Why is no real title available?)

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)