Dueling over Multiple Pieces of Dessert
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917269846622208 |
|---|---|
| author | Brânzei, Simina Phillips, Reed |
| author_facet | Brânzei, Simina Phillips, Reed |
| contents | We study the dynamics of repeated fair division between two players, Alice and Bob, where Alice partitions a cake into two subsets and Bob chooses his preferred one over $T$ rounds. Alice aims to minimize her regret relative to the Stackelberg value -- the maximum utility she could achieve if she knew Bob's private valuation.
We show that if Alice uses arbitrary measurable partitions, achieving strongly sublinear regret is impossible; she suffers a regret of $Ω\Bigl(\frac{T}{\log^2 T}\Bigr)$ regret even against a myopic Bob. However, when Alice uses at most $k$ cuts, the learning landscape becomes tractable. We analyze Alice's performance based on her knowledge of Bob's strategic sophistication (his regret budget). When Bob's learning rate is public, we establish a hierarchy of polynomial regret bounds determined by $k$ and Bob's regret budget. In contrast, when this learning rate is private, Alice can universally guarantee $O\Bigl(\frac{T}{\log T}\Bigr)$ regret, but any attempt to secure a polynomial rate $O(T^β)$ (for $β< 1$) leaves her vulnerable to incurring strictly linear regret against some Bob.
Finally, as a corollary of our online learning dynamics, we characterize the randomized query complexity of finding approximate Stackelberg allocations with a constant number of cuts in the Robertson-Webb model. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_11486 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Dueling over Multiple Pieces of Dessert Brânzei, Simina Phillips, Reed Computer Science and Game Theory We study the dynamics of repeated fair division between two players, Alice and Bob, where Alice partitions a cake into two subsets and Bob chooses his preferred one over $T$ rounds. Alice aims to minimize her regret relative to the Stackelberg value -- the maximum utility she could achieve if she knew Bob's private valuation. We show that if Alice uses arbitrary measurable partitions, achieving strongly sublinear regret is impossible; she suffers a regret of $Ω\Bigl(\frac{T}{\log^2 T}\Bigr)$ regret even against a myopic Bob. However, when Alice uses at most $k$ cuts, the learning landscape becomes tractable. We analyze Alice's performance based on her knowledge of Bob's strategic sophistication (his regret budget). When Bob's learning rate is public, we establish a hierarchy of polynomial regret bounds determined by $k$ and Bob's regret budget. In contrast, when this learning rate is private, Alice can universally guarantee $O\Bigl(\frac{T}{\log T}\Bigr)$ regret, but any attempt to secure a polynomial rate $O(T^β)$ (for $β< 1$) leaves her vulnerable to incurring strictly linear regret against some Bob. Finally, as a corollary of our online learning dynamics, we characterize the randomized query complexity of finding approximate Stackelberg allocations with a constant number of cuts in the Robertson-Webb model. |
| title | Dueling over Multiple Pieces of Dessert |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2602.11486 |