Feeds:
Posts

## 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 $d+1$ players with $d$ cuts, for both the oracle function model and the polynomial time function model. 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.

### One Response

1. […] This post was Twitted by geomblog […]