On the Complexity of Envy-Free Cake Cutting

Xiaotie Deng, Qi Qi, Amin Saberi

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. For the former, we derive a…