xlvi. Cake Cutting and Fair Division

Problem. Divide a cake $[0,1]$ among $n$ people with different tastes (each has a value measure: non-negative, additive, continuous) so that everybody is satisfied, using only cut queries (“where is the point $x$ with $v_i([a,x])=t$?”) and eval queries (“what is $v_i([a,b])$?”), the Robertson–Webb model.

Fairness	Meaning	Protocol	Cuts / queries
proportional, $n=2$	each gets $\ge \frac{1}{2}$ of their own value	I cut, you choose	1 cut; also envy-free
proportional, any $n$	each gets $\ge \frac{1}{n}$	Dubins–Spanier moving knife / last diminisher (Banach–Knaster)	$n-1$ cuts, $O(n^2)$ queries
proportional, any $n$	each gets $\ge \frac{1}{n}$	Even–Paz divide and conquer	$O(n\log n)$ queries, optimal (Edmonds–Pruhs lower bound)
envy-free, $n=3$	nobody prefers another’s piece	Selfridge–Conway (1960)	at most 5 cuts, pieces not connected
envy-free, $n=3$, connected pieces		Stromquist’s four moving knives (1980)	no finite protocol exists (Stromquist, 2008)
envy-free, any $n$		Brams–Taylor (1995, unbounded); Aziz–Mackenzie (2016, bounded but a tower of exponentials)

Envy-free implies proportional (if you value nobody’s piece above yours, yours is at least the average $\frac{1}{n}$).

struct Agent {                                       // value density w[k] on [k/K, (k+1)/K)
    vector<double> w;
    double val(double a, double b) const {
        int K = sz(w); double s = 0;
        for (int k = 0; k < K; k++) s += w[k] * max(0.0, min(b, double(k + 1) / K) - max(a, double(k) / K));
        return s;
    }
    double cut(double a, double t) const {           // smallest x >= a with val(a, x) = t
        int K = sz(w); double last = a;              // (if t is too large, the point where val(a, x) stops growing)
        if (t <= 0) return a;
        for (int k = int(a * K); k < K; k++) {
            double lo = max(a, double(k) / K), hi = double(k + 1) / K, v = w[k] * (hi - lo);
            if (w[k] > 0 && v >= t) return lo + t / w[k];
            if (w[k] > 0) last = hi;
            t -= v;
        }
        return last;                                 // also absorbs rounding when t = val(a, b) exactly
    }
};
using Piece = vector<pair<double, double>>;
double value(const Agent& A, const Piece& P) { double s = 0; for (auto [a, b] : P) s += A.val(a, b); return s; }
 
vector<Piece> dubinsSpanier(const vector<Agent>& A) {    // proportional; the knife sweeps from left to right
    int n = sz(A); vector<Piece> res(n); vector<int> left(n); iota(all(left), 0); double pos = 0;
    while (sz(left) > 1) {
        int bi = 0; double bx = 2;
        for (int t = 0; t < sz(left); t++) { double x = A[left[t]].cut(pos, A[left[t]].val(0, 1) / n); if (x < bx) bx = x, bi = t; }
        res[left[bi]] = {{pos, bx}}; pos = bx; left.erase(left.begin() + bi);   // first to shout "stop" leaves
    }
    res[left[0]] = {{pos, 1}};
    return res;
}
 
void evenPaz(const vector<Agent>& A, const vector<int>& ids, double a, double b, vector<Piece>& res) {
    int n = sz(ids); if (n == 1) { res[ids[0]] = {{a, b}}; return; }
    int k = n / 2; vector<pair<double, int>> marks;
    for (int i : ids) marks.push_back({A[i].cut(a, A[i].val(a, b) * k / n), i});
    sort(all(marks)); double x = marks[k - 1].first;     // cut at the k-th smallest mark
    vector<int> L, R; for (int t = 0; t < n; t++) (t < k ? L : R).push_back(marks[t].second);
    evenPaz(A, L, a, x, res); evenPaz(A, R, x, b, res);
}
 
