Dueling over Dessert, Mastering the Art of Repeated Cake Cutting

Authors: simina  brânzei
mohammadtaghi  hajiaghayi
reed  phillips
suho  shin
kun  wang
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 19:59:45

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})$.

Main paper: 
 introduction: 
 Cake cutting is a model of fair division Steinhaus (1948) , where the cake is a metaphor for a heterogeneous divisible resource such as 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 players-denoted 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 a 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 simultaneous setting, where both players take their actions at the same time each day, and analyzed the payoffs 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 chosen cut point before making his selection. Tactical considerations remain pivotal in the sequential version, which is none other than the repeated Cut-and-choose protocol with strategic players.A key observation in our study is 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 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. To fight back Alice's 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 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, it requires that Alice's value for her allocation should equal Bob's value for his allocation. Achieving equitability is particularly important in scenarios with potential for conflict, such as splitting an inheritance.We show that achieving equitable outcomes in the repeated interaction is in fact possible. Specifically, each player has a 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 a 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, 1/2) at a rate of O(1/ √ T ).Cake cutting model for two players. The cake is modelled as the interval [0, 1]. There are players N = {A, B}, where A stands for Alice and B for Bob. Each player i has a private value density function v i : [0, 1] → R + . A piece of cake is a measurable set S ⊆ [0, 1]. The value of player i for S is V i (S) = x∈S v i (x) dx. Atoms are worth zero and the valuations are normalized so thatV i ([0, 1]) = 1 ∀i ∈ [n]. We require bounded densities, i.e. there exist fixed arbitrary δ, ∆ > 0 such that δ ≤ v i (x) ≤ ∆ for all x ∈ [0, 1].An allocation Z = (Z A , Z B ) is a partition of the cake among the players such that each player i receives piece Z i , the pieces are disjoint, and i∈N Z i = [0, 1]. The valuation (aka utility or payoff) of player i at an allocation Z is V i (Z i ). An allocation Z is equitable if the players are equally happy with their pieces, meaning V A (Z A ) = V B (Z B ).Let m A be Alice's midpoint of the cake and m B Bob's midpoint. Alice's Stackelberg value, denoted u * A , is the utility she receives when she cuts the cake at m B and Bob chooses his favorite piece, breaking ties in Alice's favor. The midpoints and Alice's Stackelberg value are depicted in Figure 1 . Repeated cake cutting. Each round t = 1, 2, . . . , T , the next steps take place:• A new cake arrives, which is identical to the ones in previous rounds.• Alice cuts the cake at a point a t ∈ [0, 1] of 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 t before choosing left/right, and simultaneous, where he only observes her cut point after making his choice.A pure strategy is a map from the history observed by a player to the next action to play. A mixed strategy is a probability distribution over pure strategies.Our results will examine how players fare in the repeated game over T rounds. Given a history H, Alice's Stackelberg regret is RegA (H) = T t=1 [u * A -u t A (H)],where u * A is Alice's Stackelberg value and u t A (H) is Alice's utility in round t under history H. Suppose Alice uses a mixed strategy S A and Bob uses a mixed strategy S B . Then S A ensures Alice's Stackelberg regret is at most γ against S B if Reg A (H) ≤ γ for all T -round histories H that could have arisen under the strategies (S A , S B ). Precise definitions for strategies/regret and the remaining notation needed for the full proofs can be found in Section 3.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 a small error and then cutting near it for the rest of time. This will lead to Alice getting essentially her Stackelberg value in all but O(log T ) rounds, while Bob will get 1/2 in all but O(log T ) rounds.Proposition 1. If Bob plays myopically in the sequential setting, then Alice has a strategy that ensures her Stackelberg regret is O(log T ).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 in each round. Her Stackelberg regret is a function of Bob's regret guarantee, as quantified in the next theorem.Theorem 1 (Exploiting a nearly myopic Bob). Let α ∈ [0, 1). Suppose Bob plays a strategy that ensures his regret is O(T α ) in the sequential setting. Let B α denote the set of all such Bob strategies.• If Alice knows α, she has a strategy S A = S A (α) that ensures her Stackelberg regret is O(T α+1 2 log T ). The exponent is sharp: Alice's Stackelberg regret is Ω(T α+12 ) for some Bob strategy in B α .• If Alice does not know α, she has a strategy S A that ensures her Stackelberg regret is O T log T . The exponent is sharp: if S A guarantees Alice Stackelberg regret O(T β ) against all Bob strategies in B α for some β ∈ [0, 1), then S A 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, if Bob deterministically commits to picking R, he will be completely exploited by an 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 it impossible for Alice to reliably get her Stackelberg value on every trajectory. For this reason, we focus on the sequential setting when studying how Alice can exploit Bob.1 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 a history H, player i is said to get an average payoff of γ if 1 T T t=1 u t i (H) = γ, where the left hand side is not expected utility, but rather the observed total utility averaged over T rounds.We say a utility profile(u A , u B ) is equitable if u A = u B .In the single round setting, u A and u B will naturally represent the utilities of the players at an allocation. In the repeated setting, u A and u B will represent the time-average utilities of the players.The next theorems show that each player can keep the other player at 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 utility diminishes if other bidders are too satisfied. Theorem 2 (Alice enforcing equitable payoffs; informal). In both the sequential and simultaneous settings, Alice has a pure strategy S A , such that for every Bob strategy S B :• on every trajectory of play, Alice's average payoff is at least 1/2 -o(1), while Bob's averagepayoff is at most 1/2 + o(1). More precisely, u A T ≥ 1 2 -Θ 1 √ T and u B T ≤ 1 2 + Θ 1 ln T, where u i is the cumulative payoff of player i over the time horizon T .A key ingredient in the proof of Theorem 2 is a connection with Blackwell's approachability theorem Blackwell (1956) . Generally speaking, Blackwell approachability can be used by a 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 strategy constructs a countably infinite set of representatives, which allows us to adapt Blackwell's argument to this setting.We show a symmetric theorem for Bob in the sequential setting, while in the simultaneous setting Bob's guarantee only holds in expectation. Theorem 3 (Bob enforcing equitable payoffs; informal).• In the sequential setting: Bob has a pure strategy S B , 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 averagepayoff is at most 1/2 + o(1). More precisely, u B T ≥ 1 2 -1 √ T and u A T ≤ 1 2 + Θ 1 √ T .• In the simultaneous setting: Bob has a mixed strategy S B , such that for every Alice strategy S A , both players have average payoff 1/2 in expectation.When Alice and Bob play such strategies against each other, they approach an 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 is a 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 simultaneous setting, where there is uncertainty for both players due to 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 2 . The convergence properties of fictitious play can be characterized as follows.Theorem 4 (Fictitious Play; informal). When both Alice and Bob run fictitious play, the average payoff of each player converges to 1/2 at a rate of O(1/ √ T ).Roadmap to the paper. Related work is in Section 2. Formal notation and preliminaries can be found in Section 3. An overview of how Alice can exploit a 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 5, with formal proofs in Appendix B. Fictitious play can be found in Section 6, with formal proofs in Appendix C. Concluding remarks can be found in Section 7. 
related work: 
 Cake cutting and fairness notions. The cake cutting model is due to Steinhaus (1948) . Standard fairness notions include proportionality, equitability, envy-freeness (Even and Paz (1984) ; Dubins and Spanier (1961); Edward Su (1999) ; Stromquist (1980) ; Alon (1987) ). For surveys, see Robertson and Webb (1998) ; Brams and Taylor (1996) ; Moulin (2003) ; Brandt et al. (2016) ; Procaccia (2013) .In the Robertson-Webb (RW) query model for cake cutting (Woeginger and Sgall (2007) ), a mediator asks the players enough queries about their preferences until it 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) Mossel and Tamuz (2010); Branzei and Miltersen (2015) studied truthful cake cutting in the RW query model, and Chen et al. (2013) ; Bu et 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 Iaru (2021) . Dynamic fair division. Closest to 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 or may not like the cherry. Alice and Bob declare their actions simultaneously and Alice is only allowed to cut in one of two locations. Additionally, Alice has a prior over the type of Bob she is facing. Aumann and Maschler (1995) analyzes the set of payoffs 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. Exploiting no-regret agents. Several works considered the extent to which one player can exploit the knowledge that the other player has a 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 payoff function. Haghtalab et al. (2022) showed that, for certain types of sequential games, an exploiting leader can approach their Stackelberg value in the limit. Theorem 1 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 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) ). None of these results directly apply to our setting, but the most relevant is Berger (2005) , which covered non-degenerate 2 × n games (i.e. where every action has a unique best response). Our "2 × ∞" game is degenerate, as Bob does not have a unique best response to Alice cutting at m B . 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. 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 at a rate of Ω(T -1/n ) using adversarial tie-breaking rules. Panageas et al. (2023) found examples of even slower convergence. Harris (1998) showed that fictitious play converges at a rate of O(T -1 ) in 2 × 2 zero-sum games. Abernethy et al. (2021) considered diagonal payoff matrices with non-adversarial tie-breaking rules, showing convergence rates of 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 to Alice only being allowed to cut at 0 or 1. This assumption is not as natural in our setting. In fact, if Alice can only cut at 0 or 1 the game becomes zero-sum. Furthermore, we allow arbitrary tie-breaking rules. 
