Dueling over Dessert, Mastering the Art of Repeated Cake Cutting
Authors: Simina Branzei
MohammadTaghi Hajiaghayi
Reed Phillips
Suho Shin
Kun Wang
Venue: NeurIPS 2024 poster (2024)
Keywords: fair division
online learning
fictitious play
repeated games
Primary area: algorithmic_game_theory
TL;DR: We analyze repeated cake cutting between two players

Abstract: We consider the setting of repeated fair division between two players, denoted Alice and Bob, with private valuations over a cake. In each round, a new cake arrives, which is identical to the ones in previous rounds. Alice  cuts the cake at a point of her choice, while  Bob  chooses the left piece or the right piece, leaving the remainder for Alice. 
We consider two versions: sequential, where Bob observes Alice's cut point  before choosing left/right, and simultaneous, where he only observes her cut point after making his choice. The simultaneous version was first considered by Aumann and Maschler.
 
We observe that if Bob is almost myopic and chooses his favorite piece too often, then he can be systematically exploited by Alice through a strategy akin to a binary search. This strategy allows Alice to approximate Bob's preferences with increasing precision, thereby securing a disproportionate share of the resource over time.

We analyze the limits of how much a player can exploit the other one and show that fair utility profiles are in fact achievable. Specifically, the players can enforce  the equitable utility profile  of $(1/2, 1/2)$  in the limit  on every trajectory of play, by keeping the other player's utility to approximately $1/2$ on average while guaranteeing they themselves get at least approximately $1/2$ on average. We show this theorem using a connection with Blackwell approachability.

Finally, we analyze a natural dynamic known as fictitious play, where players best respond to the empirical distribution of the other player. We show that
fictitious play converges to the equitable utility profile of $(1/2, 1/2)$ at a rate of $O(1/\sqrt{T})$.

Dueling Over Dessert, Mastering the Art of Repeated Cake Cutting
Simina Brânzei Purdue University iimina.branzeti @ @gmail.commmmmmmmmmmm.mmmmm
Mohammad'Tagh Hajiaghayi University of Maryland hajiaghayi @ gmail.com
Reed Phillips Purdue University
phill289 @ purdue.
Suho Shin
Kun Wang
University of Maryland suhoshin umu.edu
Purdue University
wang5675 @urduueeduuuuuueuuuu
Abstract
We consider the setting of repeated fair division between two players, denoted Alice and Bob, with private valuations which is identical to the ones in previous rounds. Alice cuts the cake at a point of her choice, while Bob chooses the left piece the right piece, leaving the remainder for Alice We consider two versions: sequential, where Bob observes Alice's 's cut point before choosing left/right, and simultaneous, where he only observes her cut point after making his choice. The simultaneous version was first considered Aumann and Maschler (1995).
cake. In each round, new cake arrives,
We observe that Bob almost myopic and chooses his favorite piece too often, then he can be systematically exploited by Alice through a strategy akin to a binary search. This strategy allows Alice approximate Bob's preferences with increasing precision, thereby securing disproportionate share of the resource over time.
We analyze the limits of how much a player can exploit the other one and show that fair utility profiles in fact achievable. Specifically, the players can enforce the equitable utility profile of (1/2, 1/2) in the limit on every trajectory of play, by keeping the other player's utility to approximately 1/2 average while guaran- teeing they themselves get at least approximately 1/2 2 on average. We show this theorem using a connection with Blackwell approachability.
Finally, we analyze natural dynamic known as fictitious play, where players best respond to the empirical distribution of the other player. We show that fictitious play converges to the equitable utility profile of (1/2, 1/2) at rate of O(1vTT).
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Introduction
Cake cutting is a model of fair division Steinhaus (1948), where the cake is a metaphor for a heterogencous divisible resource such land, time, memory in shared computing systems, clean water, greenhouse gas emissions, fossil fuels, or other natural deposits (Procaccia (2013)). The problem is to divide the resource among multiple participants so that everyone believes the allocation is fair. There is an extensive literature on cake cutting in mathematics, political science, economics (Robertson and Webb (1998); Brams and Taylor (1996); Moulin (2003)) and computer science (Brandt et al. (2016)), with a number of protocols implemented (Goldman and Procaccia (2014)).
Traditional approaches to cake cutting often consider single instances of division. However, many real-world scenarios require a repeated division of resources. For instance, consider the recurring task of allocating classroom space in educational institutions each quarter or that of repeatedly dividing computational resources (such as CPU and memory) among the members of an organization. These settings reflect the reality of many social and economic interactions, necessitating a model that not only addresses the fairness of a single division, but also the dynamics and strategies that emerge among participants over repeated interactions.
Repeated fair division is a classic problem first considered by Aumann and Maschler (1995), where two deaytes Alice and Bob-have private valuations over the cake and interact in the following environment. Every day a new cake arrives, which is the same as the ones in previous days. Alice cuts the cake at point of her choosing, while Bob chooses either the left piece or the right piece, leaving the remainder to Alice. Aumann and Maschler (1995) considered the simultancous setting, where both players take their actions at the same time each day, and analyzed the payoff's achievable by Bob when he can have one of two types of valuations.
In this paper, we provide the first substantial progress in this classic setting. We further analyze the simultaneous version from Aumann and Maschler (1995) and also go beyond it, by considering the sequential version where Bob has the advantage of observing Alice's 's chosen cut point before making his selection. Tactical considerations remain pivotal the sequential version, which is none other than the repeated Cut-and-choose protocol with strategic players.
key observation in our study the strategic vulnerability inherent in repeated Cut-and-choose. At a high level, if Bob consistently chooses his preferred piece, then he can be systematically exploited by Alice through strategy akin binary search. This strategy allows Alice to approximate Bob's preferences with increasing precision, thereby securing a disproportionate share of the resource over time. To fight back Alice's 'ss attempt to exploit him, Bob could deceive her by being unpredictable, thus hiding his preferences. While this behavior has the potential to reduce Alice's 's share of the cake, it could also come at the price of affecting Bob's own payoff guarantees in the long term.
Our analysis of the repeated cake cutting game formalizes the intuition that Alice can exploit a (nearly) myopic Bob that often chooses his favorite piece. This outcome, where Alice gains more value, is not entirely fair, as it leaves her happier than Bob. The fairness notion of equitability addresses this imbalance, embodying the idea that players should be equally happy. Formally, requires that Alice's 's value for her allocation should equal Bob's 's value for his allocation. Achieving equitability is particularly important in scenarios with potential for conffict, such as splitting an inheritance.
We show that achieving equitable outcomes in the repeated interaction is in fact possible. Specifically, each player has strategy that guarantees the other player receives no more than approximately 1/2 on average, while securing at least approximately 1/2 for themselves. This approaches the equitable utility profile of (1/2, 1/2) in the limit. We obtain this result by using a connection with Blackwell approachability (1956). Moreover, we consider natural dynamic known as fictitious play (Brown (1951)), where players best respond to the empirical frequency of the other player's past actions. We show that fictitious play converges to the equitable utility profile of (1/2, at rate of O(1/VT).
1.1 Model
Cake cutting model for two players. The cake is modelled as the interval [0, 1]. There are players
N = {A, BJ. where A stands for Alice and B for Bob. Each player i has private value density
function 0; [0.1] + R4,. A piece of cake is measurable set S S [o, 1). The value of player i for S is VS() JOES vx(x) dr. Atoms are worth zero and the valuations are normalized so that

---

v.( 11) 1 vi E [n]. We require bounded densities, i.e. there exist fixed arbitrary 6, A >> 0 such that 6 - (x) < for all E [0, 1].
An allocation = AZ 7B) is a partition of the cake among the players such that each player i receives piece Z₁ the pieces disjoint, and UieN Zi [0, The valuation (aka utility or payoft) of player with their pieces, meaning (ZA) = (ZB).)
allocation Z is V.(Z.). An allocation Z is equitable if the players equally happy
Let A be Alice's midpoint of the cake and m. Bob's midpoint. Alice's Stackelberg value, denoted "AA. is the utility she receives when she cuts the cake at ma and Bob chooses his favorite piece, breaking ties in Alice's favor. The midpoints and Alice's Stackelberg value are depicted in Figure 1.
Figure I: Densities for Alice (blue) and Bob (red). Figure (a) shows Alice's midpoint ma and Bob's midpoint mn. The shaded area in Figure (b) is Alice's Stackelberg value.
, T, Repeated cake cutting. Each round 1. 2. ..,
the next steps take place:
A new cake arrives, which is identical to the ones in previous rounds.
Alice cuts the cake a point a, E [0, 1] her choice. Bob chooses either the left piece or the right piece, then Alice takes the remainder.
We consider two versions: sequential, where Bob observes Alice's cut point a, before choosing left/right, and simultaneous, where he only observes her cut point after making his choice.
pure strategy a map from the history observed by player to the next action play. A mixed strategy is a probability distribution over pure strategies.
1.2 Our Results
Our results will examine how players fare in the repeated game over T rounds. Given history H, u', (H)), where n' is Alice's Stackelberg value and u², (ff) is Alice's utility in round under history Н.
Alice's Stackelberg regret is Reg (If Στ= [u]
Suppose Alice uses mixed strategy SA and Bob uses mixed strategy Sg. Then SA ensures Alice's Stackelberg regret is at most y against SB Reg (H) S y for all T-ruund histories H that could have arisen under the strategies (SA, Sn). Precise definitions for strategies/regret and the remaining notation needed for the full proofs can be found in Section
Alice exploiting Bob
We start with an observation about the sequential setting. If Bob chooses his favorite piece in each round, then Alice can exploit him by running binary search until identifying his midpoint within small error and then cutting near it for the rest time. This will lead to Alice getting essentially her Stackelberg value in all but Ollog T) rounds, while Bob will get 1/2 in all but O T) rounds.
Proposition 1. If Bob plays myopically in the sequential setting, then Alice has strategy that ensures her Stackelberg regret is OllogT)
This exploitation phenomenon holds more generally: if Bob's strategy has bounded regret with respect to the standard of selecting his preferred piece in every round in hindsight, then Alice can almost get her Stackelberg value each round. Her Stackelberg regret a function Bob's regret guarantee, quantified in the next theorem.

---

Theorem 1 (Exploiting a nearly myopic Bob). Let E [0, 1). Suppose Bob plays strategy that ensures his regret O(T*) in the sequential setting. Let B denote the set of all such Bob strategies.
If Alice knows o, she has a strategy SA = S^(a) that ensures her Stackelberg regret is O log T). strategy in B
T). The exponent is sharp: Alice's Stackelberg regret is (1(T for some Bob
If Alice does not know a, she has a strategy SA that ensures her Stackelberg regret is O logT The exponent is sharp: if SA guarantees Alice Stackelberg regret ( against all Bob strategies in Ba for some 3 E [0. 1), then SA has Stackelberg regret ((T)) for some Bob strategy in B
In contrast, in the simultaneous setting, Alice may not approach her Stackelberg value on every trajectory of play. In order to get her Stackelberg value in any given round, Alice needs to cut near Bob's midpoint and Bob needs to pick the piece he prefers, say R. However, Bob deterministically commits to picking R, he will be completely exploited by Alice who cuts at 1, breaking any reasonable regret guarantee he might have. Indeed, any Bob with a deterministic strategy (possibly using different actions over the rounds) has a corresponding Alice who can completely exploit him. Therefore, any Bob strategy with a good regret guarantee would behave randomly, making impossible for Alice to reliably get her Stackelberg value every trajectory. For this reason, focus on the sequential setting when studying how Alice can exploit Bob.'
Equitable payoffs.
Motivated by Theorem 1, we examine the general limits of how much each player can exploit the other and whether fair outcomes are achievable, in both the sequential and simultaneous settings.
Given history H, player i is said to get average payoff of if (+) left hand side not expected utility, but rather the observed total utility averaged over T rounds.
(H) = where the
We say utility profile (u ug) is equitable if Uą = ug. In the single round setting, 4 and up will naturally represent the utilities of the players at an allocation. In the repeated setting, U and up will represent the time-average utilities of the players.
The next theorems show that each player can keep the other player 1/2 while guaranteeing 1/2 for themselves. This type of behavior is reminiscent of spiteful bidding in auctions (Tang and Sandholm (2012)), where a buyer's 's utility diminishes if other bidders are too satisfied.
Theorem 2 (Alice enforeing equitable payoffs; informal). In both the sequential and simultaneous settings, Alice has a pure strategy S. such that for every Bob strategy Sg:
on every trajectory of play, Alice's average payoff is least 1/2-o(1) while Bob's 's average
payoff is at most 1/2 o(1). More precisely. MA 2 - (
and up
2t + e (1+T).
(T)
where un is the cumulative payoff of player over the time horizon T.
key ingredient in the proof of Theorem 2 is connection with Blackwell's ' approachability the- orem Blackwell (1956). Generally speaking, Blackwell approachability can be used by player to limit the payoff of the other player in a certain region of the utility profile. However, the main challenge is that there are uncountably many types of Bob and so Alice cannot apply the strategy from Blackwell directly. Instead, Alice's s strategy constructs a countably infinite set of representatives, which allows to adapt Blackwell's 's argument to this setting.
We show a symmetric theorem for Bob in the sequential setting, while in the simultaneous setting Bob's ss's guarantee only holds in expectation.
Theorem 3 (Bob enforcing equitable payoffs; informal).
In the sequential setting: Bob has a pure strategy SB, such that for every Alice strategy S., on every trajectory of play, Bob's 's average payoff is at least 1/2 o(1), while Alice's 'ise'' average
payoff is at most 1/2 - o(1). More precisely, ue 2
1 and uي < + θ
VT
'One may explore weaker regret benchmark for Bob of always picking the better of left or right in hindsight, which we believe would be an interesting direction for future work.
3

---

In the simultaneous setting: Bob has a mixed strategy Sg, such for every Alice strategy SA. both players have average payoff 1/2 expectation.
When Alice and Bob play such strategies against each other, they approach equitable utility profile of (1/2.1/2). If just one player follows such a strategy, then the best the other player can do is to ensure the safety value of 1/2 for themselves, thus achieving the utility profile (1/2, 1/2).
Fictitious play
Fictitious play is classic learning rule where at each round, each player best responds to the empirical frequency of play of the other player. Fictitious play was introduced in Brown (1951). Convergence to Nash equilibria has been shown for zero-sum games (Robinson (1951)) and special cases of general-sum games (Nachbar (1990); Monderer and Shapley (1996b,a)).
In the cake cutting model, learning rules such as fictitious play are more meaningful in the simul- taneous setting, where there uncertainty for both players due the simultaneous actions. The precise definition of the fictitious play dynamic is in Section 6, while an example of trajectories for an instance with random valuations and uniform random tie-breaking can be found in Figure
0.9
0.6
0.7
0.6
0.3
055
07
1000
1000
3500
(a) Alice's utility.
(b) Bob's utility.
Figure 2: Illustration of Alice's and Bob's average payoff in a randomly generated instance of valuations. The X axis shows the time and the Y axis shows the average payoff up to that round.
The convergence properties of fictitious play can be characterized as follows. Theorem 4 (Fictitious Play; informal). When both Alice and Bob fictitious play, the average payoff of each player converges to 1/2 a rate of O(1/VT).
Roadmap to the paper. Related work is in Section 2. Formal notation and preliminaries can be found in Section An overview of how Alice can exploit nearly myopic Bob can be found in Section 4, with formal proofs in Appendix A. An overview of how players can enforce equitable payoffs can be found in Section with formal proofs Appendix B. Fictitious play can be found in Section 6, with formal proofs in Appendix C. Concluding remarks can be found in Section 7.
2 Related Work
Cake cutting and fairness notions. The cake cutting model is due to Steinhaus (1948). Standard fairness notions include proportionality. equitability, envy-freencee (Even and Paz (1984); Dubins and Spanier (1961); Edward Su (1999); Stromquist (1980); Alon (1987)). For surveys, Robertson and Webb (1998); Brams and Taylor (1996); Moulin (2003); Brandt et al. (2016); Procaccia (2013).
In the Robertson- Weeeb (RW) query model for cake cutting (Woeginger and Sgall (2007)), mediator asks the players enough queries about their preferences until can output a fair allocation. For studies on the query complexity of cake cutting, see Even and Paz (1984); Woeginger and Sgall (2007); Edmonds and Pruhs (2006); Procaccia (2009); Aziz and Mackenzie (2016); Amanatidis et al. (2018); Cheze (2020); Stromquist (2008); Deng et al. (2012); Goldberg et al. (2020a); Filos-Ratsikan al. (2022); Regal-Halev (2018); Deligkas et al. (2021); Goldberg al. (2020b); Brânzei and Nisan (2022, 2019); Ratos-as et al. (2020); Alon and Graur (2020); Filos-Ro Ratsikas et al. (2021).

---

Mossel and Tamuz (2010); Branzei and Miltersen (2015) studied truthful cake cutting in the RW query model, and Chen al. (2013); Bu al. (2023); Bei et al. (2022); Tao (2022) in the direct revelation model. The equilibria of cake cutting protocols were considered in Nicolò and Yu (2008); Brânzei and Miltersen (2013); Brânzei et al. (2016); Goldberg and laru (2021).
Multiple divisible/indiviibble goods and chores. The algorithms and complexity of finding fair allocations in settings with multiple divisible/nddivsible goods/bads were considered in Oh et al. (2021); Plaut and Roughgarden (2020, 2019); Manurangsi and Suksompong (2021); Chaudhury et al. (2021c); Bilò et al. (2019); Amanatidis et al. (2022); Procaccia (2020); Chaudhury et al. (2020, 2021b); Procaccia and Wang (2014); Kulkarni et al. (2021); Chaudhury et al. (2021a). Tucker-Foltz and Zeckhauser (2023) analyze how the cutter should act in a single-round cut-and-choose on multiple goods where the players' valuations of the goods are drawn from publicly known distribution.
Ghodsi et al. (2011) 1) studied fairness in cloud computing settings, where there are multiple divisible goods (e.g. CPU and memory) and the users have to run jobs with different resource requirements. Kandasamy et al. (2020) studied players who do not know their own resource requirements.
Dynamic fair division. Closest our setting is the analysis in the book of Aumann and Maschler (1995) (page 243), where two players are dividing a cake with a cherry. Alice (the cutter) has a uniform density and so she does not care for the cherry, while Bob (the chooser) may may not like the cherry. Alice and Bob declare their actions simultancously and Alice is only allowed to cut in one of two locations. Additionally, Alice has a prior over the type of Bob she facing. Aumann and Maschler (1995) analyzes the set of payoff's approachable for Bob using Blackwell approachability. In contrast, we allow arbitrary value densities for the players and do not assume priors and also consider the sequential version of the game.
Tamuz et al. (2018) introduced exploitability in repeated cut-and-choose protocols, with some cuts made by a mediator, designing non-exploitable protocols. Online cake cutting was studied by Walsh (2011), where agents can arrive/depart over time. For dynamic fair division where goods are allocated irrevocally upon arrival, see Kash et al. (2014); Friedman et al. (2015); Benadè et al. (2022).
Learning in repeated Stackelberg games. The Stackelberg game was introduced by Stackelberg (1934) to understand the first mover advantage of firms when entering market. The Stackelberg equilibrium concept has important applications such as security games Tambe (2011), 1); Balcan et al. (2015), online strategic classification Dong et al. (2018), and online principal agent problems Hajiaghayi et al. (2023). Our model can be seen as each player facing an online learning version of a repeated Stackelberg game.
Kleinberg and Leighton (2003) considered seller's problem of designing an efficient repeated posted price mechanism to buy identical goods when it interacts with sequence of myopic buyers. Gan et al. (2019); Birmpas et al. (2020); Zhao et al. (2023) considered repeated Stackelberg game to study how the follower or leader can exploit the opponent in a general game with arbitrary payoffs. Their techniques, however, do not apply to our model as they typically consider the setting of one player knowing the entire payoff matrix trying to deceive the other player given behavioral assumptions.
Exploiting no-regret agents. Several works considered the extent to which one player can exploit the knowledge that the other player has strategy with sublinear regret. The goal is often to approach the Stackelberg value, the maximum payoff that the exploiter could get by selecting an action first and allowing the opponent to best-respond. In simultaneous games, Deng et al. (2019) showed the exploiter can approach their Stackelberg value, assuming knowledge of the other player's 's payoff function. Haghtalab et al. (2022) showed that, for certain types of sequential games, exploiting leader can approach their Stackelberg value in the limit. Theorem is a similar statement in our setting, but we bound the exploited agent's behavior with an explicit regret guarantee rather than using discounted future payoffs; also, our setting is not captured by the types of games they consider.
Fictitious play. Fictitious play was introduced in Brown (1951). Convergence Nash equilibria has been shown for zero-sum games (Robinson (1951)) and special cases of general-sun sum games (Nachbar (1990); Monderer and Shapley (1996b,a)). None of these results directly apply to our setting, but the most relevant is Berger (2005), which covered non-degenerate 2 x n games (i.e. where every action has a unique best response). Our "2 x xo" game is degenerate, as Bob does not have a unique best response to Alice cutting at m.. Few existing works apply fictitious play to games with continuous action spaces. An example is Perkins and Leslie (2014), which showed that stochastic fictitious play does converge in two-player zero-sum games with continuous action spaces.
5

