Steinhaus' Lone-Divider
Overview
Rather than a continuous moving knife, Steinhaus introduced the "lone-divider" method to enable fair cake division for 3 parties. The procedure has weak fairness guarantees but provides a solid foundation for more complex algorithms to build off.
Read more →Algorithm Flowchart
Fairness Properties
Steinhaus' procedure guarantees one fundamental fairness property:
Proportionality
All three players receive at least 1/3 of their subjective valuation of the resource.
Formal Statement: $\forall i \in \{1,2,3\}, v_i(\text{piece}_i) \geq 1/3$
Proof: Suppose the Player 1 is chosen to be the lone-divider. They then choose their cut positions such that $v_1(\text{piece}_1) = v_1(\text{piece}_2) = v_1(\text{piece}_3)$
Since $v_1(\text{piece}_1) + v_1(\text{piece}_2) + v_1(\text{piece}_3) = v(\text{cake})$, we know $v_1(\text{piece}_i) = 1/3$
Player 1 will receive one of these pieces by the nature of the algorithm so they are guaranteed to receive a proportional allocation, regardless of which case the division enters.
For the non-dividers we can analyze the case behavior:
Case 1: At least one non-divider believes there are $\geq 2$ proportional pieces.
Without loss of generality, assume Player 2 believes at least two pieces are worth $\geq 1/3$. Player 3 is then guaranteed, by order of choosing, a proprtional piece by their own valuation.
Since Player 2 believed there were $\geq 2$ proportional pieces they are guaranteed to see at least 1 proportional piece after Player 3 chooses one. Thus, they are also guaranteed a proprotional piece.
Case 2: Both non-dividers believe there is $\leq 1$ proportional piece.
In this case we assume that both Player 2 and 3 believe there is at most 1 proportional piece. Thus, one of the "non-proportional" pieces is assigned to Player 1 while the rest of the cake is reassembled for Divide-and-Choose. This reconstructed cake, in the eyes of the original non-dividers, must be > 2/3 (since the removed piece was valued at < 1/3 in their view). Divide-and-Choose guarantees both players will recieve at least 1/2 of the reconstructed cake and 1/2 of 2/3 is 1/3.
Thus, both of the original non-dividers are guaranteed to recieve at least 1/3 of their valuation of the cake. Therefore, this algorithm guarantees proportionality.