On the complexity of cake cutting

In the cake cutting problem, n≥2n≥2 players want to cut a cake into nn pieces so that every player gets a ‘fair’ share of the cake by his/her own measure.We prove that in a certain, natural cake cutting model, every fair cake division protocol for nn players must use Ω(nlogn)Ω(nlogn) cuts and evaluation queries in the worst case. Up to a small constant factor, this lower bound matches a corresponding upper bound in the same model obtained by Even and Paz, from 1984.