-
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, divide-and-choose)
- Lecture 3 (Variations on divide-and-choose, 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, Steinhaus-Kuhn lone divider)
- Lecture 7 (Woodall intermediate step,
Conway-Guy-Selfridge envy-free for 3, Stromquist moving knives for 3)
- Stromquist (finished)
(Remainder of Stromquist algorithm, covered before review for exam)
- Lecture 8 (Levmore-cook 2 knives, envy-free
for 3, Webb envy free for 3, pie-cutting evny-free for 3)
- Lecture 9 (Easy 3-way envy free, 4-way
envy-free, 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 n-1 cuts).
envy-free, 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, envy-free adaptation to chores)
- Lecture 13 (near-exact division for n
people, another near-exact 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 → envy-free
- 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
- Banach-Knaster 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
- Steinhaus-Kuhn lone divider: divides cake proportionally among 3 people
- Exam I was given
- Conway-Guy-Selfridge envy free for 3 parties
- Stromquist moving knives (one referee and one knife for each of the three parties), envy-free for 3 parties
- Levmore Cook moving knives (one referee knife and one player knife), envy-free for
3 parties
- Webb moving knife (single knife but requires Austin's procedure),
envy-free for 3 parties
- Brams-Taylor-Zwicker pie cutting (3 radially moving knives)
- (attr) Brams and Taylor, envy-free for 3 using Austin's extension
- (attr) Brams and Taylor, evny-free for 4 players, using
Austin's extension and the Guy-Selfridge-Conway algorithm