Almost Envy-Freeness with General Valuations

DOI10.1137/19M124397XzbMath1437.91237arXiv1707.04769OpenAlexW3015797191MaRDI QIDQ5107066

Benjamin Plaut, Tim Roughgarden

Publication date: 22 April 2020

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

fair divisionenvy-freenessindivisible goods

Mathematics Subject Classification ID

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

Related Items (22)

Two-person fair division of indivisible items when envy-freeness is impossible ⋮ Allocating indivisible goods to strategic agents: pure Nash equilibria and fairness ⋮ Computing envy-freeable allocations with limited subsidies ⋮ On the existence of EFX allocations ⋮ Fair and efficient allocation with few agent types, few item types, or small value levels ⋮ Existence of EFX for two additive valuations ⋮ Exact and approximation algorithms for PMMS under identical constraints ⋮ Repeatedly matching items to agents fairly and efficiently ⋮ Fair division of indivisible goods: recent progress and open questions ⋮ Fairly taking turns ⋮ Approximately EFX allocations for indivisible chores ⋮ Improved maximin guarantees for subadditive and fractionally subadditive fair allocation problem ⋮ The existence and efficiency of PMMS allocations ⋮ Contiguous Cake Cutting: Hardness Results and Approximation Algorithms ⋮ The price of fairness for indivisible goods ⋮ Fair division of mixed divisible and indivisible goods ⋮ Computing fair and efficient allocations with few utility values ⋮ A Little Charity Guarantees Almost Envy-Freeness ⋮ Closing Gaps in Asymptotic Fair Division ⋮ Fairly Allocating Many Goods with Few Queries ⋮ The Price of Connectivity in Fair Division ⋮ Consensus Halving for Sets of Items

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The exact bound in the Erdős-Ko-Rado theorem for cross-intersecting families
• Fair assignment of indivisible objects under ordinal preferences
• Local optimization on graphs
• Welfare inequalities and Rawlsian axiomatics
• Impartial division of a dollar
• Combinatorial auctions with decreasing marginal utilities
• On the diameter of Kneser graphs
• The Bargaining Problem
• The Nash Social Welfare Function
• Social Choice Theory: A Re-Examination
• Which Is the Fairest (Rent Division) of Them All?
• Fairly Allocating Many Goods with Few Queries
• A Little Charity Guarantees Almost Envy-Freeness
• Handbook of Computational Social Choice
• Communication Complexity of Discrete Fair Division
• Course Match: A Large-Scale Implementation of Approximate Competitive Equilibrium from Equal Incomes for Combinatorial Allocation
• On the Complexity of Computing an Equilibrium in Combinatorial Auctions
• Random Matching Under Dichotomous Preferences
• Communication Complexity of Combinatorial Auctions with Submodular Valuations

This page was built for publication: Almost Envy-Freeness with General Valuations