Fair Division Theory
Fair division addresses how to divide resources among parties with different preferences in a way that satisfies fairness criteria. The classic problem is cake-cutting: how do you divide a heterogeneous cake (where different parts have different values to different people) so that everyone feels they received a fair share?
Key Fairness Criteria
- Proportionality: Each player receives at least 1/n of the value (by their own valuation) for n players. "I got my fair share."
- Envy-freeness: No player prefers another player's allocation to their own. "I wouldn't trade with anyone."
- Equitability: All players value their own share equally. "We all got the same value."
- Pareto efficiency: No reallocation can make someone better off without making someone worse off. "No value is wasted."
Classic Algorithms
Cut-and-Choose (2 players)
One player divides the cake into two pieces they consider equal, the other chooses first. Both players guarantee themselves at least half the value. This is proportional and envy-free but may not be equitable (the chooser may value their piece higher) or efficient (both may prefer different divisions).
Selfridge-Conway (3 players)
A discrete procedure for 3 players that guarantees envy-freeness:
- Player 1 divides the cake into three pieces they consider equal.
- Player 2 trims one piece to create a two-way tie for largest (keeps the trimmings).
- Players choose in order 3, 2, 1, with Player 2 required to take the trimmed piece if available.
- The trimmings are then divided among the players who didn't take the trimmed piece.
This ensures each player believes they received at least as much as any other player.
Last Diminisher (n players)
A sequential procedure that works for any number of players:
- Player 1 cuts a piece they think is worth exactly 1/n of the cake.
- Each subsequent player can either pass or trim the piece to what they think is 1/n.
- The last player to trim (or Player 1 if no one trimmed) receives that piece and exits.
- Repeat with remaining players and remaining cake.
Each player guarantees themselves at least 1/n, achieving proportionality. However, it's not always envy-free.
Adjusted Winner (2 players, multiple items)
For dividing discrete items between two parties:
- Each player distributes 100 points across all items based on how much they value them.
- Initially, each player gets all items they valued higher than the other player.
- Transfer items from the player with higher total points to equalize the valuations.
This achieves envy-freeness, equitability, and Pareto efficiency simultaneously.
Impossibility Results
- No finite bounded algorithm: For n ≥ 3 players, there's no finite procedure with bounded steps that guarantees both envy-freeness and Pareto efficiency with general valuations.
- Strategy-proofness: The Gibbard-Satterthwaite theorem implies that any reasonable fair division mechanism can be manipulated by misreporting preferences.
- Proportionality vs envy-freeness: Envy-freeness is strictly stronger than proportionality. An envy-free division is always proportional, but not vice versa.
Why This Matters
Fair division applies to:
- Divorce settlements: Dividing shared property
- Estate inheritance: Allocating assets among heirs
- International disputes: Territory, resources, emissions rights
- Time allocation: Scheduling shared resources
- Computational resources: Fair allocation in distributed systems
Connection to Game Theory
Fair division connects to cooperative game theory through the concept of the core - allocations where no coalition can do better by breaking away. An envy-free allocation is in the core if coalitions are allowed to form. This links fairness to stability: divisions perceived as unfair are unstable because disadvantaged parties have incentive to renegotiate.