Poster
The Query Complexity of Cake Cutting
Simina Branzei · Noam Nisan
Hall J (level 1) #829
Keywords: [ fair division ] [ query complexity ] [ lower bounds ] [ upper bounds ] [ cake cutting ]
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 players and for computing perfect and equitable allocations with minimum number of cuts between players. For -envy-free allocations with contiguous pieces, we also give an upper bound of and lower bound of queries for any number 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.