Confidently Cutting a Cake into Approximately Fair Pieces

摘要

We give a randomized protocol for the classic cake cutting problem that guarantees approximate proportional fairness, and with high probability uses a linear number of cuts.