备 6
6
envy-free Theorem.The outcome is envy-free (and thus fair). Proof. Alice:gets exactly half,no matter which piece Bob chooses. 口 Bob:gets at least half,no matter how Alice cuts the cake
envy-free ◼ Theorem. The outcome is envy-free (and thus fair). ◼ Proof. ❑ Alice: gets exactly half, no matter which piece Bob chooses. ❑ Bob: gets at least half, no matter how Alice cuts the cake. 7
n=3 Stage 0:Player 1 divides into three equal pieces 0 according to his valuation. Player 2 trims the largest piece s.t.the remaining is the same as the second largest. The trimmed part is called Cake 2;the other form Cake 1. 8
𝑛 = 3 ◼ Stage 0: Player 1 divides into three equal pieces ❑ according to his valuation. ◼ Player 2 trims the largest piece s.t. the remaining is the same as the second largest. ◼ The trimmed part is called Cake 2; the other form Cake 1. 8
Stage 1:division of Cake 1 Player 3 chooses the largest piece. If player 3 didn't choose the trimmed piece, player 2 chooses it. ■ Otherwise,player 2 chooses one of the two remaining pieces. Either player 2 or player 3 receives the trimmed piece;call that player T ▣ and the other player by T'. Player 1 chooses the remaining (untrimmed) piece 9
Stage 1: division of Cake 1 ◼ Player 3 chooses the largest piece. ◼ If player 3 didn’t choose the trimmed piece, player 2 chooses it. ◼ Otherwise, player 2 chooses one of the two remaining pieces. ◼ Either player 2 or player 3 receives the trimmed piece; call that player 𝑇 ❑ and the other player by 𝑇 ′ . ◼ Player 1 chooses the remaining (untrimmed) piece 9
Stage 2(division of Cake 2) T'divides Cake 2 into three equal pieces 0 according to his valuation. Players T,1,and T'choose the pieces of Cake 2,in that order. 10
Stage 2 (division of Cake 2) ◼ 𝑇 ′ divides Cake 2 into three equal pieces ❑ according to his valuation. ◼ Players 𝑇, 1, and 𝑇 ′ choose the pieces of Cake 2, in that order. 10