## The Query Complexity of Cake Cutting

### Simina Branzei · Noam Nisan

##### Hall J #829

Keywords: [ cake cutting ] [ upper bounds ] [ lower bounds ] [ query complexity ] [ fair division ]

[ Abstract ]
[ [
Tue 29 Nov 9 a.m. PST — 11 a.m. PST

Abstract: We consider the query complexity of cake cutting in the standard query model and give lower and upper bounds for computing approximately envy-free, perfect, and equitable allocations with the minimum number of cuts. The lower bounds are tight for computing contiguous envy-free allocations among $n=3$ players and for computing perfect and equitable allocations with minimum number of cuts between $n=2$ players. For $\epsilon$-envy-free allocations with contiguous pieces, we also give an upper bound of $O(n/\epsilon)$ and lower bound of $\Omega(\log(1/\epsilon))$ queries for any number $n \geq 3$ of players.We also formalize moving knife procedures and show that a large subclass of this family, which captures all the known moving knife procedures, can be simulated efficiently with arbitrarily small error in the Robertson-Webb query model.

Chat is not available.