PPAD-Completeness of Contiguous Envy-Free Cake Cutting with Additive Valuations

Yasushi Kawase, Bodhayan Roy, Mohammad Azharuddin Sanpui

We prove that computing a complete contiguous $\epsilon$-envy-free cake allocation is PPAD-complete for normalized rational piecewise-constant additive valuations. The hardness…