preliminaries: 
 In this section we formally define the notation used in our proofs. All our notation applies to both the sequential and simultaneous settings, unless otherwise stated.History. Recall T is the number of rounds. For each round t ∈ [T ],• let a t ∈ [0, 1] be Alice's cut at time t and b t ∈ {L, R} be Bob's choice at time t, where L stands for the left piece [0, a t ] and R for the right piece [a t , 1].• let A t = (a 1 , . . . , a t ) be the history of cuts until the end of round t and B t = (b 1 , . . . , b t ) the history of choices made by Bob until the end of round t.A history H = (A T , B T ) 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 t is a functionS t A : [0, 1] t-1 × {L, R} t-1 × P × N → [0, 1], such that S t A (A t-1 , B t-1 , v A , T) is the next cut point made by Alice as a function of the history A t-1 of Alice's cuts, the history B t-1 of Bob's choices, Alice's valuation v A , and the horizon T .For Bob, we define pure strategies separately for the sequential and simultaneous settings due to the different feedback that he gets: Sequential: A pure Bob strategy at time t is a map S t B : [0, 1] t × {L, R} t-1 × P × N → {L, R} . That is, Bob observes Alice's cut point and then responds.Simultaneous: A pure Bob strategy at time t is a map S t B : [0, 1] t-1 ×{L, R} t-1 ×P ×N → {L, R} . Thus here Bob chooses L/R before observing Alice's cut point at time t.A pure strategy for Alice over the entire time horizon T is denoted S A = (S 1 A , . . . , S u i = u i (S A , S B ) = T t=1 u t i . The utility of player i from round t 1 to t 2 is u i (t 1 , t 2 ) = t2 t=t1 u t i .The expected utility of player i isE[u i ] = T t=1 E[u t i ],where the expectation is taken over the randomness of the strategies S A and S B .Given a history H, let u t i (H) be player i's utility in round t under H and let u i (H) = T t=1 u t i (H) be player i's cumulative utility under H.Midpoints and Stackelberg value. Let m A ∈ [0, 1] be Alice's midpoint of the cake, with V A ([0, m A ]) = 1/2, and m B ∈ [0, 1] be Bob's midpoint, with V B ([0, m B ]) = 1/2. Since the densities are bounded from below, the midpoint of each player is uniquely defined. Alice's Stackelberg value, denoted u * A , is the utility Alice gets when she cuts at m B and Bob chooses his favorite piece breaking ties in favor of Alice (i.e. taking the piece she prefers less). 
