Source-linked AI summary
Fair Division of Indivisible Goods: Recent Progress and Open Questions
Georgios Amanatidis, Haris Aziz, Georgios Birmpas, Aris Filos-Ratsikas, Bo Li, Hervé Moulin, Alexandros A. Voudouris, Xiaowei Wu
TL;DR
Indivisible goods make exact envy-freeness and proportionality difficult or impossible, motivating computational study of fairness relaxations. This survey synthesizes recent algorithmic progress, fairness notions, and open questions, including results on structured valuations, efficiency, truthfulness, and limited information. It also identifies unresolved existence questions for EFX and related fairness concepts.
Problem
Indivisible goods can prevent exact envy-free or proportional allocations, motivating the study of achievable relaxations and computational methods.
Method
The paper surveys recent literature on relaxed fairness notions, algorithm-design techniques, efficiency, truthfulness, information limits, and valuation classes.
Results
The survey reports progress including EF1 and EFX algorithms, market-based fair and efficient allocations, strategic-agent impossibility results, limited-information guarantees, and approximation bounds for general valuations.
Takeaways & Limitations
Relaxing exact fairness enables meaningful algorithmic guarantees for indivisible goods, while computational and structural limits remain important research directions.
Takeaways & Limitations
EFX allocations are not known to exist for n ≥4 agents with unrestricted additive valuations.
Abstract
from arXiv · showhide
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.
1 Introduction
Fair division allocates resources among people with heterogeneous preferences. Recent research increasingly focuses on indivisible goods, where exact fairness is difficult and relaxations, algorithms, and open questions are central.
- Motivation: Fair division studies how to partition or allocate resources fairly among people with diverse preferences.Examples include course allocation, rent sharing, taxi-fare splitting, and other practical allocation problems.
- Fairness notions: Proportionality and envy-freeness are two predominant interpretations of fairness.For divisible resources, envy-free allocations can also be proportional under standard additive valuations.
- Indivisibility: Indivisible resources make exact fairness inherently challenging because some instances cannot provide every person a fair share.A single valuable item already prevents an exact fair allocation for everyone who values it.
- Relaxations: Randomization and relaxations such as MMS and EFX provide two fundamentally different responses to indivisibility.These approaches seek fairness in expectation or weaken exact envy-freeness and proportionality requirements.
- Survey scope: The survey emphasizes algorithmic developments from the past decade rather than an exhaustive review of the field’s long history.It organizes the literature around fairness notions, efficiency, truthfulness, limited information, general valuations, and randomness.
2 Te Setting
The survey models discrete fair division as allocating indivisible goods to agents with normalized, monotone valuations, usually additive. Because exact envy-freeness and proportionality may not exist, the setting uses relaxations including EF1, EFX, and MMS.
- The Setting: A discrete fair-division instance contains n agents, m indivisible goods, and valuation functions assigning non-negative values to every subset.Valuations are normalized and monotone; the survey mainly studies additive valuations.
- Solution Concepts: Exact envy-freeness and proportionality may fail even in the two-agent, single-good instance.The unassigned agent receives zero while envying the agent who receives the positively valued good.
- Important Relaxations: EF1 permits envy when removing one good from the other agent’s bundle would eliminate it.It is a weaker relaxation than EFX, which requires the condition after removing any good.
- Important Relaxations: The example allocation A is EF1 but not EFX because removing the least-valued relevant good does not eliminate one envy relation.A modified allocation B is EFX in the same example.
- Important Relaxations: MMS gives each agent the value she could guarantee by partitioning all goods into n bundles and keeping the least valuable bundle.MMS is therefore a relaxation of proportionality, but exact MMS allocations do not always exist for more than two agents.
- Computational Questions: Computing an agent’s maximin share is NP-hard, although a PTAS exists for that task.The survey also discusses further relaxations such as PMMS, GMMS, Prop1, PropX, and PropM.
3 Envy-Freeness up to One Good (EF1)
EF1 is a readily achievable relaxation of envy-freeness. Simple polynomial-time procedures allocate goods sequentially while ensuring that any envy can be removed by hypothetically deleting one good.
- Algorithms: Round-Robin allocates goods over multiple rounds, with each agent choosing her most valuable available good when her turn arrives.The presented algorithm takes a fair allocation instance as input and outputs an allocation.
11 end
EF1 algorithms can use either balanced sequential turns or dynamic envy-graph operations. Envy-Cycle Elimination repeatedly assigns goods to unenvied agents and resolves directed envy cycles by exchanging bundles.
- Round-Robin Variants: Sequential EF1 algorithms need not use the same agent order in every round, provided turn counts remain recursively balanced.The difference between any two agents’ numbers of turns is at most 1.
- Envy-Cycle Elimination: Envy-Cycle Elimination dynamically selects an agent with in-degree 0 in the envy graph and gives that agent her favorite available good.The envy graph has one node per agent and an edge from i to j when i envies j’s bundle.
- Envy-Cycle Elimination: When the envy graph contains a directed cycle, the algorithm resolves it by exchanging bundles along the cycle.Repeated cycle resolution eventually produces an agent who is not envied by anyone else.
- Algorithm Structure: The Envy-Cycle Elimination procedure outputs an allocation for the fair-division instance.Its pseudocode specifies the instance and allocation as input and output, respectively.
14 end
The survey connects EF1 with Pareto efficiency through maximum Nash welfare, while highlighting unresolved polynomial-time computation questions.
- EF1 allocations can be computed by polynomial-time procedures including Round-Robin and Envy-Cycle Elimination.Envy-Cycle Elimination assigns a good only when its recipient is not envied by others.
- Pareto optimality means that no alternative allocation weakly improves every agent while strictly improving at least one.
- Every maximum Nash welfare allocation is both EF1 and Pareto optimal.MNW first maximizes the number of agents with positive value, then maximizes the product of their values.
- Nash welfare maximization is the only welfarist maximization criterion identified as yielding both EF1 and Pareto optimality.
- Computing MNW allocations remains difficult, with polynomial-time computation still unknown despite pseudo-polynomial progress.MNW allocations are generally hard even to approximate in polynomial time.
- Whether an EF1 and Pareto optimal allocation can be computed in polynomial time remains open.
4 Envy-Freeness up to Any Good (EFX)
EFX remains unresolved for unrestricted instances, but exact allocations are known in several structured settings and approximate guarantees are available.
- EFX existence is a challenging open problem, unlike EF1, whose existence follows from simple polynomial-time algorithms.
- 4.1.1 Identical Valuations: Leximin++ allocations are EFX for identical valuations, including when the common valuation is non-additive.Leximin++ refines leximin by maximizing the size of the minimum-valued bundle before optimizing the next minimum value.
- 4.1.2 Ordered Valuations: For ordered instances, Envy-Cycle Elimination computes an EFX allocation even when agents have distinct cardinal valuations.Ordered instances share an identical ranking of goods across agents.
- 4.1.3 Few Agents: EFX allocations always exist for two agents, while three-agent allocations are computable in pseudo-polynomial time but not yet known to be computable in polynomial time.
- 4.1.4 Restricted Valuations: For bi-valued instances, EFX allocations exist and can be efficiently computed for any number of agents, with Pareto optimality also achievable.
- 4.1.5 Discussion: For n ≥4 agents with unrestricted additive valuations, the existence of exact EFX allocations remains an open problem.A positive answer would establish α = 1 for the corresponding approximation question.
- 4.2 Relaxations of EFX: A 1/2-EFX allocation always exists and can be computed using Envy-Cycle Elimination.The approximation notion requires each agent’s value to be at least half the value of every other bundle after removing any one good.
5 Maximin Share Fairness (MMS)
MMS allocations are not guaranteed to exist, so the literature develops approximation algorithms using monotonicity, large-good allocation, bag-filling, and Round-Robin techniques.
- MMS allocations need not exist when there are more than two agents, and computing them is NP-hard.Computing an individual agent’s maximin share admits a PTAS.
- An α-MMS allocation gives every agent at least an α fraction of her maximin share value.
- MMS monotonicity says removing one agent and one good does not decrease the remaining agents’ MMS values.This property supports approximation-algorithm design.
- A sufficiently valuable good can be assigned directly to an agent and removed from further consideration without hurting the remaining agents’ MMS guarantee.
- Round-Robin also returns a 1/2-MMS allocation.The guarantee follows from comparing each agent’s bundle with other bundles after removing their first-round selections.
- Envy-Cycle Elimination computes a 1/2-MMS allocation, in addition to providing EF1 and 1/2-EFX.
- The Bag-Filling Algorithm computes a 1/2-MMS allocation by accumulating goods until a remaining agent values the bag at least 1/2.The procedure repeats for the remaining agents and goods, assigning the final available goods to the last agent.
11 end
The supplied passage contains an implementation fragment without a supported substantive result.
- The passage records a loop condition that continues while more than one agent remains.
22 end
Recent MMS research improves polynomial-time guarantees beyond 2/3, using ordered instances and a reduction that transfers guarantees back to arbitrary instances. Exact existence and approximation limits remain open, with stronger results for restricted settings.
- Ordered instances: Ordered instances can be constructed so each good’s rank reflects agents’ descending values, and allocations for the ordered instance transfer without reducing any agent’s value.This ordering property supports both exact and approximate MMS guarantees.
- Approximation guarantees: 2/3-MMS allocations can be found in polynomial time for every instance by combining an ordered-instance algorithm with a guarantee-preserving reduction.The Envy-Cycle Elimination algorithm achieves 2/3-MMS on ordered instances, while the reduction transfers approximate MMS guarantees to arbitrary instances.
- Approximation guarantees: A simpler algorithm achieves a 3/4 + 1/(12n) approximation guarantee, improving on the earlier (3/4 −ǫ) result.The earlier algorithm is described as elaborate, whereas the later one is simpler and slightly stronger.
- Restricted settings: For two agents, cut-and-choose always produces an MMS allocation, although computing an agent’s exact maximin share is NP-hard.A polynomial-time (1−ǫ)-MMS allocation remains possible for the two-agent case.
- Restricted settings: MMS allocations always exist for identical or binary valuations, while whether they exist for other structured valuations remains open.The survey specifically asks about valuation classes with only a few, but more than two, possible values.
6 Further Notable Fairness Notions
The survey introduces fairness notions that refine or relax EF1, EFX, MMS, and proportionality, including epistemic, pairwise, groupwise, and equitability-based variants. Several notions have existence or approximation results, but PMMS, GMMS, EFR, and PropX leave important gaps.
- EFL, EFR, and Epistemic Notions: Epistemic fairness addresses agents’ incomplete knowledge of allocations, including epistemic EF and epistemic EFX under social-network information constraints.Epistemic EFX allocations exist for additive valuations when the social network contains only isolated nodes.
- PMMS and GMMS: PMMS evaluates each pair of agents, whereas GMMS requires the maximin-share guarantee simultaneously for every subset of agents.GMMS is stronger than both MMS and PMMS.
- PMMS and GMMS: 0.781 is the best known approximation for PMMS, while the best known approximation of GMMS is 4/7.Exact PMMS allocations are not known to always exist, and the optimal GMMS existence factor remains open.
- Prop1, PropX and PropM: Prop1 and PO allocations always exist and are computable in polynomial time, but PropX cannot always be guaranteed.A cited counterexample has an agent whose proportional share is 13/3 while adding an available good yields value only 4.
- Prop1, PropX and PropM: PropM lies between Prop1 and PropX, and a PropM allocation always exists and can be computed in polynomial time.PropM uses the value of a maximin good to reach the proportional share.
- Equitability: EQ allocations may fail to exist even with one good and two agents, whereas EQX allocations always exist and are polynomial-time computable.EQX implies EQ1, so the existence result also applies to EQ1 allocations.
7 Beyond Fairness: Efficiency and Incentives
The survey examines how fairness can be combined with efficiency and incentives in discrete fair division, emphasizing market-based algorithms, welfare trade-offs, and strategic-agent constraints.
- Fair and Pareto Optimal Allocations: Fisher-market techniques support algorithms for computing allocations that combine relaxed fairness guarantees with Pareto optimality.Perturbing budgets or values can produce integral equilibria, enabling EF1+PO, PROP1+PO, and EF1+fPO algorithms.
- Fair and Pareto Optimal Allocations: Integral market equilibria would be envy-free and fractionally Pareto optimal, but such equilibria rarely exist.Equal-budget market equilibria yield EF allocations, while market equilibrium allocations are fPO.
- Fair and Pareto Optimal Allocations: Fairness and efficiency can conflict: EFX and PO are compatible for bi-valued instances but incompatible with three distinct values.Other results include EQX+PO under strictly positive values and impossibility of EQ1+PO in instances allowing zero values.
- Fair and Pareto Optimal Allocations: Nash-welfare optimization is computationally difficult, with a 1.069 hardness threshold and a best additive-valuation approximation of about 1.45.The survey notes that approximate Nash-welfare allocations are not known to guarantee even approximate EF1.
- Price of Fairness: The price of EF1 is Θ(√n) for arbitrary numbers of agents, with matching Ω(√n) lower and O(√n) upper bounds.Tight bounds are also known for 1/2-MMS and Prop1, while fairness can have an unbounded price when no fair allocation has positive welfare.
- Fair Division with Strategic Agents: Strategic behavior adds difficulty because mechanisms must achieve fairness under true values despite potentially misleading declarations.Truthfulness and fairness are broadly incompatible, but restricted settings support EF1, PO, and NOM, while Round-Robin equilibria guarantee EF1.
8 Different Settings
The survey examines discrete fair division under limited information, general valuations, and asymmetric entitlements, covering fairness notions, algorithms, guarantees, and open problems.
- 8.1 Limited Information: With only ordinal information, EF1 is easy to obtain, but approximate MMS is limited to between 1/(2H_n) and 1/H_n.Round-Robin needs only rankings, whereas stronger MMS guarantees are information-theoretically constrained.
- 8.2 General Valuations: For general valuations, Envy-Cycle Elimination guarantees EF1, while no MMS approximation guarantee is possible without restrictions.The survey therefore emphasizes structured classes such as submodular, XOS, and subadditive valuations.
- 8.2 General Valuations: Structured valuations yield partial MMS guarantees: 1/3 for submodular, 1/8 algorithmically for XOS, and Ω(1/(log n log log n)) existentially for subadditive valuations.For XOS valuations, no algorithm can guarantee better than a 1/2-approximation for all instances.
- 8.3 Arbitrary Entitlements: Under arbitrary entitlements, Round-Robin guarantees a 1/n approximation to WMMS, while weighted EF1 always exists and is efficiently computable.Weighted fairness generalizes familiar notions to entitlement-adjusted comparisons.
- 8.3 Arbitrary Entitlements: AnyPrice share offers another weighted fairness benchmark, and an allocation giving every agent at least 3/5 of her APS can be computed efficiently.In the unweighted setting, APS is at least MMS and can be strictly larger.
8.4 Group Fairness
The survey broadens discrete fair division beyond individual static allocations to groups, randomized mechanisms, stochastic instances, and online arrival models.
- 8.4 Group Fairness: Group-fairness research considers either fairness for any group or fairness within pre-existing groups such as families.For indivisible goods, group-fairness extends group envy-freeness, with EF and PO appearing as extreme cases.
- 8.4 Group Fairness: Randomization can guarantee ex-ante fairness, but uniformly random allocation is insufficient for ex-post guarantees; randomized Round-Robin gives ex-ante PROP but not ex-ante EF.Probabilistic-Serial provides an ex-ante EF allocation by assigning probability shares as agents consume preferred goods.
- 8.5 Randomness in Fair Division: When values are randomly drawn, envy-free allocations are likely with sufficiently many goods, and welfare maximization is envy-free with high probability when m = Ω(n log n).Random perturbations can also make envy-free allocations likely in worst-case instances that originally admit none.
- 8.6 Online Fair Division: In online allocation, random or deterministic algorithms can make cumulative envy vanish asymptotically, while reallocations enable stronger guarantees such as EF1.With two agents Θ(T) reallocations suffice; with more than two, O(T^3/2) suffice and Ω(T) are necessary.
- 8.6 Online Fair Division: Competitive online algorithms for approximate MMS or Prop1/PropX allocations remain an open question.This remains unresolved despite known optimal competitive ratios for identical valuations in related scheduling models.
8.7 Subsidies
The survey discusses subsidies and related extensions to chores and mixed manna, where fairness relaxations, efficiency, and existence remain unevenly understood.
- 8.7 Subsidies: Some allocations cannot be made envy-free using subsidies, while deciding whether an envy-freeable allocation exists is characterized separately from minimizing subsidy.For a fixed envy-freeable allocation, minimum total subsidy is polynomial-time computable; finding the minimum-subsidy allocation is NP-hard.
- 8.7 Subsidies: Any envy-freeable allocation requires at most (n−1)m·v* total subsidy, and the (n−1) factor is unavoidable.A single good valued at v* by every agent requires at least (n−1)·v* in total payments.
- 8.9 Chores and Mixed Manna: For chores, EF1 is computable by Round-Robin, but EF1 and PO compatibility remains unknown except for bi-valued instances.Top-trading resolution is needed in Envy-Cycle Elimination to preserve EF1.
- 8.9 Chores and Mixed Manna: Prop1 always exists with PO for mixed goods and chores, while PropX always exists and is efficiently computable for chores, including asymmetric entitlements.Whether PropX and PO are compatible for chores remains open.
- 8.9 Chores and Mixed Manna: For mixed goods and chores, double Round-Robin computes EF1 for any number of agents, while generalized adjusted winner gives EF1+PO for two agents.Mixed manna includes non-monotone valuation settings.