Envy-Free Division

Fair division asks how to split a resource among n agents who value it differently, and the first thing to learn is that “fair” is not one property but at least four mutually inequivalent ones: proportionality (everyone gets at least 1/n by their own measure), envy-freeness (nobody would swap), equitability (everyone reports the same satisfaction number), and Pareto efficiency (no costless improvement). These are routinely conflated, and the conflation is not harmless — the ancient two-person “cut and choose” protocol is envy-free but not equitable, and cannot be made so (Procaccia, Cake Cutting Algorithms, Ch. 13 of the Handbook of Computational Social Choice). For a divisible good, envy-free division for n ≥ 4 was an open problem for roughly half a century: Brams and Taylor’s 1995 protocol terminates but with an unbounded number of queries, and the first bounded protocol — Aziz and Mackenzie’s — arrived only in 2016, with a query bound of n^(n^(n^(n^(n^n)))), which is a theorem and not an algorithm (Aziz & Mackenzie 2016). For indivisible goods envy-freeness is simply impossible in general — two people and one car settles it — so practice runs on relaxations: EF1, EFX, and the maximin share. This note walks all of that, and implements the relaxations with exhaustive verification.

Mental Model

The single most useful picture is the lattice of fairness criteria, because almost every confusion in this area is an implication drawn in the wrong direction.

flowchart TB
    subgraph criteria["The four criteria — NOT interchangeable"]
        EF["<b>Envy-freeness</b><br/>for all i,j:  V_i(A_i) >= V_i(A_j)<br/><i>I would not swap with you</i>"]
        PROP["<b>Proportionality</b><br/>for all i:  V_i(A_i) >= 1/n<br/><i>I got at least my share</i>"]
        EQ["<b>Equitability</b><br/>for all i,j:  V_i(A_i) = V_j(A_j)<br/><i>we report the same number</i>"]
        PO["<b>Pareto efficiency</b><br/>no reallocation helps someone<br/>without hurting someone<br/><i>nothing is left on the table</i>"]
    end
    EF -->|"always<br/>(additivity)"| PROP
    PROP -.->|"only when n = 2"| EF
    EQ -.->|"never implies"| PROP
    PROP -.->|"never implies"| EQ
    PO -.->|"orthogonal to all three"| EF

    style EF fill:#dbeafe
    style PROP fill:#dcfce7
    style EQ fill:#fef3c7
    style PO fill:#fae8ff

What it shows: the implication structure among the four fairness criteria for a divisible good with additive valuations. The insight: only one arrow is unconditional — envy-freeness implies proportionality. The reverse holds only for two agents. Equitability is incomparable to both: an allocation in which every agent values their own piece at 0 and someone else’s at 1 is perfectly equitable and grotesquely unfair. Pareto efficiency is orthogonal: giving one agent everything is Pareto efficient and maximally envious.

The proof of the one real arrow is three lines and worth internalizing, because it is the only free lunch in the subject. Valuations are additive — the value of a union of disjoint pieces is the sum of their values — and normalized so the whole cake is worth 1 to everyone. Then for agent i, Σ_j V_i(A_j) = 1 because the pieces partition the cake. A set of n non-negative numbers summing to 1 must contain one that is at least 1/n, so there exists some j with V_i(A_j) ≥ 1/n. Envy-freeness says V_i(A_i) ≥ V_i(A_j), hence V_i(A_i) ≥ 1/n, which is proportionality (Procaccia Ch. 13, §13.2).

The converse fails from n = 3 upward, and the counterexample is worth carrying around: an agent can value its own piece at exactly 1/3 (proportional, tick) while valuing another agent’s piece at 1/2 (envious, cross). Nothing about “I got my share” says “I would not rather have yours.” At n = 2 the two coincide because V_i(A_i) + V_i(A_{3-i}) = 1, so V_i(A_i) ≥ 1/2 forces V_i(A_i) ≥ V_i(A_{3-i}). That coincidence at n = 2 is why cut-and-choose looks like it solves the problem, and why the problem was underestimated for so long.

The Model, Symbol by Symbol

The standard abstraction is the cake: the interval [0, 1], standing in for any heterogeneous divisible resource — land, machine time, an advertising slot, a frequency band.

• N = {1, …, n} is the set of agents.
• V_i is agent i’s valuation, a function from measurable subsets of [0,1] to the reals. It is assumed normalized (V_i([0,1]) = 1), non-negative (V_i(X) ≥ 0), additive (V_i(X ∪ Y) = V_i(X) + V_i(Y) for disjoint X, Y), and divisible/non-atomic (for any X and any 0 ≤ λ ≤ 1 there is a Y ⊆ X with V_i(Y) = λ·V_i(X) — no single point carries mass). These are stated as the standard assumptions in Aziz & Mackenzie’s four-agent paper.
• An allocation A = (A_1, …, A_n) partitions the cake. In general each A_i may be a finite union of intervals; if each A_i must be a single interval the allocation is contiguous (or connected), and that restriction changes the theory dramatically.

Two agents can value the same piece completely differently, and that is the entire source of both the difficulty and the opportunity: heterogeneity is what makes it possible for everyone to get “more than their share” simultaneously.

Divisible vs indivisible is the load-bearing distinction

Everything through the Aziz–Mackenzie result below assumes the cake can be cut anywhere. The second half of this note covers indivisible goods — a finite set M of items, each of which must go to exactly one agent — where the entire fairness vocabulary has to be rebuilt because the exact criteria become unsatisfiable. Do not carry a theorem across that line.

Cut and Choose: Correct, Ancient, and Not Equitable

For n = 2 the protocol is the one every child reinvents. Agent 1 cuts the cake into two pieces it values equally; agent 2 picks the piece it prefers; agent 1 takes the remainder.

sequenceDiagram
    participant A1 as Agent 1 (cutter)
    participant C as Cake [0,1]
    participant A2 as Agent 2 (chooser)
    A1->>C: cut at y with V1(0,y) = V1(y,1) = 1/2
    C-->>A2: two pieces X1 = [0,y], X2 = [y,1]
    A2->>A2: compare V2(X1) vs V2(X2)
    A2->>C: take argmax  (value >= 1/2 by additivity)
    C-->>A1: the other piece (value exactly 1/2)
    Note over A1,A2: envy-free and proportional<br/>V1(A1) = 1/2 exactly;  V2(A2) >= 1/2
    Note over A1,A2: NOT equitable whenever V2(A2) > 1/2

