...the science of cake cutting

31 July, 2009
Page 39 

How do you cut a cake fairly, so everyone gets an equal slice? That's a question that has troubled some of the greatest minds in history. Thankfully, technologyreview.com has reported on "a significant breakthrough" in this complex art. A mathematical algorithm has been found, which allows each person to have a fair share.

According to Xiaotie Deng at Hong Kong City University, along with friends Qi Qi and Amin Saberi, the answer is simple. You cut the cake three ways, thus: "We study the envy-free cake-cutting problem for $d+1$ players with $d$ cuts, for both the oracle function model and the polynomial time function model," they note. "For the former, we derive a $\theta(({1\over\epsilon})^{d-1})$ time matching bound for the query complexity of $d+1$ player cake-cutting with Lipschitz utilities for any $d> 1$. When the utility functions are given by a polynomial time algorithm, we prove the problem to be PPAD-complete. For measurable utility functions, we find a fully polynomial-time algorithm for finding an approximate envy-free allocation of a cake among three people using two cuts." Glad to clear that up. Perhaps more tellingly, this reveals that computer geeks think it reasonable to scoff a third of a cake!

My Account


Most read