alice exploiting bob: 
 In this section we give an overview of Theorem 1, which considers the sequential setting and quantifies the extent to which Alice can exploit a Bob that has sub-linear regret with respect to 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) for some Bob strategy in B α .Proof sketch. We sketch both the upper and lower bounds.Sketch for the upper bound. Let S B denote Bob's strategy, which guarantees his regret is O(T α ). Suppose Alice knows α. Then Alice initializes an interval I = [0, 1] and uses the following strategy.Iteratively, for i = 0, 1, . . . ,:(1) Alice discretizes the interval I = [u, w] in a constant number of sub-intervals (set to 6) of equal value to her, by cutting at points a i,j for j ∈ [5] such that u < a i,1 < a i,2 < . . . < a i,5 < w. Denote a i,0 = u and a i,6 = w. An illustration is in Figure 3 .Figure 3 : Illustration of step (1) for i = 0. Alice divides the interval [0, 1] in 6 disjoint intervals of equal value to her, demarcated by points a 0,0 = 0 < a 0,1 < a 0,2 < a 0,3 < a 0,4 < a 0,5 < 1 = a 0,6 .(2) Alice selects a number η, which will be set "large enough" as a function of T and α. In the next 5η rounds, Alice cuts an equal number of times at each point a i,j for j ∈ [5]. That is:• In each of the next η rounds, Alice cuts at a i,1 and observes Bob's choices there, computing the majority answer as c i,1 = L if Bob picked the left piece more times than the right piece, and c i,1 = R otherwise. The next η rounds after that Alice switches to cutting at a i,2 , and so on.In this fashion, Alice computes c i,j as Bob's majority answer corresponding to cut point a i,j for all j ∈ [5]. Also, by default c i,0 = R and c i,6 = L. An illustration is in Figure 4 . (3) The points a i,j for j ∈ {0, . . . , 6} are arranged on a line and each is labelled L or R, with the leftmost point a i,0 = 0 labelled R and the rightmost point a i,6 = 1 labelled L. Then there is an index j ∈ {0, . . . , 5} such that c i,j = R and c i,j+1 = L.Alice computes a smaller interval I i+1 , essentially consisting of [a i,j , a i,j+1 ] and some extra space around it to make sure that I i+1 contains Bob's midpoint as follows. If j ∈ {1, . . . , 4}, setI i+1 = [a i,j-1 , a i,j+2 ]. If j = 0, set I i+1 = [a i,0 , a i,3 ]. If j = 5, set I i+1 = [a i,3 , a i,6 ].Then Alice iterates steps (1 -3) on the interval I 1 . An illustration is in Figure 5 .Figure 5 : Illustration of step (3) for i = 0. Alice labels each point a 0,j with the majority answer there. Then she identifies the index j such that the point a 0,j is labelled R and the point a 0,j+1 is labelled L. At this stage she is assured that either the interval [a 0,j , a 0,j+1 ] or one of the adjacent ones contains Bob's midpoint. Alice sets I 1 = [a 0,3 , a 0,6 ] and recurses on it.The full proof explains why the index j from step 3 is unique and why it is in fact necessary to include a slightly larger interval than [a i,j , a i,j+1 ] in the recursion step, due to Bob potentially having lied if his midpoint was very close to a boundary of [a i,j , a i,j+1 ] but on the other side. regret. To avoid accumulating more regret than this, Bob can afterwards revert to picking his truly preferred piece; the damage to Alice's payoff has already been done. Proposition 3. Let α ∈ [0, 1). Suppose Bob plays a strategy that ensures his regret is O(T α ). Let B α denote the set of all such Bob strategies. If Alice does not know α, she has a strategyS A that ensures her Stackelberg regret is O T log T . The exponent is sharp: if S A guarantees Alice Stackelberg regret O(T β ) against all Bob strategies in B α for some β ∈ [0, 1), then S A has Stackelberg regret Ω(T ) for some Bob strategy in B β .Proof sketch. Alice's strategy that achieves O(T / log T ) regret follows the same template as her strategy from Proposition 2. The only difference is that she sets η 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 α in Bob's regret bound, she cannot know when she has true information about Bob's preferences. We use this by having a Bob with O(T β ) regret behave exactly like one with O(T α ) regret but a different midpoint. Then Bob can hide his deception from an Alice with O(T β ) regret since he can tolerate more regret than her.Theorem 1 is implied by Propositions 2 and 3. The players' value densities must be bounded for Theorem 1 to hold; see Remark 1 in Appendix A.2 for a counterexample with unbounded densities. 
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 infinite-Bob issue in two steps. First, Alice defines a countably infinite set V as a stand-in for the full variety of Bobs; V includes arbitrarily good approximations to any valuation.Second, we replace Blackwell's original finite-dimensional space with a countably-infinitedimensional one, where the elements of V are the axes. We define an 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 of the space where all of them have payoffs at most 1/2. In each round, she constructs a 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 to 1/2. We achieve the substantially better bound on Alice's payoff by explicitly including her value density v A in the set V of Bobs, thus eliminating any approximation error.Theorem 3 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 is extremely simple: in each round, randomly select L 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 simultaneous 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 √ T intervals I 1 , . . . , I √ T of equal value to him. He then treats each interval I i as a separate cake, alternating between L and R for the rounds Alice cuts in I i . Alice can still exploit this strategy on a single interval I i , but doing so can only give her an average payoff of1/2 + O(V A (I i )) ∈ 1/2 + O(1/ √ T ).The full proof shows this bound applies for any Alice strategy. 
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 t = 0, . . . , T two quantities called α t and β t . Let α t = r t -ℓ t , where r t is the number of times Bob picked R up to round t and ℓ t is the number of times he picked L. Letβ t = t τ =1 2V B ([0, a τ ]) -1 .The quantities α t and β t control what happens under fictitious play: Alice's decision in round t + 1 is based on α t and Bob's decision in round t + 1 is based on β t . These decisions in turn affect α t+1 and β t+1 , forming a dynamical system that results in a counterclockwise spiral through α-β space. Figure 6 illustrates the sequences α t and β t for the instance in Figure 2 .We define ρ t = |α t | + |β t | and formalize this spiral, by showing that the sequence {ρ} T t=0 is non-decreasing and analyzing the change in (α t , β t ) from round to round. Figure 6 illustrates the parameter ρ t over time, while Figure 7 illustrates the spiral (associated with the same trajectory as in Figure 2 and 6 ), where the spiral is visualized as a scatter plot of the sequence (α t , β t ) t≥1 .We first use these dynamics to bound Bob's payoff. Bob's payoff can be almost directly read off due to changes in β t closely matching changes in Bob's payoff. Bob's total payoff to round t turns out to be of the order t/2 ± ρ t , so bounding the rate at which the spiral expands also bounds Bob's payoff. Figure 7 : Scatter plot of the sequence (α t , β t ) t≥1 , illustrating the spiral for the instance with trajectories shown in Figure 2 , where the sequences α t and β t 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 α t = 0, which happens less and less often as the spiral expands. The players' total payoff when Alice cuts at one end of the cake is 1, so across T rounds we show the sum of cumulative payoffs of the players is of the order T ± Θ( √ T ). Combining the bound on the total payoff with the bound on Bob's payoff gives a bound for Alice's payoff. 
concluding remarks: 
 There are several directions for future work. One direction is to consider a 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 to update their strategies? It 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. Proof. We consider an explore-then-commit 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 approximate midpoint. This leads to Alice getting nearly her Stackelberg value in nearly every round. Figure 8 shows a visualization of a cake instance with Alice and Bob's midpoints, respectively, with Alice's search process. Alice's algorithm is described precisely in Figure 9 .Alice's algorithm when Bob is myopic:Initialization Set ℓ 1 = 0, r 1 = 1 and τ = ln(T ).Exploration For t = 1, 2, . . . , τ :• Cut at a point x t ∈ [ℓ t , r t ] such that V A ([ℓ t , x t ]) = V A ([x t , r t ]). Then observe Bob's action b t . • If b t = L, then set (ℓ t+1 , r t+1 ) = (ℓ t , x t ).• Else if b t = R, then set (ℓ t+1 , r t+1 ) = (x t , r t ).Exploitation For t = τ + 1, . . . , T :• If m A ≤ ℓ τ , then cut at ℓ τ -1/T . • If m A ≥ r τ , then cut at r τ + 1/T . Figure 9: Algorithm A.1We show that Algorithm A.1 in Figure 9 with τ = Θ(ln T ) gives the desired regret bound in several steps.Bob's midpoint lies in the interval [r t , ℓ t ] for all t To this end, we first claim that Bob's midpoint lies in [ℓ t , r t ] at each round t. We proceed by induction on t. The base case is t = 1 clearly holds sinceℓ 1 = 0 and r 1 = 1, so m B ∈ [ℓ 1 , r 1 ]. Suppose that m B ∈ [ℓ t , r t ] for some t ≥ 1. Given that Alice cuts at x t ∈ (ℓ t , r t ), if b t = L, this implies that m B ∈ [ℓ t , x t ]. Hence m B ∈ [ℓ t , x t ] = [ℓ t+1 , r t+1 ].This argument also holds when Bob chooses R. Thus by induction, we conclude thatm B ∈ [ℓ t , r t ] for every t ∈ [T ].Alice's midpoint satisfies m A / ∈ (ℓ t , r t ) for every t ≥ 2 Now, during the execution of the algorithm, we will next show that Alice's midpoint m A satisfies either of m A ≤ ℓ t and m A ≥ r t , i.e., m A / ∈ (ℓ t , r t ) for every t ≥ 2. To see this, recall that in the first round, Alice cutsx 1 = m A . If b 1 = L, then ℓ 2 = 0 and r 2 = m A . In this case, [ℓ 2 , r 2 ] = [0, m A ], so m A / ∈ (ℓ 2 , r 2 ).Afterwards, it still holds since the intervals only shrink, i.e., (ℓ t+1 , r t+1 ) ⊂ (ℓ t , r t ). Similarly, consider the case that b 1 = R. Then, we have ℓ 2 = m A and r 2 = 1.Thus [ℓ 2 , r 2 ] = [m A , 1], which implies that m A / ∈ (ℓ 2 , r 2 ).Again since the intervals (ℓ t , r t ) only shrink, we conclude that m A / ∈ (ℓ t , r t ) for every t ≥ 2.V A ([ℓ t , r t ]) = V A ([ℓ t-1 , r t-1 ])/2 for every t ∈ [T ],as we shrink the interval by cutting a point that equalizes Alice's value for both parts within the interval. This implies thatV A ([ℓ τ , r τ ]) = 2 -τ +1 .Bounding exploitation phase regret In the exploitation phase, due to the observation above, we have two cases: (i) m A ≤ ℓ τ and (ii) m A ≥ r τ . We will prove that in either case, Alice's single-round regret in the exploitation phase is at most 2 -τ +1 + ∆/T .• For the first case of m A ≤ ℓ τ , Alice keeps cutting at ℓ τ -1/T for the rest of rounds as per the algorithm's description. Then, Bob will myopically choose R and Alice will obtainV A ([0, ℓ τ -1/T ]). In this case, we have that m A ≤ m B since m B ∈ [ℓ τ , r τ ].Then, Alice's single-round regret in the exploitation phase is bounded byV A ([0, m B ]) -V A ([0, ℓ τ -1/T ]) = V A ([ℓ τ , m B ]) + V A ([ℓ τ -1/T, ℓ τ ]) ≤ V A ([ℓ τ , r τ ]) + ∆ T = 2 -τ +1 + ∆ T .• Otherwise suppose m A ≥ 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 havem A ≥ m B since m B ∈ [ℓ τ , r τ ].Similarly, Alice's single-round regret can be upper-bounded byV A ([m B , 1]) -V A ([r τ + 1/T, 1]) = V A ([m B , r τ ]) + V A ([r τ , r τ + 1/T ]) ≤ V A ([ℓ τ , r τ ]) + ∆ T = 2 -τ +1 + ∆ T .Hence in both cases, Alice's single-round regret in the exploitation phase is at most 2 -τ +1 + ∆/T .Final regret bound Overall, by simply upper-bounding Alice's single-round regret in the exploration phase by 1, we obtain the following upper bound for the total regret:τ • 1 + (T -τ ) • 2 -τ +1 + ∆ T .Plugging τ = ln(T ), we obtain the regret bound of O(ln T ), which completes the proof.3 A.2 Appendix: Exploiting a Nearly Myopic BobIn this section we prove Theorem 1, which explains the payoffs achievable by Alice when Bob has a strategy with sub-linear regret. We restate it here for reference.Restatement of Theorem 1 (Exploiting a nearly myopic Bob). Let α ∈ [0, 1). Suppose Bob plays a strategy that ensures his regret is O(T α ). Let B α denote the set of all such Bob strategies.• If Alice knows α, she has a strategyS A = S A (α) that ensures her Stackelberg regret is O T α+1 2 log T . The exponent is sharp: Alice's Stackelberg regret is Ω T α+1 2for some Bob strategy in B α . In particular, if • Bob's strategy has regret at most rf (T ), for some r > 0; and • T is large enough so that T > exp 4r∆ δ and f (T ) < T (ln T ) 2 ; then Alice's payoff satisfies:u A ≥ T • u * A - 5 ln 2 + 6 f (T ) • T ln T .Before proving the proposition, we present the algorithm that Alice will run to beat a Bob with a regret guarantee of O(f (T )).Alice's strategy when Bob's regret is at most r • f (T ), for some constant r > 0:Informational assumption: Alice needs to know f and T , but not r.Initialization Definex 0 = 0; y 0 = 1; η = ⌈ f (T ) • T ⌉; n = ⌊-log 2 3 f (T )/T ln T ⌋ .Exploration For i = 0, 1, . . . , n -1:• Step 1: Set a i,0 = x i and a i,6 = y i . For j ∈ [5], let a i,j be the point withV A ([x i , a i,j ]) = j 6 V A ([x i , y i ]) .•Step 2: For j ∈ [5]:-Cut at a i,j for η rounds. Define c i,j = L if the majority of Bob's answers were left when the cut point was a i,j , and c i,j = R otherwise. • Step 3:(3.a):If c i,j = L ∀j ∈ [5], then set x i+1 = x i and y i+1 = a i,3 . (3.b): If c i,j = R ∀j ∈ [5], then set x i+1 = a i,3 and y i+1 = y i .(3.c): Else, there exists a unique k ∈ [4] such that c i,j = R for all j ≤ k and c i,j = L for all j > k. Set x i+1 = a i,k-1 and y i+1 = a i,k+2 .Exploitation For the rest of the rounds, Alice cuts at χ based on the following cases: 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 to his midpoint. We overcome this challenge by having Alice's algorithm stay far enough from m B so that Bob is forced to answer truthfully most of the time.χ =    x n m A < x n y n m A > y n m A m A ∈ [x n , y n ].Notation. Let w = f (T )/T ln T . Then n = ⌊-log 2 (3w)⌋. Since f (T ) < T (ln T ) 2 by the assumption in the proposition statement, we have w < 1 and thereby n ≥ 0. Also recall the proposition statement assumes that Bob's strategy guarantees him a regret of at most rf (T ) for some r > 0. Moreover, T was chosen such that T > exp 4r∆ δ . Consider the Alice strategy described in Algorithm A.2 (Fig. 10 ). By Lemma 1, the exploration phase in Alice's strategy is well-defined.Next we derive some useful observations and then combine them to upper-bound Alice's regret. Then, we obtainV A (INTV[χ, m B ]) ≤ V A ([x n , y n ]) (By definition of χ) = 2 -n (By property 2 of Lemma 2) ≤ 2 log 2 (3w)+1(Plugging in n and using -⌊-x⌋ ≤ x + 1 )EQUATIONwhere 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 χ:(a) If χ = x n then m A < x n . Thus x n ̸ = 0, so V B ([χ, m B ]) > r f (T )/T by Lemma 2. SinceBob's regret is at most rf (T ), it follows that Bob takes the wrong piece at most1 2 f (T ) • T times. (b) If χ = y n then m A > y n . Thus y n ̸ = 1, so V B ([m B , χ]) > r f (T )/T by Lemma 2. SinceBob's regret is at most rf (T ), it follows that Bob takes the wrong piece at most 1 2 f (T ) • T times.(c) If χ = m A , then there is 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 at most n•5 f (T ) • T , since that is the length of the exploration phase. In the exploitation phase, the regret comes from two sources:• The gap between χ and m B , which is bounded in equation ( 1).• The rounds in the exploitation phase in which Bob chooses his least favorite piece. There are at most 1 2 f (T ) • T such rounds by cases (a-c). Thus Alice's cumulative regret due to these rounds is also at most 1 2 f (T ) • T . Then Alice's overall regret is at most:n • 5 f (T ) • T + T •6 f (T )/T ln T + 1 2 f (T ) • T ≤n • 10 f (T ) • T + T • 6 f (T )/T ln T + 1 2 f (T ) • T (Since ⌈x⌉ ≤ 2x ∀x ≥ 1) ≤ 5 ln 2 + 6 f (T ) • T ln T, (Plugging in n and rearranging) which is O f (T ) • T ln T .This completes the proof.The following lemma shows that the exploration phase is well-defined. Lemma 1. Alice's 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 k ∈ [4] such that c i,j = R ∀j ≤ k and c i,j = L ∀j > k.(ii) For each j ∈ [5], define ci,j = L if Bob prefers [0, a i,j ] to [a i,j , 1] and ci,j = R otherwise. If there exists j ∈ [5] such that ci,j ̸ = c i,j , then m B ∈ (a i,j-1 , a i,j+1 ).(iii) For all i ∈ {0, . . . , n -1} and j ∈ {0, 1, . . . , 5}, we have V B ([a i,j , a i,j+1 ]) > 2r f (T )/T .Proof. We prove each of the parts (i -iii) required by the lemma.Proof of part (iii). Let j ∈ {0, . . . , 5}. Bob's valuation for the interval [a i,j , a i,j+1 ] can be lower bounded as follows:EQUATIONBy definition, Alice's strategy halves the cake interval considered with each iteration i ∈ {0, . . . , n -1}, that is:V A ([x i , y i ]) = 1/2 • V A ([x i-1 , y i-1 ]). Thus V A ([x i , y i ]) = 2 -i and 2 -i ≥ 2 -nfor all i ∈ {0, . . . , n}. Combining these observations with inequality (2), we obtainEQUATIONEQUATIONCombining inequalities (3) and ( 4), we conclude thatEQUATIONThis concludes the proof of part (iii).Proof of parts (i) and (ii). For each i = 0, . . . , n -1, we will show that at most one of the majority answers c i,j , for j ∈ [5], is different from Bob's truthful response.To be precise, recall from the lemma statement that ci,j ∈ {L, R} is Bob's truthful response that maximizes his value when Alice cut at a i,j .DefineEQUATIONLet INTV[x, y] denote the interval [x, y] if y ≥ x and [y, x] if x > y. If j ∈ S i , it must be the case that Bob picked the wrong piece in at least 1 2 f (T ) • T rounds in which the cut was a i,j . Then Bob accumulated at leastV B (INTV[m B , a i,j ]) regret in each such round. Let ℓ ∈ [4]. We have 1 2 f (T ) • T j∈Si V B (INTV[m B , a i,j ]) ≤ r • f (T ) (Since Bob's total regret is at most r • f (T )) < 1 2 V B ([a i,ℓ , a i,ℓ+1 ]) f (T ) • T .(By (5))Dividing both sides byEQUATIONWe show that |S i | ≤ 1. Suppose towards a contradiction that |S i | > 1, meaning there exist indices j, ℓ ∈ S i with j ̸ = ℓ. ThenINTV[a i,j , a i,ℓ ] ⊆ (INTV[m B , a i,j ] ∪ INTV[m B , a i,ℓ ]) .This implies thatEQUATIONwhich contradicts (7). Thus the assumption was false and |S i | ≤ 1.For any j ∈ S i , we must have either m B ∈ (a i,j-1 , a i,j ] or m B ∈ [a i,j , a i,j+1 ), as otherwise ( 7) would be violated. Therefore, if ci,j ̸ = c i,j for some j ∈ [5], then m B ∈ (a i,j-1 , a i,j+1 ). This is part (ii) required by the lemma.Finally, we prove part (i). We will show there exists a unique k ∈ [4] such that c i,j = R ∀j ≤ k and c i,j = L ∀j > k. The proof considers two cases:• Case |S i | = 0. Then every c i,j truthfully reflects Bob's preferences:EQUATIONc i,j = L if a i,j > m B ; c i,j ∈ {L, R} if a i,j = m B .An illustration can be seen in Figure 11 . In all cases, there is a single switch from R to L, and so the index k is unique. In this example, the majority answer at each cut point is consistent with Bob's true preference.• Case |S i | = 1. Then all but one of the c i,j 's truthfully reflect Bob's preferences. An illustration can be seen in Figure 12 . In this example, the majority answer at each cut point is consistent with Bob's true preference except for cut point a 0,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 an index j with the property m B ∈ (a i,j-1 , a i,j+1 ). But then c i,ℓ = ci,ℓ = R for ℓ ≤ j -1 and c i,ℓ = ci,ℓ = L for ℓ ≥ j + 1, so regardless of c i,j there will be a single switch from R to L.This concludes that the conditions for c i,j in Step 3.c hold if the conditions in steps 3.a and 3.b do not. This concludes the proof of part (i).The following lemma further reveals several properties of the constructed intervals during the execution of the algorithm. Lemma 2. In the exploration phase of Algorithm A.2 (Fig. 10 ), Alice constructs a sequence of intervals[x 0 , y 0 ], [x 1 , y 1 ], . . . , [x n , y n ]such that the following properties hold:• Property 1: x 0 = 0 and y 0 = 1,• Property 2: V A ([x i+1 , y i+1 ]) = 1 2 V A ([x i , y i ]) for i = 0, . . . , n -1, • Property 3: m B ∈ [x i , y i ], for all i,• Property 4:If x i ̸ = 0, then V B ([x i , m B ]) > r f (T )/T . • Property 5: If y i ̸ = 1, then V B ([m B , y i ]) > r f (T )/T .Proof. Property 1 holds since [x 0 , y 0 ] = [0, 1] by definition of the algorithm.Property 2 follows from our choice of x i+1 and y i+1 always ensuring that [x i+1 , y i+1 ] contains 3 of the 6 intervals of equal value the a i,j divide [x i , y i ] into.We will show Properties 3-5 by induction. The base case is i = 0. Then [x 0 , y 0 ] = [0, 1]. Properties 3-5 are vacuously true for this interval.Assume that Properties 3-5 hold for i ∈ {0, 1, . . . , n -1}. For each j ∈ [5], let ci,j represent Bob's truthful answer when the cut point is a i,j . Formally, we have ci,j = L if Bob prefers [0, a i,j ] to [a i,j , 1] and ci,j = R otherwise.We show Properties 3-5 also hold for i + 1 by considering the next three cases:Case c i,j = L for all j. In this case, the majority of Bob's answers is L at each cut point used byAlice. An illustration can be seen in Figure 13 . Then the algorithm recurses in the interval [x i+1 , y i+1 ] given by x i+1 = x i and y i+1 = a i,3 . By Lemma 1, we have ci,j = c i,j for each of j ∈ {2, 3, 4, 5}, as otherwise Bob's "true" preferences would alternate between R and L more than once.We claim that m B ∈ [x i , a i,2 ). To see this, consider two cases:• Case ci,1 = c i,1 : then m B ∈ [x i , a i,1] since the majority answers are consistent with Bob's true preference.• Case ci,1 ̸ = c i,1 : then m B ∈ (x i , a i,2 ) by Lemma 1.Then m B ∈ [x i , a i,2 ) ⊂ [x i+1 , y i+1 ], which proves Property 3 for i + 1.If x i+1 = 0, then Property 4 vacuously follows. Otherwise, we have x i+1 = x i . Then by the inductive hypothesis we obtainV B ([x i+1 , m B ]) = V B ([x i , m B ]) > r f (T )/T . Thus Property 4 holds for i + 1 as well. Since m B ∈ [x i , a i,2 ), we have V B ([m B , y i+1 ]) ≥ V B ([a i,2 , a i,3 ]) > 2r f (T )/T ,and so Property 5 holds for i + 1.Case c i,j = R for all j. In this case, the majority of Bob's answers is R at each cut point used byAlice. An illustration can be seen in Figure 14 . Then the algorithm recurses in the interval [x i+1 , y i+1 ] given by x i+1 = a i,3 and y i+1 = y i . By Lemma 1, we have ci,j = c i,j for each of j ∈ {1, 2, 3, 4}.We claim that m B ∈ (a i,4 , y i ]. To see this, consider two cases:• Case ci,5 = c i,5 : then m B ∈ [a i,5 , y i ] since the majority answers are consistent with Bob's true preference. • Case ci,5 ̸ = c i,5 : then m B ∈ (a i,4 , y i ) by Lemma 1.Then m B ∈ (a i,4 , y i ] ⊂ [x i+1 , y i+1 ], which proves Property 3 for i + 1.Since m B ∈ (a i,4 , y i ], we have Case where there is a transition from R to L and the last R is c i,k for some k ∈ {1, . . . , 4}. An illustration can be seen in Figure 15 . Figure 15 : Illustration of Alice's initial cuts for i = 0. In this example, there is a transition from R to L in the interval [a 0,2 , a 0,3 ]. Then the algorithm recurses in the interval [a 0,1 , a 0,4 ], which is guaranteed to contain Bob's midpoint.V B ([x i+1 , m B ]) ≥ V B ([a i,In this case, Alice recurses on the interval [x i+1 , y i+1 ] given by x i+1 = a i,k-1 and y i+1 = a i,k+2 .If any of the c i,j differ from the ci,j , it must be c i,k or c i,k+1 because otherwise Bob's true preferences would alternate between R and L more than once, which is impossible. We consider three sub-cases:1. Case ci,k ̸ = c i,k . Each time Bob picked his less-preferred piece when Alice cut at a i,k , he lost 2V B (INTV[a i,k , m B ]) in value compared to his regret benchmark. Since ci,k ̸ = c i,k , he did so at least 1 2 f (T ) • T times. In order to have regret at most rf (T ), he must haveEQUATIONBy Lemma 1, we haveEQUATIONandEQUATIONCombining equations ( 9), (10), and ( 11) we obtainV B ([x i+1 , m B ]) = V B ([a i,k-1 , m B ]) (Since x i+1 = a i,k-1 ) ≥ V B ([a i,k-1 , a i,k ]) -V B (INTV[a i,k , m B ]) (Since m B > a i,k-1 by (10)) > r f (T )/T .(By ( 9) and ( 11))Thus V B ([x i+1 , m B ]) > r f (T )/T , so Property 4 holds for i + 1. Since m B ∈ (a i,k-1 , a i,k+1 ), we have V B ([m B , y i+1 ]) ≥ V B ([a i,k+1 , a i,k+2 ]) > 2r f (T )/T ,proving Property 5 for i + 1.Case ci,k+1 ̸ = c i,k+1 . Each time Bob picked his less-preferred piece when Alice cut at a i,k+1 , he lost 2V B (INTV[a i,k+1 , m B ]) in value compared to his regret benchmark. Since ci,k+1 ̸ = c i,k+1 , he did so at least 1 2 f (T ) • T times. In order to have regret at most rf (T ), he must haveEQUATION)By Lemma 1, we haveEQUATIONandEQUATION)Combining equations ( 12), ( 13), and ( 14) we obtainV B ([m B , y i+1 ]) = V B ([m B , a i,k+2 ]) (Since y i+1 = a i,k+2 ) ≥ V B ([a i,k+1 , a i,k+2 ]) -V B (INTV[a i,k+1 , m B ])(Since m B < a i,k+2 by ( 13))> r f (T )/T . (By ( 12) and ( 14))Thus V B ([m B , y i+1 ]) > r f (T )/T , so Property 5 holds for i + 1.Since m B ∈ (a i,k , a i,k+2 ), we haveV B ([x i+1 , m B ]) ≥ V B ([a i,k-1 , a i,k ]) > 2r f (T )/T ,which proves Property 4 for i + 1.Case ci,j = c i,j for all j ∈ [5]. Then m B ∈ [a i,k , a i,k+1 ]. By Lemma 1, we haveV B ([x i , m B ]) ≥ V B ([x i , a i,k ]) = V B ([a i,k-1 , a i,k ]) > 2r f (T )/T (15)andEQUATION)Inequality (15) implies Property 4 for i + 1, while inequality (16) implies Property 5 for i + 1.In all three cases, m B ∈ [a i,k-1 , a i,k+2 ] = [x i+1 , y i+1 ],showing Property 3 for i + 1.Thus, in all three cases, Properties 3-5 hold for i + 1. By induction, they hold for all i ∈ {0, 1, . . . , n}. This completes the proof.Proposition 5. Let v A be an arbitrary Alice density and α ∈ [0, 1). Then there exists a value density function ṽB = ṽB (v A ) and strategySB = SB (v A , α) that ensures Bob's regret is O(T α ) while Alice's Stackelberg regret is Ω T α+1 2 .Proof. At a high level, the Bob we construct will behave as if his midpoint were at m B -T α-12 . If Alice calls his bluff, i.e. cuts close to m B "enough" times, then Bob reverts to being honest by actually selecting his preferred piece.Formally, let y be an arbitrary point such that y > m A . Define the Bob value density ṽB as follows:EQUATIONBob's value density ṽB is bounded since y is a fixed constant. Moreover, Bob's midpoint m B is exactly at y. Let SB be Bob's strategy as defined in Figure 16 .Bob strategy SB : times, and this only happens when Alice cuts in the intervalInput: α. Initialize c = 0. For t ∈ [T ]: • If m B < a t ≤ 1 then play b t = L. • If 0 ≤ a t < m B -T α-1 2 then play b t = R. • If m B -T α-1 2 ≤ a t ≤ m B then: If c ≥ T α+1 2 then play b t = R; Else, play b t = L. Update c ← c + 1.EQUATION)Since the density ṽB is bounded from above by a constant, Bob gives up a value of at most O(T α-12 ) in each such round. Thus Bob's regret is O(T α ). Now let us compute Alice's regret with respect to her Stackelberg value. Suppose that T is sufficiently large, so that m B -T α-1 2 > m A . There are two cases depending on whether Alice triggers the switch in Bob's strategy or not. times Alice cuts in P . Whenever Alice cuts at some point x ∈ P , her utility will be V A ([x, 1]) since Bob plays L. Therefore, her payoff in that round is maximized when x is minimized, which occurs at the left-hand endpointx = m B -T α-1 2 . However, m B -T α-1 2 > m A ,and soEQUATION)Then her Stackelberg regret over all the rounds in which she cuts in P is at leastT α+1 2 • V A ([0, m B ]) -V A m B -T α-1 2 , 1 > T α+1 2 • V A ([0, m A ]) + V A ([m A , m B ]) - 1 2 = T α+1 2 V A ([m A , m B ]) ∈ Ω T α+1 2.• Alice cuts in P fewer than T α+1 2times. In this case, we will show that Alice's payoff per round cannot be more thanV A 0, m B -T α-1 2. To see this, we consider two sub-cases.If Alice cuts at a point x < m B -T α-1 2 , then Bob picks R and Alice's utility in that round isEQUATION)If Alice cuts at a point x ≥ m B -T α-1 2 , then Bob picks L and Alice's utility in that round isEQUATION)Combining ( 20) and ( 21), we obtain that in each round t ∈ [T ], Alice's utility isEQUATION)Summing over all rounds t ∈ [T ], we obtain that Alice's Stackelberg regret isEQUATION)Thus in both cases, Alice's Stackelberg regret is at least Ω T α+1 2, which concludes the proof.Lemma 3. Let α, β ∈ [0, 1). Suppose Alice's density is v A and her strategy is S A . There exists a Bob Bob 1 = (v B,1 , S B,1 ) that depends on v A and a Bob Bob 2 = (v B,2 , S B,2 ) that depends on v A and S A , such that• Bob 1 has regret O(T α ) (i.e. strategy S B,1 ensures that a player with density v B,1 has regret O(T α ))• Bob 2 has regret O(T β ); and• if S A ensures Alice Stackelberg regret of O(T β ) against Bob 1 , then S A has regret at least T /6 against Bob 2 .Proof. Let x be the cake position such that V A ([0, x]) = 2/3, and let y be the cake position such that V A ([0, y]) = 5/6. The first Bob, Bob 1 , will have a valuation function v B,1 that has midpoint x. We define Bob 1 's strategy S B,1 so that it truthfully picks his preferred piece, i.e.,EQUATION)Against Bob 1 , Alice's Stackelberg value is 2/3. Suppose S A ensures Alice Stackelberg regret at most rT β against Bob 1 for some r > 0.Then we define our second Bob, denoted Bob 2 , having a valuation function v B,2 which has a midpoint at y. Let k(t) be the number of times Alice cuts in the interval (x, y] in rounds {1, . . . , t}. Then Bob 2 's strategy will be defined as follows:EQUATIONIntuitively, S B,2 switches to being honest after Alice cuts in (x, y] sufficiently many times. This transition gives Bob 2 a regret guarantee of O(T β ).When Alice plays S A against Bob 1 , her total payoff isEQUATIONHowever, every round she cuts in (x, y], her payoff is less than 1/3. Therefore, against Bob 1 , her total payoff can also be bounded byEQUATION)Combining inequalities ( 28) and ( 29), we obtainEQUATION)By definition, strategy S B,2 behaves the same as strategy S B,1 when k(T ) ≤ 3rT β . By (30), we have k(T ) ≤ 3rT β when Alice uses strategy S A . Thus, if Alice uses strategy S A , then Bob 1 and Bob 2 behave exactly the same way. Therefore, Alice receives no more than 2/3 per round against Bob 2 , so her regret is at least T /6 ∈ Ω(T ).If Bob's density is not lower bounded by any constant, then Theorem 1 fails as shown in the next remark.Remark 1. Let α ∈ (0, 1). There exist value densities v A and v B , wherev A (x) ∈ [δ, ∆] ∀x ∈ [0, 1] and v B (x) ∈ (0, ∆] ∀x ∈ [0, 1]such that Bob has a strategy S B which guarantees his regret is at most T α and Alice's Stackelberg regret is at least Ω(T / log T ), no matter what strategy she uses.Proof. The specific valuations will be defined in terms of cumulative valuations. Let Alice's valuation be:V A ([0, x]) = 1 2 x if x ∈ [0, 1/2] 3 2 x -1 2 if x ∈ (1/2, 1]Let Bob's valuation be:EQUATIONIntuitively, Alice has a well-behaved piecewise uniform density with midpoint m A = 2/3. Bob's density is well-behaved for x ≤ 1/2, but the density rapidly approaches zero just to the right of x = 1/2.This appendix has two parts. In Appendix B.1, 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 payoffs.In this section we prove Theorem 2, the statement of which is included next.Restatement of Theorem 2 (Alice enforcing equitable payoffs; formal). In both the sequential and simultaneous settings, Alice has a pure strategy S A , such that for every Bob strategy S B :• on every trajectory of play, Alice's average payoff is at least 1/2 -o(1), while Bob's average payoff is at most 1/2 + o(1). More precisely, for all t ∈ {3, . . . , T }:EQUATIONrecalling that ∆ is the upper bound on the players' value densities.Moreover, even if Bob's value density is unbounded, his average payoff 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 5 (Set of valuations W n ). For each n ∈ N * , we define the following set of non-decreasing piecewise linear functions with n pieces:EQUATIONf (x) = f i n + x - i n f i + 1 n -f i n ∀i ∈ {0, . . . , n -1} ∀x ∈ i n , i + 1 n .Definition 6 (Set of functions V n ). For each n ∈ N * , recall W n was given in Definition 5 and define V n as the following set of functions:V n = W n if n ̸ = 2 W 2 ∪ {f A } if n = 2, where f A : [0, 1] → [0, 1] is the function f A (x) = V A ([0, x]). Definition 7 (The set V). Let V = ∞ n=1 {(n, V ) : V ∈ V n }, where V n is given by Definition 6. Remark 2. By construction, for each n ∈ N * , every function f ∈ V n is non-decreasing.For each n ∈ N * , W n contains the nondecreasing piecewise linear functions through a grid with spacing 1/n. For large n, then, W n should contain approximations to any given function accurate to roughly O(1/n).If Alice bases her strategy on limiting the payoff of the Bobs in each W n , then she will limit Bob's payoff but not necessarily guarantee herself a very good payoff. The inclusion of Alice's valuation function in V rectifies this, allowing us to show a much tighter bound on Alice's payoff.To formalize the ability of the elements of the V n to approximate arbitrary valuation functions, we prove the following three lemmas. The first of them (Lemma 4) is somewhat technical, but most directly shows the richness of the V n . It will be used to prove Lemmas 5 and 6, which will be used directly to bound the payoff of an unbounded-density and bounded-density Bob, respectively. Lemma 4. Let f : [0, 1] → [0, 1] be continuous and increasing with f (0) = 0 and f (1) = 1. Suppose there exist n ∈ N * and ε ∈ (0, ∞) such thatEQUATION)Then there exists V n ∈ V n , where V n is the set of functions from Definition 6, such that|f (x) -V n (x)| ≤ ε + 2/n ∀x ∈ [0, 1].Proof. For x ∈ R, let ⌊x⌉ denote the nearest integer to x, breaking ties in favor of ⌈x⌉ when x = ⌊x⌋ + 1/2.Recall the set of functions W n from Definition 5. Let V n be the function in W n such that:EQUATIONThen we claim the function V n approximates well the function f at the points i/n, that is:EQUATIONwhere• for i ∈ [n -1]the inequality in (36) follows from (35);• for i = 0 it follows from V n (0) = 0 = f (0), and• for i = n it follows from V n (1) = 1 = f (1). Let x ∈ [0, 1].We show three inequalities next:1. By inequality (34) from the lemma statement with parameters ⌊xn⌋/n and ⌈xn⌉/n, we getEQUATION2. By inequality (36) with i = ⌈xn⌉, we haveEQUATION3. By inequality (36) with i = ⌊xn⌋, we haveEQUATIONSumming up inequalities (37), ( 38), (39) and applying the triangle inequality, we obtainEQUATIONWe obtainV n ⌊xn⌋ n - 1 2n ≤ f ⌊xn⌋ n (By (36) with i = ⌊xn⌋) ≤ f (x) (Since f is non-decreasing) ≤ f ⌈xn⌉ n (Since f is non-decreasing) ≤ V n ⌈xn⌉ n + 1 2n .(By (36) with i = ⌈xn⌉)Denoting J = V n ⌊xn⌋ n -1/(2n), V n ⌈xn⌉ n+ 1/(2n) , we conclude that f (x) ∈ J. Since the function V n is non-decreasing by Remark 2, we haveEQUATION) Thus V n (x) ∈ J. Since both f (x) ∈ J and V n (x) ∈ J, we can bound |f (x) -V n (x)| as follows: |f (x) -V n (x)| ≤ |J| = V n ⌈xn⌉ n + 1 2n -V n ⌊xn⌋ n - 1 2n ≤ ε + 2 n . (Since V n ⌈xn⌉ n -V n ⌊xn⌋ n ≤ ε + 1/n by (40))Since this holds for all x ∈ [0, 1], the function V n required by the lemma exists.Lemma 5. Let f : [0, 1] → [0, 1] be continuous and increasing with f (0) = 0 and f (1) = 1. For each ε > 0, there exists n ∈ N * and a function V n ∈ V n such thatEQUATIONrecalling that the set of functions V n is given by Definition 6.Proof. Let ϵ > 0. Since f is continuous and increasing, its inverse f -1 is also continuous and increasing. Since f (0) = 0 and f (1) = 1, we haveEQUATIONSince f -1 is continuous and bounded over a closed interval, so is the function g. Therefore, by the extreme value theorem, g attains a global minimum value δ * . Since f -1 is strictly increasing, g is never zero, soEQUATIONSince we will analyze g(f (x)), it will be useful to define the set of values x for which g(f (x)) is well defined, that is:EQUATIONSince δ * is a global minimum of g, we haveEQUATIONUsing the definition of g (equation ( 43)) in (46) yieldsEQUATIONEQUATIONApplying f to both sides of (48) and using monotonicity of f , we obtain f (x) + ε/4 ≥ f (x + δ * ) for all x ∈ S ε , or equivalentlyEQUATIONSince ε > 0 and δ * > 0 by ( 44), there exists n ∈ N such thatEQUATIONNote that because the range of f -1 is [0, 1], the left side of ( 48) is at most 1. Therefore, from (48) and the fact that δ * > 1/n by (50):EQUATIONConsider an arbitrary x, y ∈ [0, 1] with x ≤ y ≤ x + 1/n. We consider two cases:• Case x ∈ S ε : Since f is strictly increasing and x + δ * ≤ 1 by (51), we have:EQUATIONSubtracting f (x) from both sides of (52) and applying (49), we obtainEQUATIONFix an arbitrary ε > 0 and x ∈ [0, 1]. Choose δ = ε/2. For any y such that |y -x| < δ:|P ′ (G y , Z) -P ′ (G x , Z)| = |P ′ (G y -G x , Z)| (By property (5)) = ∞ n=1 1 2 n |V n | V ∈Wn (V (y) -V (x))Z(n, V ) ≤ ∞ n=1 1 2 n |V n | V ∈Wn |V (y) -V (x)| • |Z(n, V )| (Triangle inequality) ≤ ∞ n=1 1 2 n |V n | V ∈Wn n|y -x| • 1 (By ineq (60) and Z ≤ 1) ≤ |y -x| ∞ n=1 n 2 n (Since |W n | ≤ |V n |) = |y -x| • 2 < 2δ (By choice of δ) = ε .Therefore, for all x ∈ [0, 1]:lim y→x P ′ (G y , Z) = P ′ (G x , Z),which is the definition of P ′ (G x , Z) being continuous in x. This concludes thatP (G x , Z) is continuous in x.Finally, the last one is a strengthening of Lemma 1 from Blackwell (1956) , under stronger hypotheses.Lemma 10. Suppose a sequence of nonnegative values δ 1 , δ 2 , . . . satisfies, for all t ≥ 1:δ t+1 ≤ 1 (t + 1) 2 + t -1 t + 1 δ t .Then lim t→∞ δ t = 0. In particular, for all t ≥ 2:δ t ≤ 1 t(t -1) t i=2 i -1 i ≤ 1 t .Proof. The latter bound will be shown by induction. As a base case, consider t = 2. The condition for t = 1 gives:EQUATIONSo the base case holds. Now suppose the conclusion holds for some t ≥ 2. Assume that the claim holds for δ t . We can expand the upper bound of δ t+1 as follows.EQUATIONFor each round t, let δ t be the distance from S to U t , defined as:EQUATIONFor t < T , let Y t : V → [-1/2, 1/2] be the function defined by:Y t (n, V ) = min{0, U t (n, V )}By Claim 3, we have δ t ≤ 1/t for all t ≥ 2. Now we will show that this strategy guarantees that, for any Bob's valuation function v B and any strategy S B Bob employs, his average payoff is at most 1/2. Consider an 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 5. Consider N, T ∈ N * such that• N is such that there existsV ′ ∈ V N with |V ′ (x) -V B ([0, x])| < ε/2 for all x ∈ [0, 1].• T is sufficiently large so thatEQUATIONFor example, takingT = 4•2 N |V N | ε 2would suffice.We will show that for each t ≥ T , we haveU t (N, V ′ ) < ε/2. This trivially holds if U t (N, V ′ ) ≤ 0, so assume U t (N, V ′ ) > 0.We then obtainEQUATIONwhere (68) follows from the fact that Y t (N, V ′ ) = min{0, U t (N, V ′ )} = 0. Using (68), we can upper bound U t (N, V ′ ) as follows:U t (N, V ′ ) ≤ 2 N |V N | ∞ n=1 1 2 n |V n | V ∈Vn U t (n, V ) -Y t (n, V ) 2 = 2 N |V N |P (U t -Y t , U t -Y t ) = 2 N |V N |δ t (69) < 2 N |V N | • ε 2 4 • 2 N |V N | = ε 2 .(By (67))Therefore, we have U t (N, V ′ ) < ε/2 for all t ≥ T . Translating back into payoffs, this gives a Bob whose cumulative valuation function is V ′ an average payoff of less than 1/2 + ε/2. By the choice of V ′ , we haveEQUATION)so the average payoff to a Bob whose valuation function is v B is less than 1/2 + ε. Since this construction works for all ε > 0, Bob's average payoff satisfies the following inequality as required:u B (1, t) t ≤ 1 2 + o(1) .Explicit bounds It remains to prove inequality (32) when Bob's density is upper bounded by ∆, and prove Alice's explicit payoff in inequality (33). Choose an integer N large enough that∆ + 2 N < ε 2 .For instance, taking N = ⌈2(∆ + 2)/ε⌉ is sufficient. By Lemma 6, there exists V ′ ∈ V N such that|V ′ (x) -V B ([0, x])| < (∆ + 2)/N for all x ∈ [0, 1] .Choose T in exactly the same way as the general case, i.e. T = ⌈4 • 2 N |V N |/ε 2 ⌉. By exactly the same algebra as the general case, we can conclude that U t (N, V ′ ) < ε/2 for all t ≥ T . By the choice of V ′ , we haveEQUATIONso the average payoff to Bob is at most 1 2 + ε. In this case, Bob's average payoff will be within ε of 1/2 by timeEQUATIONHence, for such T ε , we haveT ε ≤ 4 • 2 N • 4 N -1 ε 2 .Since ⌈x⌉ ≤ 2x for x ≥ 1/2, this impliesT ε ≤ 2 8 N ε 2 .Due to our choice of N , we can further obtainEQUATION)Taking the natural logarithm of both sides in (73), we have ln(T ε ) ≤ ln(16) + 2(∆ + 2) ε ln(8) + 2 ln 1 ε .Using the fact that ln(x) ≤ x -1 for every x > 0, it follows thatEQUATIONRearranging (74), we finally obtain ε ≤ 2 ln(8)(∆ + 2) + 2 ln(T ε ) -ln(16) + 2 .Note that this requires the step of dividing by ln(T ε ) -ln( 16) + 2 and it needs this quantity to be positive, which is indeed positive for T ≥ 3. Rounding the terms gives the desired regret bound for Bob.To provide Alice's payoff bound in inequality (33), consider a hypothetical Bob whose valuation function ṽB is exactly the same as Alice's valuation function v A . For all rounds τ , the payoff ũτ B to this Bob then satisfies:u τ A + ũτ B = V A ([0, a τ ]) + V A ([a τ , 1]) (One player gets V A ([0, a τ ]) and the other getsEQUATIONFor any t, summing u τ A + ũτ B over τ ∈ [t] and dividing by t then gives:EQUATIONSo it suffices to upper-bound this particular Bob's payoff to lower-bound Alice's payoff.Choose an arbitrary ε > 0.Let T ε = 2 2 |V2| ε 2, ensuring δ t < ε 2 2 2 |V2| for all t ≥ T ε . By construction, Alice's valuation function V A ([0, x]) ∈ V 2 . Taking N = 2 and V ′ = V A , we can then use identical algebra as the general-Bob case up to (69) to conclude that, for t ≥ T ε :EQUATIONSo this Bob's payoff is upper-bounded by 1/2 + ε, and so by (76) Alice's payoff is lower-bounded by 1/2 -ε. To solve for ε, observe that T ε ≤ 16/ε 2 + 1. Solving this bound on T ε for ε givesε ≤ 4 √ T ε -1 ,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 t / ∈ S, then argmin X∈S P (U t -X, U t -X) exists. Furthermore:argmin X∈S P (U t -X, U t -X) = Y t = min{0, U t (n, V )} Proof of the claim. Let Y t = min{0, U t (n, V )} ∈ S. For any X ∈ S, P (U t -X, U t -X) = ∞ n=1 1 2 n |Vn| V ∈Vn U t(n, V ) -X(n, V ) 2 = ∞ n=1 1 2 n |Vn|     V ∈Vn U t (n,V )>0 U t(n, V ) -X(n, V ) 2 + V ∈Vn U t (n,V )≤0 U t(n, V ) -X(n, V ) 2     (78)Since X ∈ S, we have that X(n, V ) ≤ 0 for every n and V , due to our 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 0. Applying these simplifications, we obtain∞ n=1 1 2 n |V n |     V ∈Vn U t(n,V )>0 U t (n, V ) -X(n, V ) 2 + V ∈Vn U t(n,V )≤0 U t (n, V ) -X(n, V ) 2     ≥ ∞ n=1 1 2 n |V n |     V ∈Vn U t(n,V )>0 U t (n, V ) -0 2 + 0     =D(U t -Y t , U t -Y t ), (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 t / ∈ S.1. P (Y t , W t ) = 0 2. P (U t+1 , W t ) = 0By using U t = W t + Y t , we can expand it byEQUATIONFurther, observe thatEQUATION)where the inequality follows from Property (3) in Lemma 8.Putting ( 81), ( 82) and ( 83) together, we obtain the following inequality for δ t > 0:δ t+1 ≤ P (U t+1 -U t , U t+1 -U t ) + 2P (U t+1 -U t , U t -Y t ) + δ t ≤ 1 (t + 1) 2 - 2 t + 1 δ t + δ t = 1 (t + 1) 2 + 1 - 2 t + 1 δ t .Now, we show that the same inequality holds for the case such that δ t = 0 too. Since U t ∈ S, we obtainδ t+1 = inf X∈S P (U t+1 -X, U t+1 -X) ≤ P (U t+1 -U t , U t+1 -U t ) ≤ 1 (t + 1) 2 (By (83)) = 1 (t + 1) 2 + 1 - 2 t + 1 δ t .By Lemma 10, we therefore have that δ t ≤ 1/t for t ≥ 2.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 a pure strategy S B , 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,u B T ≥ 1 2 - 1 √ T and u B T ≤ 1 2 + ∆ 2δ + 2 1 √ T ,recalling that δ and ∆ are, respectively, the lower and upper bounds on the players' value densities.• In the simultaneous setting: Bob has a mixed strategy S B , such that for every Alice strategy S A , both players have average payoff 1/2 in expectation.There is at most one round without a pair for each interval I i , namely round r i,c = T 2 + T P • ∆ 2δ + P ≤ T 2 + √ T ∆ 2δ + 2 (P = ⌈ √ T ⌉ ≤ 2 √ T )This completes the proof.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 t is:ϕ t A (x) = t-1 τ =1 1 {aτ =x} ∀x ∈ [0, 1] .• The empirical frequency of Bob's play up to (but not including) time t is:ϕ t B (x) = t-1 τ =11 {bτ =x} ∀x ∈ {L, R} .• The empirical distribution of player i's play up to (but not including) time t is:p t i (x) = ϕ t i (x) (t -1),Where x ∈ [0, 1] for Alice and x ∈ {L, R} for Bob.Definition 9. (Fictitious play) In round t = 1, each player simultaneously selects an arbitrary action.In every round t = 2, . . . , T , each player simultaneously best responds to the empirical distribution of the other player up to time t. If there are multiple best responses, the player chooses one arbitrarily.We now give the proof of Theorem 4 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 tie-breaking rules, their average payoff will converge to 1/2 at a rate of O(1/ √ T ). Formally:EQUATION)Proof. The bounds on Bob's payoff follow immediately from Lemma 21, which states thatEQUATIONEQUATIONSubtracting equation ( 90) from (91) givesEQUATIONSince u A = T t=1 u t A and u B = T t=1 u t B , 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 use round t = 0 as a fake round in which nothing actually happens and all the defined quantities are zero. Definition 10. For t ∈ {0, 1, . . . , T }:• Let r t be the number of rounds in which Bob has picked R, up to and including round t. . . , T . The x-axis denotes the quantity of α t and the y-axis denotes that of β t . Blue circles represent the sequence of points in the plane, where the number inside the circle denotes the index t. Note that α t only takes integer values, while β t possibly takes noninteger values at 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 to the origin point. Importantly, Lemma 13 guarantees that ρ t and u t B for t = 0, 1, . . . , T remain exactly the same for both dynamics.Inductive step We show that (99) holds for t + 1. Suppose that, under the original tie-breaking rules, Alice cut at a t+1 and Bob picked b t+1 ∈ {L, R} in round t + 1. First, we analyze for Alice. Let a ′ t+1 ∈ [0, 1] be the unique point for whichEQUATIONThe point a ′ t+1 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 αt and βt , Alice cuts at a ′ t+1 in round t + 1. We split into cases based on α t :(α t > 0): Then a t+1 = 1 by Lemma 11. Since V B ([0, a t+1 ]) = V B ([0, 1]), we have a ′ t+1 = 0 by definition. By the inductive hypothesis, we have αt = -α t , and so αt < 0. Then, regardless of tie-breaking rules, Alice cuts at 0 = a ′ t+1 . (α t < 0): Then a t+1 = 0 by Lemma 11. Since V B ([0, a t+1 ] = 0 = V B ([1, 1]), we have a ′ t+1 = 1 by definition. By the inductive hypothesis, αt = -α t , and so αt > 0. Then, regardless of tie-breaking rules, Alice cuts at 1 = a ′ t+1 . (α t = 0): Then Alice can break ties any way she likes by Lemma 11. However, αt = -α t = 0, so any cut point is a valid choice for her new tie-breaking rule. In particular, she can cut at a ′ t+1 .Second, we analyze for Bob. Let b ′ t+1 ∈ {L, R} be such that b ′ t+1 ̸ = b t+1 . We show that there exist tie-breaking rules under which, starting from αt and βt , Bob chooses b ′ t+1 . We split into cases based on (β t = 0): Then Bob can break ties any way he likes by Lemma 11. However, βt = -β t = 0, so either L or R is a valid choice for his new tie-breaking rule. In particular, he can choose b ′ t+1 .Finally, we show that these opposite choices have exactly the desired effect on αt+1 , βt+1 , and ũt+1 B . Covering each in turn:• Since Bob picks the opposite side under the trajectory associated with α and β, the change from α t to α t+1 is in the opposite direction as the change from αt to αt+1 by Lemma 12. By the inductive hypothesis, we have αt = -α t , and so αt+1 = -α t+1 .• Since Alice picks the mirror image of her cut point under the trajectory associated with α and β, the change from β t to β t+1 is exactly opposite to the change from βt to βt+1 . Specifically,EQUATIONwhileEQUATIONBy the inductive hypothesis, we have βt = -β t . Using equations ( 101) and ( 102), we obtain βt+1 = -β t+1 .• Under Alice's new cut point a ′ t+1 , Bob's valuation of the left and right sides of the cake swap, i.e., V B ([0, a ′ t+1 ]) = V B ([a t+1 , 1]). But he also chooses the opposite side, so he gets exactly the same payoff as under the original tie-breaking rules in round t + 1. Therefore,ũt+1 B = u t+1 B .By induction, the claim holds for all t, which completes the proof.In addition, it is helpful to distinguish between the rounds that cross an axis in the α-β 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 a round t where at least one of the following occurs:• α t = 0 • β t+1 > 0, but β t ≤ 0 • β t+1 < 0, but β t ≥ 0.Importantly, we will show that ρ t 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 t ∈ {0, 1, . . . , T }. The radius ρ t satisfies the following properties: In particular, the radius ρ t is non-decreasing in t.(a) ρ t = ρ t+1 if t is not axis-crossing (b) ρ t ≤ ρ t+1 ≤ 2 + ρ t if t is axis-crossing (c) ρ 0 = 0 (d) ρ t ≥ 1 for t ≥ 1.Proof. First, we will show (a) and (b). Consider an arbitrary round t ∈ {0, . . . , T }. By Lemma 12, we have |α t+1 -α t | ≤ 1 and |β t+1 -β t | ≤ 1, so by the triangle inequalityEQUATION)Therefore, ρ t+1 ≤ 2 + ρ t , as required by (b). Thus for (a) and (b) it remains to show that ρ t+1 ≥ ρ t ∀t ∈ {0, . . . , T } and that ρ t+1 = ρ t if t is not axis-crossing.By Lemma 13, it suffices to consider α t ≥ 0. More precisely, this is because if α t ≤ 0, then there exists a tie-breaking rule with associated αt satisfying αt = -α t for every t = 0, 1, . . . , T , so αt ≥ 0.Crucially, the lemma ensures the sequences αt and α t have the same radius ρ t .We consider a few cases based on α t and β t , considering only α t ≥ 0. Since α t is an integer, also divide into α t ≥ 1 and α t = 0:(α t ≥ 1 and β t > 0): By Lemma 11 Alice will cut at 1 and Bob will pick L. Then by Lemma 12, we have α t+1 = α t -1 and β t+1 = β t + 1. Therefore:EQUATION(α t ≥ 1 and β t = 0): Then Alice will cut at 1 and Bob will pick whichever piece he likes. Therefore α t+1 = α t ± 1 and β t+1 = β t + 1 = 1. Since β t ≤ 0 but β t+1 > 0, round t is axis-crossing. What remains is to show that ρ t+1 ≥ ρ t in this case:EQUATION(α t ≥ 1 and -1 < β t < 0): Then Alice will cut at 1 and Bob will pick R. Therefore, α t+1 = α t + 1 and β t+1 = β t + 1. Since β t < 0 but β t+1 > 0, round t is axis-crossing. What For n ≥ 7, we have 1 2 n 2 -7 2 n + 5 ≥ 1 10 n 2 ,4 and so t n -t 1 > n 2 /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 ≥ 5, the final radius ρ T satisfies the following:ρ T ≤ 2 √ 10T .Proof. Let t 1 = 0, and for i ≥ 2 recursively define t i be the first round after t i-1 satisfying ρ ti ≥ ⌊ρ ti-1 ⌋ + 1. Let n be the last index of such t i given the time horizon T .As an immediate corollary of Lemma 19, we have n ≤ max{7, √ 10T }.For T ≥ 5, this implies that n ≤ √ 10TBy Lemma 14, we also know that ρ can increase by at most 2 per round. Furthermore, since t n is the last element in the sequence {t i } i∈[n] , we have ρ T < ⌊ρ tn ⌋ + 1. Relaxing this slightly, we haveρ T ≤ ρ tn + 2 (122)Therefore, we obtain the following inequalities:EQUATIONPutting ( 121) and ( 123) together, we obtainρ T ≤ 2 √ 10T ,which finishes the proof of 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 ≥ 5, Bob's total payoff satisfies:T 2 - √ 10T ≤ T t=1 u t B ≤ T 2 + √ 10T .• 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 or the standard error of the mean. • It 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 a 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 of range (e.g. negative error rates). • If error bars are 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. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [NA] .Justification: The code we 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 not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs 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). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?Answer: [Yes] Justification: We do not propose a model, use a dataset, or involve human participants. Our theoretical results do not have immediate possibilities for misuse.Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
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 idealized setting does not have any immediate societal applications.Guidelines:• 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 negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.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 a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an 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 to 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 or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: The paper poses no such risks.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a 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 a 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 a 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 we are 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 or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• 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.One may explore a 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.In fact, this is equivalent to the behavior strategy in which the player assigns a probability distribution given a history, thanks to Kuhn's theoremKuhn (1950); Kuhn 1 (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 byAumann (1961);Dresher et al. (2016), which contains our setting.We do not optimize over τ .We omit the elementary calculus. 
 
 Appendix:  