What it shows: the two-message protocol and the values each side ends with. The insight: the guarantees are asymmetric in kind but not in fairness. The cutter’s 1/2 is exact; the chooser’s is at least 1/2 and typically strictly more. That gap is precisely the failure of equitability, and it is not a bug that better engineering removes — it is structural.

Three properties deserve to be stated separately because they get merged:

1. It is envy-free. The cutter is indifferent between two pieces it made equal, so it cannot envy. The chooser took its preferred piece by construction.
2. It is therefore proportional (by the implication above), and at n = 2 the two are the same thing.
3. It is not equitable. If agent 2 values agent 1’s cut-point differently — say it sees the left piece at 0.7 — then agent 2 ends with 0.7 and agent 1 with exactly 0.5. Both are unenvious; their reported satisfactions differ by 0.2. Equitability would demand V_1(A_1) = V_2(A_2), which cut-and-choose never targets.

The equitability failure is not fixable inside the standard computational model. Alon’s 1987 theorem says that if valuations come from continuous density functions, there exists a division into n² − n cuts whose n pieces satisfy V_i(A_j) = 1/n for all pairs i, j — simultaneously equitable and envy-free (Procaccia Ch. 13, Thm 13.1). But Procaccia notes directly that “equitable allocations are impossible to achieve in the computational model that we adopt,” and that methods achieving them “require continuous operations” — moving knives rather than a finite sequence of discrete queries. Existence and computability part company immediately, and that split is the theme of everything below.

There is a further property of cut-and-choose that matters for deployment and is often mistaken for strategyproofness. Each agent can unilaterally guarantee its fair share by following the protocol, regardless of what the other agent does. Agent 1 gets exactly 1/2 even if agent 2 chooses irrationally; agent 2 gets at least 1/2 even if agent 1 cuts unevenly. Procaccia calls this out as a property “shared by other classic algorithms.” It is not the same as truthfulness — a cutter who knows the chooser’s valuation can cut to exploit it and do better than 1/2 — but it is the guarantee that lets you deploy the protocol among adversaries.

The Robertson–Webb Query Model

Cake-cutting complexity cannot be measured in the usual way, because an instance has no finite representation: a valuation is a measure over a continuum. The field’s answer is a concrete complexity model that counts operations rather than bits. The standard is the Robertson–Webb model (Robertson & Webb, Cake-Cutting Algorithms: Be Fair If You Can, 1998), which allows exactly two queries (Procaccia Ch. 13, §13.4):

Query	Signature	Meaning
eval	eval_i(x, y) → V_i(x, y)	“Agent i, what is the interval [x, y] worth to you?”
cut	cut_i(x, α) → y	“Agent i, starting at x, where is the leftmost point y with V_i(x, y) = α?”

Two facts make this the right model. First, each query touches exactly one agent’s valuation, so information about agent i cannot be obtained by interrogating agent j — that separation is what makes lower bounds provable. Second, it is expressive enough to simulate the classic protocols: cut-and-choose is cut_1(0, 1/2) followed by eval_2(0, y) — two queries, and the Selfridge–Conway initialization is cut_1(0, 1/3) then cut_1(y, 1/3) then a query to agent 2.

Two vocabulary distinctions inside this model are load-bearing and constantly muddled:

• A protocol is finite / discrete if it always terminates after finitely many queries.
• A protocol is bounded if there is a function of n alone that caps the number of queries for every valuation profile.

A protocol can be finite and unbounded: it terminates on every input, but no f(n) bounds it, so an adversarial (or merely unlucky) valuation profile can make it run arbitrarily long. That gap — finite but unbounded — is the exact shape of the twenty-one-year hole between Brams–Taylor 1995 and Aziz–Mackenzie 2016.

flowchart LR
    A["<b>Moving-knife</b><br/>continuous operations<br/>Dubins-Spanier, Stromquist,<br/>Barbanel-Brams"] --> B["<b>Finite but unbounded</b><br/>terminates always,<br/>no f(n) cap<br/><i>Brams-Taylor 1995</i>"]
    B --> C["<b>Bounded</b><br/>f(n) queries for<br/>every input<br/><i>Aziz-Mackenzie 2016</i>"]
    C --> D["<b>Practically bounded</b><br/>polynomial in n<br/><i>still open for<br/>envy-freeness</i>"]
    style A fill:#fee2e2
    style B fill:#fef3c7
    style C fill:#dcfce7
    style D fill:#e0e7ff

What it shows: the four rungs of “constructive” for a cake-cutting protocol, in strictly increasing strength. The insight: the headline “envy-free cake cutting was solved in 2016” means rung 3 was reached; rung 4 is wide open, and the gap between rungs 3 and 4 in this particular case is a tower of exponentials.

Proportionality Is Easy: Dubins–Spanier and Even–Paz

Proportionality for arbitrary n was settled decades before envy-freeness, which is itself evidence they are different problems.

Dubins–Spanier (1961), in its discrete form: every remaining agent i marks the point x_i with V_i(0, x_i) = 1/n. The agent with the leftmost mark exits with [0, x_{i*}]. Repeat on the remainder with the remaining agents; the last agent takes what is left (Procaccia Ch. 13, §13.3.2).

Why it is proportional: an agent that exits gets a piece it values at exactly 1/n. The final agent j never exited, which means at every round its own mark was not leftmost, so every departing agent i took a piece with V_j(A_i) ≤ 1/n. Hence V_j(A_j) ≥ 1 − (n−1)/n = 1/n. It costs O(n²) queries: n marks in the first round, n−1 in the second, and so on.

Even–Paz (1984) achieves the same guarantee by recursive halving. Given agents 1..k and a piece [y, z], each agent marks the point splitting [y,z] in half by its own measure; the marks are sorted; the left half of the agents recurse on the left sub-piece and the right half on the right sub-piece. At recursion depth d, n/2^d agents share a piece each of them values at ≥ 1/2^d; at depth lg n a single agent holds a piece worth ≥ 1/n. This is O(n log n) queries.

And O(n log n) is optimal. Edmonds and Pruhs proved a matching Ω(n log n) lower bound in the Robertson–Webb model, and Procaccia’s chapter gives the proof in full: reduce proportional division to n/2 independent instances of the thin-rich problem (find a piece with length ≤ 2/n and value ≥ 1/n), then show the thin-rich problem needs Ω(lg n) queries by an adversary argument on a ternary value tree whose edges carry weight 1/2 (heavy) or 1/4 (light). A rich leaf needs Ω(lg n) heavy edges on its root path; the adversary answers each query while revealing at most two heavy edges per path, so Ω(lg n) queries are forced (Procaccia Ch. 13, Thm 13.2 and Lemmas 13.3–13.4).

