7 min read
On this page

Algorithmic Fair Division

Overview

Fair division studies how to allocate resources among agents with heterogeneous preferences in a way that satisfies formal fairness criteria. The two major settings are divisible goods (cake cutting) and indivisible goods, each with distinct fairness notions, possibility results, and algorithms.

Cake Cutting (Divisible Goods)

The "cake" metaphors a heterogeneous divisible resource (e.g., land, time). Each agent i has a valuation measure v_i over subsets of [0,1], typically assumed to be non-atomic (no single point has positive value), additive, and non-negative.

Fairness Criteria

Proportionality: Each of n agents receives a piece worth at least 1/n of the total cake according to their own valuation: v_i(X_i) >= v_i([0,1]) / n.

Envy-freeness (EF): No agent prefers another agent's piece to their own: v_i(X_i) >= v_i(X_j) for all i, j. Envy-freeness implies proportionality (for additive valuations) but is strictly stronger.

Equitability: All agents value their own piece equally: v_i(X_i) = v_j(X_j) for all i, j.

Pareto efficiency: No reallocation makes everyone weakly better off and someone strictly better off.

Connected pieces: Sometimes we require each agent to receive a contiguous interval. This restriction makes envy-free division harder.

Proportional Protocols

Cut-and-Choose (n=2): One agent cuts the cake into two pieces they value equally; the other chooses. Guarantees proportionality and envy-freeness for two agents.

Dubins-Spanier (moving knife): A knife moves across the cake; the first agent to call "stop" receives the piece to the left. Repeat for remaining agents. Proportional for n agents. Not envy-free.

Even-Paz (divide and conquer): Recursive halving. Each agent marks where half their remaining value lies. Divide agents into two groups at the median mark. Recurse on each half. O(n log n) queries. Proportional, not envy-free.

Envy-Free Protocols

