Austin's Moving Knife
Overview
Austin's procedure introduces a moving-knife mechanism to making a fair cake division. The procedure builds on Divide-and-Choose by guaranteeing exact divisions for two parties, rather than merely a proportional one.
Austin's procedure relies on the intermediate value theorem to guarantee exact divisions. Let $f(x)$ represent Player 1's valuation of the cake from position 0 to position $x$, where the cake spans $[0,1]$. Since Player 1's valuation function is continuous and $f(0) = 0$ while $f(1) = 100$, there exists some position $x^* \in (0,1)$ such that $f(x^*) = 50$.
During the knife-moving phase, the player in control maintains two knives at positions $L(t)$ and $R(t)$ such that their valuation of the piece between the knives remains constant:
$$v_1([L(t), R(t)]) = k \text{ for all } t$$where $k$ is the value that player assigned to the initial piece when they first called "stop". The constraint that $L(T) = R(0)$ when $R(T) = 1$ ensures the entire cake is partitioned into exactly three pieces with valuations that sum to 100.
Read more →Algorithm Flowchart
Fairness Properties
Austin's procedure satisfies four fundamental fairness properties:
Equitable
Both players receive exactly 50% of their subjective valuation of the resource.
Formal Statement: $\forall i \in \{1,2\}, v_i(\text{piece}_i) = 50$
Proof: When the first player calls "stop" in the initial phase, they believe the left piece has value exactly 50. During the two-knife phase, Player 1 maintains the middle piece at constant value $k$, while the constraint $L(T) = R(0)$ ensures the three pieces have values $(50-k, k, 50)$ according to Player 1.
Player 2 calls "stop" when they believe the division creates pieces worth exactly 50 each according to their valuation. Since pieces are randomly assigned, both players receive exactly 50% in expectation according to their own valuations.
Envy-free
Neither player prefers the other's allocation to their own.
Formal Statement: $\forall i,j \in \{1,2\}, v_i(\text{piece}_i) \geq v_i(\text{piece}_j)$
Proof: When Player 2 calls "stop" in the final phase, they believe both pieces have equal value according to their valuation: $v_2(\text{piece}_A) = v_2(\text{piece}_B) = 50$. Therefore, Player 2 cannot envy either piece.
For Player 1, the two-knife constraint ensures they value both final pieces equally at the moment of division. Since $v_1(\text{piece}_A) = v_1(\text{piece}_B)$, Player 1 also cannot experience envy regardless of the random assignment.
Strategy-proof
Truth-telling is optimal for both players throughout the procedure.
Formal Statement: Honest revelation of preferences is a dominant strategy for both players.
Proof by contradiction:
Phase 1: If a player calls "stop" before they truly believe the left piece is worth 50, they risk receiving less than 50% if chosen to control the knives. If they wait too long, the other player will call "stop" first and gain control.
Phase 2 (Player 1): Misrepresenting valuations while moving the knives cannot improve the outcome, as Player 1 must maintain truthful valuations to satisfy the geometric constraints of the procedure.
Phase 2 (Player 2): Calling "stop" before truly believing in a 50-50 division risks receiving a piece worth less than 50% according to their true valuation. Waiting longer allows Player 1 to potentially create a division more favorable to Player 1.
Computational Complexity
Austin's moving knife procedure presents a fundamental challenge in the Robertson-Webb query model due to its continuous nature:
Theoretical Query Complexity: O(∞)
Unlike discrete algorithms, Austin's procedure requires unbounded query complexity because:
- Phase 1: Continuous evaluation as the knife moves - players must assess "Is the left piece exactly 50%?" at every infinitesimal position
- Phase 2: Dual knife coordination requiring continuous monitoring of piece values while maintaining geometric constraints
- Exactness Requirement: Achieving perfect 50-50 division fundamentally requires infinite precision
ε-Approximate Implementation: O(log(1/ε))
For any approximation parameter ε > 0, we can achieve an ε-exact division where each player receives a piece valued between $(50-ε)$ and $(50+ε)$ percent of their total valuation.
Definition: ε-Exact Division
A division is ε-exact if for each player $i$:
$$|v_i(\text{piece}_i) - 50| \leq ε$$where $v_i(\text{piece}_i)$ is player $i$'s valuation of their allocated piece as a percentage of their total valuation.
Query Complexity Result: Any ε-exact division for 2 players can be computed using O(log(1/ε)) Robertson-Webb queries.
Intuition for the O(log(1/ε)) Bound:
Binary search can locate a cut position within ε-precision of the exact 50% point. Each query halves the search interval, so achieving precision ε requires approximately $\log_2(1/ε)$ queries.
Mathematical Example: To guarantee each player receives between 49.9% and 50.1% (ε = 0.1), we need $\log_2(10) ≈ 3.3$ queries, so at most 4 Robertson-Webb queries suffice.
The Exactness Barrier: True exactness (ε = 0) requires $\log(1/0) = ∞$ queries, which is why Austin's theoretical guarantee of perfect 50-50 division cannot be achieved with finite Robertson-Webb queries.