---

Karlin (1959) conjectured that fictitious play converges at a rate of O(T-1/2). Brandt et al. (2013) found small games where the convergence rate is O(T-1/2), but with very large constants in the O() Daskalakis and Pan (2014) disproved Karlin's conjecture, showing there exist games with n n payoff matrices in which convergence takes place rate of (2(T-1/m) using adversarial tie- ree-braking rules. Panageas et al. (2023) found examples of even slower convergence.
Harris (1998) showed that fictitious play converges rate of O(T~1) in 2 zero-sum games. Abernethy et al. (2021) considered diagonal payoff matrices with non-adversarial tie-breaking rules, showing convergence rates O(T=1/2). Abernethy et al. (2021) does not give a rate of convergence in our setting because requiring the payoff matrix to be diagonal would correspond being allowed to cut at O or 1. This assumption is not as natural in our setting. fact, if Alice can only cut at 0 or the game becomes zero-sum. Furthermore, we allow arbitrary tie- tie-brakiig rules.
Alice only
Preliminaries
In this section we formally define the notation used in our proofs. All our notation applies to both the sequential and simultancous settings, unless otherwise stated.
History. Recall T' is the number of rounds. For each round t [T].
let E [0, IJ be Alice's cut at time and b E {L, RR be Bob's choice at time t, where L stands for the left piece [0, ar] and R for the right piece (a,, 1].
let A, = (01..... a.) be the history of cuts until the end of round and B, (b1..... br)
the history of choices made by Bob until the end of round t.
history H = (Ar, Br) denotes an entire trajectory of play.
Strategies. Let P be the space of integrable value densities over [0, 1]. A pure strategy for Alice at time is function S [0, 1]a-1 x {L, R]]-1 P x N + [0, 1]. such that S (A,-1, Br- U. T) is the next cut point made by Alice as function of the history A, of Alice's cuts, the history B of Bob's 'ss choices, Alice's 's valuation UA, and the horizon T.
For Bob, we define pure strategies separately for the sequential and simultancous settings due to the different feedback that he gets:
Sequential: A pure Bob strategy at time t is a map Sh [0, 1Jj x {L, (L,-) P R}. That is, Bob observes Alice's ' cut point and then responds.
Simultaneous: A pure Bob strategy at time is a map Stg : [0, 1j"-1 x {L, R) x + (L, R}. Thus here Bob chooses L/R before observing Alice's 's cut point at time t.
A pure strategy for Alice over the entire time horizon T is denoted S = A , and tells Alice what cut to make at each time l. A pure strategy for Bob over the entire time horizon T is denoted SB (S). ... 5%) and tells Bob whether to play L/R at each time L.
mixed strategy is a probability distribution over the set of pure strategies. 2
Rewards and utilities. Suppose Alice has mixed strategy SA and Bob has mixed strategy Sg. Let w and u'g be the random variables for the utility (payoff) experienced by Alice and Bob, respectively, at round t. The utility of player E (A is denoted = AS, SB) = Σ up The utility of player i from round f to is u, (t Eie,, u²
The expected utility of player i is E[u]] = Eful]. where the expectation is taken over the randomness of the strategies SA and Sn.
T
Given history H, let ut (H) be player i's utility in round under H and let (HH) =I- (HH be player i's cumulative utility under H.
IIn fact, this is equivalent the behavior strategy in which the player assigns a probability distribution given a history, thanks to Kuhn's 's theorem Kuhn (1950); Kuhn' (1953). The original version of Kuhn's theorem is restricted to games with finite action space, but can be extended to any action space that is isomorphic to unit interval by Aumann (1961): Dresher al. (2016). which contains our setting.

---