Crucially, neither algorithm is envy-free. Procaccia gives the reason in one sentence: in Dubins–Spanier an agent never envies those who exited earlier (their pieces were worth ≤ 1/n to it), but it may certainly envy those who exited later, since the residue they carved from could be worth a great deal to it.

flowchart TB
    subgraph ds["Dubins-Spanier round 1, n = 4"]
        direction LR
        M["marks at 1/4 of each agent's own measure"]
    end
    ds --> R1["agent with LEFTMOST mark exits<br/>with [0, x*]  — worth exactly 1/4 to it"]
    R1 --> R2["3 agents remain, renormalise on [x*, 1]<br/>repeat: mark at 1/3 of the residue"]
    R2 --> R3["2 agents remain: mark at 1/2"]
    R3 --> R4["last agent takes the remainder<br/>worth >= 1/4 to it"]
    R4 --> ENVY["<b>proportional, NOT envy-free</b><br/>the first agent to exit may value<br/>the last agent's piece at 1/2"]
    style ENVY fill:#fee2e2

What it shows: the exit sequence of the Dubins–Spanier protocol and where its guarantee comes from. The insight: the guarantee is sequential and one-sided — each departing agent locks in 1/n and then stops observing. Envy-freeness is a global condition over all pairs, which no protocol built from “take your share and leave” can deliver.

Envy-Freeness for n = 3: Selfridge–Conway

Around 1960, John Selfridge and (independently) John Conway found a bounded, discrete envy-free protocol for three agents. It was never published by either of them; it circulates through Brams and Taylor’s book. Its structure — trim, allocate, then divide the trimmings — is the germ of everything that followed.

flowchart TB
    S1["<b>1.</b> Agent 1 cuts into X1, X2, X3<br/>with V1(X1) = V1(X2) = V1(X3) = 1/3"]
    S2["<b>2.</b> Agent 2 trims its favourite piece down<br/>to tie with its second favourite.<br/>Trimmed remainder = <b>cake 2</b>;<br/>the three pieces = <b>cake 1</b>"]
    S3["<b>3.</b> Agent 3 chooses any piece of cake 1"]
    S4["<b>4.</b> If agent 3 took the trimmed piece,<br/>agent 2 picks from the other two.<br/>Else agent 2 must take the trimmed piece."]
    S5["<b>5.</b> Agent 1 takes the last piece of cake 1<br/>— guaranteed untrimmed"]
    S6["<b>6.</b> Let T = whoever took the trimmed piece,<br/>T' = the other of {2,3}.<br/><b>T' cuts cake 2 into three equal parts</b>"]
    S7["<b>7.</b> Pick order on cake 2: <b>T, then 1, then T'</b>"]
    S1 --> S2 --> S3 --> S4 --> S5 --> S6 --> S7
    S7 --> DONE["envy-free overall"]
    style DONE fill:#dcfce7
    style S6 fill:#fef3c7

What it shows: the seven steps of Selfridge–Conway, with the two non-obvious ones highlighted. The insight: step 6’s choice of cutter and step 7’s pick order are the whole trick — the agent who did not get the trimmed piece is made indifferent over cake 2, so it can be served last.

The envy-freeness argument, walked through (Procaccia Ch. 13, §13.3.3):

• Cake 1 is envy-free. Agent 3 chose first, so it is content. Agent 2 either chose second from two untrimmed pieces or received the trimmed piece — which it deliberately trimmed to tie for best — so it is content. Agent 1 receives an untrimmed piece, and it made all three untrimmed pieces equal, so it is content.
• Cake 2 is envy-free. T' cut it into three parts it values equally, so it is indifferent and can go last. T picks first. Agent 1 picks second.
• The combination is envy-free — envy-free divisions of two disjoint parts of the cake sum to an envy-free division of the whole, by additivity.
• The one worry, resolved. Could agent 1 envy T’s combined holdings? No: even if T received all of cake 2, T’s total would reconstruct at most one of agent 1’s original thirds — worth exactly 1/3 to agent 1, which is exactly what agent 1’s own untrimmed piece is worth. This is the irrevocable advantage (or domination) idea: agent 1 is safe against T no matter what happens to the residue.

That domination idea is stated explicitly by Aziz and Mackenzie as the heart of their protocol too: “An agent i dominates another agent j if he is not envious of j even if the unallocated cake is given to j” (Aziz & Mackenzie 2016, §1). Once a subset S dominates N \ S, the agents in S can stop worrying about the residue entirely.

The n ≥ 4 Saga: Fifty Years of Being Stuck

This is the part of the story most summaries get wrong, so it is worth telling with dates and with what exactly was and was not achieved.

The problem was recognized as hard early. Aziz and Mackenzie quote Garfunkel (1988) calling envy-free cake division “one of the most important open problems in 20th century mathematics,” and Saberi and Wang (2009) calling it “one of the most important open problems in the field.” Procaccia (2013) wrote: “Since the 1940s, the computation of envy-free cake divisions has baffled many great minds across multiple disciplines. Settling this problem once and for all is an important challenge for theoretical computer science” (all quoted in Aziz & Mackenzie 2016, §1).

Existence was never the issue. Su (1999) showed via Sperner’s Lemma that an envy-free allocation exists for any n using only n − 1 cuts — that is, with connected pieces. The obstacle was always finding one with queries.

1995 — Brams and Taylor. Their An Envy-Free Cake Division Protocol (American Mathematical Monthly 102(1), 9–18) was the breakthrough: an envy-free protocol for any number of agents that terminates in finite time. Its flaw, which the authors themselves flagged, is that “the running time or number of queries and even the number of cuts required is unbounded even for four agents. In other words, the number of queries required to identify an envy-free allocation can be arbitrarily large for certain valuation functions” (Aziz & Mackenzie 2016, §1). Procaccia calls unboundedness “a serious flaw.” Brams and Taylor explicitly posed the bounded case for n = 4 as an open problem.

Two more finite-but-unbounded protocols followed — Robertson & Webb (1997) and Pikhurko (2000) — and Gasarch (2015) wrote a paper comparing which of the three unbounded protocols was less bad. That is the state of a field that is stuck.

2008 — Stromquist’s impossibility, and why it does not contradict 2016. Walter Stromquist proved that no finite protocol, even an unbounded one, can guarantee an envy-free division among three or more players if each player must receive a single connected piece (Stromquist 2008, Electronic Journal of Combinatorics 15, R11, abstract). This is a real impossibility theorem and it is frequently misquoted as “envy-free cake cutting is impossible.” It is not: it applies only under the contiguity constraint. Drop the requirement that each agent’s share be one interval — allow finite unions of intervals — and the theorem says nothing. Selfridge–Conway itself already violates contiguity: after step 7, agents hold a piece of cake 1 plus a piece of cake 2.

