Title: The Query Complexity of Cake Cutting,
Abstract: We study the query complexity of cake cutting 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 connected
envy-free allocations among n=3 players and for computing perfect and equitable
allocations with minimum number of cuts between n=2 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.