Divide-and-Choose

Overview

The divide-and-choose algorithm is the most fundamental fair division procedure. The algorithm exploits the zero-sum nature of the division problem.

Let $S$ be the total resource and $v_i(S) = 100$ for each player $i$. For any partition $\{A, B\}$ where $A \cup B = S$ and $A \cap B = \emptyset$:

$$v_i(A) + v_i(B) = v_i(S) = 100$$

Player 1 uses this constraint by creating pieces such that $v_1(A) \approx v_1(B) \approx 50$, guaranteeing they cannot receive less than 50% regardless of Player 2's choice. Player 2 then optimizes: $v_2(\text{chosen piece}) = \max(v_2(A), v_2(B)) \geq 50$.

Algorithm Flowchart

Fairness Properties

The Divide-and-Choose algorithm satisfies three fundamental fairness properties:

Proportionality

Both players receive at least 50% of their subjective valuation of the resource.

Formal Statement: $\forall i \in \{1,2\}, v_i(\text{piece}_i) \geq 50$

Proof: Player 1 chooses cut position to maximize $\min(v_1(\text{left}), v_1(\text{right}))$.

Since $v_1(\text{left}) + v_1(\text{right}) = 100$, we have $$\min(v_1(\text{left}), v_1(\text{right})) \leq 50 \leq \max(v_1(\text{left}), v_1(\text{right}))$$

Player 1 can achieve $\min(v_1(\text{left}), v_1(\text{right})) \geq 50$ by positioning the cut appropriately.

Player 2 chooses their preferred piece, so $v_2(\text{piece}_2) = \max(v_2(\text{left}), v_2(\text{right})) \geq 50$.

Envy-Freeness

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: Player 1 made the cut such that $v_1(\text{left}) = v_1(\text{right})$ (or as close as possible), so Player 1 cannot prefer the other piece. Player 2 chose their preferred piece by definition. Thus:

$$v_2(\text{piece}_2) = \max(v_2(\text{left}), v_2(\text{right})) \geq v_2(\text{piece}_1)$$

Strategy-Proofness

Truth-telling is optimal for both players.

Formal Statement: Truth-telling is a dominant strategy for both players.

Proof by contradiction:

Player 1: Suppose Player 1's true valuations are $v_1$ but they report $v_1'$ and cut accordingly. This may not optimize $\min(v_1(\text{left}), v_1(\text{right}))$ under their true valuations, so misreporting cannot improve their outcome.

Player 2: Given two pieces, choosing the piece with lower value according to their true valuations $v_2$ gives a worse outcome than choosing the piece with higher value. Therefore, misrepresenting preferences cannot improve Player 2's outcome.

Learn more about fairness properties →

Computational Complexity

Under the Robertson-Webb query model, Divide-and-Choose achieves optimal query complexity for two-player proportional division:

Cut Query: Player 1 makes a cut creating two pieces of equal value
Eval Query: Player 2 evaluates and selects their preferred piece

This 2-query bound is provably optimal - any algorithm guaranteeing proportional division for 2 players must use at least 2 queries.

Compare with other algorithms →