Source-linked AI summary
Almost Envy-Freeness with General Valuations
Benjamin Plaut, Tim Roughgarden
TL;DR
Because envy-free allocations may not exist for indivisible goods, this paper studies EFX and develops leximin-based existence results. It also identifies limits: EFX with Pareto optimality requires assumptions in some settings, while finding EFX can require exponentially many value queries.
Problem
Envy-free allocations may not exist for indivisible goods, motivating general study of the relaxed EFX fairness property.
Method
The paper uses the leximin solution and related leximin++ analysis to study EFX allocations, Pareto optimality, and query complexity under additive and general valuations.
Results
The leximin solution is EFX and Pareto optimal for identical general valuations and two players with possibly distinct additive valuations under nonzero marginal utility, while EFX identification has an exponential query lower bound.
Takeaways & Limitations
Under nonzero marginal utility, the two-player additive result gives stronger guarantees than Spliddit’s EF1 and Pareto-optimality guarantee.
Takeaways & Limitations
Leximin++ may fail to be EFX for different valuations, and EFX and Pareto optimality cannot always be guaranteed together when zero-value goods are allowed.
Abstract
from arXiv · showhide
The goal of fair division is to distribute resources among competing players in a "fair" way. Envy-freeness is the most extensively studied fairness notion in fair division. Envy-free allocations do not always exist with indivisible goods, motivating the study of relaxed versions of envy-freeness. We study the envy-freeness up to any good (EFX) property, which states that no player prefers the bundle of another player following the removal of any single good, and prove the first general results about this property. We use the leximin solution to show existence of EFX allocations in several contexts, sometimes in conjunction with Pareto optimality. For two players with valuations obeying a mild assumption, one of these results provides stronger guarantees than the currently deployed algorithm on Spliddit, a popular fair division website. Unfortunately, finding the leximin solution can require exponential time. We show that this is necessary by proving an exponential lower bound on the number of value queries needed to identify an EFX allocation, even for two players with identical valuations. We consider both additive and more general valuations, and our work suggests that there is a rich landscape of problems to explore in the fair division of indivisible goods with different classes of player valuations.
1 Introduction
Indivisible goods make full envy-freeness impossible, motivating EFX as a stronger relaxation than EF1. The paper gives existence, optimality, and computational results across valuation classes, including stronger two-player guarantees than Spliddit.
- Motivation: Indivisible goods can prevent envy-free allocations, even with two players and one good.One player must receive the good, leaving the other envious.
- Relaxed fairness: EFX requires removing any good from an envied player’s bundle to eliminate envy, making it strictly stronger than EF1.EF1 requires only one suitable good, whereas EFX requires every good to work.
- Contributions: The paper provides the first general EFX results, spanning additive, submodular, subadditive, and general valuations.Its results include both existence guarantees and exponential query lower bounds.
- Computational complexity: An exponential lower bound applies to deterministic EFX-finding queries, even for two players with identical submodular valuations.The bound is obtained through a reduction from local search on Odd graphs and extends to randomized algorithms using prior results.
- Positive EFX results: A modified leximin solution yields EFX for identical general valuations and supports a cut-and-choose protocol for two players with possibly distinct general valuations.Finding leximin can itself require exponential time for general valuations.
- Limitations and scope: Without nonzero marginal utility, EFX and Pareto optimality cannot always be guaranteed together; for distinct general valuations, impossibility remains even under that assumption.The positive leximin results therefore depend on valuation class and marginal-utility conditions.
- EFX and Pareto optimality: With nonzero marginal utility, leximin is both EFX and Pareto optimal for two additive players and for any number of players with identical general valuations.For two additive players, this improves on Spliddit’s EF1-and-PO guarantee; a 1/2-EFX allocation also exists for subadditive valuations.
2 Model
The model allocates indivisible goods among players with normalized, monotone valuation functions. It defines EF1, EFX, Pareto optimality, and approximate EFX, while distinguishing additive, submodular, subadditive, and general valuations.
- Valuations: Each player’s valuation assigns a nonnegative value to every bundle, with normalization v_i(∅)=0 and monotonicity under adding goods.General valuations impose only these assumptions.
- Valuation classes: Additive valuations sum individual-good values, while submodular valuations have diminishing returns and subadditive valuations satisfy a broader union-value condition.Every additive valuation is submodular, and every submodular valuation is subadditive.
- Model: An allocation partitions the indivisible goods M into disjoint bundles, one bundle A_i for each player i.Partial allocations may leave some goods unallocated.
- Fairness notions: EF1 allows envy when removing one suitable good from the envied bundle would eliminate it, and such allocations always exist and are polynomial-time computable for general valuations.The good is removed only as a definitional thought experiment.
- Fairness notions: EFX requires that removing any good from the envied bundle eliminates envy, whereas Pareto optimality forbids improving one player without worsening another.EFX is strictly stronger than EF1 but weaker than full envy-freeness.
- Approximate fairness: A c-EFX allocation is the paper’s approximate fairness notion, and the paper gives a 1/2-EFX existence result for subadditive valuations.Here c ranges from 0 to 1.
3 Query complexity lower bound
The paper proves exponential value-query lower bounds for finding EFX allocations, even with two players sharing identical submodular valuations, by reducing the task to local search on Odd graphs.
- Reduction to local search: The lower bound applies to deterministic algorithms even for two players with identical submodular valuations.The valuation construction is shown to be submodular, while identical valuations form the restricted EFX problem used in the reduction.
- Local search: Local Search treats the function as a black box and asks for a vertex whose value is at least that of every neighboring vertex.Algorithms learn function values only through vertex queries, which may be adaptive.
- Exponential local-search bound: The separation-game adversary forces algorithms either to make many queries or disconnect a sufficiently large component, supporting exponential local-search complexity.The argument exploits large graph boundaries and adversarially increasing answers on the still-connected unqueried subgraph.
- Consequences: The resulting deterministic query lower bound transfers from K(2k + 1, k) to EFX Allocation, and a separate result establishes an exponential randomized lower bound as well.The deterministic transfer is stated in Theorem 3.3; the randomized result is explicitly described as exponential but weaker.
4 Existence of EFX allocations for general but identical valuations
For identical general valuations, the paper modifies leximin by prioritizing the minimum-utility player's bundle size, obtaining EFX allocations and a two-player protocol for possibly distinct valuations. The modification has limits: it may fail under distinct valuations, and unlike standard leximin it need not be Pareto optimal.
- 4.1 The leximin solution: The standard leximin solution is globally maximal under its ordering and is Pareto optimal, but it can fail to be EFX even for identical valuations.In the two-good example, leximin selects B although A is EFX and B is not.
- 4.2 The leximin++ solution: Leximin++ first maximizes minimum utility, then the bundle size of that minimum-utility player, before proceeding lexicographically.This tie-breaking modification selects the EFX allocation A over the non-EFX allocation B in the two-good example.
- 4.2 The leximin++ solution: The leximin++ solution is EFX for general but identical valuations.Its comparison operator is a total ordering, with utility checked before bundle size.
- 4.2 The leximin++ solution: For two players with general, possibly distinct valuations, Algorithm 2 returns an EFX allocation via cut-and-choose.The protocol has player 1 use leximin++ to divide, after which player 2 chooses a preferred piece.
- 4.3 Limitations of leximin++: Leximin++ can fail to be EFX for distinct valuations, even when all players have the same total value for the goods.A three-player additive example yields a unique leximin++ allocation that is not EFX; the equal-total-value condition does not eliminate this issue.
- 4.3 Limitations of leximin++: Unlike standard leximin, leximin++ is not guaranteed Pareto optimal, and some instances admit no allocation that is both EFX and Pareto optimal.The impossibility example relies on zero-value goods.
5 Pareto optimality
The section characterizes when EFX and Pareto optimality can coexist. Zero marginal utility permits impossibility results, while nonzero marginal utility enables leximin-based guarantees in several valuation settings but not for distinct general valuations.
- Negative results: Zero marginal utility can make EFX and Pareto optimality mutually exclusive, even with two players and additive or general identical valuations.The paper gives separate impossibility theorems for additive valuations and general identical valuations.
- Positive results: For additive and identical valuations, an allocation that is both EFX and Pareto optimal exists even when zero marginal utility is allowed.The authors describe this as an extremely restrictive and minor result.
- Nonzero marginal utility: Nonzero marginal utility requires every added good to increase a player’s value, even if the increase is arbitrarily small.The paper motivates this as a reasonable practical assumption.
- Positive results from leximin: With nonzero marginal utility, leximin is EFX and Pareto optimal for any number of players with general identical valuations.The proof rules out a non-EFX leximin allocation by constructing one with a higher lexicographic utility profile.
- Positive results from leximin: With nonzero marginal utility, leximin is EFX and Pareto optimal for two players with possibly distinct additive valuations.Additivity and normalization support the proof’s utility comparisons.
- Practical significance: Under nonzero marginal utility, the two-player additive result provides stronger guarantees than Spliddit’s currently deployed EF1-and-PO algorithm.The comparison is stated even for simple examples.
- Counterexample: For two players with distinct general valuations, EFX and Pareto optimality cannot be guaranteed simultaneously even under nonzero marginal utility.A constructed allocation can Pareto-improve an EFX allocation, showing that no allocation is both properties.
6 Existence of 1 2-EFX allocations for subadditive valuations
The section presents an algorithm that guarantees 1/2-EFX for any number of players with subadditive valuations. It maintains approximate fairness through envy-cycle elimination, reassignment, and a termination argument.
- Envy-cycle elimination: Envy-cycle elimination preserves c-EFX while producing an acyclic envy graph.The procedure permutes bundles along an envy cycle and strictly reduces the number of envy-graph edges.
- Algorithm: The algorithm maintains 1/2-EFX partial allocations through successive rounds until all goods leave the pool.Each round either assigns the selected good to an unenvied player or reassigns it when a violation would occur.
- Invariant: Subadditivity ensures that when a newly assigned good would violate 1/2-EFX, giving that good alone to the envious player restores the invariant.The resulting singleton bundle also makes envy directed toward that player fully EFX.
- Termination: The algorithm terminates by a potential-function argument: pool size decreases in one case, while total utility strictly increases in the other.At most m(n + 1)^m rounds are needed according to the supplied bound.
- Comparison with EF1: 1/2-EFX and EF1 are incomparable, so neither fairness property implies the other.The section gives one allocation satisfying EF1 but not 1/2-EFX and another satisfying 1/2-EFX but not EF1.
7 Conclusion and future work
The conclusion consolidates the paper’s positive and negative results on EFX across valuation classes. It emphasizes leximin-based guarantees, an approximate-EFX algorithm, exponential query lower bounds, and unresolved cases for distinct valuations.
- Contributions: The paper provides the first general results on envy-freeness up to any good.Its results span existence, Pareto optimality, algorithms, and query complexity.
- Query complexity: An exponential lower bound on value queries holds for deterministic EFX-finding algorithms, even with two players and identical submodular valuations.The lower bound is obtained through a reduction from local search on Odd graphs, with analogous randomized lower bounds derived from prior results.
- Leximin and protocols: A modification of leximin guarantees EFX for any number of players with general identical valuations and yields a cut-and-choose protocol for two players with general possibly distinct valuations.The cut-and-choose protocol provides an EFX allocation in that two-player setting.
- EFX and Pareto optimality: With nonzero marginal utility, leximin is both EFX and Pareto optimal for general identical valuations and for two players with possibly distinct additive valuations.For two players with distinct general valuations, the paper instead gives a counterexample where no EFX allocation is Pareto optimal.
- Open questions: Whether EFX allocations always exist for more than two players with distinct valuations remains open, even for additive valuations.The conclusion describes the problem as challenging, including for three players with different additive valuations.
- Future work: The paper identifies a separation between query and communication complexity and calls for further study across valuation classes.The two-player cut-and-choose protocol is linear in communication, while EFX finding remains hard in the query model for two players.
A Additional proofs
The appendix supplies proofs for the leximin ordering and the zero-marginal-utility extension. It establishes that the ordering is well-defined and transitive, then extends EFX and Pareto optimality from positive-value goods to all goods.
- Leximin ordering: The leximin++ relation is irreflexive because a fixed allocation has a unique valid player ordering.Comparing identical allocations therefore reaches the end of the ordering without returning true.
- Leximin ordering: The leximin++ relation is transitive by comparing the first iterations at which successive allocation comparisons terminate.The proof handles the cases where either comparison terminates earlier or both terminate simultaneously.
- Zero-marginal-utility extension: When zero marginal utility is allowed, zero-valued singleton goods can be removed before applying the positive-marginal-utility theorem.The resulting leximin allocation is then extended by assigning all such goods to a minimum-utility player.
- EFX preservation: Assigning the zero-valued goods to the minimum-utility player preserves EFX because that player remains minimum utility after the assignment.The proof checks bundles of both the recipient and other players separately.
- Pareto optimality: The same assignment preserves Pareto optimality because zero-valued goods do not affect bundle values.Thus Pareto optimality follows from the allocation restricted to the positive-value goods.
B A setting where an EFX allocation can be computed quickly
With identical rankings, Algorithm 4 computes an EFX allocation in polynomial time by allocating goods in descending value while maintaining an acyclic envy graph. The approach extends to certain general valuations and yields a two-player cut-and-choose guarantee.
- B A setting where an EFX allocation can be computed quickly: The algorithm allocates goods in rounds in descending order of value while maintaining an acyclic envy graph.Envy cycles are eliminated by permuting bundles along cycles, and goods are not returned to the pool.
- B A setting where an EFX allocation can be computed quickly: Algorithm 4 computes an EFX allocation for additive valuations with identical rankings in O(mn^3) time.Identical rankings require all players to agree on the relative ordering of individual goods, without requiring identical valuations.
- B A setting where an EFX allocation can be computed quickly: The proof maintains that each player’s value difference between another bundle and her own is bounded by the value of the least valuable good in that bundle.The most recently added good is the least valuable because goods are allocated in decreasing order, yielding EFX throughout the algorithm.
- B A setting where an EFX allocation can be computed quickly: The algorithm generalizes to valuations whose marginal values share a fixed common ordering across all sets.Goods are then allocated in descending order of marginal value rather than ordinary value.
- B A setting where an EFX allocation can be computed quickly: For two players with additive, possibly distinct valuations, cut-and-choose produces an EFX allocation that is fully envy-free from player 2’s viewpoint.Player 1 runs Algorithm 4 with two copies of herself, then player 2 chooses her preferred bundle.