2016 — Aziz and Mackenzie close it. First for four agents (arXiv:1508.05143), then in general (arXiv:1604.03655): a discrete, bounded, envy-free protocol for any n. The result was a genuine surprise; the paper quotes Ian Stewart’s earlier prediction that “no discrete procedure with a bounded number of cuts (however large) is known for four players, and such schemes probably don’t exist,” and Procaccia’s own framing of the question as possibly a lower-bound problem.

The bound, and why it is a theorem rather than an algorithm

The query bound Aziz and Mackenzie prove is

n^(n^(n^(n^(n^n))))

a power tower of six ns. Read it carefully: this is not n^6, not n!, not 2^n — it is iterated exponentiation five levels deep. For the smallest open case, n = 4:

Level	Expression	Value
1	4	4
2	4^4	256
3	4^(4^4) = 4^256	≈ 1.34 × 10^154 (155 decimal digits)
4	4^(4^(4^4))	≈ 10^(10^153.9)
5–6	two more exponentiations	not expressible in this notation

Level 3 alone — ≈10^154 — already exceeds the estimated number of atoms in the observable universe (~10^80) by seventy-four orders of magnitude, and there are three more levels above it. Say this plainly: the Aziz–Mackenzie protocol has never been run and never will be. Its value is that it converts an open existence-of-an-algorithm question into a closed one. The gap between “bounded” and “usable” is the entire remaining research programme.

Two partial results in the same paper are far more practical, and are what you would actually implement. Running only the paper’s SubCore Protocol — a prefix of the full protocol — yields, in at most n^(3·(n^(2^n))) queries (still enormous, but a single tower rather than a sextuple one), either (a) a partial allocation that is proportional with respect to the whole cake and envy-free, or (b) an envy-free partial allocation in which every agent gets a connected piece worth at least 1/(3n) of the cake (Aziz & Mackenzie 2016, abstract and §1). Note the word partial: some cake is left unallocated. Discarding cake to buy fairness is a recurring, and legitimate, move.

Uncertain

Verify: the claim that no substantially better bound for envy-free cake cutting has been published since 2016. Reason: I read the Aziz–Mackenzie paper (arXiv v-of-August-2017) directly and confirmed its n^(n^(n^(n^(n^n)))) bound, but I did not exhaustively survey the 2017–2026 literature for improvements, and the field is active. To resolve: search for citations of arXiv:1604.03655 with “improved bound” or a lower bound better than the known Ω(n²). What is verified: a Ω(n²) lower bound for envy-free cake cutting in the Robertson–Webb model, cited in Aziz & Mackenzie’s four-agent paper. The gap between Ω(n²) and a sextuple power tower is the largest such gap I know of in any studied algorithmic problem. uncertain

Indivisible Goods: Where Exact Envy-Freeness Simply Dies

Now cross the line. Let M be a finite set of m indivisible goods; an allocation gives each good to exactly one agent. Valuations are additive: v_i(S) = Σ_{g ∈ S} v_i(g).

The impossibility is immediate and needs no theory. Two agents, one good, both value it positively. Whoever does not get it envies whoever does. This is not a corner case — it is the modal case. Here is that fact verified by exhaustive enumeration rather than asserted:

# /tmp/.../fairdiv.py  — the full verifier is reproduced in the next section
v = [[1], [1]]                       # 2 agents, 1 good, both value it 1
for assign in itertools.product(range(2), repeat=1):
    A = [[g for g in range(1) if assign[g] == i] for i in range(2)]
    print(A, is_EF(v, A), is_EF1(v, A), is_EFX(v, A))

    A=[[0], []]  EF=False  EF1=True  EFX=True
    A=[[], [0]]  EF=False  EF1=True  EFX=True
  EF allocation found by exhaustive search: None

  3 agents, 2 identical goods (3^2 = 9 allocations):
    EF allocations: []
    EF1 allocations: 6 of 9

Both of the two possible allocations fail envy-freeness; both satisfy the relaxations. With three agents and two identical goods, zero of nine allocations are envy-free — someone must get nothing while someone else gets something — while six of nine are EF1. That ratio, 0/9 versus 6/9, is the whole argument for relaxing.

The three relaxations that the literature converged on are the following. Let A_i be agent i’s bundle.

flowchart TB
    EF["<b>EF</b> — envy-free<br/>v_i(A_i) >= v_i(A_j)<br/><i>often does not exist</i>"]
    EFX["<b>EFX</b> — envy-free up to ANY good<br/>v_i(A_i) >= v_i(A_j minus g)<br/>for <b>every</b> g in A_j<br/><i>existence OPEN for n >= 4 additive;<br/>FALSE for submodular</i>"]
    EF1["<b>EF1</b> — envy-free up to ONE good<br/>v_i(A_i) >= v_i(A_j minus g)<br/>for <b>some</b> g in A_j<br/><i>always exists, poly-time</i>"]
    MMS["<b>MMS</b> — maximin share<br/>v_i(A_i) >= max over partitions<br/>of min bundle value<br/><i>does NOT always exist;<br/>3/4 + 1/(12n) achievable</i>"]
    EF --> EFX --> EF1
    EF --> MMS
    style EF fill:#fee2e2
    style EFX fill:#fef3c7
    style EF1 fill:#dcfce7
    style MMS fill:#e0e7ff

What it shows: the relaxation hierarchy for indivisible goods, with existence status as of August 2026. The insight: the arrow EFX → EF1 is the one to memorize — EFX is strictly stronger because it must survive removing the least valuable good in the envied bundle, whereas EF1 gets to remove the most valuable one. That single quantifier swap (“any” vs “one”) is the difference between an open problem and a fifteen-line algorithm.

The formal definitions, from the Amanatidis et al. survey (Definitions 3–5):

• EF1 (envy-freeness up to one good), implicitly in Lipton et al. 2004, formally named by Budish 2011: for every pair i, j, either A_j = ∅ or there exists g ∈ A_j with v_i(A_i) ≥ v_i(A_j \ {g}).
• EFX (envy-freeness up to any good), Caragiannis et al. 2019 (also “near envy-freeness”, Gourvès et al. 2014): for every pair i, j and every g ∈ A_j, v_i(A_i) ≥ v_i(A_j \ {g}).
• MMS (maximin share), Budish 2011: agent i’s maximin share μ_i^n(M) is the value it could guarantee itself by partitioning M into n bundles and then being given the worst one — max over partitions (X_1..X_n) of min_j v_i(X_j). An allocation is MMS-fair if v_i(A_i) ≥ μ_i^n(M) for all i. It is the natural generalization of “you cut, I choose” to n agents, and it is ordinal in flavour: it asks only what you could have guaranteed yourself.

