Posts

Showing posts from November 15, 2026

A Deterministic Polynomial-Query Protocol for Envy-Free Cake Cutting

Image
How do you divide a cake among n people so that nobody prefers someone else’s piece? For two people the answer is ancient: one cuts, the other chooses. For more people the road has been long. Brams and Taylor (1995) gave the first protocol for any number of people, but the number of steps it needs has no upper bound. Aziz and Mackenzie (2016) gave the first bounded protocol, with a bound that is a tower of six n’s. Earlier this year, Ye and Bai brought this down to a single-exponential bound, and Psomas gave a 2^O(n log n) protocol. In a new working paper, I give a deterministic protocol that uses O(n⁸ log n) queries, the first deterministic polynomial bound. (A query asks one person to value a piece or to mark a cut.) Similar techniques give a polynomial bound for chore division as well.  The paper is getting early feedback and will be public soon on this page.