Selfridge-Conway (n=3): The classical envy-free protocol for three agents.

  1. Agent 1 cuts the cake into three pieces they value equally
  2. Agent 2 trims the largest piece (if any is strictly largest in their view) to create a tie for largest. The trimming is set aside.
  3. Agent 3 picks first (from the three pieces, one possibly trimmed)
  4. Agent 2 picks next (must take the trimmed piece if agent 3 didn't)
  5. Agent 1 takes the remaining piece
  6. The trimming is divided between agents 2 and 3 using cut-and-choose (cutter depends on who took the trimmed piece)

This is a bounded protocol (finite number of cuts) achieving envy-freeness for 3 agents.

Aziz-Mackenzie (n agents): First bounded envy-free protocol for any number of agents (2016). However, requires a number of queries that is a tower of exponentials in n, making it impractical.

Unbounded protocols: Stromquist (moving knives, n=3, not discrete), Robertson-Webb query model protocols. The query complexity of envy-free cake cutting is a major open problem.

Computational Complexity

In the Robertson-Webb query model (eval and cut queries):

  • Proportional division requires Theta(n log n) queries
  • Envy-free division for n agents: best known bound is finite but astronomically large
  • Finding a perfect (exact) division is harder than approximate division

Theorem (Procaccia, 2009): There is no finite protocol for envy-free cake cutting with n agents in the Robertson-Webb model using a bounded number of cuts that also guarantees connected pieces (for n >= 3).

Indivisible Goods

When goods cannot be divided, exact envy-freeness is generally impossible (consider one indivisible good and two agents). Relaxed fairness notions are required.

Fairness Notions

Envy-freeness up to one good (EF1): Agent i does not envy agent j after removing some single good from j's bundle: there exists g in X_j such that v_i(X_i) >= v_i(X_j \ {g}).

Envy-freeness up to any good (EFX): Agent i does not envy agent j after removing any single good from j's bundle: for all g in X_j, v_i(X_i) >= v_i(X_j \ {g}). Strictly stronger than EF1.

Maximin share (MMS): Agent i receives at least their maximin share: v_i(X_i) >= MMS_i, where MMS_i = max_{partition P into n bundles} min_{bundle B in P} v_i(B). Intuitively, the best guarantee from being the "divider" in a divide-and-choose generalization.

Relationships: EFX implies EF1. Neither EF1 nor MMS implies the other. EFX implies 1/2-MMS for additive valuations.

EF1 Algorithms

Round-Robin: Fix an ordering of agents. Each agent in turn picks their most-preferred remaining good. Always produces an EF1 allocation (trivially: agent i envies agent j's bundle by at most one good, the one j picked in the round before i). Simple, polynomial time.

Envy-Cycle Elimination (Lipton et al.): Maintains a partial allocation that is EF1. At each step, allocate an unallocated good to an unenvied agent. If no unenvied agent exists, find an envy cycle and resolve it by each agent in the cycle taking the bundle of the agent they envy.

  • Always terminates (number of envies decreases)
  • Produces a complete EF1 allocation
  • Polynomial time

Maximum Nash Welfare (MNW)

The allocation maximizing the product of agents' valuations (Nash social welfare): max sum_i log v_i(X_i).

Theorem (Caragiannis et al., 2019): The MNW allocation simultaneously satisfies:

  • EF1
  • Pareto efficiency

This is remarkable: MNW provides both fairness and efficiency. However, computing MNW is NP-hard (it generalizes the Santa Claus problem). Approximation algorithms and ILP formulations are used in practice.

EFX: Existence and Computation

The existence of EFX allocations for general additive valuations and n >= 4 agents remains a major open problem.

Known results:

  • EFX exists for 2 agents (trivially, via cut-and-choose over bundles)
  • EFX exists for 3 agents with additive valuations (Chaudhury et al., 2020)
  • EFX exists for any number of agents with identical valuations
  • EFX exists for two types of valuations (Mahara, 2020)
  • Partial EFX allocations (with charity/unallocated goods) can be computed efficiently

MMS: Existence and Approximation

Negative result: MMS allocations do not always exist for n >= 3 agents with additive valuations (Kurokawa et al., 2018).

Approximation: alpha-MMS allocations (each agent gets at least alpha * MMS_i):

  • 3/4-MMS: Guaranteed to exist and computable in polynomial time (Ghodsi et al., 2018)
  • 3/4 + 1/(12n)-MMS: Improved bound (Garg-Taki, 2020)
  • Best current: approximately 3/4 + epsilon

Computing MMS_i itself is NP-hard (equivalent to optimal partition into n equal-valued groups).

Goods and Chores (Mixed Manna)

When items include both goods (positive value) and chores (negative value), fairness definitions and results change substantially:

  • EF1 for chores: v_i(X_i) >= v_i(X_j) after removing one chore from X_i
  • Double round-robin can handle mixed manna
  • Bogomolnaia et al. studied fair division of a mixture, showing existence of competitive equilibrium-based solutions

Rent Division

A practical fair division problem: n agents share n rooms in an apartment and must divide rent fairly.

Sperner's lemma approach (Su, 1999): Model as an envy-free pricing problem. Sperner's lemma guarantees existence of an envy-free room assignment with rent division (each agent prefers their room at their price over all other room-price pairs). Constructive via simplicial subdivision algorithms.

Rental Harmony Theorem: For any assignment of rooms, there exists a division of rent such that each agent weakly prefers their assigned room. The total rent is fixed; only the division varies.

Practical implementations: Splitwise's fair rent calculator, the Adjusted Winner procedure (Brams-Taylor).

Course Allocation

Allocating course seats to students with preferences over bundles of courses.

Combinatorial assignment: Each student needs a schedule (bundle of courses) satisfying constraints (time conflicts, prerequisites).

A-CEEI (Approximate Competitive Equilibrium from Equal Incomes): Budish (2011). Give each student approximately equal budget of fake currency; find approximate market-clearing prices for courses. Used at Wharton. Properties: approximately strategy-proof, approximately efficient, EF1-like guarantees.

Draft mechanisms: Sequential selection (like NFL draft). Strategy-proof if single-unit demand. Course allocation versions must handle multi-item bundles and scheduling constraints.

Fairness and Efficiency Trade-offs

Price of fairness: The ratio of optimal social welfare to the best welfare achievable by a fair allocation. For proportionality with n agents: at most n^{n/(n-1)} (Caragiannis et al.). For EF1: can be bounded in specific settings.

Competitive equilibrium: Under divisible goods with additive valuations, a competitive equilibrium from equal incomes (CEEI) is simultaneously envy-free, proportional, and Pareto efficient (First Welfare Theorem). For indivisible goods, approximate versions (A-CEEI) trade off exact fairness for computational tractability.

The field remains active with open problems: EFX existence for 4+ agents, tight approximation ratios for MMS, fair division under constraints (connectivity, cardinality, matroid), and strategic considerations (manipulation-resistant fair division mechanisms).