The survey’s own worked example (Example 2) is a good hand-check: an allocation can be EF1 without being EFX precisely when the envy survives removal of a low-value good from the envied bundle even though it dies on removal of a high-value one.

Existence status, dated

Because these statuses change, they must be dated.

Notion	Exists always?	Best approximation	As of
EF (indivisible)	No — two agents, one good	—	trivial, forever
EF1	Yes, polynomial time	exact	Lipton et al. 2004; Caragiannis et al. 2019
EFX, n = 2	Yes	exact	Plaut & Roughgarden 2020
EFX, n = 3 (additive)	Yes	exact	Chaudhury, Garg & Mehlhorn, arXiv:2002.05119
EFX, n ≥ 4 (additive)	OPEN	≈0.618-EFX (Amanatidis et al.)	still open Aug 2026
EFX, submodular / subadditive	NO — counterexamples exist	α ≤ 1/2^(1/6) ≈ 0.89 for subadditive	Mackenzie & Suzuki, arXiv:2605.06451, May 2026
MMS	No — Kurokawa, Procaccia & Wang	3/4 + 1/(12n); upper bound 39/40	Garg & Taki 2021; survey Table

Two entries deserve elaboration because they are the most recent and the most misreported.

EFX for n ≥ 4 additive is still open. The Amanatidis et al. survey states it as Open Problem 2 — “Do EFX allocations exist for instances with n ≥ 4 agents and unrestricted additive valuations?” — and it is still being attacked as of this month. In August 2026, Alkassar, Fouz and Mehlhorn published Complete EFX Allocations Exist for Four Additive Agents and Up to Nine Goods (arXiv:2608.08590), pushing the frontier from m ≤ n + 3 to m = 9 = n + 5 for four agents using a machine-verified certificate corpus over a covered valuation polytope. That a 2026 paper is celebrating nine goods and four agents is the clearest possible evidence that the general case is untouched. The same paper reports a striking measurement: on near-identical valuations, only ≈0.14% of all 4^9 allocations are EFX in the strong zero-tolerant sense, which is why the problem resists.

EFX is false beyond additive. Mackenzie and Suzuki (arXiv:2605.06451, May 2026) construct a three-agent, eight-good instance with monotone submodular (in fact weighted-coverage) valuations for which no EFX allocation exists, and a companion subadditive instance where no α-EFX allocation exists for any α > 1/2^(1/6) ≈ 0.89. The construction is symmetric — the agents’ valuations are identical up to a relabelling of the goods — which makes it compact and hand-checkable. Anyone still writing “EFX existence is open” without qualifying additive is now wrong.

Uncertain

Verify: the 3/4 + 1/(12n) MMS bound (Garg & Taki 2021) and the 39/40 upper bound are current. Reason: both are read from the Amanatidis et al. survey, whose most recent revision on arXiv is dated 21 June 2023; I confirmed via an arXiv listing query that fair-division work has continued heavily through August 2026 but did not check whether the MMS constants moved. To resolve: check for post-2023 MMS approximation papers. Treat the constants as “best known as of mid-2023.” uncertain

Implementation: Two EF1 Algorithms, Exhaustively Verified

Everything below was written and run on this machine with CPython 3.14.7 and no third-party libraries (numpy and pip are absent here). The verification strategy is deliberately dumb: compute the full pairwise envy matrix and check every condition by brute force, because a fairness checker that shares code with the allocator proves nothing.

The verifier

def value(v, agent, bundle):
    return sum(v[agent][g] for g in bundle)
 
def envy_matrix(v, A):
    """A[i] = list of goods held by agent i. Returns (i,j) -> v_i(A_j) - v_i(A_i)."""
    n = len(A)
    return {(i, j): value(v, i, A[j]) - value(v, i, A[i])
            for i in range(n) for j in range(n) if i != j}
 
def is_EF(v, A):
    return all(d <= 0 for d in envy_matrix(v, A).values())
 
def is_EF1(v, A):
    """No envy after removing SOME single good — take the BEST good out of A_j."""
    for i in range(len(A)):
        for j in range(len(A)):
            if i == j or value(v, i, A[j]) <= value(v, i, A[i]):
                continue
            if not A[j]:
                return False
            best = max(A[j], key=lambda g: v[i][g])          # most generous removal
            if value(v, i, [g for g in A[j] if g != best]) > value(v, i, A[i]):
                return False
    return True
 
def is_EFX(v, A):
    """No envy after removing ANY single good — must hold for the WORST good too."""
    for i in range(len(A)):
        for j in range(len(A)):
            if i == j:
                continue
            for g in A[j]:
                if value(v, i, [h for h in A[j] if h != g]) > value(v, i, A[i]):
                    return False
    return True

Line by line, the only subtle part is the difference between is_EF1 and is_EFX. is_EF1 picks best = max(A[j], key=lambda g: v[i][g]) — the single most generous removal available, because EF1 needs only some good to work. is_EFX loops over for g in A[j] and fails on the first violation, because EFX must survive every removal, including that of a good worth almost nothing to the envious agent. A good worth 0 to agent i is exactly the adversarial case: removing it does not reduce v_i(A_j) at all, so EFX degenerates to plain EF with respect to that good.

is_EF is the ground truth. brute_force_EF_exists enumerates all n^m assignments and returns an envy-free one if any exists — exponential, and used only as an oracle on small instances.

Round-robin

def round_robin(v, m, order=None):
    n = len(v)
    order = order or list(range(n))
    A = [[] for _ in range(n)]
    remaining = set(range(m))
    t = 0
    while remaining:
        i = order[t % n]
        g = max(remaining, key=lambda g: (v[i][g], -g))   # each agent takes its own favourite
        A[i].append(g); remaining.discard(g); t += 1
    return A

Fifteen lines. Agents take turns in a fixed cyclic order; on your turn you take the remaining good you value most. That is the whole algorithm, and Caragiannis et al. prove it is EF1 (Theorem 1 in the survey).

