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.
1. For n=2, proportionality → envy-free
2. Under the assumptions
• Players act to maximize the value they receive
• Preferences are secret
Divide and Choose is proportional
3. 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