On the Complexity of Efficiency and Envy-Freeness in Fair Division of Indivisible Goods with Additive Preferences

DOI10.1007/978-3-642-04428-1_9zbMath1260.91132OpenAlexW1573064394MaRDI QIDQ3645308

Sylvain Bouveret, Tomas B. Klos, Ying-Qian Zhang, Bart de Keijzer

Publication date: 17 November 2009

Published in: Algorithmic Decision Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-04428-1_9

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Resource and cost allocation (including fair division, apportionment, etc.) (91B32)

Related Items (15)

Envy-free allocations respecting social networks ⋮ Distributed fair allocation of indivisible goods ⋮ A polynomial-time algorithm for computing a Pareto optimal and almost proportional allocation ⋮ Computing fair and efficient allocations with few utility values ⋮ Efficient Fair Division with Minimal Sharing ⋮ Fair and efficient allocation with few agent types, few item types, or small value levels ⋮ Generalized binary utility functions and fair allocations ⋮ Computing welfare-maximizing fair allocations of indivisible goods ⋮ Fair assignment of indivisible objects under ordinal preferences ⋮ On best-of-both-worlds fair-share allocations ⋮ Minimizing envy and maximizing average Nash social welfare in the allocation of indivisible goods ⋮ Efficient reallocation under additive and responsive preferences ⋮ Computing fair and efficient allocations with few utility values ⋮ Competitive Equilibrium with Indivisible Goods and Generic Budgets ⋮ Fair in the Eyes of Others

This page was built for publication: On the Complexity of Efficiency and Envy-Freeness in Fair Division of Indivisible Goods with Additive Preferences