An $Ω(n \log n)$ Randomized Lower Bound for Cutting a Cake into Proportionally Fair Pieces
arXiv:2605.2182992.1
AI Analysis
This resolves the randomized query complexity of proportional cake cutting, a fundamental problem in fair division.
The paper proves a lower bound of Ω(n log n) queries for any randomized algorithm achieving proportional fairness in the Robertson-Webb cake-cutting model.
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 $Ω(n \log n)$ queries.