Midpoints and Stackelberg value. Let MA [0, be Alice's midpoint of the cake, with VA ([0, ma)) 1/2. and my [0, 1] be Bob's midpoint, with (o m 1/2. Since the densities are bounded from below, the midpoint of each player is uniquely defined. Alice's Stackel- berg value, denoted 4 the utility Alice gets when she cuts at ma and Bob chooses his favorite piece breaking ties in favor of Alice (i.e. taking the piece she prefers less).
4 Alice exploiting Bob
In this section we give an overview of Theorem I, which considers the sequential setting and quantifies the extent to which Alice can exploit Bob that has sub-linear regret with respect the benchmark of choosing the best piece in each round. Formal proofs for this section are in Appendix A.
We start by defining the notion of Stackelberg regret (Dong et al. (2018); Haghtalab et al. (2022)).
Definition 1 (Stackelberg regret). Given history H of the places Alice cut and the pieces Bob chose in each round, Alice's 's Stackelberg regret is Reg (H) = - [ua u' (H),, where u'A is Alice's Stackelberg value and u'A (H) ) is Alice's 's ufility in round l. under history H.
For Bob, consider the basic notion of static regret, where Bob compares his payoff what would have happened if Alice's actions remained the same but he chose the best piece in each round.
Definition (Regret). Given a history H, Bob's 's regret is
T
Reg = Σ
max
VB([O, arl,, VB((a,, 11} u ub))
1=1
recalling that u'g (H) is Bob's ulility in round under history H.
Next we provide a proof sketch for Theorem 1, which is divided in the next two propositions, corresponding to the cases where Alice knows a and does not know a.
Proposition 2. Let E [0. 1). Suppose Bob plays strategy that ensures his regret is O(T") and lei 8 denote the set of all such Bob strategies. Assume Alice knows a. Then she has a strategy SA = Sa)) that ensures her Stackelberg regret is OTT T) The exponent is sharp: Alice's s Stackelberg regret (1(T==) for some Bob strategy in B
Proof sketch. We sketch both the upper and lower bounds.
Sketch for the upper bound. Let Sn denote Bob's strategy, which guarantees his regret is O(T"). Suppose Alice knows a. Then Alice initializes an interval / = [0, 1] and uses the following strategy.
Iteratively, for i = 0, ,,
(1) Alice discretizes the interval I = [u, wi] constant number of sub-intervals (set 6) of equal value to her, by cutting at points dz,j for j E [5] such that u < 0;,1 < 0,2 <... 0g,5 < w. Denote 0; = u and 0;,6 = w. An illustration is Figure 3.
6,2
41
GG
ags
Figure 3: Illustration of step (1) for = 0. Alice divides the interval [0, 1] in 6 disjoint intervals of equal value to her, demarcated by points ou,u = a0,1 < 00,2 < d0,3 < a0,4 < da,s < 1 = Q0,6-
(2) Alice selects number n,, which will be set "large enough" as a function of T and a. In the next 5n rounds, Alice cuts an equal number of times at each point a;,j for j [5). That is:
In each of the next 7 rounds, Alice cuts at ai and observes Bob's choices there, computing the majority answer C, L if Bob picked the left piece more times than the right piece, and c,1 = R otherwise. The next 77 rounds after that Alice switches to cutting 0,,2, and on.
In this fashion, Alice computes G, as Bob's majority answer corresponding cut point anj for all j E [5]. Also, by default c;, = R and C,,6 L. An illustration is in Figure 4.
7

---

R.R.I
R.R.R L.R.R
R.L.R
L.4.
62..2
Figure 4: Illustration of step (2) for i O. Suppose 17 = Alice cuts times at each the points do.j and observes Bob's 's choices, which are marked near each such cut point. By default, Alice knows what the answer would be if she cut at 0 or 1, so those are set to R and L, respectively. The truthful answers (reflecting Bob's 's favorite piece according to his actual valuation) are marked with green, while the lying answers are marked with orange.
(3)
The points a, for E [O,...,6] 66 are arranged on a line and each is labelled I. or R. with the leftmost point as,0 = 0 labelled R and the rightmost point 0,,6 = labelled L. Then there is index E {O..... 5] such that C.j R and C1,++1 L.
Alice computes a smaller interval I,+1, essentially consisting of [a..; 0i.j+1] and some extra space around it to make sure that I;+1 contains Bob's s midpoint as follows. If {1...., 4). set [1+1 [0:.j-1. As.jt2]. If j set I++1 [a.,u. dg,3). If j 5, set I5+1 = |ar,3, d3,6)- Then Alice iterates steps (1 3) on the interval I An illustration is in Figure 5.
R
4g
18g
6o.5
Figure 5: Illustration of step (3) for O. Alice labels each point on with the majority answer there. Then she identifies the index such that the point do,j is labelled R and the point do.j+1 is labelled L.. At this stage she is assured that either the interval (oo.;:00..+1 or one of the adjacent ones contains Bob's midpoint. Alice sets 1 = [00.3, d0,6] and recurses on it.
The full proof explains why the index j from step 3 unique and why it fact necessary to include a slightly larger interval than [as.j. 0t,j+1] ] in the recursion step, due to Bob potentially having lied if his midpoint was very close boundary of [a..j 0i.j+1] but on the other side.
Sketch for the lower bound. The lower bound of {(T relies on the observation that rounds where Alice cuts near m and Bob picks his less-preferred piece cost Bob very little but cost Alice a lot. More precisely, suppose mA < mm and Alice cuts at s. Then compared to his regret bound, Bob loses (e)) he picks the wrong piece. On the other hand, Alice loses (mB m.) = O(1) compared to her Stackelberg value.
Bob can use this asymmetry by acting as if his midpoint were (TT closer to mA than it really is. Lying (T times costs Bob only O(TT) regret, but costs Alice ((T))) regret. To avoid accumulating more regret than this, Bob can afterwards revert picking his truly preferred piece; the damage to Alice's payoff has already been done.
Let a E [0, 1). Suppose Bob plays strategy that ensures his regret is O(T)). Let T denote the set of all such Bob strategies. If Alice does not know she has strategy SA that ensures her Stackelberg regret is O
Proposition 3.
Tog
The exponent is sharp: SA guarantees Alice Stackelberg regret ((T against all Bob strategies in 8 for some B E [0, 1), then SA has Stackelberg regret Q(T)) for some Bob strategy in B
Proof sketch. Alice's strategy that achieves O (/T//oo// log T') regret follows the same template as her strategy from Proposition 2. The only difference is that she sets v differently (and much larger) to cover any possible regret bound Bob could have.
The idea of the lower bound is that, if Alice does not know the value of a in Bob's 's regret bound, she cannot know when she has true information about Bob's preferences. We use this by having a Bob with ( regret behave exactly like one with ((T²) regret but different midpoint. Then Bob can hide his deception from an Alice with ( regret since he can tolerate more regret than her. O
Theorem 1 is implied by Propositions 2 and 3. The players' value densities must be bounded for Theorem to hold; see Remark 1 in Appendix A.2 for counterexample with unbounded densities.

---

5
Equitable payoffs
Here we sketch the proofs of Theorems 2 and 3. The formal proofs can be found in Appendix B. Theorem 2 shows how Alice can get at least 1/2 per round while keeping Bob at 1/2 per round.
Proof sketch of Theorem 2. Alice's strategy uses Blackwell approachability (1956). A challenge is that Blackwell's original version required the number of player types to be finite, but Alice has to be prepared for an uncountably infinite variety of Bob's valuation functions. Another difference is that Alice's ' action space is also infinite, which turns out to be necessary.
We get around the mafinit--Bob issue in two steps. First, Alice defines countably infinite set V as stand-in for the full variety of Bobs; V includes arbitrarily good approximations to any valuation.
Second, we replace Blackwell's original mmite-dimensional space with a countably-infinite dimensional one, where the elements of V are the axes. We define inner product on this space and adapt Blackwell's argument for it. Briefly, Alice's ' strategy tracks the average payoff to each type of Bob in V and defines S to be the region the space where all of them have payoffs at most 1/2. In each round, she constructs cut point which moves the Bobs' average payoff closer to S, and in the limit traps them in S.
Under this strategy, Alice's payoff guarantee is mostly a byproduct of Bob's. If Bob and Alice have the same value density, then their payoffs sum to 1, so bounding Bob's payoff to 1/2 also bounds Alice's s to 1/2. We achieve the substantially better bound on Alice's payoff by explicitly including her value density U in the set V of Bobs, thus eliminating any approximation error.
Theorem shows how Bob can do the same, albeit only in expectation in the simultaneous setting.
Proof sketch of Theorem 3. We cover the simultaneous setting first because it informs the sequential setting. In the simultaneous setting, Bob's algorithm extremely simple: in each round, randomly select I or R with equal probability. The expected payoffs to each player follow immediately.
Bob's strategy for the sequential setting can be seen as a derandomized version of the simultancous strategy. The simplest way to derandomize it would be to strictly alternate between L and R. but if Bob runs that strategy Alice can easily exploit it. Instead, Bob mentally partitions the cake into vT intervals , .TT of equal value him. He then treats each interval I₁ as a separate cake, alternating between L and R for the rounds Alice cuts in 4, Alice can still exploit this strategy on single interval 4, but doing so can only give her an average payoff of 1/2 + O(Va(L)) 1/2 + O(1/VT). The full proof shows this bound applies for any Alice strategy.
6 Fictitious play
In this section we include a proof sketch of Theorem 4, which analyzes the fictitious play dynamic. The formal proof can be found in Appendix C.
Proof sketch of Theorem 4. To analyze the fictitious play dynamic, we define for each = O.... ., T two quantities called a and 8. Let = l,, where ra is the number of times Bob picked R up to round / and l, is the number of times he picked L. Let 3, = (2V (20 ar)) 1).
The quantities a and 3. control what happens under fictitious play: Alice's 's decision in round ++1 1 is based on Oe and Bob's decision in round / + is based on 3r. These decisions in turn affect a++1 and Be+1. forming a dynamical system that results in a counterclockwise spiral through a-B space. Figure 6 illustrates the sequences and 3e for the instance in Figure 2.
We define Pt |a,l + | and formalize this spiral, by showing that the sequence {p) is non-decreasing and analyzing the change in (as, 3.) from round to round. Figure 6 illustrates the parameter P over time, while Figure 7 illustrates the spiral (associated with the same trajectory in Figure and 6), where the spiral is visualized as a scatter plot of the sequence (a,, 8t)
We first use these dynamics to bound Bob's payoff. Bob's payoff can be almost directly read off due to changes in B, closely matching changes Bob's payoff. Bob's total payoff to round turns out to be of the order t/ + Pt. so bounding the rate at which the spiral expands also bounds Bob's payoff.

---

50
-50
-75
-75
1000
1500
2000
2500
3000
4000
1000
1500
2000
2500
2000
3500
(a) The sequence Oic-
(b) The sequence Bx.
2000 2500
3000
3500
4200
(c) The sequence Pa.
Figure 6: Illustration of the sequences [a)) (.0 and {pete for the instance with trajecto- ries shown in Figure 2. The X axis shows the round number t and the Y axis the variable plotted.
10
20
0-
-5-
-20
-10
-10
-10
(a) The spiral over the first 100 rounds.
(b) The spiral over the first 1000 rounds.
Figure Scatter plot of the sequence (0),8))121 illustrating the spiral for the instance with trajectories shown in Figure 2, where the sequences and 3, are illustrated separately in Figure 6.
We then use the dynamics to bound the total payoff to Alice and Bob. Alice can only cut in the interior of the cake when a₁ players' total payoff when Alice cuts at one end of the cake is 1, so across 7' rounds we show the sum of cumulative payoffs of the players is of the order T @(VT). Combining the bound on the total payoff with the bound on Bob's payoff gives bound for Alice's 's payoff.
which happens less and less often the spiral expands. The
7 Concluding remarks
There are several directions for future work. One direction is to consider wider class of regret benchmarks and understand how the choice of benchmark influences the outcomes reached. Moreover, what payoff profiles are attained when the players use randomized algorithms such as exponential weights update their strategies? would also make sense to consider settings where the cake has both good and bad parts. Finally, studying richer feedback models, e.g., when Alice and Bob takes turns cutting and choosing, or allowing Alice to divide the cake into any multiple measurable sets would be intriguing directions.
10

---

Acknowledgements
We would like thank the reviewers for useful feedback that helped improve the paper. This work was supported by US National Science Foundation CAREER grant CCF-2238372, DARPA QuICC, NSF AF:Small #2218678, NSF AF:Small #21 14269, Army-Research Laboratory (ARL) #N911NF2410052, and MURI on Algorithms, Learning and Game Theory.
References
Jacob Abemethy, Kevin A. Lai, and Andre Wibisono. 2021. Fast Convergence of Fictitious Play for Diagonal Payoff Matrices. 1387-1404. https: /0tp://////o.////.//.////// http///1.111/1.99111111 1187711.99881111977444..
N. Alon. 1987. Splitting necklaces. Advances in Mathematics 63, (1987), 247-253.
Noga Alon and Andrei Graur. 2020. Efficient Splitting of Measures and Necklaces.
https:
//doi.org/10 48550/550//00 ARXIV 2006. 16613
Georgios Amanatidis, Georgios Birmpas, Aris Filos-Ratsikan and Alexandros A. Voudouris. 2022. Fair Division of Indivisible Goods: Survey. In Proceedings of the Thirty-First International
Joint Conference on Artificial Intelligence, IJCAI 2022, Viemna, Austria, 23-29 July 2022, Luc De https: //doi. ceriiiorrg//100 10. 24923/119934AC 2022/756
Raedt (Ed.). ijcai.org, 5385-5393,
G. Amanatidis, G. Christodoulou, Fearnley, E. Markakis, C.-Alexandros Psomas, and Vakaliou. 2018. An Improved Envy-Free Cake Cutting Protocol for Four Agents. In Proceedings of the 11th International Symposium on Algorithmic Game Theory SAGT. 87-99.
Robert Aumann and Michael Maschler. 1995. Repeated Games with Incomplete Information. MIT Press.
Robert J Aumann. 1961. Mixed and behavior strategies in infinite extensive games. Princeton University Princeton.
H. Aziz and Mackenzie. 2016. A Discrete and Bounded Envy-Free Cake Cutting Protocol for Any Number of Agents. In FOCS. 416-427.
Maria-Florina Balcan, Avrim Blum, Nika Haghtalab, and Ariel D Procaccia. 2015. Commitment without regrets: Online learning in stackelberg security games. In Proceedings of the sixteenth ACM conference on economics and computation. 61-78.
Xiaohui Bei, Xinhang Lu, and Warut Suksompong. 2022. Truthful cake sharing. In Proceedings of the AAAI Conference Artificial Intelligence, Vol. 36. 4809-4817.
Gerdus Benadè, Daniel Halpern, and Alexandros Psomas. 2022. Dynamic fair division with partial information. Advances in neural information processing systems 35 (2022), 3703-3715.
U. Berger. 2005. Fictitious Play in 2xN Games. Journal of Economic Theory 120 (2005). 139-154.
Vittorio Bild, Ioannis Caragiannis, Michele Flammini, Ayumi Igarashi, Gianpiero Monaco, Dominik Peters, Cosimo Vinci, and William S. Zwicker. 2019. Almost Envy-Free Allocations with Con- nected Bundles. In 10th Innovations in Theoretical Computer Science Conference, ITCS 2019, January 10-12, 2019, San Diego, California, USA (LIPles, Vol. 124), Avrim Blum (Ed.). Schloss https: / /doii org/10.....ooooo.ooooo..oo... 4230/LIPICs.
Dagstuhl Leibniz-Zentrum Zentrum für Informatik, 14:1-14:21.
ITCS. 2019.019111 14
Georgios Birmpas, Jiarui Gan, Alexandros Hollender, Francisco Marmolejo, Ninad Rajgopal, and Alexandros Voudouris. 2020. Optimally deceiving a learning leader in stackelberg games. Advances in Neural Information Processing Systems 33 (2020), 20624-20635.
David Blackwell. 1956. An analog of the minimax theorem for vector payoffs. Pacific J. Math. 6, 1 (1956), 8.
Brams and Taylor. 1996. Fair Division: from cake cutting to dispute resolution. Cambridge University Press.

---

F. Brandt, V. Conitzer, U. Endriss, J. Lang, and A. D. Procaccia (Eds.). 2016. Handbook of Computa- tional Social Choice (1 ed.). Cambridge University Press.
Felix Brandt, Felix Fischer, and Paul Harrenstein. 2013. On the rate of convergence of fictitious play. Theory of Computing Systems 53 (2013), 41-52.
Simina Brânzei, Joannis Caragiannis, David Kurokawa, and Ariel D. Procaccia. 2016. An Algorithmic Framework for Strategic Fair Division. In Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, February 12-17, 2016, Phoenix, Arizona, USA, Dale Schuurmans and Michael P. Wellman (Eds.). AAAI Press, 418-424. http://wwer aaai org/ wwtg///c/idddxx.c//////e//o// php/ AAAI/ AAAL/AAAA1/// wwtp///pee///aeeee banperrviiww/ie 112944
Simina Brânzei and Peter Bro Miltersen. 2013. Equilibrium analysis in cake cutting.. AAMAS. Citeseer, 327-334.
S. Branzei and P. B. Miltersen. 2015. A Dictatorship Theorem for Cake Cutting. In IJCAI. 482-488.
Simina Brânzei and Noam Nisan. 2019. Communication Complexity of Cake Cutting. In Proceedings of the 2019 ACM Conference on Economics and Computation (EC). 525.
Simina Brânzei and Noam Nisan. 2022. The Query Complexity of Cake Cutting. In NeurIPS. 37905-37919. http: //ppperspppprs.... nips cc wc/paper_ftateeeeeeeeeeeeeeeeeee fiw.f/illppppe wwtp//pppppe////a//eeeeee Abstract
-tttraartttttttt-t-ttat--------e Conference html
G.W. Brown. 1951. Iterative Solutions of Games by Fictitious Play. Activity Analysis of Production and Allocation (1951).
Xiaolin Bu, Jiaxin Song, and Biaoshuai Tao. 2023. On existence of truthful fair cake cutting mech- anisms. Artificial Intelligence 319 (2023), 103904. 2023. 103904
wtt........../////.............t artint.
Bhaskar Ray Chaudhury, Jugal Garg, Peter McGlaughlin, and Ruta Mehta. 2021a. Competitive allocation of a mixed manna. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 1405-1424.
Bhaskar Ray Chaudhury, Jugal Garg, and Kurt Mehlhorn. 2020. EFX exists for three agents. In Proceedings of the 21st ACM Conference on Economics and Computation. 1-19.
Bhaskar Ray Chaudhury, Jugal Garg, Kurt Mehlhorn, Ruta Mehta, and Pranabendu Misra. 2021b. Improving EFX guarantees through rainbow cycle number. In Proceedings of the 22nd ACM Conference on Economics and Computation. 3 310-311.
Bhaskar Ray Chaudhury, Telikepalli Kavitha, Kurt Mehlhorn, and Alkminí Sgouritsa. 2021c. A Little Charity Guarantees Almost Envy-Freeness. SIAM J. Comput. 50, 4 (2021), 1336-1358. https://doi. org/10. 10. 1137 11137220M /20M135913
Yiling Chen, John K. Lai, David C. Parkes, and Ariel D. Procaccia. 2013. Truth, justice, and cake cutting. Games and Economic Behavior 77, (2013), 284-297. https: / httpe////cpPaaaerreeeeee reper.
org/RePEc:esse :::ebe:v:77::3::: 201:::::::011::::11 ::::::22::::9299 284-297
Guillaume Cheze. 2020. Envy-free cake cutting: A polynomial number of queries with high probability.
Constantinos Daskalakis and Qinxuan Pan. 2014. A Counter-example to Karlin's Strong Conjecture for Fictitious Play. In 2014 IEEE 55th Annual Symposium Foundations of Computer Science. 11-20. https://doi. wtt.:ii.rgg....0 1109//0O..00/FCCS 2014.10 10
Argyrios Deligkas, Aris Filos-Ratsikass and Alexandros Hollender. 2021. Two's Company, Three's Crowd: Hansensus-Halving for Constant Number of Agents. In EC '21: The 22nd ACM Conference on Economics and Computation, Budapest, Hungary, July 18-23, 2021, Péter Biró, Shuchi Chawla, and Federico Echenique (Eds.). ACM, 347-368. attps://doi. aefoi.org//i org/10. 0045/ 3465456. 3467625
X. Deng, Q. Qi, and A. Saberi. 2012. Algorithmic Solutions for Envy-Free Cake Cutting. Oper. Res 60, 6 (2012), 1461-1476.
12

---

Yuan Deng, Jon Schneider, and Balasubramanian Sivan. 2019. Strategizing against no-regret learners. Advances in neural information processing systems 32 (2019).
Jinshuo Dong, Aaron Roth, Zachary Schutzman, Bo Waggoner, and Zhiwei Steven Wu. 2018. Strategic classification from revealed preferences. In Proceedings of the 2018 ACM Conference on Economics and Computation. 55-70.
Melvin Dresher. Lloyd S Shapley, and Albert William Tucker. 2016. Advances in Game Theory(AM- 52), Volume 52. Vol. 52. Princeton University Press.
L. E. Dubins and E. H. Spanier. 1961. How to Cut A Cake Fairly. Am. Math. Mon 68, (1961), 1-17.
Edmonds and K. Pruhs. 2006. Cake Cutting Really Is Not a Piece of Cake. In SODA. 271-278.
Francis Edward Su. 1999. Rental harmony: Sperner' lemma in fair division. The American mathematical monthly 106, 10 (1999), 930-942.
S. Even and A. Paz. 1984. A note on cake cutting. Discrete Applied Mathematics 7,3 (1984), 285 296.
Aris Filos-Ratsikan Kristoffer Arnsfelt Hansen, Kasper Hogh, and Alexandros Hollender, 2022. mex-eeembrshhi via Convex Optimization: Games, Cakes, and Markets. In 202/ IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), 827-838. https://doi. org/
10. 1e-11199FOCS5297 2021. 00085
Aris
Alexandros Hollender, Katerina Sotiraki, and Manolis Zampetakis. 2020. Honsensus-Halving Does It Ever Get Easier?. In Proceedings of the 21st ACM Conference on Economics and Computation (Virtual Event, Hungary) (EC '20). Association for Computing Machinery, New York, NY, USA, 381-399. https://dof org/ /t///.0.14444 00111///399400 3399527
Aris Filos-Ratsikas, Alexandros Hollender, Katerina Sotiraki, and Manolis Zampetakis. 2021. A topological characterization of modulo-p arguments and implications for necklace splitting. In Proceedings of the 202/ ACM-SIAM Symposium Discrete Algorithmss (SODA). SIAM, 2615- 2634.
Eric Friedman, mal disruptions. In Proceedings of the sixteenth ACM conference on Economics and Computation. 697-713.
Psomas, and Shai Vardi. 2015. Dynamic fair division with mini-
Jiarui Gan, Haifeng Xu, Qingyu Guo, Long 2019. Imitative follower deception in stackelberg games. In Proceedings of the 2019 ACM Conference on Economics and Computation. 639-657.
Zinovi Rabinovich, and Michael Wooldridge.
Ali Ghodsi, Matei Zaharia, Benjamin Hindman, Andy Konwinski, Scott Shenker, and Ion Stoica. 2011. Dominant resource faimess:: Fair allocation of multiple resource types. In 8th USENIX symposium on networked systems design and implementation (NSDI 11).
Paul Goldberg, Alexandros Hollender, and Warut Suksompong. 2020a. Contiguous Cake Cutting: Hardness Results and Approximation Algorithms. J. Artif. Intell. Res. 69 (2020), 109-141.
https: org/100./// 10. 1011//61aaai 1.......22200 12222
Paul W. Goldberg, Alexandros Hollender, Ayumi Igarashi, Pasin Manurangsi, and Warut Suksompong. 2020b. Consensus Halving for Sets of Items. In Web and Internet Economics 16th International Conference, WINE 2020, Beijing, China, December 7-11, 2020, Proceedings (Lecture Notes in Computer Science, Vol. 12495), Xujin Chen, Nikolai Gravin, Martin Hoefer, and Ruta Mehta (Eds.). Springer, 384-397
3-03---990----------- https http://oi..oo////////// 100 1007 /977-/7783333 0300000--600 64946-3.4955 3_27
Paul W. Goldberg and Ioana Iaru. 2021. Equivalence of Models of Cake-Cutting Protocols. https:
//doi. //doi.org/11 /0. 48550/ARXC 2108 03641
2108.00641
Goldman and A. D. Procaccia. 2014. Spliddit: Unleashing fair division algorithms. ACM SIG.
Exch 13, 2 (2014), 41-46.
13

---

Nika Haghtalab, Thodoris Lykouris, Sloan Nietert, and Alexander Wei. 2022. Learning in stackelberg games with non-myopic agents. In Proceedings of the 23rd ACM Conference on Economics and Computation. 917-918.
MohammadTaghi Hajiaghayi. Mohammad Mahdavi, Keivan Rezaci, and Suho Shin. 2023. Regret Analysis of Repeated Delegated Choice. arXiv preprint arXiv:2310.0488. (2023).
Christopher Harris. 1998. On the Rate of Convergence of Continuous-Timee Fictitious Play. Games and Economic Behavior 22, (1998), 238-259. attpss///oi..
1006 www.//ame...////..o 1997. 0582
Kirthevasan Kandasamy, Gur-Eyal Sela, Joseph E Gonzalez, Michael Jordan, and lon Stoica. 2020. Online Learning Demands in Max-min Fairness. arXiv:2012.08648 [stat.ML]
Samuel Karlin. 1959. Mathematical Methods and Theoryin Games, Programming, and Economics. Addison Wesley.
Ian Kash, Ariel D Procaccia, and Nisarg Shah. 2014. No agent left behind: Dynamic fair division of multiple resources. Journal of Artificial Intelligence Research 51 (2014), 579-603.
Robert Kleinberg and Tom Leighton. 2003. The value of knowing demand curve: Bounds on regret for online costed-price auctions. In 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings. IEEE, 594-605.
Harold W Kuhn. 1950. Extensive games. Proceedings of the National Academy of Sciences 36, 10 (1950), 570-576.
HW Kuhn?. 1953. Extensive games and the problem of information. Contributions to the Theory of Games 24 (1953), 193.
Rucha Kulkarni, Ruta Mchta, and Setarch Taki. 2021. Indivisible mixed manna: On the computability of MMS+ PO allocations. In Proceedings of the 22nd ACM Conference Econonics and Computation. 683-684.
Pasin Manurangsi and Warut Suksompong, 2021. Closing Gaps in Asymptotic Fair Division. SIAM Journal on Discrete Mathematics 35, 2 (2021), 668-706. https://doi.orgg// 113370.11//// 1137/
20M1353381 ar xrXivhhttp::/doi.orr//..11 13722
D. Monderer and L.S. Shapley. 1996a. Fictitious Play Property for Games with Identical Interests.
Journal of Economic Theorr 68 (1996), 258-2688 355-.65.
D. Monderer and L.S. Shapley. 1996b. Potential Games. Games and Economic Behavior 14 (1996). 124-143,
Elchanan Mossel and Omer Tamuz. 2010. Truthful Fair Division. In Algorithmic Game Theory, Spyros Kontogiannis. Elias Koutsoupias, and Paul G. Spirakis (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 288-299.
H. Moulin. 2003. Fair Division and Collective Welfare. The MIT Press.
J. Nachbar. 1990. Evolutionary Selection Dynamics in Games: Convergence and Limit Properties. International Journal of Game Theory 19 (1990), 59-89.
Antonio Nicolò and Yan Yu. 2008. Strategic divide and choose. Games and Economic Behavior 64, (2008), 268-289. https://dois org/ wt.g//0..11011 1016/ geb. 2008. 01.006
Hoon Oh, Ariel D. Procaccia, and Warut Suksompong. 2021. Fairly Allocating Many Goods https:
with Few Queries. SIAM Journal on Discrete Mathematics 35, 2 (2021), 788-813.
arXivihttps:/doioog//..... 1111:////1111113///0111113444
Ioannis Panageas, Nikolas Patris, Stratis Skoulakis, and Volkan Cevher. 2023. Exponential Lower Bounds for Fictitious Play Potential Games. arXiv:2310.02387 [cs.GT]
S. Perkins and D.S. Leslie. 2014. Stochastic fictitious play with continuous action sets. Journal of Economic Theory 152 (2014), 179-213, https://dois org/10 10. 10166/ jet. 2014. 04.008
14

---

Benjamin Plaut and Tim Roughgarden. 2019. Communication Complexity of Discrete Fair Division. In Proceedings of the Thirtieth Annual ACM SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, Timothy M. Chan (Fd.). SIAM, 2014-2033. https://doot /doii wwg/oo////// 10. 1137 978111197541112 111.1/1.111//.9988111177999999
Benjamin Plaut and Tim Roughgarden. 2020. Almost envy-freeness with general valuations. SIAM Journal on Discrete Mathematics 34, 2 (2020), 1039-1068.
A. D. Procaccia. 2009. Thou Shalt Covet Thy Neighbor's Cake. In IJCAI, 239-244.
A. D. Procaccia. 2013. Cake Cutting: Not Just Child's Play. Commun. ACM 56, (2013), 87.
Ariel D. Procaccia. 2020. Technical perspective: An answer to fair division's 's most enigmatic question.
Commun. ACM 63, 4 (mar 2020), 118. https://doi. org/ 10 1 1011/113531111
Ariel D Procaccia and Junxing Wang. 2014. Fair enough: Guaranteeing approximate maximin shares.
In Proceedings of the fifteenth ACM conference on Economics and computation. 675-692.
J. M. Robertson and W. A. Webb. 1998. Cake Cutting Algorithms: Be Fair If You Can. A. K. Peters.
J. Robinson. 1951. An Iterative Method of Solving Game Annals of Mathematics 54 (1951), 296-301.
Erel Segal-Halevi. 2018. Cake-Cutting with Different Entitlements: How Many Cuts are Needed? CoRR abs/ 803.05470 (2018). arXiv:1803.cm 05470 http://axxiv.orggg org.absgg................... bargg//bs//ee /ttt/////...//// 05470
Heinrich von Stackelberg. 1934. Marktform und gleichgewicht. (No Title) (1934).
H. Steinhaus. 1948. The Problem of Fair Division. Econometrica 16 (1948), 101-104.
W. Stromquist. 1980. How to cut cake fairly. Am. Math. Mon 8 (1980), 640-644. Addendum, vol.
88, no. 8 (1981). 613-614.
W. Stromquist. 2008. Envy-frre cake divisions cannot found by finite protocols. Electron. J. Combin. 15 (2008).
Milind Tambe. 2011. Security and game theory: algorithms, deployed systems, lessons learned. Cambridge university press.
Omer Tamuz, Shai Vardi, and Juba Ziani. 2018. Non-Exploitable Protocols for Repeated Cake Cutting. In Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, (AAAI-18), the 30th innovative Applications of Artificial Intelligence (IAAI-18), and the 8th AAAI Symposium on Educational Advances in Artificial Intelligence (EAAI-18), New Orleans, Louisiana, USA, February 2-7, 2018, Sheila A. Mcllraith and Kilian Q Weinberger (Eds.). AAAI Press, 1226-1233. https: /doi. org/10. 10. 1609 AAAI, V32I1 11472
Pingzhong Tang and Tuomas Sandholm. 2012. Optimal Auctions for Spiteful Bidders. In Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence, July 22-26, 2012, Toronto, Ontario, Canada. Jörg Hoffmann and Bart Selman (Eds.). AAAI Press, 1457-1463. https://dob org/ 10. 1609 AAAI. V2611. 8235
Biaoshuai Tao. 2022. Existence of Truthful Fair Cake Cutting Mechanisms. Proceedings of the 23rd ACM Conference on Economics and Computation (Boulder, CO, USA) (EC '22). Association for Computing Machinery, New York, NY, USA, 404-434. nttps://doi.org: 1145/3490486. 3538321
Jamie Tucker-Foltz and Richard Zeckhauser. 2023. Playing Divide-and-Choose Given Uncertain Preferences. In Proceedings of the 24th ACM Conference on Economics and Computation (London, United Kingdom) (EC '23). Association for Computing Machinery, New York, NY, USA. 1127.
https://doi. org/ 10. 1145/3580507 .3978811
Toby Walsh. 2011. Online cake cutting. In Algorithmic Decision Theory: Second International Conference, ADT 2011, Piscataway, NJ, USA, October 26-28, 201 1. Proceedings Springer, 292-305.
15

---

Gerhard J Woeginger and Jiří Sgall. 2007. On the complexity of cake cutting. Discrete Optimization (2007), 213-220.
Geng Zhao, Banghua Zhu, Jiantao Jiao, and Michael Jordan. 2023. Online learning in stackelberg games with an omniscient follower. In International Conference Machine Learning. PMLR, 42304 42316.
16

---

A Appendix: Alice exploiting Bob
In this section we present the proofs for Proposition showing how Alice can exploit myopic Bob that chooses his favorite piece in each round, and for Theorem 1, where Bob is nearly myopic.
Before giving the proofs, formally define what mean for Alice Bob to ensure themselves certain amount of regret.
Definition 3 (Ensuring Alice's regret). Suppose Bob plays a strategy Sg. A mixed strategy SA for Alice ensures her Stackelberg regret at most Y against S3 if R S for all T-round histories H. that could have arisen under the stralegy pair (SA,
instead Alice only knows that Bob plays strategy from a of strategies, then mixed strategy for Alice ensures her Stackelberg regret is at most if ensures her Stackelberg regret is most Y against all SB E B.
Definition 4 (Ensuring Bob's regret). Suppose Alice plays a strategy SA- A mixed sirategy SB for Bob ensures his regret is most against S if Reg S for all T T-round histories H that could have arisen under the strategy pair SB).
In general, mixed strategy SB for Bob ensures his regret is at most y if ensures his regret is at most y against all Alice strategies.
A.1 Appendix: Exploiting a Myopic Bob
Restatement of Proposition If Bob plays myopically in the sequential setting, then Alice has strategy that ensures her Stackelberg regret is T).
Proof. We consider an explore-then-comii type of algorithm for Alice. In the exploration phase,
Alice does binary search to find Bob's midpoint (within accuracy of 1/T). In the commitment (exploitation) phase, Alice repeatedly cuts at Bob's s approximate midpoint. This leads to Alice getting nearly her Stackelberg value nearly every round. Figure 8 shows visualization of cake instance with Alice and Bob's 's midpoints, respectively, with Alice's 's search process.
Figure 8: Alice's algorithm against myopic Bob in the exploration phase. Alice's density is shown with blue and her midpoint is m.. while Bob's density is shown with red and his midpoint is my- The algorithm initialized & and rı 1 and then re-computes them iteratively depending on Bob's answers. The constructed interval [e,, ry] shrinks exponentially and becomes closer to ma as the time increases.
Alice's algorithm is described precisely in Figure 9,
17

---

Alice's algorithm when Bob is myopic:
Initialization
Set É = 0, r1 1 and In()).
Exploration
For & = 1,,,=....... .,
Cut at a point xt E re, such that V((( = Va((zt,r1)) Then observe Bob's action b,.
If b, L, then set (l(+1, (t+1) x4).
Else b, R. then set (441, Tz).
Exploitation
For = t + ,.
m. S l. then cut at & T/T.
m 2 rr, then cut at r, + 1/T.
Figure 9: Algorithm A.1
We show that Algorithm A.I in Figure with OIn T)) gives the desired regret bound in several steps.
Bob's ' midpoint lies in the interval [rt, 4 for all To this end, we first claim that Bob's midpoint lies in (4, r²] at each round f. We proceed by induction on The base case f clearly holds since l 0 and T1 1, m E ri]. Suppose that ma [Le, re] for some > 1. Given that Alice cuts at r, E (e.rrr). if b, = L. this implies that mg E [&,, wt). Hence mg E [e, = fee- 1 Tt+1] This argument also holds when Bob chooses R. Thus by induction, we conclude that my E Te for every E [T].
Alice's midpoint satisfies mA & (e,,T)) for every t 2 2 Now, during the execution of the algorithm, we will next show that Alice's midpoint m satisfies either of m. S le and m, 2 rt. i..,, mA & (4,, rx) for every f 2 2. To see this, recall that in the first round, Alice cuts b, L, then lg and r2 m A- In this case, 12,, r2] [0, m.). so m $ (2), Afterwards, still holds since the intervals only shrink, i.e., (l++1,7441) C (e), Similarly, consider the case
m.. If
that b, = R. Then, we have la = mA and r2 1. Thus [l2, r2] = [m, 1], which implies that mA $ r2). Again since the intervals (z) only shrink, we conclude that m (C,, for every t 2 2.
Interval exponentially shrinks We have V VA((,, ((((--1.r-11)) for every E [T]. as we shrink the interval by cutting a point that equalizes Alice's value for both parts within the interval. This implies that (a((e, r))) = 2 2-7+1
Bounding exploitation phase regret In the exploitation phase, due the observation above, have two cases: (i) A S E, and (ii) mA 2 ry. We will prove that in either case, Alice's 's single-round regret in the exploitation phase is at most 2
For the first case m S ly, Alice keeps cutting at e, 1/T for the rest of rounds as per the algorithm's 's description. Then, Bob will myopically choose R and Alice will obtain this case, we have that m S mp since mB [[,,ry] Then, Alice's
Va & - I-TT). single-round regret in the exploitation phase is bounded by
Va - Va & 1/T)) = VA(le, mBl) + VA(le, - 1/T,e-)
A
< VA(le, rr]) +
T
A
= 2 2
T
Otherwise suppose ma 2 r.. According to the algorithm, Alice keeps cutting r+ + 1/T for all the rest of the rounds, and Bob will respond with L. In this case we have mA 2 mg
18

---

since mB [.]. Similarly, Alice's single-round regret can be upper-bounde by
Va((BB. 1I) Va(r, + 1/T, 11) = Va([mB: r-)) + Va((r,, r, + 1/T))
A
- Va(le, rr)) + T
2 A
T
Hence in both cases, Alice's single-round regret in the exploitation phase is at most ~ + A/T.
--
Final regret bound Overall, by simply upper- boundin Alice's single-round regret in the explo- ration phase by 1, we obtain the following upper bound for the total regret:
(2 (2-
A
r+ (T
Plugging T = In()), we obtain the regret bound of O T), which completes the proof."
A.2 Appendix: Exploiting Nearly Myopic Bob
In this section we prove Theorem 1, which explains the payoffss achievable by Alice when Bob has strategy with sub-linear regret. We restate it here for reference.
Restatement of Theorem (Exploiting nearly myopic Bob). Let a [0, 1). Suppose Bob plays strategy that ensures his regret is O(T)). Let B denote the set of all such Bob strategies.
Alice knows a, she has a strategy SA SA(a) that ensures her Stackelberg regret is O ( log T). The exponent is sharp: Alice's 's Stackelberg regret is ((T for some Bob strategy in 1
If Alice does not know a, she has strategy SA that ensures her Stackelberg regret is O log The exponent is sharp: if S guarantees Alice Stackelberg regret O(T*) against all Bob strategies BD for some [0, 1), then SA has Stackelberg regret (2(T) for some Bob strategy in B
Proof of Theorem 1. The known-a upper bound of OT log T) follows from invoking Proposi- tion 4 with f(T) = T The (TT lower bound is Proposition 5,
The lower bound for the case where a is unknown follows from Lemma 3. The upper bound follows
from invoking Proposition 4 with f(T) = (log
T
Both upper bounds follow the same template, which is captured by the following proposition. Proposition 4. Suppose Bob's 's strategy has regret ((f(T)) for f(T) E of (Tog and f(T) 2 1. If
T
Alice knows f. then she has strategy that guarantees her Stackelberg regret is O(VT ( log T). In particular, if
* Bob's strategy has regret at most (T)) some > 0; and
large enough so that exp
Ar and S(T) < (n
then Alice's 's payoff satisfies:
5 (T(T))TInT.
T
+6)
2n
Before proving the proposition, we present the algorithm that Alice will run to beat a Bob with regret guarantee (()).))
We do optimize over
19

---

Alice's strategy when Bob's regret is at most - f(T",, for some constant 0:
Informational assumption: Alice needs know and T, but
Initialization Define
0; 1; = IV f(T) T] n == -- 1-1g ((TTTTTT
Exploration For i = 0, , n2 1:
Step 1: Set 04,0 2; and 02,6 = yi- For j E [5]. let ai, be the point with
Val an.)) Va (a v:l)
Step 2: For [5]:
Cut at a for 1) rounds. Define Ct2 L if the majority of Bob's answers were left when the cut point was ai,j and Ct, R otherwise.
Step 3:
(3.a): If e.j = L Vj E [5]. then set 2i+1 2i and yi+1 di,3-
(3.b): If c.j R Vj [5). then set T++1 01,3 and yi+1 Vi-
(3.c): Else, there exists unique &o E [4] such that Ci,j R for all j S k and
C.j = L for all > k. Set 21+1 = 0 and Vi+1 = 04,b+2.
Exploitation For the rest the rounds, Alice cuts at based on the following cases:
MA < Zn
1/n
MA
Vn
MA
MA
[Tny Vnl
Figure 10: Algorithm A.2
Proof of Proposition 4. Overall, Alice will use an explore-then-commit style of algorithm:
In the exploration phase, Alice conducts a variant of binary search to locate Bob's midpoint mB within an accuracy of O ((F(TT//Tlo) T).
In the exploitation phase, Alice cuts near the estimated midpoint for the rest of the rounds.
The main difficulty that Alice encounters is to precisely locate Bob's midpoint in the exploration phase, since Bob can fool Alice if she cuts sufficiently close his midpoint. We overcome this challenge by having Alice's algorithm stay far enough from my so that Bob is forced to answer truthfully most of the time.
Notation. Let In. Then n L-
Since f(T) (In by the
assumption in the proposition statement, we have w < and thereby n 2 0. Also recall the proposition statement assumes that Bob's 's strategy guarantees him regret of at most (IT) for some
> 0. Moreover, T was chosen such that T > exp (rrA).
Consider the Alice strategy described in Algorithm A.2 (Fig. 10). By Lemma the exploration phase in Alice's strategy is well-defined.
Next derive some useful observations and then combine them to upper-bound Alice's regret.
Useful observations. By Lemma 2, we have ma E [In, vn). Consider the cut point X in the exploitation phase. We write INTv[æ, y] to denote the interval [x, y] if y 2 and [y. x]] if > y.
20

---

Then, we obtain
(I (1 mBl) - VA [Tn: ynl)
(By definition of x)
2 n
(By property 2 of Lemma 2) (Plugging in n and using -[-x] S x +
- 2 (3w)+1
= 6v S(T) T lnT,
where the last identity in (1) holds by definition of w.
To upper-bound the number of times that Bob chooses the piece he likes less in the exploitation phase, we consider the following three cases with respect to X:
(a) If X Zn then mA < Zn. Thus 2n of O, so (B mBl) > FT)(TT/T by Lemma 2. Since Bob's regret is at most (T)), follows that Bob takes the wrong piece at most 1 LV((T) T times.
(b) If X = yh then mA > Thus # 1, so VB([mB, x)) > TV F(T//T by Lemma 2. Since Bob's regret is at most rf (T), it follows that Bob takes the wrong piece at most 2/2 VV((T) . times.
(c) X = MA. then there no wrong piece because Alice values both equally, Thus this case does not increase the count of incorrect decisions.
Putting it all together. In the exploration phase, Alice accumulates regret most n-5 since that is the length of the exploration phase. In the exploitation phase, the regret comes from two sources:
VF(T) T
The gap between X and mp, which is bounded in equation (1).
The rounds in the exploitation phase which Bob chooses his least favorite piece. There are at most 2 / /T) such rounds by cases (a-c). Thus Alice's cumulative regret due to these rounds is also at most (Vf(TT)2
Then Alice's overall regret is at most:
5 (/((T) T
T-6 T - V)(T)
In (
/(T) T
(Since [x] 2x Vo 2 1)
1n2 (112 +6) /J(T)-ThZ
(Plugging in and rearranging)
which is O (VF(T).TIn)) This completes the proof.
The following lemma shows that the exploration phase is well-defined.
Lemma 1. Alice's 'ss strategy from Algorithm A.2 (Fig. 10) has the following properties:
(i) If step (3.c) is executed in Alice 's exploration phase, then there is a unique index l E [4] such that Cz.j RVj S and 0z.j T. k.
(ii) For each j E [5), define ē., = L Bob prefers [0, dt,j] to (ar,s 1] and ē.,5 R otherwise. there exists j E [5] such that c., # Ci.j. then mg E (as,j-1. 01.j+1).
(iii) For all i E (O...., 1) and e
5}, we have Vi ([a (i.5+1)) > 2r 2r /FT)/T.
Proof. We prove each of the parts (i tii) required by the lemma.
21

---

Proof of part (di)..
Let E (o....,.5! 5}. Bob's valuation for the interval [at.j ai,++1 can be lower
bounded follows:
VB( (i,0,,)
ai.++1))
2 8. (1 - ai.))
(Since uB 2 8 Vi [0, 1) (Since (1(x)
2 Va (las.j. ar,sta))
4 [0, 1)
A
8 1
= A 6
Va yel)
(2)
By definition, Alice's strategy halves the cake interval considered with each iteration
i E {O..... 72 l.. that is: Va( (:]) = 1/2 (a( 91-1)). Thus VA (a((z,8))) 2 and 2 2 2- for all E nO....,m.. Combining these observations with inequality (2), we obtain
VB([ar,, Vi(laes.ai.tt1)) 2
2
12A
Let (f(T) In T. Then 1- loga (3w)J. We have
2
2- (og,((3))
(By definition of n)
12A
12A
> 2l08g(3u)
(Since - -[-x] 2 a)
12A
8
I(T)
4rA
>
(By definition of w and since 7 >> exp (#r²
4A
T
5
= =rvf DTT/TT
(4)
Combining inequalities (3) and (4), conclude that
f(T) T
VB(aa als+1l) > 27V
(5)
This concludes the proof of part (Hii).
Proof of parts (i) and (ii). For each ...... majority answers Cijy for j E [5], is different from Bob's truthful response.
will show that at most one of the
To be precise, recall from the lemma statement that رر E {L. R) is Bob's truthful response that maximizes his value when Alice cut at aj.j-
Define
S = {s E [5] Gi # C.)
Let INTV[Z, y] denote the interval [z, y] if y 2 x and [g) x) if > y. if E S,, it must the case that Bob picked the wrong piece at least (f(T) T rounds which the cut was a.j. Then Bob accumulated least Vn (INTV(mn, as.5)) regret in each such round. Let l [4]. We have
2 (((T) Σ VB(INTV(MB, og.5)) gr f(T) (Since Bob's total regret is at most r f(T)) jeS;
Vallosee
(By (5))
Dividing both sides by (f(T) gives:
Σ
(I andl) < a,,41l) AA E [4].
(7)
JES:
We show that |S,| < 1. Suppose towards a contradiction that |S, 1, meaning there exist indices
j, & S, with j + Then
INTV(ar, andel S (INTv http://ma./JUUNu/mmmo....
22

---

This implies that
VB (INTVVaaa, ax & VINNNNV/mB as5s) (L S
Σ
VB(INTV(mg. ar,l),
jES.
(8)
which contradicts (7). Thus the assumption was false and |S|] S 1.
For any j E S₁, we must have either mg E (at,-11, d(,) or mg E [at. ai.j+1), as otherwise (7) would be violated. Therefore, if Cr, # Cijj for some E [5], then mg E (Asg-11 01,+1). This is part (1i) required by the lemma.
Finally, we prove part (i). We will show there exists unique E [4] such that Ci.j = R Vjj I k and C.j L Vj k. The proof considers two cases:
Case [S;] = 0. Then every Cij truthfully reflects Bob's preferences: G.j = if as < m. and Cr T. if aij > mBi Cuy E (I,, RJ if a. m- An illustration can be seen in Figure I.. all cases, there a single switch from R to L, and so the index is unique.
R.R.L
R,R.R L,R.R R,I.R
4,R
4o.4
4g.5
00.1
0..2
0g.4
40.5
(a)
(b)
Figure 11: Illustration of Alice's initial cuts for i O. this example, she cuts 3 times at each of the points do,; and observes Bob's 's choices, which are marked with L/R near each such cut point. By default, Alice knows what the answer would if she cut at 1, so those are set to and T,, respectively. In Figure (a), the truthful answers (reflecting Bob's favorite piece according to his actual valuation) are marked with green, while the lying answers are marked with orange. The majority answer at each cut point 4o.j. denoted Co.j. is illustrated in Figure (b). In this example, the majority answer each cut point consistent with Bob's true preference.
Case |S|| =
1. Then all but one of the Grj's truthfully reflect Bob's preferences. An illustration can be seen in Figure 12.
R,R.I.
R.R.R LRR.R
LLL
L,R.
40.1
40.2
4g33
40.4
41.55
dg.11
dg.2
dg,3
0g.4
m1g
0g.5
(a)
(b)
Figure 12: Illustration of Alice's & initial cuts for i 0. In this example, she cuts 3 times at each of points do.; and observes Bob's choices, which are marked with L/R near each such cut point. By default, Alice knows what the answer would be if she cut at 0 or 1, those set to R and L, respectively. Figure (a), the truthful answers (reflecting Bob's favorite piece according to his actual valuation) marked with green, while the lying answers marked with orange. The majority answer at each cut point on denoted co is illustrated Figure (b). In this example, the majority answer each cut point is consistent with Bob's true preference except for point a0,4 where Bob lied every time and so the majority is incorrect as well.
By part (ii) of the lemma, the only exception occurs at index j with the property my E (az,j-1- 01.j+1). But then G, = č R for < j and Gie = GG,6 = for 8 82 + 1, regardless of o there will be single switch from R to L.
This concludes that the conditions for egg in Step 3.c hold if the conditions steps 3.a and 3.b do not. This concludes the proof of part (i).
23

---

The following lemma further reveals several properties of the constructed intervals during the execution of the algorithm.
Lemma In the exploration phase of Algorithm A.2 (Fig. 10), Alice constructs a sequence of intervals
(zo. Vol, [x1. v1l.
[Zn. Vnl
such that the following properties hold:
Property 1: zo = and yo =
Property 2: VA (a M++1]) = Va for O,....
Property 3: mB E [2s, vil. for all
Property 4: If rı + then (a(aa, > FTT/T.
Property 5: y + 1, then V vil) (T)/T
Proof. Property holds since (rro yo] = [0, 1] by definition of the algorithm.
Property 2 follows from our choice of 244 and 1/+1 always ensuring that [204-1, M6+1] contains 3 of the 6 intervals of equal value the or, divide [a.,, y/ into.
We will show Propertics 3-5 by induction. The base case is Then [ro, yol = [0, 1]. Properties 3-5 are vacuously true for this interval.
Assume that Properties 3-5 hold for {0, I....,, 1}. For each j E [5], c., represent Bob's truthful answer when the cut point is Oz,j- Formally, we have či.j = L if Bob prefers [0, وiان to [as.j 1] and را = otherwise.
We show Properties 3-5 also hold for + by considering the next three cases:
Case C., for all j. In this case, the majority of Bob's answers is L at each cut point used by Alice. An illustration can be seen in Figure 13.
H d1.55
H
40.1
40.2
da,3
40.5
40.1
4g.2
0o.3
0g.5
dg.5
(a)
(b)
Figure 13: Illustration of Alice's 's initial cuts for i 0. At each cut point do.j. the majority of Bob's answers L (i.e. Co.; = L). Then the algorithm recurses in the interval [0, dp.3).
Then the algorithm recurses in the interval [I;+1, 3/++ given by 4++1 = x; and M/+1 = 04,3- By Lemma 1, we have č.j C., for each of E (2, 4,5), as otherwise Bob's "true" preferences would alternate between R and L more than once.
We claim that mg [24, a,,2). To see this, consider two cases:
Case ē. C;,1: then my [1t, a1,1] since the majority answers consistent with Bob's true preference.
Case ē,,1 A C,,1 then mg E (æ;, ax22) by Lemma 1.
Then mB E [ra 0..2) C [Mi+1, 1e41), which proves Property 3 for + 1.
If 24+1 0. then Property 4 vacuously follows. Otherwise, we have Zi+1 24. Then by the inductive hypothesis we obtain Vi (1 mm)) Vn([,,, mn)) r Property 4 holds for i + well.
(rpp))>>(((TTT /J(TT) Thus
24

---

Since mg E [24, a4,2), we have
(B Vi+1l) 2 VB( 01,3)) > 2r S(T)/T,
and so Property 5 holds for +.
Case Cijj = R for all j. In this case, the majority of Bob's answers is It at each cut point used by Alice. An illustration can be seen in Figure 14.
R
R
8
R
0
do.1
do.2
0o,3
do.s
do.5
4g.1
de.2
0033
0o.4
0o.5
(a)
(b)
Figure 14: Illustration of Alice's 's initial cuts for i = O. At each cut point do.j. the majority of Bob's
answers is R (i.e. Co.j = Rt). Then the algorithm recurses in the interval [00.3. 1].
Then the algorithm recurses in the interval [2441, yi+1 given by #441 = 01,3 and 1/+1 y/- By Lemma we have (, Cig for each of j E (1,2,3,
We claim that my (ai,4, To see this, consider two cases:
Case e,,5 = 6,55 then ma E [05,5, wi] since the majority answers are consistent with Bob's true preference.
Case 0,, # 0g,5 then mg (ai,A, Mc) by Lemma 1.
Then ma E (01,4, Mi] C
which proves Property 3 for i + 1.
Since my E (as,1s Vel. we have
VB(F=,1mB)) 2 VB(aa,,, a;,4) 2r S(T)/T
and so Property 4 holds for 1.
If ys+1 1, then Property vacuously follows. Otherwise, we have Vi+1 = yi- Then by the inductive hypothesis we obtain Property 5 holds for 4 well.
Vn((mB, rTJ(()/T Thus
Case where there is transition from R to L and the last R is ci for some k {I...., 4). An illustration can seen Figure 15.
H 4o.
H
do.1
dg.2
0g33
dg.4
0g.1
0g2
4g3
0g
Ag.5
(a)
(b)
Figure 15; Iusstration of Alice's initial cuts for 0. In this example, there is a transition from R to the interval [ao.2, d0,3). Then the algorithm recurses in the interval [0o.1, a0,4]. which is guaranteed to contain Bob's midpoint.
In this case, Alice recurses the interval [1:+1; 1,4+1, given by
Ti+1 0 and 3/+1 0i,k+2
If any of the o.j differ from the ē.j. it must be CLe or G because otherwise Bob's true preferences would alternate between R and more than once, which impossible. We consider three sub-cases:
25

---

1. Case Ci,b # Cs.k- Each time Bob picked his less dess-preferred piece when Alice cut at ar, he lost 2V (InTIINV(aL, (a,,e, m in value compared to his regret benchmark. Since G.K # Cak. he did so at least f(T) times. order to have regret at most rT(),. he must have
f(T)
VB (IN S srV
(9)
T
By Lemma I, we have
mB (0,A-1,
(10)
and
f(T)
VB((ai,-11a > 2
(11)
T
Combining equations (9), (10), and (11) obtain
Ta( = VB m.B)
(Since 2i+1 = ai,k-1)
2 VB((a,,--,,0,
VB VINTVV[a mg])
(Since mn > 01,k-1 by (10)
/VT/TT)
(By 9 and (11))
Thus "a([z41,,BB)) > T TV ((T)/T, Property 4 holds for i + 1.
Since mB E 0i,k1), we have
VB([mB, M++1)) 2 VB Va((axxe, > 2r /
proving Property 5 for
Case G1 # C1,++1. Each time Bob picked his less- less-preferred piece when Alice at 01,++1, he lost (INTV Since 0j,k41 C2,++1, he did at least Vf(() T times. In order to have regret most rT)),, he must have
in value compared to his regret benchmark.
f(T)
[I S STV
(12)
By Lemma I, we have
mB (ai,k, gi,44)
(13)
and
f(T)
Va[(ai, ((x > 2rV Combining equations (12), (13), and (14) we obtain
(14)
Vn(mm, 91+1l) VB ([mB (1,++2))
(Since W6+1 01,442)
2 VB ([a,, (,0,,,1,,,,,,,00 ax)) - VB (INTv (Since mg < 04,k+2 by (13)
TTT/TT
(By (12) and (14))
Thus VB(IB, Mi+1l) FTT/T, so Property 5 holds for +
Since mg (ai,k, 01,442), we have
Vn([*41, mn)) 2 V > 2r //T)/T,
which proves Property 4 for
26

---

3. Case Ci, Ct.j for all [5]. Then mB E [0,, di,k+1] By Lemma 1, we have
VB( mp)) 2 (a a,,xl) = V 2r F(T//T (15)
and
VB((mB.u.) VB((a vil) VB ((a,,, (T)S(T) (16)
Inequality (15) implies Property 4 for + 1, while inequality (16) implies Property for +.
In all three cases, my E
= [1 Me+i]. showing Property for i 1.
Thus, in all three cases, Properties 3-5 hold for i+ By induction, they hold for all E {0. 1, ........... ,n). This completes the proof.
Proposition 5. Let be arbitrary Alice density and a E (0,1). Then there exists value density function ün (n(a and strategy Sn = (n(vA, a)) that ensures Bob's 's regret is O(Ta) while Alice's Stackelberg regret is Q (T
Proof. At a high level, the Bob we construct will behave as if his midpoint were at m T _ If Alice calls his bluff, i.e. cuts close mn "enough" times, then Bob reverts being honest by actually selecting his preferred piece.
Formally, let be arbitrary point such that y m.. Define the Bob value density üg as follows:
Va E [0, yl Vr (v, 1]
2v
(17)
2(1
Bob's value density üB is bounded since y is a fixed constant. Moreover, Bob's midpoint mg is exactly at y. Let SB be Bob's 's strategy as defined in Figure 16.
Bob strategy Šp:
Input: a.
Initialize = 0. For t E [T):
mg < 0: $ then play b, = L.
If0 0. < mB = then play b,
mf - T < dr < then:
If 2 T +1 then play b, = R; Else, play b, L.
Update c
Figure 16: Algorithm A.3
Strategy Ša ensures that Bob takes his less-favorinn piece most T 2 times, and this only happens when Alice cuts in the interval
P [m T mB
(18)
Since the density eB bounded from above by a constant, Bob gives up value of most 0+ in each such round. Thus Bob's regret is O(7").
Now let compute Alice's regret with respect to her Stackelberg value. Suppose that T' sufficiently large, so that mB - ad m.. There are two cases depending on whether Alice triggers the switch in Bob's 's strategy not.
27

---

Alice cuts in P at least T 4 Alice cuts at some point P. utility will be (1 1J) since Bob plays L. Therefore, her payoff in that round is maximized when is minimized, which occurs at the left-hand endpoint x mB T However,
times. Consider the first T times Alice cuts in P. Whenever
mB - MA:
and so
VA m (
T - .1)
1/22.
(19)
Then her Stackelberg regret over the rounds which she cuts P is at least
T T (Va(1o, mBl) Va [mB-TT 11)
> T (Va(1,, mal) Va Va mBl)
T 3 = Va((ma,mBl) (T*
Alice cuts in P fewer than T times. In this case, will show that Alice's payoff per round cannot be more than VA ((0, [0 T= )) To see this, we consider two sub-cases.
If Alice cuts point mg T T then Bob picks R and Alice's utility in that round
is
va((O,z)) VA ([o, mB T=
(20)
If Alice cuts at point x 2 mB _ then Bob picks and Alice's utility in that round
is
VA 1J) < < V. (0.mB - -T"=") =T"="))
(21)
Combining (20) and (21), obtain that in each round t [T]. Alice's utility is
a' VA (0. mg -
(22)
Summing over all rounds t [7]. we obtain that Alice's Stackelberg regret is
Σ t=1
Wna wna) 2
(V((O,, (B)) VA (l0.m - -- 1))
(23)
1=1
VA
mB -T mB
(24)
> Σ T E En (T
(25)
Thus in both cases, Alice's Stackelberg regret at least (T which concludes the proof.
Lemma 3. Let 0, [0, 1). Suppose Alice's density v and her strategy is SA There exists Bob Bod: (UB11, that depends va and Bob Bod, (VB,2, SB,2) that depends UA and S., such that
Boby has regret ((Ta) ) (L.e. strategy SB,1 ensures that a player with density UB,1 has regret O(T)))
Boby has regret O(T²); and
28

---

if SA ensures Alice Stackelberg regret of O against Bob1. then SA has regret at least T 16 against Bob2.
Proof. Let x be the cake position such that VA (1, = 2/3, and let y be the cake position such that (10 v)) 5/6. The first Bob, Bob1, will have valuation function UB that has midpoint æ. We define Bob 's strategy SR so that it truthfully picks his preferred piece, i.e.
fL R
if a (x, 1] if a, [0,
S SB,1 ( =
(26)
Against Bobi, Alice's Stackelberg value is 2/3. Suppose SΛ ensures Alice Stackelberg regret at most rT against Bob, for some r > 0.
Then we define our second Bob, denoted Boby, having a valuation function UB,2 which has midpoint y. Let k(I) be the number of times Alice cuts in the interval (x, in rounds {1,...,(}. Then
Boby's 's strategy will be defined as follows:
S S B1-1)
ift S 3r
SB,
L
if i(t) > 3r and at (y. 1] if k(t) > 3r and a, E [0, 00.l.
(27)
R
Intuitively, SB,2 switches to being honest after Alice cuts in (I,, y] sufficiently many times. This transition gives Bob, regret guarantee of O(T9).
When Alice plays SA against Bob1. her total payoff
u. UA 2 rr
(28)
However, every round she cuts in (ar y). her payoff is less than 1/3. Therefore, against Bob,, her total payoff can also be bounded by
uA ( SB,1) S 2T/3 k(T)/3.
(29)
Combining inequalities (28) and (29), we obtain
k(T) < 3
(30)
By definition, strategy SB,2 behaves the same as strategy SB.1 when k(T) s 3rT By (30), we have k(T) S 3rT' when Alice uses strategy S Thus, if Alice uses strategy S then Bob; and Boby behave exactly the same way. Therefore, Alice receives more than 2/3 per round against Bob2, so her regret at least T/6 E Q(T).
Bob's density not lower bounded by any constant, then Theorem fails as shown in the next remark.
Remark 1. Let E (0, 1). There exist value densities VA and un, where va(x) (6, A] Vx E [0, 1] and un(r) E (0, A] Vx E [0, 1] such that Bob has strategy Sp, which guarantees his regret is at most T and Alice's Stuckelberg regret is at least Q(T/ log T), no maller what strategy she uses.
Proof. The specific valuations will be defined in terms of cumulative valuations. Let Alice's valuation be:
x 3
if I E [0, 1/2] if E (1/2,1]
VA (A æ))
x
Let Bob's valuation be:
x E [0, 1/2]
VB (10, x))
(31)
+ T if x (1/2,1]
Intuitively, Alice has well-behaved piecewise uniform density with midpoint m. 2/3. Bob's density is well-hehaved for S 1/2, but the density rapidly approaches zero just to the right of = 1/2.
29

---

Fix an arbitrary a (0, 1). There exists a point on the cake such that (B((1/2. = -T--1 Define Bob's strategy SB as follows:
At. B {
R
a < L a, y
This strategy would be honest if Bob's midpoint were y rather than 1/2. That means it only differs from his preferred piece when az E (1/2, - The worst outcome for Bob occurs when dt = y- But by construction, picking his preferred piece. Since there are T rounds, his overall regret at most 7o
in round where Alice cuts y. Bob only loses 7 utility compared to
Alice, the other hand, cannot do very well compared to her Stackelberg value. Her Stackelberg value is 3/4 4, achieved by cutting at Bob's midpoint of 1/2 and receiving her preferred piece. But Bob prevents this payoff by pretending his midpoint is at To obtain the exact location of y, note that
(B((122 = 2 Tm-1
Plugging (31), this is equivalent
2 2--1 T
2
Solving for y, we have
y
+
2 (2 20x) loga T +
For sufficiently large 7', we have y E (mg, mA). Alice's best cut location in each round is then at y itself, which gives her a per-round payoff of
3
VA (ly, 1]) 4
(4 4a log, T + 4
Adding this up over all T rounds gives total regret of at least, obtain
3T
4a) log T 4'
which is Q(T/ log T as required. This completes the proof.
30

---

B Appendix: Equitable payoffs
This appendix has two parts. In Appendix B.I, we prove Theorem 2, which shows that Alice can enforce equitable payoffs. In Appendix B.2, we prove Theorem 3, which shows that Bob can enforce equitable payofi's.
B.1 Appendix: Alice enforcing equitable payofts
In this section we prove Theorem 2, the statement of which is included next.
Restatement of Theorem 2 (Alice enforcing equitable payoff's; formal). In both the sequential and simultaneous settings, Alice has a pure strategy S such that for every Bob strategy Sg:
every trajectory of play, Alice's average payoff is al least 1/2 o(1), while Bob's 's average payoff is al most 1/2 + o(1). More precisely, for all (3,...,T) T}:
uB(1,t)
1
5
+1
(32)
2
(215/5)
(1,
1
4
(33)
2
I
recalling that is the upper bound on the players' value densities.
Moreover, even if Bob's 's value density is unbounded, his averuge puyoff will still converge to 1/2.
The proof of the theorem is deferred until additional definitions have been stated and helpful lemmas have been proved. We first define some notations.
Definition (Set of valuations W.). For each n E N", we define the following set of non-decreasing piecewise linear functions with n pieces:
Wn { f [0, 1] + [0.1]] f is non non-decreasing with f(0) = 0, f(1) 1,f(i/m)) n Ezu, and
f(x) f(x)= = (;] ((, ) +0= 1++1 (1))
i 1
Vi no...., 1 E n
Definition 6 (Set of functions Vn). For each Nº, recall W2, given in Definition 5 and define Vn as the following set of functions:
W. V W2
#2
i = 2, where fa [o, + [0,1] the function fa(x) = (a((
Definition 7 (The set V). Let V U (n, v): e.E. where Vn is given by Definition 6. every Remark By construction, for each n E N*, every function f E Vn is non-decreasing.
For each E N Wn contains the nondecreasing piecewise linear functions through grid with spacing 1/n. For large n, then, Wr, should contain approximations to any given function accurate to roughly ((1/n).
If Alice bases her strategy on limiting the payoff of the Bobs in each WR, then she will limit Bob's payoff but not necessarily guarantee herself very good payoff. The inclusion of Alice's valuation function in rectifies this, allowing us to show a much tighter bound on Alice's payoff.
To formalize the ability of the elements of the Vn to approximate arbitrary valuation functions, prove the following three lemmas. The first of them (Lemma 4) is somewhat technical, but most directly shows the richness of the V.. It will be used to prove Lemmas 5 and 6, which will be used directly to bound the payoff an unbounded density and bounded -ensity Bob, respectively.
[0, 1] be continuous and increasing with f(0) 0 and f(1) 1. Suppose there exist n. E N and E (0, 0o) such that
Lemma Let f [0, 1] +
[x()) f(v)) S
Vx, y E [0, 1] with |x $ 1/n.
(34)
Then there exists V, E V., where V,, is the set of functions from Definition 6, such that [f(x) Vz)( & E + 2/n Vx [0, 1].
31

---

Proof. For E R, let [x]] denote the nearest integer to breaking ties in favor of [x]] [ + 1/2.
when
Recall the set of functions W, from Definition Let Vn be the function in Wn such that:
Va(i/n) n f(i/n)]
Vi [n-1).
(35)
7
Then we claim the function V, approximates well the function f at the points i/n, that is:
Vi((in) - ((i/n)) = n f(i/n)] f(i/n) S 2n
E ( nn.
(36)
where
for E [n - 1] the inequality in (36) follows from (35);
for = follows from (0) = 0 = f(0), and
for = n follows from (1)
f(1).
Let x E [0, 1]. We show three inequalities next:
1. By inequality (34) from the lemma statement with parameters [an]/n and [an]/n /nn we get
[nn]]
[nn
S E.
(37)
n
n
2. By inequality (36) with i [an] ]. have
[on]]
1
V
(38)
n
2m
3. By inequality (36) with
[an]]. have
[mn]
[on
1
Vn
(39)
m
2n
Summing up inequalities (37), (38), (39) and applying the triangle inequality, obtain
[mm]]
[nn]]
1 n
Vn
Vn
(40)
We obtain
[nn]
[mn]]
V
(By (36) with i [.m] )
2n
n
< f(r)
(Since f is non-decreasing)
[x7]]]
< f
(Since f is non-decreasing)
[2rv]]
< Vn
(By (36) with i == [am)] )
2n
Denoting
22 Vn ( function V, is non-decreasing by Remark 2, we have
n 1/(2n), Vn
[xn]]
n + 1/(2n) we conclude that f(x) E Since the
[mn]
1
1
[20]]]
V,
Vn (z)
< Vv(())
< V.(x
+
I V,
(41)
2n
2n
2n
2n
32

---

Thus (1((z) E J. Since both f()) E J and (x) E J, we can bound If(x) - (z)) as follows:
[f(x) Vx(]l |J|
[
V
+
V
n
2m
S E +
(Since
Vn
Vx
2070
S 3 + 1/n by (40))
Since this holds for all x E [0, 1]. the function Vn required by the lemma exists.
Lemma 5. Let f: [0, 1] - 10 be continuous and increasing with f(O) 0 and f(1) For
each & > O, there exists E N" and a function V,, E Vn such that
[Vn(x) - f(x) S E Vxr [0, 1],
(42)
recalling that the set of functions V is given by Definition
Proof. Let c > 0. Since f is continuous and increasing, its inverse f is also continuous and increasing. Since f(0) 0 and f11 1, we have f (0) and (1) 1. Consider
function g [0, - e/4] + [0. 1] defined as
g(z)= - (=)=))))))
(43)
Since f- is continuous and bounded over closed interval, so is the function g. Therefore, by the extreme value theorem, y attains global minimum value 8" Since f-1 is strictly increasing, is never 7ero, so
8 > 0.
(44)
Since we will analyze g(f(x)), it will be useful to define the set of values x for which (x())) is well defined, that is:
S. = fx E [0. 1] f(x) E [0, - -/4]}
(45)
Since 8* is a global minimum of g. we have
g(f(x)) 2 8*
Vo E Sz.
(46)
Using the definition of (equation (43)) in (46) yields
s(f(x)) = f-1 (f(x) e/4) (f()) 8
Vr E Se.
(47)
Since (-)((())) = x, inequality (47) yields / (/(x) + e/4) - 2 8", or equivalently,
/ (f(x) + e/4) 2 x 8*
Vr E Sz.
(48)
Applying f to both sides of (48) and using monotonicity of f. we obtain f(x) + e/4 2 f(x for all x E S,, or equivalently
+
I (x+ - f(x) s//4 Vr S,
(49)
Since E > 0 and 8" > 0 by (44), there exists n E N such that
1/8* and 4/e.
(50)
Note that because the range of f-1 is [0, 1]. the left side of (48) at most 1. Therefore, from (48)
and the fact that 8* > 1/n by (50):
12 x + 1/n
Va E S.
(51)
Consider an arbitrary 2, E [0, 1] with x S y S x + 1/n. We consider two cases:
Case x E Sg: Since f is strictly increasing and + 5* < 1 by (51), have: f(y) < fx + 1/n) + Subtracting f(x) from both sides of (52) and applying (49), we obtain
(52)
f(0) f(x < e/4
(53)
33

---

Case x & Se: Then f(x) > 1 - E/4. Since f(y) S 1, we have:
f()) f(x) < (1 e/4) =//4.
(54)
Combining cases Se and x & Sz gives f(v) - f(x) < e/4
VI. E [0, 1] with S S x 1
Since f is strictly increasing, we have f(x) S f() when x S y, and so
If(x) - f(v)l < E/4
Vx,y E [0, with | - yl S 1/n.
(55)
By Lemma 4, there exists a function Vn Va such that:
[f(x) - V. (=)) - e/4 + 2/n
Vr E
(56)
Since n > 4/e by (50), inequality (56) gives
[ - Vn(( </4 </////////////////
Vo E [0,
(57)
This completes the proof.
Lemma 6. Suppose up is value density function for Bob with (g(x) A for some A 0 and all
x E [0,1] 1]. Then for all n E N", there exists a function Vn E Vn such that
A+2 2
(x - Via((0, ai)
Vr E 1].
Proof. Let n E N". Since Bob's density is upper bounded by A, we have
[V x]) - V=.(0, v)) = A - vl Ve,y E [0,
(58)
When x yl S 1/n, we get [V=(002))) ( v|I - A o - ya $ D/n.
By Lemma 4 applied to the function f: [0, [0, 1] given by f(x) VB (B0 æ)), there exists
Vn E Vn with (x) - VB([0, x=)1 < A/n + 2/n for all x E [0, 1]. This completes the proof. O
The set of functions Vn will be used to construct strategy for Alice. Next we bound the size of Vn as function of as this rate of growth will influence the eπror bounds on the players' utilities.
Lemma' 7. |.l < 4n-1 Vn E N
Proof. We first estimate the size each set W., and then will infer the bound for the size of Vn. Consider the density function corresponding to any particular V E Wn. Because V is piccewise linear, its density is piecewise constant. Each V is then uniquely determined by a sequence d1, d2...., dn- where d; is the value density between i-1 and 1. Each d, must be non-negative integer, because each these intervals has width 1/n " sees rise by an integer multiple of 1/n. More strongly, because V(O) 0 and ((1)
must have the next relation between the d; 's:
d nn
(59)
n
Thus, the size [W, is the number of possible partitions of into n parts with nonnegative integer sizes. The size of W,, can then be counted by standard combinatorics technique. Represent each choice of di, d2, .., d, with sequence of n "stars" and n "bars": di stars, then a bar, then d2 stars, then another bar, and so on. Each choice of di...., dn corresponds to unique arrangement of stars and bars. The opposite is also true: given an arrangement, the number of stars between each pair of bars can be read off as di..... dn. The size of V,, is then the number of arrangements, which is (2
The upper bound can then be shown by induction. As base case, (21-1) = -1) =1=55 1--1
34

---

Now assume (2m - 4m for an arbitrary n 2 1. We have
22n + 1) 11
(2n + 1)!
(2n 1)! 2n (2n +
2n 10011 1 n ))
2n(2n
n n+1
(n + 1)! n!
n! (n - 1)!- n(n + +1
n(n + 1)
$ 4 -4+ 2
(By the inductive hypothesis)
+ 1 S 4 4= 4(m+1)-1
So by induction, the bound holds for all n 2 1.
Because Vn Wn for all n + the only case left verify is By calculation, [Wal (2) so including the extra function makes [221 4 42-1
Some other technical lemmas are necessary. The first two relate to the following function, which acts like
inner product.
Definition 8. Let X be the collection of all functions X V. [-1,1], For each pair of functions
X,Y: + 11 define P X X > as follows:
00
P(X,Y) Σ
Σ V)n
2 Va
VEV.
Lemma 8. The function P has the properties of an inner product. In particular, for all functions
Y, [- and all constants E [-,,1], the following holds:
(1) P(X,Y) exists, and the infinite sum converges absolutely
(2) P(X,Y) = P(Y,))
(3) PP(, Y
(4) P(cX,Y, Y) = =c((X,))
(5) P(X +Z,1)= P(X,Y) + P(Z,Y), assuming X + Z is in the domain of P
(6) P(X.X) (n, V) 0 for all and all V, and P(X, > 0 otherwise
Proof. We separately prove each of the properties.
For the first property, note that the individual terms go to zero
lim n-
Σ V)Y,
< lim
Σ
[Xnn, (n V)I
2n
n=c 2 Vn
VER.
VEV.
lim >oc
Σ
(By the bounds on X and Y)
2n
VEV.
lim
Vna
lim
n-
2 Vn
2n
0.
Using the above upper bound for individual terms, the sum of the absolute values does not diverge as follows
Σ (V,,
2
2
VER.
n=1
So P(X, Y) exists and the infinite sum converges absolutely.
The existence is enough for property (2), which follows directly from the product ((n, V)Y V) being commutative. This calculation directly verifies property (3).
35

---

The absolute convergence allows for the linear operations in properties (4) and (5) to factor through the sum.
First, for property (4) we obtain
20
P)cX,
Σ
Σ
2" Vn
VEV.
20
Σ ((,
2n 2
VEV.
cP(A, B)
For property (5) observe that:
P(X Z,Y) Σ
Σ (X(n, ())
2n 2n|V VEV.
00
Σ
2n\ Σ VYn, V) + I(n, V)Y(n,
VEV.
1
Σ (Y,,V) Σ
Σ VEV.
Z(n, V),,V)n,,
2 V/
2
VEV,
= P(X, Y) + P(Z,Y).
For property (6), observe that the expression can be rewritten as:
P(X,X)=
Σ
X(n, v)2.
2
VEV.
This is sum of squares, which will be zero all the included X (n, V) are zero and positive otherwise.
1
Lemma 9. For each E [0, 1]. let G. : V- -1/2) -122 be given by Gz(n, V) V(x) } Then, for all Z V > [-1,1] 1), the following function is continuous in x:
1) Z(n, V). Σ (v(#) - 2
(v(o)-
P(G., Z) Σ 2n 2
VEV.
Proof. Alice's valuation function in V/2 needs to be handled separately. Accordingly, write:
P(G,, =)=
Σ
Σ VEV.
(v(o)= -22) 2 2(n,v) V)
2n Vn
==1
1
(va((0,)))
1 2 (1n, VA)
Σ
Σ VeW.
V(x) - 1 7(n.V)
2 V2
2
As long as each of these two parts continuous, the sum will be too. The first part is continuous because (a æ²)) is continuous. To prove the second part, for notational simplicity, define
P'(G,, 2) =
Σ VEW,
(((x) - 1/1 7(n, V)
2D
The continuity of P' will be shown by directly appealing to the definition of a limit. First, note that each V E Wr, is made of n linear segments, each of width and height at most 1. Therefore, V E W,, for all 2, y E [0, 1]:
[V() - Vx)) $ by x x/n
(60)
36

---

Fix an arbitrary E > 0 and r E [0, 1]. Choose å = E//2. For any y such that ly - x < 8:
,G 2) - P' 2 = P'G Gz:
(By property (5))
Σ
Σ (V(v)- - ((z)) V)
2 [vl VEW,
n=1
1
Σ
[V()) V(x) 1Z(,, V)
(Triangle inequality)
2 11
1=1
VEW.
Σ
Σ
nly x 1
(By ineq (60) and Z S 1)
2n
V1
==1
VEW.
00
Y1
(Since [ S [ )
2
2
(By choice of 6)
Therefore, for all x E [0, 1]:
lim P' (Gy, z)= =) Z),
4-2
which is the definition of P' P'(Gz; Z) being continuous in This concludes that P(G,, Z) is continuous in x.
Finally, the last one is strengthening of Lemma from Blackwell (1956), under stronger hypotheses. Lemma 10. Suppose a sequence of nonnegative values ò1 62.... satisfies, for all 2 1:
1
d S 11
+
8
|+1
Then 1im 5, = O. In particular, for all t 2 2:
8, 5 t(t 1) 1=
Proof. The latter bound will be shown by induction. As a base case, consider t = 2. The condition for tort= 1 gives:
2
82 S
+
[+1 81 11-4-- 2(2
(61)
(1 + 1)2
i=
So the base case holds. Now suppose the conclusion holds for some t 2 2. Assume that the claim holds for dt. We can expand the upper bound of 8,41 follows.
1
8,4 S
8
(62)
(t 1)2
t+1
1
(t-1)
(By the induction hypothesis)
(1+ 1)2
[++]
1) 1(1
i
1=2
1
1-1
(63)
1)
+(t+1)
1=
1
i-1
(64)
(t+1)t
i
1=2
37

---

Now it suffices to show that the last term in (64) is upper bounded by 1/t, which follows from the following inequality:
1
1(1-1) (t- - 7. ()-1)=
(65)
1(1
1=2
Thus 8c-1 S 1/4, which completes the proof.
Now the groundwork is laid to prove Theorem 2. The idea is to limit every strategy and every valuation in every Vn to average payoff of 1/2, which is sufficient to limit Bob equipped with arbitrary valuation as well.
Proof of Theorem 2. We first define the Alice's strategy in an analytical manner, and then prove that it is well-defined. Then will show that this strategy will force Bob's payoff to be at most 1/2 on average, by showing both that Bob's valuation can be well well-approximated by functions in V and that such valuation functions are limited to a payoff of 1/2 on average. Finally, we establish explicit convergence rates for Bob's payoff if his valuation is bounded, well as the convergence of Alice's s payoff to 1/2.
Defining Alice's strategy SA Consider Alice's decision in round T. In each round T, let the payoff to Bob whose cumulative valuation function is V be w,,v- For each x E [0, 1], let Ge : - [-1,, 1] be function defined as Gz(n2, V) V (xx 1/2. Let (r, V) = ut,V 1/2 for t= 1, T 1, and let (n, V) Ei= (n, V)ft. Let (n V) max U (n. V)} for
t t= I=,....,,T T- - 1. In round T, Alice's 's strategy S is to cut at a point o such that P(G,, Wr-1) = 0.
We then show that SA is well-defined. It suffices to prove that such an x always exists. To this end, observe that
20
P(Go, 1r- =
Σ
(v())
W V)
Vnl
VEV.
00
WT-i(n,V)
Vn
2
==1
VEVU
Σ 0
(Since Wr-1 is nonnegative)
2
Vnl
n=1
VEV.
=0.
Using similar algebra for P(G1, 1), we obtain
P(G,, (T-1) =
00
Σ
V(L) (V1)--)
2) 2) Wr-1(n,V)
2n Vn
n=1
VEV.
00
W W V)
2 Vn
==1
VEV.
2
Σ 0
(Since Wr-1() is nonnegative)
2 T.
n=1
VEV.
0
By Lemma 9, P(Z,, Wr-1) is continuous in x, so by the Intermediate Value Theorem there exists such that PGG,, Wr-1) = 0.
Bounding Bob's payoff
Define
1 S <X,n, V) < 0 for all (n.V) E V
S =
X :
2
38

---

For each round t, let 5e be the distance from S to U,, defined as:
inf P(U. x, X,U, X). XES
(66)
Fort < T. let Y; V + (-1/2,1/ be the function defined by:
(n, V) mmin(0, Un,,, V)
By Claim 3, we have S 1/t for all 2
Now we will show that this strategy guarantees that, for any Bob's valuation function UB and any strategy Sg Bob employs, his average payoff is at most 1/2. Consider arbitrary > 0. It will be shown that, for some sufficiently large T, Bob's average payoff up to any point after round T is at most 1/2 +
In the general case, this convergence can be established from Lemma Consider N, E N such that
N is such that there exists V E VN with V'(x) Vi((0,,)) x|] <// for all [0,
T is sufficiently large so that
c2
86
vA 2 T.
(67)
4 2 VNv
For example, taking T
1-2 Vwl
would suffice.
We will show that for each T. have UN,, VTJ </22. This trivially holds U.NN V` s
so assume UN, Vt) O. We then obtain
1 Ve(2
UNNN.
221
2N|VN|
22/VNl
(U,(N, Y VO)
(68)
2
where (68) follows from the fact that YI(N, V²) = mi,, VD} 0. Using (68), we can upper bound U, UN,, V') as follows:
V((
2
VN
(U,(n, V) - Ye(n, v))
2n VM
n=1
VEV.
22 Y,, Y.)
22
(69)
22
6
(By (67))
4 V
2
Therefore, we have UN, V') < <e/2 for all > Translating back into payoffs, this gives Bob whose cumulative valuation function is V average payoff of less than 1/2 + =/2. By the choice of V", we have
V'(x) V (0,, =])| < </2
for all x E [0,
(70)
so the average payoff Bob whose valuation function is ug is less than 1/2 + Since this construction works for all E > 0, Bob's average payoff satisfies the following incquality as required:
uB
2 + o(1.
39

---

Explicit bounds It remains to prove inequality (32) when Bob's ' density is upper bounded by A, and prove Alice's explicit payoff inequality (33). Choose integer N large enough that
+ N
For instance, taking N 22 + 2)/e] is sufficient. By Lemma 6, there exists V E V/y such that
(z) - VB (0, x=) < (A 2)/N for all E [].
Choose T in exactly the way the general case, i.e. T [4.2% Vw 1w/1/221 By exactly the same algehra as the general case, conclude that U (N, VT) < e/2 for all 2 T. By the choice of V', we have
(v) (=( < e/2
for all x E [0, 1],
(71)
so the average payoff to Bob is most + In this case, Bob's average payoff will be within e of 1/2 by time
4 2 VN]
Te
where
N [2(2 + 2)/e1
(72)
Hence, for such Te, we have
4 2 4
Tg
?
Since [x] < 2x for x 2 1/2, this implies
8N
T S 2
g2
Due to our choice of we can further obtain
21
Te S 2. 8
(73)
E²
Taking the natural logarithm of both sides in (73), we have
(n(T)) S (n66)) + 2(A + 2)
In(8) + 2
Using the fact that Ixx S x for every x >> 0, it follows that
2(A 2)
In(T.) < In(16)
In (8) +
(74)
E
Rearranging (74), we finally obtain
2 (8 + +2
(n(T.) - (n(16) +
Note that this requires the step of dividing by In(T.)- In(16) + and it needs this quantity to be positive, which is indeed positive for T 2 Rounding the terms gives the desired regret bound for Bob.
To provide Alice's payoff bound in inequality (33), consider hypothetical Bob whose valuation function ün exactly the same as Alice's valuation function va. For all rounds t, the payoff ü to this Bob then satisfies:
7 VA((O, Va([a=: 1))
(One player gets Va( ar]) and the other gets Va Va( 1)))
(75)
For any f, summing nAA üß over [t] and dividing by t then gives:
(1
uz (1,t))
(76)
t
40

---

So suffices to upper- bound this particular Bob's payoff to lower-bound Alice's ' payoff.
c² Choose arbitrary O. Let T. | ensuring 6, 2 for all 2 Tg. By construction,
Alice's s valuation function Va( æ²) E V22 Taking = 2 and V = Va. we can then use identical algebra as the general-Bob case up (69) conclude that, for Te:
(, VA) & 12
(Copying over (69))
62
V2 2
(77)
2
So this Bob's payoff is upper-bounded by 1/2 +. e, and so by (76) Alice's payoff is lower-bounded by 1/2 - E. To solve for e, observe that Tg S 16/e² +.. Solving this bound on T, for gives
VT.
and it finishes the proof.
We finally provide the claims and their proofs used throughout the main proof.
Claim 1. In the setting of Theorem 2. if U, & S, then argminxes P(U, X,U, X) exists. Furthermore:
argmin P(U,- - -,U - -x) XES
min U,,,,, V)}
Proof of the claim. Let Y min (0, V) S. For any X Xes S,
P(U. - X,U, X)=
Σ (U.(n, X(n, VI)
2 [nl
n=
VeVa
Σ
(U,(n, -(x,))))((,V)))
Σ
(Ui(n,V) - x(n,V))
n=1
VEVa ())..))s
VEV. U.(n.))oo
(78)
Since X E S, we have that X(n, V) S 0 for every and V. due to construction of S.
Therefore, replacing them with 0 brings them closer to any positive value and so decreases the first sum of squares. The second sum of squares is nonnegative, so it can be reduced by replacing it with Applying these simplifications, we obtain
Σ
Σ VEV. Viin
(U,(n,)) -xx,))
Σ
(U.(n, X(n,
2 Vnll
VEV. Vs(o,V)go
8
Σ
V) +0
2 Vn
1=1
VEV.
V)(,
=D(U, - Y,, U. Y(),
(Only the U(n, V) > 0 terms remain)
and it proves the claim.
Claim 2. In the setting of Theorem 2, the following properties hold when U, $ S.
1. P(Y,, WT) =0
2. P(U+1 Wt) 0
41

---

3. P(U,, Wt) > 0
4. P(X, Wi) & for all X E
Proof of the claim. All of these properties can be explained by expanding the dot product and referring to the strategy SA- The first one is the most straightforward: Y, and W, never nonzero in the same coordinate, so P(y, W₂) = 0. For the second one, by definition, in round + Alice cuts point I such that P(Gg, W,) = O. If Bob selects the left piece, Uc+1 Gg. If Bob instead selects the right piece:
Un V) (1 V(x))
V(x)
(n, V).
So by property 4 of Lemma 8, we have P(U,-1, W.) = P(G.,, W:) = 0. Because Pis linear as per property 5 in Lemma 8, any mixed strategy over these outcomes must also satisfy P(U++1, W.) For part (3) of the lemma, expanding the dot product gives:
00
P(X, Σ
Σ
X(n, max ma (n, V))
2n(Vn
VEV,
00
Σ
X(n, (),,(n,
2d Vn
n=1
As there exists (n, V) such that (n,, V) 0, this sum is strictly positive when X Ün, V), and so P(U,, W;) >> 0. Similarly, for X E S, have X(n, V) < for all (n, V), so P(X, W)) < 0.
Claim 3. In the setting of Theorem 2, the sequence {6 defined in (66) satisfies the inequality < for all 2.
Proof. We will show that construction of o, satisfies the recursion formula defined in Lemma 10. We first focus on the case such that 6, >> O, which is equivalent to U, & S, and then prove that it also holds for d, O. Given that 6, > 0, we observe that
8 inf - X) P(U++1 U411111-0 Y.).
(79)
XES
By rewriting the right hand side of (79), we obtain
6ct1 S P(U - U.) + (U, Yi), (U++1-U)) (U,-Y.))
-..-Y,)
(80)
Distributing over P in the expression on the right hand side of (80), we get that (80) is equivalent to
81+1 S P(U +1 U.U - +2) - U,, U. Yi) + P(U. Y,U, Y2)
P(U++1 U,+1 U.) 2P U, Y.) + 8.,
(81)
where the inequality follows from Claim 1.
Noting that U++1 -U, (U++1 (t)/(t= + 1), we have
P(U (+ - U, Y,)
t ++1 P(U++1 - U,U.-VY
P(UU++) - Yz) + (Y, U.), U. Y.)
t. ++1
(P(U++1 U, Y) P(Y, - UU,UU - -Y)).
42

---

6. By using U, We + Yt, we can expand it by
P(U++1 U.U. Y7)
(P(U++1, Wi) P(Y, Wt) P(Y, - -U, Yi))
t+1
(P(U++1, Wi) P(Y. W.) 6.)
(By Claim 1)
t t+]
(0 10-0-a)
(By Claim 2)
1+1
1
1+1 dr.
(82)
Further, observe that
P(U++1 - U. U2.1 - -U,) (t+ 1)2
P(U++1 - U..U++) U,)
1
(83)
(1+ 1)2
where the inequality follows from Property (3) in Lemma 8.
Putting (81), (82) and (83) together, we obtain the following inequality for 6, 0:
8.t1 S P(U++ 41 U.U
U.) 2P(U.+1 U. U. Y,) 6t
2
S 1}2
5,
++1
(L 11z + (1-
(-(+1) (1-1+1)
2
Now, we show that the same inequality holds for the case such that = 0 too. Since U, S, we obtain
8141 = inf P(U (+1 X,U,+11 X)
XES
< P(U++1 - U,, U++1 -U.)
1
S (t + 1)2
(By (83))
2
1
dc.
(1+
(
By Lemma 10, we therefore have that 8, 1/t for t 2.
B.2 Appendix: Bob enforcing equitable payoffs
In this section, we prove Theorem 3, which shows how Bob can enforce equitable payoffs. Restatement of Theorem 3 (Bob enforcing equitable payoffs; formal).
In the sequential setting: Bob has pure strategy Sg. such that for every Alice strategy S A. on every trajectory of play, Bob 's average payoff is at least 1/2 - o(1), while Alice's average payoff is at most 1/2 + o(1). More precisely.
UB T
UB T
A
1
and
+
2
VT
2
28
VT
recalling that å and A are, respectively, the lower and upper bounds the players' value densities.
In the simultaneous setting: Bob has a mixed strategy Ss, such that for every Alice strategy
SA. both players have average payoff 1/2 in expectation.
43

---

Proof of Theorem 3. Bob's strategy for the simultaneous setting follows from Proposition 6. His strategy for the sequential setting follows from Proposition 7.
[
Proposition 6. In the simultaneous setting, Bob has mixed strategy SB such that, for every Alice strategy SA:
Euaa]
E Elun]
1
T
T
Proof. Bob's strategy is very simple: in each round, randomly pick I. or R with equal probability.
To analyze the expected payoffs, consider an arbitrary player E (A, B} and arbitrary round t. Bob is equally likely to pick L or R in round t, so each player is equally likely to receive [0, axl or [ar, 1]
in round f. Therefore, their expected payoft is:
E Elu
Vi(10, ar)) - Vi((ar, 1))
vi((o, 1))
(Since valuations additive)
1
(84)
2
Summing (84) over the T rounds gives the desired expected payoffs for each player.
Proposition 7. Bob has pure strategy Sg, such that for every Alice strategy SA. the cumulative utilities in the sequential game are bounded by:
A 28
u ST/2+
VT
and
2B) 2 VT.
Proof. Bob devises his strategy Sg by considering a division the cake into P= = [VT]] consecutive intervals Ip of equal value to him. That is, Bob chooses points 0 = S S zp = such that
[z)-
if < j --1 if = P:
1
and VB(l) = 1/P Vj Pl.
(85)
[2p-1,2p]
An illustration of the division into intervals used by Bob can seen Figure 17.
21
23
Figure 17: Example of a Bob density and the discretization used by Bob when T 10. The number of intervals is P [T] 4. The intervals are 15 [z)-1, for j E [3] and IA [2a, 21], with VB(4, = 1/4 1/4 E [4].
Bob's s strategy SB is defined as follows. Bob keeps counter associated with each interval Ij. such that the value of the counter time 4, denoted Cj,t, represents how many times Alice has cut inside the interval Ij in the first t rounds (including round t). For each time t [T]:
44

---

Let 1 be the interval that contains Alice's cut at time t (that is, at Iÿ), for j E [P].
If Cj is even then Bob plays L; if Cj.a is odd, then Bob plays R.
Informally, Bob alternates between I. and R inside each interval 15. We argue that this Bob strategy ensures his payoff least 1/2 - o(1) per round, while Alice cannot get more than 1/2 + o(1) per round.
For each E [P] and j E [c,,]] let riij be the first time when the number of cuts in L reached j. That is,
Th = minft E N Ciat = j and E 1.).
By definition the sequence {ra.e). for each i, with 2j S c,Tr
Alice cut the interval I in both rounds 71,25-1 and 7,2y (meaning Cr Oruzy E 4,);
Bob played different actions the rounds 25,25-1 and Tt22j-
We view rounds 71,25-1 and r5,2j as pair. For each E [P]. there is at most one round ri,, that does have pair, namely round ri the last round Alice cut in 4. However, this loss only represents at most P rounds in total, which will translate to a sub-linear loss for either Alice's 's or Bob's 's utility estimates.
Now we can bound the cumulative utility of each player.
Bob's payoff. For each i, E N with 2j S C,r,, Bob's payoff across the two rounds T1,2j-1 and T222 bounded by
2 1 VI 1
ug
+ "
(86)
Since the rounds ray with i E [P] and 2j S G,T represent subset of the total set of rounds [7], Bob's cumulative payoff is at least
P6a5-1
"B
21
JEN:2SSar
Σ
Σ
1-
(By (86)
P
1=1
JeN
T P
1
(Since the sum is over at least T-P pairs of rounds)
Since P= [VT 2 /
T,
we get
uB Σ
uB
1
1
T
-
P
T
VT
T
1
p
2
2
(T)
2
VT+1 +1
VT
>
+
2 2
2
2
= 2
VT.
(87)
Alice's payoff. For each i,j E with 2j S G,T, Alice's payoff across rounds rı,2j and ri,2j
A =
UA
F625-1
+ uu < 1 + (4(
Ti.2i
<
11 Vo(I)
1
8 P
(88)
45

---

There is at most one round without a pair for each interval I,, namely round rr the last time Alice cut in 4. For each such round without a pair, we upper bound Alice's payoff by 1. Then we can upper bound Alice's s cumulative utility by
T
P+
P4.23-1 1 +
13,20
A
i=1
JEN:2jSor.
p
P
Σ
E
1+
(By (88))
8
1=1
JEN:2fSc.r
T
A
S
1+
(Since the sum over at most T/2 pairs)
2
P8
T T
A
+P
T
A
$ 2 VT
+
+
(P= [VT] 22VT)
28
This completes the proof.
46

---

C Appendix: Fictitious play
In this section, we analyze the fictitious play dynamics. We first formally define fictitious play in terms of the empirical frequency and empirical distribution:
The empirical frequency of Alice's ' play up to (but not including) time is:
t-1
(x = Σ (a, Vo E [0, 1].
The empirical frequeney of Bob's play up to (but not including) time t is:
(x()) Σ (m, Ve E R}.
The empirical distribution of player i's play up (but not including) time is:
pl(x) of (x)
1)
Where E [0, 1] for Alice and x E (L, R2 for Bob.
Definition 9. (Fictitious play) In round 1, each player simultaneously selects arbitrary action. In every round t ...... ,, each player simultaneously best responds to the empirical distribution of the other player up to time i. there multiple best responses, the player chooses one arbitrarily.
We now give the proof of Theorem using lemmas that will be presented later, and then prove the required lemmas.
Restatement of Theorem 4, When both Alice and Bob run fictitious play, regardless of lie-breuking rules, their average payoff will converge to 1/2 at rate of O(1/VT). Formally:
UA
2V10
uB T
v10
and
VT 5.
(89)
T
VT
VT
Proof. The bounds on Bob's payoff follow immediately from Lemma 21, which states that
T
T + VIOT.
10T
(90)
2
B
2
t=1
By Lemma 22,
T
V1TT
u/) ST VIOT.
(91)
Subtracting equation (90) from (91) gives
T
T 2
2v 10T
+
+21107.
(92)
tm1
Since U = ET= u'A and ug = DT unz both players' utilities are bounded as required, which completes the proof.
To prove the required lemmas, we first introduce several notations. For ease of exposition, we often round = 0 as fake round in which nothing actually happens and all the defined quantities zero.
Definition 10. For E (0.1....,T}:
Let Pt be the number of rounds in which Bob has picked R. up to and including round t.
47

---

Let & be the number of rounds in which Bob has picked L up to and including round t.
Let (4 = - 4.
Let -i a;l) - 1).
Pt 1 + |.,], which we call the radius.
We remark that in the fake round t = 0, all these variables have the value zero. Alice's action under fictitious play entirely depends the variable o, while Bob's action entirely depends on 8t. Overall, we will bound the payoffs using the growth the radius P: over / = 0, o......77 T. To this end, introduce two lemmas that will play an essential role throughout the proof.
First, the following lemma formally argues that the action taken by each player is guided by their corresponding variable a and 3,, respectively.
Lemma 11. Let & 10.
T- - 1}. Then the the following hold for round + 1:
Alice's 's action with respect to oạ:
If a4 > 0, Alice will cut at 1.
- If a4 O, Alice will cut at 0.
- af 0, any action would incur the same payoff, so she could cut anywhere.
Bob's action with respect Bi:
!f Be Bob will pick I.
If Bt Bob will pick R.
1f Bt O, any action would incur the same payoff. he could pick either L or R.
Proof. First, consider Alice's choice. For = O, there is no history, so any choice has the same value to her; accordingly, ag O. Fort 2 the expected value she assigns to any particular cut location is:
(r.Va((0,z)) + + (V 1)) = (reVA(10, x)) + 4 Va((O, x)))
Ti b VA( x|) +
t
01 VA(O, + 4
(93)
From (93), get that Alice's decision is entirely based at. If a, < 0, she will minimize ([O æz), which means she cuts at O. If a; > 0, she will maximize Va([0, z)), which means she cuts 1. If a, 0, then her choice of doesn't 't affect her expected value.
Now consider Bob's choice. For = 0, there is no history, so Bob indifferent between L and R; accordingly, 30 0. For / 2 1, the expected value he assigns to choosing L is:
EL 1 Σ (o)
(94)
The expected value he assigns to choosing ii:
ER Σ Vo((a,,
(95)
Combining (94) and (95), the difference between his expected value for choosing L and R is:
Vo( vo((o...1)
Ve(lan 11)
1 Σ (2Va((0, - 11 8
EL ER =
(96)
From (96), we get that Bob's decision is entirely based on B. 9, < 0, he values more than L, so he picks R. If 3e > 0, he values L more than R, so he picks L. If 3, 0. he values each equally. D
48

---

The following lemma further describes the evolution of and 6e given the actions taken by the players.
Lemma 12. For each round E [T]:
Alice's 's action affects Be as follows:
If Alice cuts at round t, then 32-1
If Alice cuts at in round t, then Bt = Bt + 1.
1), then |8, Bt-1 1. Bob's action affects as as follows:
she cuts
If Bob picks in round t, then at = 0tt-1
!f Bob picks R in round I, then Oz, = 04 + 1.
Proof. First, we consider the impact of Alice's cut point a, on S.. Explicitly writing out the difference
3e 3 gives:
Be 3 Σ (2VB a.l) - 1) Σ (2VB(((, =V)( -.
(97)
az 0, then (80 arl) (1s 0)) = 0, so by (97) we have Br Bt-1 = as desired.
a = 1, then VB ([0, a.l) VB ((0, 1]) = 1, so by (97) we have B1 3
If E (0, 1). then there is at least some cake each side of ae, have VB a:)) E (0, 1). By (97), we have 3, 1 E (-,,1), so 13, 3 <
as stated by the lemma.
Second, we consider the impact of Bob's choice on Explicitly writing out the difference de 02--1 we obtain the following:
b. R
ag 04-1 - ( l4-1) (r: re-1) - (le l(-1)
{
(98)
be =
This completes the proof.
Let us elaborate more the dynamics each player based on Lemma and 12. either of a or 3 exactly 0, the corresponding player will their tie- tie-breaking rules. Ignoring these cases, these choices lead to movement through (a,, BB) space that spirals counter-clockwise around the origin at exactly 45 degree angles. Figure 18-(a) describes the overall dynamics of the variables (a,, Bt).
The following lemma shows a symmetry that will help reduce the number of cases the subsequent analysis. Figure 18-(b) depicts the rotational symmetry of fictitious play dynamics in the a-8-plane shown by the lemma. Specifically, the symmetry will allow us assume aę 2 0 without loss of generality when analyzing Pt and u'g.
Lemma 13. Consider an arbitrary pair of tie- tie-breaking rules for both players. Consider the resulting sequence for the variables Oit, Be and u'n for O...., T. Then, there exists another choice of tie-breaking rules that would result in the sequence of variables on, Br, and üig for I = 0...., T such that
āg = 04g5
B -B:; 1 = u
(99)
Proof. The proof will proceed by induction.
Base case All of on. āo. 3o. 3o. ub, and ih are zero, (99) trivially holds.
Inductive hypothesis Assume that (99) holds for some 2 0.
49

---

B
(a) Overall dynamics
(b) Reflected dynamics by Lemma 13
Figure 18: Figure (a) represents the overall illustration of the dynamics of the action quantities ap and Be for f = 0, 1, ... T. The æ-axis denotes the quantity of o₁ and the y-axis denotes that of 8t- Blue circles represent the sequence of points in the plane, where the number inside the circle denotes the index f. Note that a, only takes integer values, while possibly takes noninteger values some rounds. Figure (b) also depicts an overall dynamics implemented by another pair of tiebreaking rules guaranteed by Lemma 13. Note that each point is reflected with respect the origin point. Importantly, Lemma 13 guarantees that Pr and up for / = 0, I...., remain exactly the same for both dynamics.
Inductive step We show that (99) holds for + 1. Suppose that, under the original tie-breaking rules, Alice a++1 and Bob picked bı41 {L, R} in round + 1. First, we analyze for Alice. Let d/+1 E [0, 1] be the unique point for which
(BO ac+ 11) = Vn ([o(+1:1)))
(100)
The point d/41 is uniquely defined since Bob's density is strictly positive.
We show that there exists another choice of tie-breaking rules under which, starting from de and B.. Alice cuts at d'41 in round + 1. We split into cases based on ay:
(ag 0): Then a++1 1 by Lemma 11. Since VB(OO, ac+1l) VB 1)). we have t'41 0 by definition. By the inductive hypothesis, we have ā. = -0t, and so á; < Then, regardless of tie-breaking rules, Alice cuts at d'+1.
(as < 0): Then dc+1 = 0 by Lemma 11. Since VB V1 a++1 = = Vn 1)). we have d'u1 = by definition. By the inductive hypothesis, Or - Oct, and so â₂ 0. Then, regardless of bie-breaking rules, Alice cuts at 1 = d'+1-
(a, = 0): Then Alice can break ties any way she likes by Lemma 11. However, å, aa, 0, so any cut point a valid choice for her new tie-breaking rule. In particular, she can cut at d/41-
Second, analyze for Bob. Let 1/+1 E {L, R) be such that 1/+1 # b We show that there exist tie- breakinking rules under which, starting from āi and Br, Bob chooses 6/41- We split into cases based on Bp:
(8, 0): Then br+1 L by Lemma 1I; therefore, 6/41 R. By the inductive hypothesis,
3. = - 3r so 3, < 0. Then, regardless of tie-breaking rules, Bob picks R = 1-1
(8t < 0): Then b = by Lemma 11; therefore, 144 = L. By the inductive hypothesis,
3, Br, so 3, 0. Then, regardless of tie- fiebbrakiig rules, Bob picks L b6+1-
50

---

(B+ 0): Then Bob can break ties any way he likes by Lemma 11. However, 3r - = 0, so either or valid choice for his new tie-breaking rule. particular, he can choose by b/+1
Finally, we show that these opposite choices have exactly the desired effect on 8e+1, Be+1, and a Covering each in turn:
Since Bob picks the opposite side under the trajectory associated with à and B, the change from a to a++1 is in the opposite direction as the change from Oy to a4+1 by Lemma 12. By the inductive hypothesis, we have å aa, and d4+1 -0++1
Since Alice picks the mirror image of her cut point under the trajectory associated with à and B, the change from Be to B0+1 is exactly opposite the change from B4 Be+1- Specifically,
B.+1 = 3, (2VB((0,a(4a)) -1),
(101)
while
8④4 3. + (2Vn(10, (/-1)
-1) -1)
3. + 2(1 - VB(la 11)) -1
B. 2(1 Vn, a++1l))
A. (2VB ac- - -1)
(102)
By the inductive hypothesis, we have 3r = -g. Using equations (101) and (102), we obtain Be+1 = -B+11
Under Alice's new cut point d.y1, Bob's valuation of the left and right sides of the cake swap, i.e., ( df+1]) VB ( 1]). But he also chooses the opposite side, he gets exactly the same payoff as under the original tie-breaking rules in round + 1. Therefore, Up u
By induction, the claim holds for all 1, which completes the proof.
In addition, it is helpful to distinguish between the rounds that cross axis in the a-B plane and those that do not. The following formalizes the definition of such rounds, which are depicted in Figure 19-(a).
Definition 11. An axis-crossing round is round where least one of the following occurs:
02 = 0
Bzt1 > 0, but Br < 0
B.+1 < 0, but Br 2 0.
Importantly, we will show that Pt can strictly increase only if the current round is axis-crossing, while it is non-decreasing over the entire game. The following lemma formalizes this observation. We provide an example in Figure 19-(b).
Lemma 14. Let & (0, ...,, T}. The radius Pt satisfies the following properties:
(a) P: = Pt-1 if is not axis-crossing
(b) Pt 5 Pt+1 2 Pt. if l. is axis-crossing
(c) Po = 0
(d) Pr > 1fort 1.
51

---

(a) Axis-crossing rounds
(b) Non-decreasing radius Pe over rounds
Figure 19: Overall dynamics of a and 3, with non axis-crossing rounds (blue circles) and axis- crossing rounds (red circles). Figure (b) shows that the radius Pr = |aul + [3+| is nondecreasing in / as shown by Lemma particular, Pt remains the same for non axis-crossing rounds but possibly increases for axis-crossing rounds.
In particular, the radius is non-decreasing in t.
Proof. First, we will show (a) and (b). Consider an arbitrary round E (O....,
T). By Lemma 12.
we have fo++1 orl < and 13++1 3el S so by the triangle inequality
Pt+1
Pr
|a++1| 1B4+1| lael 18,1 2.
(103)
Therefore, Pt+1 I 2 + Pr. as required by (b). Thus for (a) and (b) it remains to show that pt+1 Pt Vt {O.... ...,.,)) T} and that P++1 = Pt not axis-crossing.
By Lemma 13, it suffices to consider o; 2 0. More precisely, this because if a₁ S 0, then there exists tie-breaking rule with associated or satisfying ā, -a, for every 0, 1,..., T. so 0. Crucially, the lemma ensures the sequences ā, and o; have the same radius Pt.
We consider a few cases based on ar and Br, considering only at 2 0. Since ae is an integer, also divide into a; 2 and a₁ = 0:
(a+: and 3, > 0): By Lemma 11 Alice will 1 and Bob will pick L. Then by Lemma 12, we have 04-1 = - 1 and 3 = Br + 1. Therefore:
Pt+1 = |a++1| + +1+++1 = 0 1 3 +1
(Since 0r41 2 0)
=la;| + [Bel
(Because 0e, 8r 2 0)
= Pt.
(104)
(a: and 3r 0): Then Alice will cut and Bob will pick whichever piece he likes. There-
fore as+1 = 0e and ß441 = 3, + 1 = 1. Since 3r & 0 but B > 0, round is axis-crossing. What remains is to show that pr+1 2 Pt in this case:
Pt+1 = |0041l + [8+11| 2 Jaal 1 1+1
(Because Jar + vl 2 |o|| - |y| for all xr, y)
|a,l
|8,1
(Since 8, 0)
Pt
(105)
(o, and -1 8, <): Then Alice will eut and Bob will pick R. Therefore, 0++1 =
0t + 1 and Br+1 Br + 1. Since Br but 3.41 > 0, round t is axis-crossing. What
52

---

remains is to show that P++1 2
Pt+1 |1+1 [8441|
04 + 1 + 1+ + 1
2 04 + 1 [3,1 -1
(Since (ar + yl 2 |ar] - |yv for all æ; 3)
Pr.
(106)
(a: 2 1 and 3r < -1): Then Alice will cut at and Bob will pick R. Therefore, 0x+1
+ 1
and Br+1 = B, + In this case, pt+1 = pr:
Pt+1 |0041 + 18 = ar + 1 - (3, +)
(Because Br + 1 0)
| + |3cl
(Since Br S 0)
(107)
(o+ = and St 2 0): Then é is an axis-crossing round. Bob could pick either I. or R, but either Be S 1 still conclude
way |Qt41 1. Alice could cut anywhere, but since 18c+1
[3 - 13++1 < 1. Therefore:
Pr+1 |0 + 18c41l 2 1 1 13 -
= | + [Bel
(Since o, = 0)
Pt.
(108)
(o+ = and 3 < 0): Then we can use the symmetry of Lemma 13 to consider 3r > 0 instead, which has already been covered.
In all cases, properties (a) and (b) must hold.
Now we show that the properties (c) and (d) hold. Property (c) follows from -0 = 0. Because Pt+1 2 Pr for I, property (d) would follow from showing P1 2 1, which can be seen true from the following inequality:
P1 p1= |a1|
|3
1 + |811
(Since og 0, 01 +-1)
2
(109)
This finishes the proof.
Lemma 15. Suppose 1 is an axis-crossing round and T > 1-t-11 is the next axis-crossing round after t 1. Then, there exists at least Pt 2 and at most Pt rounds between them, i.e.,
Pt 2 < T Pc.
(110)
Proof. By Lemma 13, we can assume a; 2 0. Then it suffices to consider only four types that the axis-crossing round could have:
(i) 0t-- 2 1, B, S 0, and 3r > 0;
(ii) 0t-- 2 1, 8 2 0, and 3: < O;
(iii) 0:-- and 3 1 >
(iv) 0t-1 and 3 < 1.
We show separately for each of the types (i)-
04-1 2 1, 3, S 0, and B. > Because 04-1 > 0, Alice will cut at I in round by Lemma 11, 3, = B1-1 + 1. Since 3 and 8, have different signs, it must be that -1 < B,- < and 0 < 3, < 1. As long as remains positive, Alice will keep cutting at and increasing 33 by Lemma 11 and Lemma 12, the next axis-crossing round r cannot be where changes sign. Thus, it must be the one satisfying ar O. Until then, Bob will keep picking L, s0 will decrease by every round. Therefore, this implies that t 04 To show T < as required by (110), we have
T- t = 0+ |a + 13 S Pt-
53

---

To prove 2 T
observe that 2 a,-1 - 1. Since a;-1 2 1, we have 2 0.
Thus
T ( = Oit
2 at + |3
and or 2 0) (Since 0 < S
> Pt 2.
(111)
(ii) a-11 2 1,,8,, -1 2 O, and 3, < 0. Because a,-1 > 0, Alice will cut at in round t, so 3 =
3;-1 But then 3 2 0, contradicting 3e < Therefore, this case cannot happen.
(iii) 0t-- and 3,-1 1. By Lemma 11, Alice
wherever she likes, but Bob will pick L. Wherever Alice cuts, we will have (e2 = -1 and 3, 2 0. In order to return to a 0, Bob must start picking R, but he cannot do until 8 s 0 by Lemma 11. Therefore, the next axis-crossing round will be the one where 3 < 0 and B, 2 O. Until then, Alice will keep cutting so will decrease by every round. Therefore, T é [Br]. and this implies that
t [B.]
laol 13al Pa-
Again to show Pt
2 T observe that
T - = [
2 |001
1 1
13.11 -1
(Since a, -1 and Br 2 0)
= Pt - 2.
(iv) a and 0 S Bt-1 < 1. Under these constraints, we have Pt-1 |ac-1| | + 18--11 1.
0. Therefore, we have ar-1 = 3 Accounting for all possible choices Alice and Bob can make, it must be the case that a +1 and -1 S 3, S 1, which implies that Pt S 2. Thus it suffices show that r - < 1. We have a few cases:
part (d) of Lemma 14 implies that
If a 1 and 3. > then Bob will pick L in round t by Lemma 11. Therefore,
Qc-1 = 0, so r = +
If ar and -1 82 S O, then Alice will at 1 in round + by Lemma 11. 0.
Therefore, Bt+1 > 0, so round é is axis-crossing and
If a, 1 and 3: 11, then Alice will cut I and Bob will pick R in round + by Lemma 11. That will lead to 0++1 = 2 and 8 = 0, so round + is axis-crossing. Therefore,
If a, = 1, we can reduce to the a₁ = 1 case by Lemma 13.
Thus for all types (i)-(iv), it follows that P: 2 < r - 1 < Ps as desired.
The next two lemmas show different conditions under which o must increase. The first (Lemma 16) more technical in nature, while the second (Lemma 17) is key to bounding the players' total payoff.
Lemma 16. Suppose there exists a round such that Be o Z. Let >> be the first round after such that BeB < 0, i.c. By is zero has the opposite sign of 3r. Then the following inequality holds:
Pr 2 1p0+11
Proof. Again by Lemma 13, assume without loss of generality that 3e 2 0. Since 3, & Z, can further assume 3, > 0.
Suppose that 8, g Z. Because > is the first round after / with 3, < 0, we must have 3 > 0.
Since 3, & Z, we also have 3, < Combining 1,9, 3--11 S and By yields 3,-1 Since 8, > 0, Bob picked in round by Lemma 11, have a, ar-1 -1. 1. As B, < B
54

---

Alice must have not cut at in round by Lemma 12. This implies that a, S 0. Finally, we obtain
Pr = arl
|3+1
2 Q1,-1 1| +
(Since a Qr-1 1)
= 1 - Qr-1
(Since ay S 0)
1 |a,-1| L|Br-11]
(Since ay-1 S 0 and 0 B 1)
= 1 + [pr-1]
(Since ar-1 E 2)
2 1 [ec.
(By Lemma 14)
On the other hand, suppose 3, E R. By Lemma 14, we have Pr 2 Pt. Since 9c E 2 but at E Z and
Or E E, we have Pr Z but Pr $ Z. Therefore, [ed] Pt Pr. Since both [oe] E Z and Pr E Z. we have Pr 2 Let] +
Lemma 17. Let be round which Alice cuts at or (0, 1). Let be the first axis-crossing round strictly after t 1. Then |Pt-1] +1.
Proof. By Lemma 11, Alice will cut at 0 if a:-1 + As Alice does not cut round f, this implies that 0:-1 O. First, if B 0, then Lemma 14 implies t - 1 = 0, so
1 in
Pr 2 [Pt-1] + required.
Otherwise, by Lemma 13, we can assume without loss of generality that 3,-1 > 0. Because P [8,-1] > 0, Lemma 14 implies 1 2 By part (d) of Lemma 14, further have
1 Pt-1
Pt-1 = |o--1 + |B-- Bt-1-
Since Alice does not cut 0 in round f, we have Be > 81-1 1 by Lemma 11, which implies that 3, > As 3t-1 > O, Bob picked L round t by Lemma 11, so we have dg < 0. Again by Lemma 11, for return to 0, Bob would have to start picking R, but he won't until 3 stops being positive. Therefore, the next axis-crossing round after t will be one where / crosses into being non-positive from positive, B,
Let [ be the first round after such that B, S Because By < O, we have S T. Because 3, >> O, we have > 1.
If 3 & then applying Lemma 16
yields Pa [pt-1] + By Lemma 14, have Pr 2 Pa. and so Pr 2 Ps [Pt-1] + as required.
If 84 Z, then applying Lemma 16 f yields P. 2 |pt] 1. By Lemma 14, we have Pr 2 Ps and P: 2 Pt-1, and so Pr 2 Ps 2 [p + 2 [p--1l + as required.
Else, we have 1, E Z. Since Alice did not cut at 0 or 1 in round I, by Lemma 12 we have
|8 3--1 1. Since 3,, 8: Z, we get B = B2. Moreover, since at-1 0, we have
|asl |a 1 + 1| 1 1. This implies that
P+ 2 Pt
(By Lemma 14)
Pt-1 +1
(Since Br = B and lool |o0-1|
2 |p-1|
This completes the proof.
The following lemma bounds Bob's total payoff using the radius pt- Lemma 18. For every round 2 0, the following inequalities hold:
P: I
(2u -1) S Pe-
(112)
Proof. We will first show the following stronger of inequalities by induction d:
0 Jar Σ (2u'g 1) Pt.
(113)
1=1
As base case, consider = 0. Before anything has happened, all three sides of (113) are zero, so the inequalities trivially hold.
55

---

Now assume that (113) holds for some & 2 O, and we will prove that it still holds for round t - 1. We consider three cases separately in what follows, depending on the values of a, and 3,. Note that again by I Lemma 13, it suffices to only consider cases where or 2 0.
If a; O, Alice will cut in round + 1 by Lemma 11. Bob picks L, then he will receive payoff of I and will decrease by I due to Lemma 12. If Bob picks R. then he will receive a payoff of and a, will increase by due to Lemma 12. either case, the changes to |ael + ( - 1) cancel out, which implics that
I+1 2(2u, - 1).
lasl + Σ (2n - 1) = |a4t1+++++ +
(114)
1=1
Further, by Lemma 14 we have pt+1 2 Pr. Together with the induction hypothesis (113). this concludes
++1 (2u's - -1) S PL+1:
0 S |141
and thus the induction holds for the first case.
If 0 and 3, 2 0, then regardless of whether Bob picks I. or R in round f + 1 we have
|0441 10 + 1 a necessarily changes by 1. Therefore, we have
"2uhh - 11 - (1ar1 + (2u'h (ommm11))) 1) = + 2u 1+1
c+1
|a142| +
2m
2u f-1
(115)
Also, the change in p can be bounded as follows:
Pi+1
P: |au+1|
+ 18e4al - llasl |Bel
++1
1+
Σ (2V ail) 1) 0 Be
(8 2 0)
1 + ((2V>((0, (+000,,,+))))))) - 1) + 3.1 3.1-8,
2 1 + ((,, ((01))))))
(Removing the absolute value)
(V0,((0,++1))
(116)
If Bob picked in round t + 1, this is exactly the same as (115). Bob picked R, then by Lemma 11 and the assumption that B3 2 0 must have 0. The change in the radius can be bounded as follows:
Pt+1 - Pt Jau+1l |3++1| |ad| |3cl
= 1 + 12V (0, a++1)) - 1| -0 0
(3 = 0)
+ |1 2V ([ 1])1
(Vn(10, a+11l) + V (1 1]) 1)
1 + - (1 2V (1a44, 1)))
2 1 2 11)+41,1)
(Removing the absolute value)
2u ++1
(Since Bob picked Rt)
In either case, the radius increased by at least much the middle of (113). More precisely, by the induction hypothesis (113), we obtain
|as+1l +
Σ (2u' 1) = larl + Σ (2u'g - 1) + 2u + |a++1| |as
2 0 2u 1+1
(a= 0 and |ar+1 = 1)
2 0.
(u f+1 2 0)
56

---

Note further that
|0441 + Σ (2ug
1) -lar|
(2u'g 1) + 2u
+ |ar+1| 1
S Pr + 2 1+1
(By the induction hypothesis)
13
(pt-1 Pt 2u 1+11
P-+1-
This finishes the proof of the induction for the second case.
If at = 0 and 3r < O, then by Lemma 13 we can consider at and Be instead, which has already been shown above.
In all cases, the inductive step holds. Therefore, by induction principle, (113) holds for all t. Subtracting loel from all three sides of it, obtain
|ayl S E (20 1) B,).
Since Pr: = |as + 13,], this immediately implies the desired bounds.
Now that have bounds the relevant events in terms of a, 8, and P. bound them as functions T' to obtain our final result.
Lemma 19. Let n 2 7. Let t .2....... ,t....,,t in be a sequence of rounds such that for all E [n - following inequality holds:
1] the
Phut 2 Upt.] + 1.
(117)
Then in t > n²
Proof. First, will show by induction that, for i [ni], we have Pt. ii 1. For the base case, Pa Z po = 0, so the inequality trivially holds.
Now assume Pt. 2 i - 1 for some E [n 1] and we will prove that the induction step holds for the case + 1. By (117), observe that
Pe++1
2 [p: +
2 i 1 +1
(i + 1) -
Thus, by the induction principle we have
Pt. i- for i 1, 1....,7
(118)
Now consider an arbitrary i E [n - 1]. Note that Pr.. 2 [et.] + implies Pr.. > Pt. Therefore, by Lemma 14, there must be an axis-crossing round e; among the interval [f;, t441). This is because this is not true, we have Pt,41 Pt. which contradicts Pt.. > Pt., Repeating the same argument for each we conclude that there exists a sequence of rounds C1, C2, ...... Gn-1 each of which is axis-crossing. and satisfies the following inequality for every i E [m 1]:
4 S G < f++1
(119)
In addition, for any E (n - 1]. we observe that
c+1 - (c++ + 1)
2 Pc,+1
(By Lemma 15, with 7 c/1 and C + 1)
2 Pt. - > 2i-3
(By (119))
(By (118))
Slightly rearranging, obtain
G+1 - 2i-2 Vi E In - 1].
(120)
57

---

Combining (119) and (120), we finally obtain
tn h > Cn-1
(By (119))
2
Σ
(0+11 -4)
(1-)
(By (120)
2 n² 7
+
2
For n 2 7, we have In² In 5 10 n² and so in 1 > n² /10, as required.
The following lemma will finally be combined with Lemma 18 to obtain the desired bound for Bob's payoff. Lemma 20. For T 2 the final radius pr satisfies the following:
pT S 22 20TOT.
Proof. Let & 0, and for recursively define be the first round after 4-1 satisfying Pt. 2 [ + 1. Let be the last index of such t; given the time horizon T.
As immediate corollary of Lemma 19, have
S m V10T3.
For T 2 5, this implies that
n S V10T
(121)
By Lemma 14, also know that p can increase by most per round. Furthermore, since La is the last element in the sequence [t.]ie[m). we have < [et..] + 1. Relaxing this slightly, we have
pr S Pt.. + 2
(122)
Therefore, we obtain the following inequalities:
pr 2 + Pt.
(By (122))
n-1
= 2 Σ (pit1 - ps)
(=1
< 2 + 2(n - 1)
(By Lemma 14)
2n
(123)
Putting (121) and (123) together, we obtain
PT S 2V10T,
which finishes the proof the lemma.
Using the above bound on the radius together with Lemma 18, Bob's payoff can now be bounded as follows.
Lemma 21. For T 2 Bob's 's total payoff satisfies:
T
T
T + VITT
10T
<
2
2
t=
'We omit the elementary calculus.
58

---

Proof. We start from the inequality (112). Halving all three sides of (112) for = I and adding T/2. we obtain
T PT
T 1
S
"B S + pT.
2
Using the upper bound pr 2V10T from Lemma 20 gives the desired bounds.
Combined with Lemma 21, Alice's payoff can eventually be bounded using the following lemma, which effectively bounds the summation of Alice and Bob's 's total payoff.
Lemma 22. For T 2 5, the summation of total payoff to Alice and Bob satisfies the following:
T 1OT
(u's + UB) ST VOT.
Proof. Given the time horizon T, let 81, $2, 8/ be the rounds in which Alice cuts at a point other than 1, where k denotes the number of such rounds. These are the only rounds which the total payoff n' + w is not necessarily 1. The total payoff in these rounds can be bounded as
E u + u 2,
for any i [k)] Thus, we obtain
T
T-k k S
U + u S T + k.
Therefore, it suffices to prove that k S V10.
If k < 7, the proof follows as k < 7 107.
Otherwise, have A: 2 For each 8;, let T; be the round after the next axis-crossing round after -1 Consider s; for an arbitrary i E [k]. Due to Lemma 11, if -1 * 0 then Alice cuts at O or 1 round s; which contradicts our definition of round s;. Thus have a, 0. This argument holds for arbitrary i [k], so both
1 and $++1 both a, 0 and ax..1 1 0, there must have been some rounds between s; and 8;+1 1 where Bob picked T. and some where he picked R. Therefore, 3 must have changed sign at least once, so there is another axis-crossing round in between 8; and 81+1 where changed sign. This implies that for every = h 1, the next axis crossing round after should exist at least before 8 1, i.e.,
are axis axis-crossing rounds. Moreover, since
< 8i41 1.
(124)
Due to the monotonicity of p by Lemma 14, for any i E {l....,k - 13 we have
PE 2 Pr.
(By (124))
2 | +
(By Lemma 17)
By Lemma 19, have:
1
(*x - (8) - 1)
k2
(125)
10
Re-arranging (125) and using the fact that 5æ Si T, we obtain k < V10T. This finishes the proof of the case k 2 7, which completes the lemma.
59

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes].
Justification:
We prove all the theorems and propositions that summarized in the abstract.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
It is fine include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes].
The paper clearly states the modelling assumptions under which the theorems and propositions hold. We also suggest few directions for future work in Concluding Remarks.
Justification:
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, c.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-tex system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
60

---

Answer: [Yes]
The main body of the paper has our model, theorem statements, and proof sketches. The formal proofs are in the appendix.
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Question:
Answer: [Yes].
Justification: We included few example trajectories from the fictitious play dynamic. The code is included with the submission. All our results are proved mathematically and the experimental data is purely illustrative.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data provided or not.
the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g.. in the of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
61

---

5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes].
Justification: This is theoretical paper, the paper provides all the proofs for the stated theorems. We also include the code for the fictitious play dynamic, which we illustrate an example trajectory of in the main file.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips cc/
for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https:
/ //nips.cc/ppppp wttppcccppppcccccccccccccccccccc htwpuii/iuuudesssss/////ppeiaail cttegguidde//odeuuniiiiiiiii
CooeeSummii issisni ssisnnolicyy for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA].
Justification: As mentioned above, just included one example trajectory for visualization purposes. Code which generates similar trajectories is included. Our results are not based experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, or as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [NA].
Justification: This is not relevant to our paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emoo bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
62

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: The code included is a very simple dynamical system that can be run on any laptop in a minute or two.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: /ttp://neuuippee
Answer: [Yes]
Justification: We do not propose model, use dataset, or involve human participants. Our theoretical results do not have immediate possibilities for misuse.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: We do not propose a concrete technology. Our idcalized setting does not have any immediate societal applications.
Guidelines:
63

---

The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negatíve societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (c.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: We wrote the paper and the simulation of fictitious play, which is very standard type of dynamic. There is no license or asset used from other sources. We cite all the related papers in the literature that aware of.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
64

---

For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperswi thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA].
Justification: Not applicable.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
65

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
66


Reviews:
[{"review_id": "ix879flgDA", "reviewer": "Reviewer_zKTZ", "summary": "This paper considers the problem of repeated cake cutting among two agents. In this problem the same cake appears at each round and Alice cuts the cake based on her utility function over the cake. Bob has to choose one of the two parts after seeing the cut.\n\nThe authors show that if Bob almost always chooses his preferred piece then Alice can learn his utility function and exploit him. Then they show that in both the sequential and simultaneous settings Alice has an strategy which gives her an average payoff of $1/2-o(1)$. They add a similar bound for Bob in the sequential setting.\n\nAt the end they analyze the fictitious play in this setting and show that the convergence rate is $O(1/\\sqrt T)$.", "questions": "If A and B take turns in cutting the cake, can we see it as two separate instances of this problem?", "limitations": "-", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "The paper considers an interesting classic problem and takes it to the next level. The problem is natural and well motivated. The results are strong and use wide range of techniques. It is well written and easy to follow. They consider a nice problem and draw a complete picture.", "weaknesses": "My main concern is that there are too many results in this paper and basically the body just gives and overview of the paper. Due to the page limit they had to shove everything to the appendix. \nThe related work section is too long. You can include a shorter version in the main body and an extended version in the appendix. This gives you space to bring the preliminaries to the body.\n\nThis is a solid piece of work but I'm not sure if NeurIPS is the right venue for such papers.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review. We will bring the preliminaries in the main body of the paper and shorten related work as necessary to make this possible.\n\nIf Alice and Bob take turns cutting and choosing, the feedback model is richer. Alice observes how Bob behaves (1) as a chooser, thus learning about his preferences observing him in this role, but also (2) as a cutter, which gives her additional information about his preferences through a different feedback model.\n \nFor this reason, we believe the problem you mention is not separable (i.e. it’s not equivalent to running two separate instances of the problem). Formalizing this intuition would take additional analysis; we will mention the question in future work, thank you for suggesting it.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "esWBkPdX32", "reviewer": "Reviewer_6j8m", "summary": "The paper considers a problem of sequential cake cutting. Each day for $T$ days, 2 players, Alice and Bob, must divide the cake. The cake is a unit interval $[0, 1]$ which they each value with some density function that in total adds up to $1$. They have the same preferences across days. The first player, Alice, makes a single cut into two contiguous pieces. Bob chooses left or right. They consider both when Bob first sees the cut and when they act simultaneously.\n\nIdeally, Alice knows Bob's midpoint and can cut right there, and Bob, indifferent between the two pieces, will take the one less valuable for Alice (assuming reasonable tie-breaking). This is the maximum value she can guarantee and is called her Stackelberg value. The paper measures Bob and Alice's performance by regret. Alice's by how far she is off from achieving her Stackelberg at each step, and Bob's from how far off he is from picking the best of the two cuts at each step.\n\nFirst, they show that if Bob always picks the more valuable piece (so has regret 0), then Alice can exploit achieving $O(\\log T)$ regret. If Bob is close to this by having regret $O(T^\\alpha)$ for $\\alpha < 1$, if Alice knows $\\alpha$, she can get regret $O(T^{\\frac{\\alpha + 1}{2}} \\log T)$, and otherwise, she can get regret $O(T/\\log T)$. Neither of these can be improved by polynomial factors.\n\nOn top of these, Alice has a strategy such that no matter what Bob plus, she gets on average $1/2 - o(1)$ and Bob gets $1/2 + o(1)$, and Bob has a strategy such that no matter what Alice plays, he gets $1/2 - o(1)$ and Alice gets $1/2 + o(1)$. If they play simultaneously, Bob also has a randomized strategy so that they both get $1/2$ in expectation (just picking left and right uniformly at random).\n\nFinally, assuming players best respond assuming the other player will pick a random strategy they have played so far, both players will have average payoff approaching 1/2 at a rate of $O(1/\\sqrt{T})$", "questions": "Do you have some real-world motivation where such repeated games with the same players/valuations make sense?", "limitations": "Yes", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- The model is simple but satisfying\n- The results are interesting and presented nicely", "weaknesses": "Although the model is very cute, it's unclear how realistic it is for agents to be playing this exact same game against each other repeatedly.\n\nAlso, there is no field for smaller comments, but you may consider citing \"Playing Divide-and-Choose Given Uncertain Preferences\" from EC'23 which seems relevant to the game-theoretic aspects of cut and choose in cake cutting", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review. \n\nRegarding playing the game repeatedly, a high level scenario is where the salespeople of a roofing company are paid by commission for solar panel installation and maintenance services. Each day, they might divide areas of town among themselves for door-to-door sales. Due to local connections or varying tactics, different salespeople would have different expected profits in different areas.\nMore generally, one can consider daily task allocation in businesses or recurring distribution of computational resources.\n\nThank you for bringing the EC 23 paper on cut-and-choose in a Bayesian setting to our attention. We had seen the paper and thought we had included it, but accidentally forgot to; we will certainly cite and discuss it in the final version.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "onPbVfflqe", "reviewer": "Reviewer_xPAG", "summary": "The paper deal with a repeated division problem where at each round a new cake (modeled as the interval $[0,1]$), identical to previous ones, arrives. Alice acts first and cuts the cake in two parts. Then, Bob chooses the piece he prefers, leaving the remainder for Alice. Alice (resp. Bob) valuation preferences are determined by the integral over her (resp. his) *private* valuation density function over the piece of cake she (resp. he) receives.\nThe authors analyze two versions of this game:\n1) sequential, where Bob sees Alice’s cut before choosing\n2) simultaneous, where Bob chooses without seeing Alice’s cut\nInterestingly, in the sequential setting, the authors shows that if Bob chooses his favorite piece in (a nearly) myopic way, then Alice can exploit this greedy tendency to build a strategy that has sublinear Stackelberg regret. Furthermore, they show how both players can devise strategies that force the other player into a dynamic yielding equitable outcomes for both.", "questions": "What if Alice can select not just a point, but say a pluri-interval and its complement (maybe with a bounded number of pieces known in advance). What if Alice can split the set $[0,1]$ in any measurable set and its complement? Does the problem turn out to be utterly intractable in these cases?", "limitations": "The authors correctly states the assumptions under which their results hold.", "rating": 7, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The writing style of the paper is rigorous, with a clear introduction to the problem and related literature.\nThe relevant definitions and claims are clearly presented in a mathematical fashion.\nThe sequential version of the problem is especially interesting from practical, modeling, mathematical, and philosophical points of view. In particular, it is very insightful that Bob's greedy behavior leads to undesirable outcomes that primarily damage himself, yet both players have a way to enforce fairness.", "weaknesses": "The analysis is limited to the case where the interval $[0,1]$ is split into two sub-intervals $[0,a]$ and $(a,1]$, for any $a \\in [0,1]$ of Alice's choice. This simplification may restrict the applicability of the results to more complex real-world scenarios where resources might need to be divided into more than two parts.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review. The question you raise about more general cutting models is interesting and likely to be tractable for many of them.\n\nFor example, suppose Alice can cut at two points $a_{t,1}$ and $a_{t,2}$ each day $t$ (placing each of the resulting three pieces in one of two bins labeled L and R, respectively). Suppose Bob is myopic, choosing his favorite bin each day.\n\nThen Alice can \n\n- (1) discretize the cake to an $\\epsilon$ grid according to her valuation, and then \n\n- (2) sample Bob’s behavior at each choice of cut points on the $\\epsilon$-grid.\n\nSteps (1-2) can be done in $O(1/\\epsilon \\cdot \\log(1/\\epsilon))$ rounds by checking every possibility for the first cut point on the $\\epsilon$-grid and doing binary search for the second. \nOnce Alice finds the best pair of cut points on the $\\epsilon$-grid (from her perspective), she can cut there for the remainder of time and get within $O(\\epsilon)$ of her Stackelberg value (defined with respect to two cuts) for the rest of the rounds.\nSetting $\\epsilon \\approx 1/\\sqrt{T}$ gives $O(\\sqrt{T} \\cdot \\log(T))$ regret.\n\nFor $n$ cuts, a similar strategy can achieve $O(T^{1-1/n} \\cdot \\log(T))$ regret. \nMaking such intuition precise and extending the analysis to a sublinear-regret Bob are interesting directions for future work.\n\nAllowing Alice to divide the cake into any two measurable sets is also interesting, though our ideas here are much more speculative. Perhaps Alice can still discretize the cake precisely enough to approximate optimal divisions, or maybe a Bob with a sufficiently pathological valuation function could never be completely exploited.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "WIaGyje9ms", "reviewer": "Reviewer_17dK", "summary": "This paper studies the game of repeated cake cutting. The cake is modeled as the unit interval $[0,1]$, and in each round $t \\in \\\\{1,\\ldots,T\\\\}$, player $A$ chooses a point $a_t$ to cut the cake into two pieces $[0,a_t]$ and $(a_t, 1]$, and player $B$ chooses one of the two pieces, either after observing $a_t$ (the sequential setting) or without observing $a_t$ (the simultaneous setting). The paper proves some properties of this game.", "questions": "1. Could valuations be defined more generally as countably additive, instead of just finitely additive? This could allow the analysis to be applicable to more general games where player $A$ could divide up the cake into any two disjoint measurable sets.\n2. Why is equitable allocation called \"fair\"? I could imagine allocation $(Z_A, Z_B)$ to players such that $V_A(Z_A) = 1/3 = V_B(Z_B)$ and thus is equitable, but allocation $(Z_B, Z_A)$ which has $V_A(Z_B) = 1- V_A(Z_A) = 2/3 = 1 - V_B(Z_B) = V_B(Z_A)$ and thus is also equitable and \"fairer\". Should fairness be defined as $V_A(Z_A),V_B(Z_B) \\ge 1/2$?", "limitations": "N/A", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "At a high level, this is a very well-written paper of theoretical nature that is easy to understand. The literature review is exhaustive. It properly defines and proves all the claims. The results proved in the paper seem new to me, and the proofs are elegant. The setting studied is interesting and will be useful to the community.", "weaknesses": "I do not find any obvious weaknesses in this paper. It a paper of theoretical nature and requiring experiments would be meaningless.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review. \n\nFor question 2: Equitability requires that each player gets the same value. As you pointed out, not all equitable allocations are equally good. When $V_A(Z_A) \\geq 1/2$ and $V_B(Z_B) \\geq 1/2$, the allocation is also proportional. Proportionality is a fairness notion that requires that when there are two players, each player gets utility at least $1/2$. Thus in the example you mention, one allocation is equitable but not proportional, and the other one is both equitable and proportional. We will clarify this point.\n\nFor question 1: Yes, the valuation of a player for a measurable set $S$ is generally defined as the integral of that player’s value density function over $S$. We will clarify this.\n\nRegarding the direction of Alice dividing the cake using more than one cut, we include an example that we also wrote for the third reviewer (xPAG). \nSuppose Alice can cut at two points $a_{t,1}$ and $a_{t,2}$ each day $t$ (placing each of the resulting three pieces in one of two bins labeled L and R, respectively). Suppose Bob is myopic, choosing his favorite bin each day.\n\nThen Alice can \n\n(1) discretize the cake to an $\\epsilon$ grid according to her valuation, and then \n\n(2) sample Bob’s behavior at each choice of cut points on the $\\epsilon$-grid.\n\nSteps (1-2) can be done in $O(1/\\epsilon \\cdot \\log(1/\\epsilon))$ rounds by checking every possibility for the first cut point on the $\\epsilon$-grid and using binary search for the second. \nOnce Alice finds the best pair of cut points on the $\\epsilon$-grid (from her perspective), she can cut there for the remainder of time and get within $O(\\epsilon)$ of her Stackelberg value (defined with respect to two cuts) for the rest of the rounds.\nSetting $\\epsilon \\approx 1/\\sqrt{T}$ gives $O(\\sqrt{T} \\cdot \\log(T))$ regret.\n\nFor $n$ cuts, a similar strategy can achieve $O(T^{1-1/n} \\cdot \\log(T))$ regret. \nMaking such intuition precise and extending the analysis to a sublinear-regret Bob are interesting directions for future work.\n\nAllowing Alice to divide the cake into any two measurable sets is also interesting, though our ideas here are much more speculative. Perhaps Alice can still discretize the cake precisely enough to approximate optimal divisions, or maybe a Bob with a sufficiently pathological valuation function could never be completely exploited.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This is a high quality algorithmic game theory paper that was truly appreciated by the reviewers. While the area chair had some doubts about its relevance to the conference itself, the reviewers defended the paper vigorously and convinced AC that the paper deserves to be accetped.
Decision: Accept (poster)