The proof sketch is worth carrying: consider agents i and j and think of the picking sequence as blocks. If i picks before j in the cycle, then in every round i picks first, so i’s k-th pick is at least as good (to i) as j’s k-th pick — i does not envy j at all. If i picks after j, discard j’s very first pick and re-pair the rounds: i’s k-th pick precedes j’s (k+1)-th, so i weakly prefers its own k-th to j’s (k+1)-th. Envy therefore vanishes after removing one good — j’s first — which is exactly EF1. The survey notes the guarantee is robust: agents need not take their global favourite, only “her favourite among the remaining goods,” and round-robin is one member of a larger family of recursive picking procedures that are all EF1.

Envy-cycle elimination

Lipton, Markakis, Mossel and Saberi (2004) gave the other classic route, and it works for general monotone valuations, not just additive ones.

def envy_cycle_elimination(v, m, order=None):
    """Give each good to an UNENVIED agent. If none exists, the envy graph
    must contain a cycle -- rotate bundles backwards along it and retry."""
    n = len(v)
    A = [[] for _ in range(n)]
    swaps = 0
    for g in (order or list(range(m))):
        while True:
            envied = {j for (i, j), d in envy_matrix(v, A).items() if d > 0}
            unenvied = [i for i in range(n) if i not in envied]
            if unenvied:
                break
            adj = {i: [j for j in range(n) if i != j
                       and value(v, i, A[j]) > value(v, i, A[i])] for i in range(n)}
            cyc = find_cycle(adj)
            assert cyc, "no sink and no cycle in a finite digraph -- impossible"
            bundles = [A[c] for c in cyc]
            for k, c in enumerate(cyc):
                A[c] = bundles[(k + 1) % len(cyc)]           # rotate along the cycle
            swaps += 1
        A[min(unenvied)].append(g)
    return A, swaps

The mechanism, step by step:

1. Build the envy graph: a directed edge i → j whenever i currently envies j.
2. A source with no incoming edge is an unenvied agent. Giving that agent one more good cannot create envy toward it from anyone who did not already… — no, it can, but only by at most one good, which is exactly the EF1 slack. Since nobody envied it before, after receiving one good the envy toward it is removable by deleting that good.
3. If there is no unenvied agent, every node has an incoming edge, and a finite digraph in which every node has in-degree ≥ 1 must contain a directed cycle. Rotate the bundles backwards along that cycle: everyone on the cycle receives the bundle of the agent they envied, so everyone on the cycle strictly improves and nobody outside changes. The number of edges in the envy graph strictly decreases, which is the termination argument.
4. Repeat until a source appears, then assign the good.

flowchart LR
    subgraph before["Envy graph — no source, must rotate"]
        A0((a)) -->|envies| B0((b))
        B0 -->|envies| C0((c))
        C0 -->|envies| A0
    end
    subgraph after["After rotating bundles along the cycle"]
        A1((a)) -.->|"holds b's old bundle"| A1
        B1((b)) -.->|"holds c's old bundle"| B1
        C1((c)) -.->|"holds a's old bundle"| C1
    end
    before ==>|"rotate: every agent on the cycle<br/>strictly gains; edge count drops"| after

What it shows: the cycle-rotation step, the only non-obvious part of envy-cycle elimination. The insight: the rotation is a potential-function argument, not a heuristic — each rotation strictly reduces the number of envy edges, which is what bounds the running time. The measurement below shows rotations are common, not exotic.

Measured behaviour

A 3-agent, 7-good instance, run on this machine:

    agent 0: [10, 9, 8, 4, 3, 2, 1]   (total 37)
    agent 1: [ 1, 2, 9, 9, 8, 7, 3]   (total 39)
    agent 2: [ 5, 5, 5, 5, 5, 5, 5]   (total 35)

  round-robin pick order 0,1,2,0,1,2,0 -> [[0, 3, 6], [2, 4], [1, 5]]
    agent 0: own= 15  sees others as [15, 11, 11]
    agent 1: own= 17  sees others as [13, 17,  9]
    agent 2: own= 10  sees others as [15, 10, 10]
  EF=False  EF1=True  EFX=True
  strongest envy: agent 2 envies agent 0 by 5
  does ANY EF allocation exist here? -> [[0, 1], [2, 3], [4, 5, 6]]

  envy-cycle elimination -> [[0, 3, 6], [1, 4], [2, 5]]   cycle rotations: 0
    agent 1: own= 10  sees agent 0's bundle as 13
  EF=False  EF1=True  EFX=False

Three findings sit in that output, and each is a real lesson:

1. Round-robin missed an envy-free allocation that exists. The exhaustive oracle found [[0,1], [2,3], [4,5,6]], which is fully envy-free. Round-robin returned an allocation in which agent 2 envies agent 0 by 5 points. EF1 algorithms do not find EF allocations when they exist — they guarantee EF1 and nothing more.
2. Envy-cycle elimination produced a non-EFX allocation here while round-robin’s happened to be EFX. Agent 1 holds {1,4} worth 10 to itself and values agent 0’s {0,3,6} at 1 + 9 + 3 = 13. Removing good 3 (worth 9 to agent 1) drops it to 4 — EF1 satisfied. Removing good 0 (worth 1 to agent 1) leaves 12, still above 10 — EFX violated. This is the “any vs one” quantifier made concrete: the near-worthless good is the one that breaks EFX.
3. Neither algorithm claims EFX. Chan et al. proved envy-cycle elimination is 1/2-EFX with the right tie-breaking, and Amanatidis et al. reach ≈0.618-EFX by combining round-robin and envy-cycle elimination with preprocessing (survey §4.2) — but full EFX is not on offer.

Scaling that up, over 50,000 random instances (n ∈ {2,3,4}, m ∈ [n, n+4], values i.i.d. uniform on {0,…,20}, seed 20260828, randomized pick order and good order per instance):

Algorithm	EF1	EF	EFX
Round-robin	50,000 / 50,000 = 1.000000	0.3443	0.7621
Envy-cycle elimination	50,000 / 50,000 = 1.000000	0.1353	0.5619

Cycle rotations were triggered 29,344 times across the 50,000 runs — the rotation branch is exercised constantly, not a theoretical corner. And on a 1-in-10 subsample checked exhaustively (5,000 instances), some envy-free allocation existed in 66.7% of them, against round-robin’s 34.4% hit rate and envy-cycle elimination’s 13.5%.

That last comparison is the number to remember. In two thirds of these instances an envy-free split was possible, and the standard EF1 algorithms found one only a third of the time (round-robin) or an eighth of the time (envy-cycle). If you actually want envy-freeness when it is achievable, an EF1 algorithm is the wrong tool; you want a search that optimizes for it, which is what maximum Nash welfare does.

Maximum Nash welfare: EF1 and Pareto optimal

