Papers on Cake Cutting I want to read

by William Gasarch

(For now this is just papers that I want to gather in one place)

1. Cutting a Cake for Five People by Saberi and Wang. Appeared in Fifth Annusal Conference on Algorithmic Aspects in Information and Management, 2009. Page 292. Moving Knife Protocol for envy-free for 5 people ENVYFREE5.PDF

2. On the Complexity of Cake cutting by Woeginger and Sgall. Appeared in Discrete Optimization Vol 4, 2007. Lower bound Omega(nlog n) on number of cuts for proportional- but the pieces must be contigous. WLBPROP.PDF

3. Cake cutting is really not a piece of cake by Edmonds and Pruhs. ACM Trans. on Alg, 2011. Earlier version in SODA 2006. Lower bound Omega(nlog n) on number of cuts for proportional. Model is reasonable, result is tight. LBPROP.PDF

4. Envy-free cake division cannot be found by finite protocol By Stromquist. Appeared in Electronic Journal of Combinatorics Vol 15, 2008. Lower bound on number of cuts for envyfree - has to be unbounded. But we insist that the pieces be contigous. LBENVYFREE.PDF

5. Towards More expressive Cake Cutting by Caragiannis, Lai, Procaccia. Looks a model where crumbs are worth zero. EXPRESSIVE.PDF

6. How to cut a cake fairly by Walter Stomquist. American Math Monthly, 1980. EXISTSENVYFREE.PDF

7. How to cut a cake before the party ends by Kurokawa, Lai, Procaccia. If the valuations are piecewise linear this gives envy free in bounded number of cuts. envyfreebounded.pdf

8. Thou shalt not covet thy neighbors cake. By Procaccia. Gives quadratic lower bound on envy free for n people. LBENVYFREESQ.PDF

9. Solution of Peter Winkler's Pizza Problem. By Cibulka, et al. From Fete of Combinatorics and Computer Science. PIZZA.PDF

10. A Discrete and Bounded Envy-free Cake cutting Protocol for Four Agents. By Haris Aziz and Simon McKenzie. ENVY.PDF