vector<Piece> selfridgeConway(const vector<Agent>& A) {  // envy-free for 3 agents
    const double eps = 1e-12;
    double x1 = A[0].cut(0, A[0].val(0, 1) / 3), x2 = A[0].cut(x1, A[0].val(0, 1) / 3);
    vector<Piece> pc = {{{0, x1}}, {{x1, x2}}, {{x2, 1}}};
    vector<int> ord = {0, 1, 2};                         // agent 1 ranks the three pieces
    sort(all(ord), [&](int p, int q) { return value(A[1], pc[p]) > value(A[1], pc[q]); });
    Piece trim; int trimmed = -1;
    if (value(A[1], pc[ord[0]]) > value(A[1], pc[ord[1]]) + eps) {   // agent 1 trims its favourite to tie the second
        auto [a, b] = pc[ord[0]][0]; double need = value(A[1], pc[ord[0]]) - value(A[1], pc[ord[1]]);
        double y = A[1].cut(a, need); trim = {{a, y}}; pc[ord[0]] = {{y, b}}; trimmed = ord[0];
    }
    vector<Piece> res(3); vector<char> taken(3, 0); int holder = -1;
    auto best = [&](int ag) { int bp = -1; for (int p = 0; p < 3; p++) if (!taken[p] && (bp < 0 || value(A[ag], pc[p]) > value(A[ag], pc[bp]))) bp = p; return bp; };
    int p2 = best(2); taken[p2] = 1; res[2] = pc[p2];
    int p1 = (trimmed >= 0 && !taken[trimmed]) ? trimmed : best(1); taken[p1] = 1; res[1] = pc[p1];
    int p0 = best(0); taken[p0] = 1; res[0] = pc[p0];
    if (trimmed < 0) return res;
    holder = p2 == trimmed ? 2 : 1; int other = 3 - holder;   // the non-holder cuts the trimming in three
    auto [a, b] = trim[0]; double third = A[other].val(a, b) / 3;
    double y1 = A[other].cut(a, third), y2 = A[other].cut(y1, third);
    vector<Piece> tp = {{{a, y1}}, {{y1, y2}}, {{y2, b}}}; vector<char> tk(3, 0);
    for (int ag : {holder, 0, other}) {                  // choose in this order
        int bp = -1; for (int p = 0; p < 3; p++) if (!tk[p] && (bp < 0 || value(A[ag], tp[p]) > value(A[ag], tp[bp]))) bp = p;
        tk[bp] = 1; res[ag].push_back(tp[bp][0]);
    }
    return res;
}

Proof: I cut you choose, Dubins–Spanier and Even–Paz are proportional

Two people. The cutter splits into two halves of equal value to them, so either half gives them exactly $\frac{1}{2}$; the chooser takes the piece they value more, at least $\frac{1}{2}$, and envies nobody; the cutter values both halves equally, so envies nobody either.

Dubins–Spanier. Each round, every remaining agent $i$ marks the point $x_i$ where the cake from the knife to $x_i$ is worth $\frac{1}{n}$ of their total; the leftmost mark wins that piece. The winner gets exactly $\frac{1}{n}$. Every other remaining agent has $x_i\ge x_{\min }$, so they value the removed piece at most $\frac{1}{n}$. By induction, after $k$ agents left, every remaining agent values the rest of the cake at least $\frac{n-k}{n}$; for the last agent this is at least $\frac{1}{n}$.

Even–Paz. Claim: if $m$ agents each value the current piece $[a,b]$ at least $\frac{m}{n}$ of their total, each ends with at least $\frac{1}{n}$. Split with $k=\lfloor m/2\rfloor$: the $k$ agents with the smallest marks get $[a,x]$, where $x$ is the $k$-th smallest mark. For them $x\ge$ their mark, so they value $[a,x]$ at least $\frac{k}{m}$ of their value of $[a,b]$, i.e. at least $\frac{k}{n}$; for the others their mark is $\ge x$, so they value $[x,b]$ at least $\frac{m-k}{m}$ of $[a,b]$, i.e. $\frac{m-k}{n}$. Recurse; a single agent with value $\ge \frac{1}{n}$ takes the piece. Queries: $m$ cuts per level, $\lceil {\log }_{2}n\rceil$ levels, so $O(n\log n)$.

Proof: Selfridge–Conway is envy-free

Agent 0 cut three pieces equal for them; agent 1 trimmed their favourite $S$ to $S^{\prime }$, tying it with their second favourite; the trimming $T$ is set aside.

Main division. Agent 2 picks first, so envies nobody. Agent 1 has at least one of their two tied favourites left (agent 2 took at most one), and takes $S^{\prime }$ if it is available, otherwise the other tied piece; they envy nobody. Agent 0 gets an untrimmed piece (if $S^{\prime }$ was left by agent 2, agent 1 must take it), worth $\frac{1}{3}$ to them, while every other piece is worth at most $\frac{1}{3}$ to them (an untrimmed third, or $S^{\prime }\subseteq S$).

The trimming. Let $X$ be the agent holding $S^{\prime }$ and $Y$ the other of agents 1, 2. $Y$ cuts $T$ into three parts equal for $Y$; $X$ chooses, then agent 0, then $Y$. $X$ chooses first, so has no envy on $T$. $Y$ values the three parts equally, so has no envy on $T$; in the main division $Y$ values their own piece at least as much as $S^{\prime }$: if $Y$ is agent 2, they chose while $S^{\prime }$ was still available, and if $Y$ is agent 1, then agent 2 took $S^{\prime }$ and agent 1 took the other piece of their tie, equal to $S^{\prime }$ for them. Agent 0 chooses before $Y$, so does not envy $Y$ on $T$; and agent 0 does not envy $X$ at all, because $X$‘s total is $S^{\prime }\cup (\text{part of }T)\subseteq S$, worth at most $\frac{1}{3}$ to agent 0, which equals agent 0’s main piece. Hence nobody envies anybody. At most 5 cuts: 2 + 1 trim + 2. All three protocols were checked on random piecewise-constant valuations (proportionality for $n\le 8$, envy-freeness for Selfridge–Conway).

Related notes

• Greedy and Exchange Arguments
• Divide and Conquer (Even–Paz)
• Stable Marriage (another fairness notion)