2017/05/08 by Brânzei, Simina, Nisan, Noam · 1 citation
#Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1705.02946
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.