A Little Charity Guarantees Almost Envy-Freeness

DOI10.1137/20M1359134MaRDI QIDQ4957912zbMATH OpenFDO

Authors Bhaskar Chaudhury, Telikepalli Kavitha, K. Mehlhorn, Alkmini Sgouritsa

Publication date 10 September 2021

Published in SIAM Journal on Computing (Search for Journal in Brave)

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

zbMATH Keywords

EFX allocationsfair divisionMMS allocations

Mathematics Subject Classification ID

Algorithms in computer science (68W99) Resource and cost allocation (including fair division, apportionment, etc.) (91B32)

Recommendations

• A Little Charity Guarantees Almost Envy-Freeness
• Multiple birds with one stone: beating 1/2 for EFX and GMMS via envy cycle elimination
• Almost envy-freeness with general valuations
• Almost envy-freeness with general valuations
• Fair enough: guaranteeing approximate maximin shares

Cites work

• A Little Charity Guarantees Almost Envy-Freeness
• Almost envy-freeness with general valuations
• Approximating the Nash social welfare with budget-additive valuations
• Approximating the Nash Social Welfare with Indivisible Items
• Approximation Algorithms for Computing Maximin Share Allocations
• Fair Allocation of Indivisible Goods to Asymmetric Agents
• Fair enough: guaranteeing approximate maximin shares
• scientific article; zbMATH DE number 7651150 (Why is no real title available?)
• Multiple birds with one stone: beating 1/2 for EFX and GMMS via envy cycle elimination
• Nash social welfare for indivisible items under separable, piecewise-linear concave utilities
• Nash social welfare, matrix permanent, and stable polynomials
• On fair division for indivisible items

Cited in

(28)

• Computing envy-freeable allocations with limited subsidies
• On the existence of EFX allocations
• A Little Charity Guarantees Almost Envy-Freeness
• EFX under budget constraint
• Fair division of indivisible goods: recent progress and open questions
• Approximating Nash social welfare by matching and local search
• EFX allocations exist for binary valuations
• The frontier of intractability for EFX with two agents
• One quarter each (on average) ensures proportionality
• Fair division with prioritized agents
• The price of fairness for budget-feasible EF1 allocations
• The frontier of intractability for EFX with two agents
• Parameterized complexity of incomplete connected fair division
• Restricted existence and approximation algorithms for PMMS
• Algorithms for 2-balanced connected k-partition problem in graphs
• Algorithms for 2-balanced connected \(k\)-partition problem in graphs
• On the existence of EFX (and Pareto-optimal) allocations for binary chores
• Finding fair and efficient allocations under budget constraints
• On the existence of EFX (and Pareto-optimal) allocations for binary chores
• Guaranteeing fairness and efficiency under budget constraints
• Fair division with subjective divisibility
• Proportional allocation of indivisible goods up to the least valued good on average
• Fair division of chores with budget constraints
• Nearly tight bounds on the price of fairness for indivisible items under budget constraints
• Almost envy-free allocation of indivisible goods: a tale of two valuations
• Best-of-both-worlds fair allocation of indivisible and mixed goods
• Approximating EFX through a new notion of fairness
• Approximating Nash social welfare by matching and local search

This page was built for publication: A Little Charity Guarantees Almost Envy-Freeness

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