An $\Omega (n\log n)$ Randomized Lower Bound for Cutting a Cake into Proportionally Fair Pieces

Stephen Arndt, Kirk Pruhs, Trung Tran

We consider the classic cake cutting problem in the Robertson-Webb model, with the objective of proportional fairness. We show that any randomized algorithm must use $\Omega (n\log n)$…