New paper on cake-cutting

A paper “On the complexity of envy-free cake cutting” by Xiaotie Deng, Qi Qi, and Amin Saberi was recently uploaded to the archive.  This paper seems to finalize the adoption of the “cake-cutting” literature (see presentation by Ulle Endris or survey by Brams and Taylor) into main stream algorithmic game theory.

Abstract: We study the envy-free cake-cutting problem for players with cuts, for both the oracle function model and the polynomial time function model. For the former, we derive a time matching bound for the query complexity of player cake cutting with Lipschitz utilities for any . 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.

Advertisement