The maximum Nash welfare (MNW) allocation maximizes the product Π_i v_i(A_i) (with a lexicographic tie-break to handle zeros). Caragiannis, Kurokawa, Moulin, Procaccia, Shah and Wang proved the result that makes it the practical default: every MNW allocation is both EF1 and Pareto optimal (Theorem 2, The Unreasonable Fairness of Maximum Nash Welfare).

Why that pairing is hard: “while envy freeness up to one good is straightforward to obtain in isolation, achieving it together with Pareto optimality is challenging.” Round-robin is EF1 but routinely wastes value; welfare maximization is Pareto optimal but arbitrarily envious. MNW gets both from one objective, with no fairness constraint bolted on.

The same paper pins two more guarantees, both tight: MNW gives every agent at least a π_n = 2/(1 + √(4n − 3)) fraction of its maximin share, and at least a Φ = (√5 − 1)/2 ≈ 0.618 fraction of its pairwise maximin share. The catch is complexity: computing an MNW allocation is strongly NP-hard, and the paper’s contribution is an algorithm tuned to the 1000-point elicitation format that solves 50 players × 150 goods in under 30 seconds where naive formulations fail on 5 × 15.

Whether an EF1-and-PO allocation can be computed in polynomial time remains Open Problem 1 in the Amanatidis et al. survey.

Failure Modes and Gotchas

Conflating proportionality with envy-freeness. The single most common error, and the reason it survives is that the two are the same thing for n = 2, which is where everyone’s intuition was formed. From n = 3 an agent can hold exactly its 1/n share and still prefer a neighbour’s pile by a wide margin. Symptom: a system that reports “everyone got their fair share” while users complain loudly about each other’s allocations. Diagnosis: compute the full envy matrix, not the diagonal.

Assuming equitability is implied, or even desirable. Cut-and-choose leaves the chooser strictly better off than the cutter in almost every realization. If your product promises “everyone will be equally happy,” you have promised equitability, which no discrete protocol delivers (Procaccia Ch. 13, §13.3) and which is anyway satisfiable by allocations that are terrible for everyone. Worse, equitability requires interpersonally comparable utilities — agent i’s “0.6” must mean the same thing as agent j’s “0.6” — an assumption envy-freeness never needs, because envy compares two bundles within one agent’s own valuation.

Quoting Stromquist’s impossibility without the contiguity hypothesis. Stromquist 2008 proves that no finite protocol finds an envy-free division for n ≥ 3 when each player must receive a single connected piece. Drop connectivity and Selfridge–Conway already contradicts the misquoted version. If someone tells you envy-free cake cutting is impossible, ask whether they mean contiguous.

Reading “bounded” as “feasible.” Aziz–Mackenzie’s n^(n^(n^(n^(n^n)))) closed the theoretical question and left the engineering question untouched. A paper that says “we give the first bounded protocol” is making a statement about quantifier structure, not about running anything.

Treating EF1 algorithms as envy-free-when-possible. Measured above: in 66.7% of random instances an EF1 algorithm could have returned an envy-free allocation; round-robin did so 34.4% of the time and envy-cycle elimination 13.5%. If envy-freeness matters, search for it (or use MNW), do not hope round-robin stumbles into it.

Forgetting that EFX’s adversary is the worthless good. The good that breaks EFX is typically the one worth nothing to the envious agent — removing it changes nothing, so EFX collapses to EF with respect to it. This is exactly the failure caught in the worked example above: agent 1 envied by 3 points, and the removable good was worth 1. A practical corollary: EFX gets much easier when every agent values every good strictly positively and the values are not too spread out, and much harder in the presence of zero-valued items.

Saying “EFX existence is open” without saying “additive.” As of Mackenzie & Suzuki, May 2026, EFX existence is settled negatively for submodular and subadditive valuations (three agents, eight goods). Open means: n ≥ 4, additive.

Assuming MMS always exists because it “feels like” n-person cut-and-choose. It does not. Kurokawa, Procaccia and Wang proved non-existence for n > 2 (Fair Enough: Guaranteeing Approximate Maximin Shares). Their own framing is the useful one: counterexamples are “elaborate and extremely unlikely to occur in practice,” which is why Spliddit could ship MMS-based allocation for eighteen months. The theoretical guarantee you can actually promise is 2/3 (their result) or 3/4 + 1/(12n) with the later algorithms.

Additivity is doing more work than it looks. Every guarantee in this note assumes v_i(S) = Σ_{g∈S} v_i(g). Complements (“the left shoe is worthless without the right”) and substitutes (“a second monitor adds less than the first”) both break it. Caragiannis et al. note that all deployed implementations they know of rely on additivity, “which is why, in our view, this assumption is indispensable in practical applications” — its real justification is elicitation, not realism: additive preferences can be gathered by asking a user to distribute 1,000 points, which is a UI a normal person can complete.

Strategic misreporting. None of these algorithms is strategyproof. Round-robin, envy-cycle elimination and MNW all reward a well-informed liar. Spliddit’s mitigation is social, not mathematical — users are typically family members dividing an inheritance and are given the guarantee explanations rather than a game-theoretic shield.

Alternatives and When to Choose Them

Setting	Use	Guarantee	Cost
2 agents, divisible	Cut and choose	EF + proportional, each side self-guaranteed	2 Robertson–Webb queries
n agents, divisible, proportionality suffices	Even–Paz	proportional	O(n log n) queries, provably optimal
n agents, divisible, need simple + intuitive	Dubins–Spanier	proportional	O(n²) queries
3 agents, divisible, need EF	Selfridge–Conway	envy-free	~9–15 queries, bounded
n ≥ 4, divisible, need EF	Aziz–Mackenzie	envy-free	tower-of-six bound — theory only
n ≥ 4, divisible, need EF and a running system	Partial allocation: run a prefix, discard residue	EF + proportional on a partial allocation	Aziz–Mackenzie SubCore, or accept moving knives
Indivisible, need something now	Round-robin	EF1	O(nm), ~15 lines
Indivisible, general monotone valuations	Envy-cycle elimination	EF1, 1/2-EFX with careful tie-breaks	polynomial
Indivisible, want efficiency too	Maximum Nash welfare	EF1 and Pareto optimal, π_n-MMS	strongly NP-hard; practical at Spliddit’s scale
Rooms + money (quasi-linear)	Market/price-adjustment (Abdulkadiroğlu et al. 2004)	envy-free and Pareto efficient	polynomial
Many students, many seats, few courses	Approximate CEEI (Budish 2011)	approximate MMS + approximate EF	LP/market clearing

Three decision rules cut through that table.