Decision: 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.

Reviews: review: paper_summary: paper_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.

The 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.

At the end they analyze the fictitious play in this setting and show that the convergence rate is $O(1/\sqrt T)$.
strength_weakness: strength_weakness: 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. 
The 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.

This is a solid piece of work but I'm not sure if NeurIPS is the right venue for such papers.
questions: questions: If A and B take turns in cutting the cake, can we see it as two separate instances of this problem?
limitations: limitations: -
paper_summary: paper_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.

Ideally, 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.

First, 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.

On 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).

Finally, 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})$
strength_weakness: strength_weakness: 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.

Also, 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
questions: questions: Do you have some real-world motivation where such repeated games with the same players/valuations make sense?
limitations: limitations: Yes
paper_summary: paper_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.
The authors analyze two versions of this game:
1) sequential, where Bob sees Alice’s cut before choosing
2) simultaneous, where Bob chooses without seeing Alice’s cut
Interestingly, 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.
strength_weakness: strength_weakness: 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.
questions: 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: limitations: The authors correctly states the assumptions under which their results hold.
paper_summary: paper_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.
strength_weakness: strength_weakness: I do not find any obvious weaknesses in this paper. It a paper of theoretical nature and requiring experiments would be meaningless.
questions: 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.
2. 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: limitations: N/A

Comments: comment: Thank you for the response. I will keep my high score for the paper.
Thank you. That is a reasonable example. I leave my original score unchanged.