Fair division of indivisible goods: recent progress and open questions
From MaRDI portal
Publication:6136107
Abstract: Allocating resources to individuals in a fair manner has been a topic of interest since ancient times, with most of the early mathematical work on the problem focusing on resources that are infinitely divisible. Over the last decade, there has been a surge of papers studying computational questions regarding the indivisible case, for which exact fairness notions such as envy-freeness and proportionality are hard to satisfy. One main theme in the recent research agenda is to investigate the extent to which their relaxations, like maximin share fairness (MMS) and envy-freeness up to any good (EFX), can be achieved. In this survey, we present a comprehensive review of the recent progress made in the related literature by highlighting different ways to relax fairness notions, common algorithm design techniques, and the most interesting questions for future research.
Cites work
- A discrete and bounded envy-free cake cutting protocol for four agents
- A Few Queries Go a Long Way: Information-Distortion Tradeoffs in Matching
- A Little Charity Guarantees Almost Envy-Freeness
- A new solution to the random assignment problem.
- A polynomial-time algorithm for computing a Pareto optimal and almost proportional allocation
- A polynomial-time approximation scheme for maximizing the minimum machine completion time
- A tight negative example for MMS fair allocations
- Allocating indivisible goods to strategic agents: pure Nash equilibria and fairness
- Almost envy-freeness for groups: improved bounds via discrepancy theory
- Almost envy-freeness in group resource allocation
- Almost envy-freeness with general valuations
- An improved approximation algorithm for maximin shares
- Approximate maximin shares for groups of agents
- Approximating Nash Social Welfare under Submodular Valuations through (Un)Matchings
- Approximating the Nash Social Welfare with Indivisible Items
- Approximation Algorithms for Computing Maximin Share Allocations
- Approximation algorithms for scheduling unrelated parallel machines
- Cake cutting algorithms
- Closing gaps in asymptotic fair division
- Competitive division of a mixed manna
- Competitive equilibrium with indivisible goods and generic budgets
- Computing envy-freeable allocations with limited subsidies
- Computing fair and efficient allocations with few utility values
- Coverage, matching, and beyond: new results on budgeted mechanism design
- Democratic fair allocation of indivisible goods
- Dividing bads under additive utilities
- Earning limits in Fisher markets with spending-constraint utilities
- Efficiency and envy-freeness in fair division of indivisible goods: logical representation and complexity
- Extending the characterization of maximum Nash welfare
- Fair Allocation of Indivisible Goods
- Fair Allocation of Indivisible Goods to Asymmetric Agents
- Fair allocation of indivisible goods: beyond additive valuations
- Fair allocation of indivisible goods: improvement
- Fair division of mixed divisible and indivisible goods
- Fair division with binary valuations: one rule to rule them all
- Fair division with subsidy
- Fair enough: guaranteeing approximate maximin shares
- Fairly allocating many goods with few queries
- How to Cut A Cake Fairly
- scientific article; zbMATH DE number 3136641 (Why is no real title available?)
- scientific article; zbMATH DE number 5764883 (Why is no real title available?)
- scientific article; zbMATH DE number 1015852 (Why is no real title available?)
- scientific article; zbMATH DE number 6850473 (Why is no real title available?)
- scientific article; zbMATH DE number 7651150 (Why is no real title available?)
- Manipulating picking sequences
- Maximin share guarantee for goods with positive externalities
- Maximum Nash welfare and other stories about EFX
- Multiple birds with one stone: beating 1/2 for EFX and GMMS via envy cycle elimination
- Near fairness in matroids
- No Agent Left Behind: Dynamic Fair Division of Multiple Resources
- On Approximate Envy-Freeness for Indivisible Chores and Mixed Resources
- On Low-Envy Truthful Allocations
- On maximin share allocations in matroids
- On the fair division of a heterogeneous commodity
- On-line machine covering
- Optimal bounds on the price of fairness for indivisible goods
- Optimal semi-online algorithms for machine covering
- Random Matching Under Dichotomous Preferences
- Simultaneously achieving ex-ante and ex-post fairness
- Sur la division pragmatique
- The efficiency of fair division
- The Impossibility of Bayesian Group Decision Making with Separate Aggregation of Beliefs and Values
- The price of fairness
- The price of fairness for indivisible goods
- The Santa Claus problem
- The vigilant eating rule: a general approach for probabilistic economic design with constraints
- Welfare bounds in the fair division problem
- When do envy-free allocations exist?
Cited in
(16)- On the computability of equitable divisions
- Fair division in the presence of externalities
- Fair division of indivisible items between two players: design parameters for contested pile methods
- Fair division of goods in the shadow of market values
- Approximately EFX allocations for indivisible chores
- Improved maximin guarantees for subadditive and fractionally subadditive fair allocation problem
- EFX allocations for indivisible chores: matching-based approach
- The frontier of intractability for EFX with two agents
- Almost proportional allocations of indivisible chores: computation, approximation and efficiency
- Weighted fair division of indivisible items: a review
- Fair division with allocator's preference
- One quarter each (on average) ensures proportionality
- EFX allocations for indivisible chores: matching-based approach
- Ex ante and ex post envy-freeness on polytope resources
- Fair division under joint ownership: Recent results and open problems
- Brams-Taylor model of fair division for divisible and indivisible items
This page was built for publication: Fair division of indivisible goods: recent progress and open questions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6136107)