Money changes everything. If the divisible resource is money and the goods carry prices, envy-freeness becomes easy rather than open. In the rent-division problem — n housemates, n rooms, total rent R, quasi-linear utilities V_ij − p_j — envy-free assignments always exist, are computable by a price-adjustment market algorithm, and are automatically Pareto efficient: “in this domain, every envy-free allocation is also Pareto efficient” (Goldman & Procaccia, Spliddit). The transferable numeraire lets you tune each agent’s utility continuously, which is exactly what indivisibility took away. If you can attach prices, do.

Discarding resources buys fairness. Aziz–Mackenzie’s partial-allocation corollary and the “EFX with charity” line of work (Open Problem 4 in the survey: can exact EFX be achieved by donating a sublinear number of goods?) both trade completeness for fairness. In systems terms: leaving capacity unallocated can be the cheapest way to keep an allocation defensible.

Contiguity is expensive. Requiring each agent’s share to be one interval turns a solved problem into an impossible one for n ≥ 3 (Stromquist 2008). If your resource is a time slot or a contiguous address range and you genuinely cannot fragment it, you are in the impossible regime and should be shopping for approximations, not exact protocols.

Production Notes

The best-documented deployment is Spliddit (www.spliddit.org), launched 4 November 2014 as a not-for-profit academic project by Goldman and Procaccia at CMU. It is unusual in this literature for reporting real numbers.

• Traffic and scale. ~20,000 visitors in the first week (Goldman & Procaccia 2014); more than 90,000 users by the time of the MNW paper (Caragiannis et al.). The divide goods application accumulated 1,281 real-world instances with n from 2 to 10 and an average n very close to 3.
• Elicitation. Every user distributes exactly 1,000 points across the goods. This is the additivity assumption made into a form field, and it is the reason additivity is non-negotiable in deployed systems.
• Original goods algorithm (2014–2016): a fairness ladder. Try envy-freeness; if infeasible, try proportionality; if infeasible, compute the largest α such that every agent gets α·MMS(i); then maximize utilitarian welfare subject to that. The provable floor was α ≥ 2/3 from Procaccia & Wang / Kurokawa et al..
• Why it was replaced, in the users’ own words. The MNW paper reproduces a user email of 7 January 2016 from four brothers dividing 30+ furniture items, complaining that with 3 people, 5 goods, and everyone placing 200 points on every good, the algorithm gave 3 items to one person and 1 to each of the others. That output is correct: in every partition of 5 goods into 3 bundles some bundle has at most one good, so every agent’s MMS is 200, and 3-1-1 maximizes utilitarian welfare subject to hitting 200 each. It is also indefensible to a human. MNW returns 2-2-1.
• Migration. MNW “has been deployed on Spliddit since May 24, 2016.” On the 1,281 recorded instances it achieves full MMS on >95% and full pairwise MMS on >90%, and never worse than a 3/4-approximation on any real instance — far above its tight worst-case ratio of π_n.

The lesson generalizes past fair division: an algorithm whose worst-case guarantee is its only selling point produces outputs users experience as arbitrary. MNW’s advantage on Spliddit was as much explicability (“nobody envies anyone else by more than one item, and no reallocation makes everyone better off”) as it was worst-case ratio.

Other deployments worth naming:

• Rent division. Spliddit implements Abdulkadiroğlu, Sönmez and Ünver’s (2004) price-adjustment algorithm, iteratively raising prices on overdemanded rooms and lowering others. Guaranteed envy-free and (in this domain) Pareto efficient. The New York Times shipped a public rent-division calculator built on Francis Su’s method in 2014. A wrinkle worth knowing: Brams and Kilgour observed that there are configurations where every envy-free allocation requires some negative prices — a housemate must be paid to live in the house — and the algorithm returns non-negative prices whenever any envy-free non-negative-price allocation exists.
• Course allocation. Budish’s approximate-CEEI drives the MBA course-allocation mechanism his paper was written for (deployed at Wharton as Course Match). Its guarantees degrade gracefully in exactly the regime course allocation lives in — many students, many seats per course, relatively few courses — and, as Caragiannis et al. note, give nothing useful in Spliddit’s regime of few agents and one copy of each good. Same theory, opposite operating point.
• Credit sharing. Spliddit’s third application divides credit for a joint project. It implements one of de Clippel, Moulin and Tideman’s (2008) rules, whose key property is impartiality: your own share does not depend on your own report. There is an impossibility here too — for n = 3 no rule can be simultaneously impartial, consensual, and exact (allocating 100%), so Spliddit requires n ≥ 4 for this application. That is a fairness impossibility theorem visible in a product’s input validation.

Inside computer systems, the same criteria appear under other names and rarely with this vocabulary. Multi-Tenancy and Fairness in LLM Serving allocates GPU throughput among tenants who each believe they are being starved — a continuously divisible resource with additive-ish valuations, i.e. cake. BFQ Budget Fair Queueing Scheduler and The Completely Fair Scheduler and Its History both enforce proportionality (weighted shares) and neither reasons about envy at all. API Priority and Fairness is a fairness criterion with strategic clients. A useful exercise on any of them: write down which of the four criteria the system actually guarantees, and whether anyone has checked the other three.

See Also

• Games and Strategic Systems in C MOC — the parent MOC; this note is part of stage P5, Matching and Fair Division
• The Shapley Value — the sibling note: the cooperative answer to “who gets what,” dividing surplus by average marginal contribution rather than by envy comparisons
• Coalitional Games — the core and when it is empty; the stability criterion that fair division’s criteria deliberately ignore
• Stable Matching and The Gale-Shapley Algorithm — the other great applied success of matching theory; note the contrast, stability is a pairwise deviation criterion where envy-freeness is a unilateral comparison criterion
• Top Trading Cycles — house allocation and kidney exchange; the cycle-rotation trick in envy-cycle elimination is structurally the same move
• Hospital-Residents and the NRMP — what happens when a fair-division-adjacent mechanism runs a real labour market
• Mechanism Design — the inverse problem; none of the algorithms here is strategyproof, and that is a mechanism-design question
• Impossibility Results — Stromquist’s contiguous-piece impossibility and the n = 3 impartial-credit impossibility both belong to that family
• The Price of Anarchy — the other way to quantify the gap between what agents do and what is socially best
• Multi-Tenancy and Fairness in LLM Serving — fairness criteria enforced in a live production system, under different vocabulary
• BFQ Budget Fair Queueing Scheduler — proportional-share I/O scheduling; proportionality without envy-freeness, in the kernel
• Bipartite Matching — maximum matching optimizes a global count with no preferences; nothing here does