Research map / Learning theory and algorithms / Submodular and game algorithms
Dueling over Dessert, Mastering the Art of Repeated Cake Cutting
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Studies repeated cake cutting between Alice and Bob (sequential and simultaneous versions), showing Alice can exploit a near-myopic Bob via binary search, that equitable (1/2,1/2) payoffs are enforceable via Blackwell approachability, and that fictitious play converges at O(1/sqrt(T)).
Problem
Repeated fair division of a cake between two strategic players with private valuations, where Alice cuts and Bob chooses a piece, in sequential and simultaneous observation models; how much one player can exploit the other and whether equitable outcomes are achievable over time.
Approach
Alice can exploit a Bob who always picks his favorite piece by binary search on his midpoint; conversely, players can enforce the equitable profile (1/2,1/2) on every trajectory using a Blackwell approachability argument extended to countably many Bob types, and fictitious play converges at rate O(1/sqrt(T)).
Key results
- Alice exploiting a myopic Bob in the sequential setting incurs O(log T) Stackelberg regret via binary search.
- Alice can enforce average payoffs of at least 1/2 - O(1/sqrt(T)) for herself and at most 1/2 + O(1/ln T) for Bob on every trajectory, in both settings.
- Fictitious play converges to average payoffs of 1/2 at rate O(1/sqrt(T)), with |u_A/T - 1/2| <= 2*sqrt(10)/sqrt(T).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Binary-search Bob's midpoint, then cut near it | Alice playing against a myopic Bob in the sequential setting · Sequential repeated cake cutting | Alice Stackelberg regret: O(log{T}) | Helped |
| Use an exploration strategy tailored to Bob's regret exponent α | Alice playing against Bob with regret O(T^{α}) · Sequential repeated cake cutting | Alice Stackelberg regret: O\Bigl(T^{\frac{\alpha+1}{2}} \log T\Bigr) | Helped |
| Use an exploration strategy without knowing Bob's regret exponent | Alice playing against Bob with sublinear regret · Sequential repeated cake cutting | Alice Stackelberg regret: O\Bigl(\frac{T}{\log{T}}\Bigr) | Helped |
| Use the Blackwell-approachability-based equitable-payoff strategy | Alice · Sequential and simultaneous repeated cake cutting | Alice average payoff: \frac{u_A(1,t)}{t} \geq \frac{1}{2} - \frac{4}{\sqrt{t-1}} | Helped |
| Use the Blackwell-approachability-based equitable-payoff strategy | Alice, limiting Bob's payoff · Sequential and simultaneous repeated cake cutting | Bob average payoff: \frac{u_B(1,t)}{t} \leq \frac{1}{2} + \frac{5\Delta+11}{\ln(2t/5)} | Helped |
| Partition the cake into √T equal-value intervals and alternate choices within each | Bob in the sequential setting · Sequential repeated cake cutting | Bob average payoff: \frac{u_B}{T} \geq \frac{1}{2} - \frac{1}{\sqrt{T}} | Helped |
| Choose L or R with equal probability each round | Bob in the simultaneous setting · Simultaneous repeated cake cutting | Expected average payoff: 1/2 | No clear effect |
| Both players best respond to the other's empirical play | Alice and Bob using fictitious play · Simultaneous repeated cake cutting | Average payoff convergence: \left| \frac{u_A}{T} - \frac{1}{2} \right| \leq \frac{2\sqrt{10}}{\sqrt{T}}; \left| \frac{u_B}{T} - \frac{1}{2} \right| | Helped |
Surprising findings
- In the simultaneous setting, any deterministic Bob can be completely exploited by an Alice who cuts at 1, so good regret guarantees force Bob to randomize.
Limitations
- Valuations must have bounded densities for the exploitation theorem to hold (unbounded counterexample given).
- Payoffs are deterministic and the model is two-player with two-piece cuts.
- Bob's regret benchmark is static best-piece-in-hindsight; the weaker benchmark is left open.
Experimental setup
Metrics: Stackelberg regret average payoff convergence rate
Builds on: Blackwell approachability fictitious play Aumann and Maschler repeated cake cutting example Robertson-Webb model
Closest papers by meaning
- On Hierarchies of Fairness Notions in Cake Cutting: From Proportionality to Super Envy-Freeness (NeurIPS 2025 · similarity 0.87)
- Fair Division via the Cake-Cutting Share (AAAI 2025 · similarity 0.86)
- Competition among Pairwise Lottery Contests (AAAI 2024 · similarity 0.86)
- Securing Equal Share: A Principled Approach for Learning Multiplayer Symmetric Games (ICML 2025 · similarity 0.85)
- Repeated Fair Allocation of Indivisible Items (AAAI 2024 · similarity 0.84)
- Fair Division with Market Values (AAAI 2025 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.