
Class page for Cake Cutting Algorithms (not fancy but may improve with time)

 Course Notes

 Stories of fair division (from Brams)
 Introduction
 Lecture 2 (formalisms, divideandchoose)
 Lecture 3 (Variations on divideandchoose, intro to moving knife)
 Lecture 4 (moving knife, agreement on 1/2 the cake)
 Lecture 5 (agreement on 1/m o th cake, last diminisher)
 Lecture 6 (Fink's lone chooser, Woodall's strongly proportional, SteinhausKuhn lone divider)
 Lecture 7 (Woodall intermediate step,
ConwayGuySelfridge envyfree for 3, Stromquist moving knives for 3)
 Stromquist (finished)
(Remainder of Stromquist algorithm, covered before review for exam)
 Lecture 8 (Levmorecook 2 knives, envyfree
for 3, Webb envy free for 3, piecutting evnyfree for 3)
 Lecture 9 (Easy 3way envy free, 4way
envyfree, One cut suffices)
 Lecture 10 (cannot get strong proportional for one, positive alloc for the other with finite cuts, cannot guarantee
proportional n=3 with finite cuts, same for n people with n1 cuts).
envyfree, One cut suffices)
 Lecture 11 (No finite algorithm can split 50/50, approximate finite 50/50 alg)
 Lecture 12 (Two may not be able to find a:b
in a single cake agreement, entitlements, chores, proportional adaptation
to chores, envyfree adaptation to chores)
 Lecture 13 (nearexact division for n
people, another nearexact method to agree on half). The rest of the time
was spent going over project code (preferences, algorithms).
 Lecture 14 (Knaster sealed bids)
 Lecture 15 (Lucas method of markers,
alternation (strict and balanced).
 Lecture 16 (Adjusted Winner)
 Lecture 17 (Fisher Market Clearing)
 Lemmas, Theorems, etc.

 For n=2, proportionality → envyfree
 Under the assumptions
 Players act to maximize the value they receive
 Preferences are secret
Divide and Choose is proportional
 Dubins Spanier is proportional
 Algorithms

 Divide and choose for 2 people
 Dubins and Spanier Moving Knife: divides cake proportionally for n people
 Austin's Moving Knives: 2 parties decide on a piece whose value is exactly half to each party
 Austin's extension: 2 parties decide on a piece whose value is exactly 1/m to each party
 Austin's extension: 2 parties divide a cake into m pieces, each of value exactly 1/m to each party
 BanachKnaster trimming algorithm (moving cake): divides cake proportionally for n people
 Fink's lone choser: divides cake proportionally for n people, but n can grow dynamically
 Woodall's algorithm: strongly proportional for two parties if there exists any piece of the cake
that is valued differently by the two parties
 SteinhausKuhn lone divider: divides cake proportionally among 3 people
 Exam I was given
 ConwayGuySelfridge envy free for 3 parties
 Stromquist moving knives (one referee and one knife for each of the three parties), envyfree for 3 parties
 Levmore Cook moving knives (one referee knife and one player knife), envyfree for
3 parties
 Webb moving knife (single knife but requires Austin's procedure),
envyfree for 3 parties
 BramsTaylorZwicker pie cutting (3 radially moving knives)
 (attr) Brams and Taylor, envyfree for 3 using Austin's extension
 (attr) Brams and Taylor, evnyfree for 4 players, using
Austin's extension and the GuySelfridgeConway algorithm