Endriss (Cake Cutting)

Question 1

What are the different cake cutting procedures?

Answer 1

1) Cut-and-Choose
2) Steinhaus procedure
3) Banach-Knaster procedure
4) Dubins-Spanier procedure
5) Even-Paz procedure
6) Selfridge-Conway procedure
7) Stromquist procedure (joker)

Question 2

What is the go-to procedure for 2 players?

Answer 2

Cut-and-choose procedure

Question 3

What are the proportional procedures for 2+ players?

Answer 3

1) Steinhaus procedure (3 players)
2) Banach-Knaster procedure (n players)
3) Dubins-Spanier procedure (n players)
4) Even-Paz procedure (n players)

Question 4

What are the envy-free procedures for 2+ players?

Answer 4

1) Selfridge-Conway procedure
2) Stromquist procedure

Question 5

How does the Cut-and-Choose procedure work?

Answer 5

1) One player cuts the cake in two pieces (which he considers of equal value)
2) The other one chooses one oof the two pieces (which they prefer)

Question 6

How does the Steinhauser procedure work?

Answer 6

1) Player 1 cuts the cake into three pieces (which he considers of equal value)
2) Player 2 “passes” (if they think at least two of the pieces are >= 1/3) or labels two of them as “bad” — if player 2 passed, then players 3, 2, 1 each choose a piece (in that order) and we are done X
3) if player 2 did not pass, then player 3 can also choose between passing and labelling. — If player 3 passed, then players 2, 3, 1 each choose a piece (in that order) and we are done X
4) If neither player 2 or player 3 passed, then player 1 has to take (one of) the piece(s) labelled as “bad” by both 2 and 3. — The rest is reassembled and 2 and 3 player cut-and-choose X

Question 7

How does the Banach-Knaster procedure work?

Answer 7

1) Player 1 cuts off a piece (that he considers to represent 1/n)
2) That piece is passed around the players. Each player either lets it pass (if she consider it too small) or trims it down further (to what she considers 1/n)
3) After the piece has made the full round, the last player to cut something off (the “last diminisher”) is obliged to take it
4) The rest (including the trimmings) is then divided amongst the remaining n-1 players. Play cut-and-choose once n=2 X

Question 8

How does the Dubins-Spanier procedure work?

Answer 8

1) A referee moves a knife slowly across the cake, from left to right. Any player mat shout “stop” at any time. Whoever does so receives the piece to the left of the knife
2) When a piece has been cut off, we continue with the remaining n-1 players, until just one player is left (who takes the rest) X

Question 9

How does the Even-Paz procedure work?

Answer 9

1) Ask each player to indicate her [n/2[ / [n/2] mark
2) Associate the part to the left of the [n/2]th mark with the players who made the leftmost [n/2] marks (group 1), and the rest with the others (group 2)
3) Recursively apply the same procedure to each of the two groups, until only a single player is left X

Question 10

How does the Selfridge-Conway procedure work?

Answer 10

1) Player 1 cuts the cake in three pieces (he considers equal)
2) Player 2 either “passes” (if she thinks at least two pieces are tied for largest) or trims one piece (to get two tied for largest pieces) — If she passed, then let players 3,2,1 pick in that order X
3) If player 2 did trim, then let 3,2,1 pick (in that order), but require 2 to take the trimmed piece (unless 3 did). Keep the trimmings unallocated for now (note: the partial allocation is envy-free)
4) Now divide the trimmings. Whoever of 2 and 3 received the untrimmed piece does the cutting. Let players choose in this order: non-cutter, player 1, cutter

Question 11

Which procedures are proportional?

Answer 11

All of them

Question 12

Which procedures are envy-free?

Answer 12

Cut-and-choose and Selfridge-Conway and Stromquist