Paper deep dive
Analyzing the Interaction of Optimal Strategies in Mean-Payoff Bidding Games
Shaull Almagor, Guy Avni, Julian Ewaied
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 91%
Last extracted: 8/10/2026, 1:58:08 AM
Summary
This paper analyzes the interaction of optimal strategies in two-player mean-payoff bidding games. It investigates the behavior generated when two agents, each designed to optimize against an adversarial opponent using known explicit constructions (block or budget strategies), play against each other. The authors prove that under certain restrictions, the generated play is ultimately periodic and develop algorithms to compute the players' utilities in these plays, addressing the challenge of infinitely many configurations and complex dynamics.
Entities (7)
Relation Signals (5)
Bidding Games → uses → Mean-Payoff Objectives
confidence 95% · We consider mean-payoff objectives; each vertex is associated with a reward for each player, and the utility in an infinite play is the limit average of the rewards.
Block Strategy → istypeof → Optimal Strategy
confidence 92% · The first question that we study regards the regularity of the path that is generated when two block strategies or two budget strategies play against each other.
Budget Strategy → istypeof → Optimal Strategy
confidence 92% · Moreover, there are two known explicit constructions of ϵ-optimal strategies: the block strategy σblk [9] and the budget strategy σbgt [18].
Interaction of Optimal Strategies → resultsin → Ultimate Periodicity
confidence 90% · We show that, under some restrictions, the generated play is ultimately periodic
Bidding Games → isclassof → Richman Games
confidence 85% · keywords: Bidding games, Richman games, Mean-payoff games
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:A common assumption when designing an agent in a multi-agent system is that the other agents behave adversarially. This allows a designer to obtain the strongest guarantees when they have no control over nor knowledge about the other agents' behavior. However, when all agents are designed under this adversarial assumption, their actual interaction is not adversarial (e.g., when all players play defensively, no player actually attacks). In such settings, we would like to know what behavior arises in the multi-agent system. However, analyzing the interaction among agents is notoriously challenging, both mathematically and algorithmically. In this paper, we provide such an analysis, focusing on bidding games, played by two agents on a graph as follows. A token is placed on a vertex, and in each turn an auction (bidding) determines which agent moves the token, thus generating an infinite path that determines the agents' utilities. We consider mean-payoff objectives; each vertex is associated with a reward for each player, and the utility in an infinite play is the limit average of the rewards. We analyze the play that is generated when each agent follows a strategy that optimizes against an adversary, and consider the two known explicit constructions of optimal strategies. The technical challenge stems from the infinitely-many configurations of a bidding game and their complicated dynamics. We show that, under some restrictions, the generated play is ultimately periodic, and develop algorithms to compute the players' utilities in it.
Tags
Links
- Source: https://arxiv.org/abs/2608.07383v1
- Canonical: https://arxiv.org/abs/2608.07383v1
Trouble viewing inline? Open PDF directly →
Full Text
90,829 characters extracted from source content.
Expand or collapse full text
1] of Computer Science, 2] of Computer Science, of Haifa Analyzing the Interaction of Optimal Strategies in Mean-Payoff Bidding Games shaull@technion.ac.il gavni@cs.haifa.ac.il jolian.ewaied@gmail.com [ [ Abstract A common assumption when designing an agent in a multi-agent system is that the other agents behave adversarially. This allows a designer to obtain the strongest guarantees when they have no control over nor knowledge about the other agents’ behavior. However, when all agents are designed under this adversarial assumption, their actual interaction is not adversarial (e.g., when all players play defensively, no player actually attacks). In such settings, we would like to know what behavior arises in the multi-agent system. However, analyzing the interaction among agents is notoriously challenging, both mathematically and algorithmically. In this paper, we provide such an analysis, focusing on bidding games, played by two agents on a graph as follows. A token is placed on a vertex, and in each turn an auction (bidding) determines which agent moves the token, thus generating an infinite path that determines the agents’ utilities. We consider mean-payoff objectives; each vertex is associated with a reward for each player, and the utility in an infinite play is the limit average of the rewards. We analyze the play that is generated when each agent follows a strategy that optimizes against an adversary, and consider the two known explicit constructions of optimal strategies. The technical challenge stems from the infinitely-many configurations of a bidding game and their complicated dynamics. We show that, under some restrictions, the generated play is ultimately periodic, and develop algorithms to compute the players’ utilities in it. keywords: Bidding games, Richman games, Mean-payoff games We consider settings in which a user designs an agent to operate on its behalf. For example, advertisers competing for online advertisement slots rely on agents to bid on their behalf [1] (this is in fact a necessity due to the high-frequency of trading in ad-allocation auctions). In such settings, users often seek agents with worst-case guarantees. This is obtained by modeling the competitors of an agent as adversarial, and the agent follows an optimal strategy in a zero-sum game. The setting in which an agent has no knowledge nor does it make assumptions on the competitors that it will play against is often called an “uncoupled” setting [2]. We consider a game in which each user knows only their utility, thus all users design their agents to operate against adversarial competitors. However, the premise that the agents are in fact adversarial typically does not hold; for example, when all players play defensively, no player actually attacks. That is, while each agent provides a worst-case guarantee, these guarantees might be overly pessimistic when the agents turn out not to be purely adversarial. Our goal in this paper is to compute the utility that the agents actually obtain in an interaction between agents that are designed to optimize against an adversary. We describe the model on which we investigate this question. Games on graphs constitute a fundamental model with applications in reactive synthesis [4] and reasoning about multi-agent systems [3], and a deep connection to foundations of logic [5]. A game on a graph proceeds by placing a token on a vertex and the players move it to generate an infinite path (play), which determines the utilities of the players. Traditional graph games are turn-based: the players alternate turns in moving the token. We consider two-player bidding games [6, 7], which are a class of games on graphs in which an auction (bidding) determines which player acts in each turn: both players are allocated initial budgets that sum up to 11, and in each turn, they simultaneously submit bids that do not exceed their available budgets, the highest bidder moves the token, and pays his bid to the other player. We focus on mean-payoff objectives, which are a fundamental quantitative objective in graph games (e.g., [8]); each vertex is associated with a reward, and the goal is to maximize the long-run average rewards that are traversed. The following example illustrates the setup. v0v_0ℓ3 _3v1v_1ℓ1 _1ℓ2 _2 v0v_0 [rgb]0,0,1 [named]pgfstrokecolorrgb0,0,10ℓ3 _3 [rgb]0,0,1 [named]pgfstrokecolorrgb0,0,12v1v_1 [rgb]0,0,1 [named]pgfstrokecolorrgb0,0,10ℓ1 _1 [rgb]0,0,1 [named]pgfstrokecolorrgb0,0,11ℓ2 _2− [rgb]0,0,1 [named]pgfstrokecolorrgb0,0,1-198⋅γ(e1) 98·γ(e_1)54⋅γ(e1) 54·γ(e_1) v0v_0 [rgb]1,.5,0 [named]pgfstrokecolorrgb1,.5,00ℓ3 _3 [rgb]1,.5,0 [named]pgfstrokecolorrgb1,.5,00v1v_1 [rgb]1,.5,0 [named]pgfstrokecolorrgb1,.5,00ℓ1 _1 [rgb]1,.5,0 [named]pgfstrokecolorrgb1,.5,02ℓ2 _2− [rgb]1,.5,0 [named]pgfstrokecolorrgb1,.5,0-118⋅γ(e2) 18·γ(e_2)14⋅γ(e2) 14·γ(e_2) v0v_0 [rgb]1,0,0 [named]pgfstrokecolorrgb1,0,00ℓ3 _3− [rgb]1,0,0 [named]pgfstrokecolorrgb1,0,0-2v1v_1 [rgb]1,0,0 [named]pgfstrokecolorrgb1,0,00ℓ1 _1 [rgb]1,0,0 [named]pgfstrokecolorrgb1,0,02ℓ2 _2 [rgb]1,0,0 [named]pgfstrokecolorrgb1,0,041⋅γ(e2)1·γ(e_2)3⋅γ(e2)3·γ(e_2) Figure 1: Left: an arena. Middle to right: respectively, the rewards and block strategy of Blue, Orange, and Red. Example 1. Consider a game played on the arena (graph) depicted in Fig. 1 Left. The Middle figure, depicts the reward that user Blue obtains in each vertex. Blue designs their agent with no assumptions on the competitors that it will encounter; Blue constructs a zero-sum game in which the competitors are adversarial, and applies an off-the-shelf algorithm [9] to construct an optimal strategy. The strategy is depicted in Fig. 1 Middle: each vertex is associated with a bid written beside the vertex, and a Blue arrow depicts the choice of successor upon winning the bidding (e.g., if Blue wins the bidding at v1v_1, he proceeds to ℓ1 _1). The construction in [9] defines bids in a specific form: a vertex-dependent constant multiplied by a normalization (depicted γ(⋅)γ(·), in Fig. 1), which depends on the history of rewards observed as we detail in Sec. 2.1. Blue can be paired with two possible competitors, Orange and Red, who differ in the rewards that they obtain in the vertices. Both users design their agents with the same adversarial assumption that Blue applies; they construct a zero-sum game and apply an off-the-shelf algorithm to find an optimal strategy. Both the rewards and the strategies that they construct are depicted in Fig. 1 Right. We illustrate how two strategies generate a play. Suppose first that Blue is paired with Orange. For simplicity, assume a=γ(e1)=γ(e2)a=γ(e_1)=γ(e_2). At v0v_0, the bids are bBlue=9/8⋅a>1/4⋅a=bOrangeb_ [rgb]0,0,1 [named]pgfstrokecolorrgb0,0,1Blue=9/8· a>1/4· a=b_ [rgb]1,.5,0 [named]pgfstrokecolorrgb1,.5,0Orange, thus Blue wins the bidding, pays bBlueb_ [rgb]0,0,1 [named]pgfstrokecolorrgb0,0,1Blue to Orange, and moves the token to ℓ3 _3. Blue obtains a reward of 22 and Orange a reward of 0, and the game returns to v0v_0. Since the collected rewards differ, this time the normalizations in the bids might differ, leading to a possible different bidding outcome. Suppose now that Blue is paired with Red. At v0v_0, the bids are bBlue=9/8⋅a<3⋅a=bRedb_ [rgb]0,0,1 [named]pgfstrokecolorrgb0,0,1Blue=9/8· a<3· a=b_ [rgb]1,0,0 [named]pgfstrokecolorrgb1,0,0Red. Now Red wins, and moves the token to v1v_1. At v1v_1, the bids are bBlue=5/4⋅a>1⋅a=bOrangeb_ [rgb]0,0,1 [named]pgfstrokecolorrgb0,0,1Blue=5/4· a>1· a=b_ [rgb]1,.5,0 [named]pgfstrokecolorrgb1,.5,0Orange, and Blue moves the token to ℓ1 _1. Fig. 2 depicts the accumulated rewards for each of the players in the two generated plays. The primary question that we study is the regularity of the generated play. The plots depict a non-trivial structure of the generated play, and hints at the technical difficulty of this problem. A careful inspection of the plots reveals a regular behavior. We prove formally that this is a general phenomenon: the generated play is ultimately periodic in all recurrent strongly-connected games (see Thm. 8). In terms of utility, while the strategies provide the same modest worst-case guarantees, a non-negative mean-payoff reward, the actual payoffs are way higher: the utility (mean-payoff reward) when Blue plays against Orange are both 0.50.5 and when Blue plays against Red they are 0.4110.411 and 0.470.47. The higher Blue utility in the former could stem from the agreement between Blue and Orange at v1v_1 whereas Blue disagrees with Red everywhere. Figure 2: Left: Blue vs Orange, Right: Blue vs Red, Y-axis: accumulated rewards (energy), X-axis: time Motivation. We describe concrete applications. Fair allocation of resources is a timely topic (e.g., [10, 11]). The goal is to allocate a collection of items i1,…,ik \i_1,…,i_k \ to agents in a fair manner. Bidding games have been applied as a natural and useful mechanism for fair allocation [12, 13]: each agent is allocated an initial scrip budget, i.e., a budget that is used for the purpose of the mechanism and carries no utility for the agent, and the resources are auctioned sequentially. It is common practice to construct agents that provide worst-case guarantees on the fraction of the utility proceeds by solving a zero-sum game (e.g., [14]). Our work gives rise to a mechanism for repeated allocation of resources, as the following example illustrates. A librarian needs to decide, each week, which newspaper it purchases, either New York Times (NYT) or Wall Street Journal (WSJ). The librarian applies the mechanism depicted in Fig. 1 Left, in which two students participate: a first bidding at v0v_0 determines whether NYT is purchased (ℓ3 _3) and otherwise, a second bidding at v1v_1 determines whether WSJ is purchased (ℓ1 _1) or whether no newspaper is purchased (ℓ2 _2). Student Blue likes both NYT and WSJ with a preference for the former, Student Orange only likes WSJ, and both students suffer from if no newspaper is purchased. Analyzing the behavior of the game allows the librarian to allocate the correct budget for newspapers, rather than use estimates based on the worst-case guarantees of the two players. Similar mechanisms can be applied for fairly allocating daily computing time to users (e.g., on a GPU) or fairly allocating an advertisement slot among two advertisers as we elaborate below. Auction-based scheduling: Consider the problem of finding a plan (a path) in a graph that models an environment for a conjunction of two objectives. For example, consider the task of designing a plan for a patrolling robot that needs to maximize the time it spends in two locations t1t_1 and t2t_2. A decoupled approach to planning [15] independently constructs a policy for each objective and composes the policies at runtime. Advantages of the approach include enabling parallel computing and modularity, e.g., if t1t_1 changes, only σ1 _1 needs to be updated and σ2 _2 can stay fixed. Runtime composition is challenging due to the need to resolve conflicts. Auction-based scheduling (ABS) [16] applies an auction in each turn to determine which policy chooses the next action. ABS proceeds as follows. For each target tit_i, construct a bidding game iG_i on the input graph, where in each turn, the players bid for who moves the robot. The game iG_i is a zero-sum game in which the proponent aims to spend as much time at tit_i. This is naturally expressed as a mean-payoff objective. Solve each game to obtain optimal strategies σ1,σ2 _1, _2 for the robot. Each σi _i is accompanied by a guarantee cic_i on the time spent at tit_i, for i∈1,2i∈ \1,2 \. Then, a plan for the robot is obtained by composing the two strategies by letting them play against one another. It is not hard to see that the worst-case guarantees apply, namely time that the robot spends at tit_i is at least cic_i. Crucially, the guarantees of the strategies may be overly pessimistic. In this work, we seek to compute the actual time the robot spends in the targets. Finally, we point out that [15, 16] only consider qualitative objectives. Our work is the first to consider quantitative objectives, which is particularly appealing since it allows to quantify and weigh the (possible) drop in performance with the advantages of decoupling. Advantages over Nash equilibrium (NE). The standard solution concept for non-zero-sum games is NE. We point to advantages of the solution that we consider. First, unlike NE, where each agent knows the objectives of the competitor as well as assumes that they rationally aim to maximize it, here, agents assume neither: they have no knowledge on the objective of their competitors and make no assumptions on their behavior. Second, a shortcoming of NE is that it is not clear how agents end up playing an NE. One either needs to assume player dynamics, which does not always converge to NE, or assume a centralized authority that can prescribe strategies to agents, which is arguably a strong assumption, not to mention that finding an NE is computationally intractable [17]. We find it a feature of our solution concept that it neither relies on dynamics nor requires a centralized authority. Our results. We consider two-player mean-payoff bidding games played on strongly-connected graphs. The game is not zero sum, but each agent only knows their individual objective. Each agent assumes the competitor is adversarial, and follows an optimal strategy. It is known that ϵε-optimal pure strategies exist in mean-payoff bidding games. Moreover, there are two known explicit constructions of ϵε-optimal strategies: the block strategy σblkσ^blk [9] and the budget strategy σbgtσ^bgt [18]. The first question that we study regards the regularity of the path that is generated when two block strategies or two budget strategies play against each other. This is highly non-trivial since a bidding game contains infinitely-many (in fact, uncountably-many) configurations, and the strategies are described succinctly; σblkσ^blk chooses bids depending on the accumulated weights and σbgtσ^bgt chooses bids depending on the current budget. One can argue that establishing regularity of the generated path is a prerequisite result; it is hard to imagine, e.g., an algorithm to predict the payoffs of the generated play, if the play is not ultimately periodic. Recurrent games. Repeated games are simple, common, and important; e.g., repeated prisoner’s dilemma is extensively studied (e.g., [19]) and a repeated mean-payoff game is studied in the seminal book [20]. In a repeated bidding game, winning a bidding entails a reward and losing a bidding entails a penalty, and the goal is to maximize the mean-payoff reward. For example, suppose that two advertisers participate in a daily bidding to determine which of the two ads displays that day, each advertiser is rewarded 11 whenever they win a bidding and 0 otherwise, then an advertiser’s mean-payoff reward represents the long-run ratio of the biddings won, which can also be thought of as their “visibility”, e.g., the number of days in a year that an ad is displayed. Recurrent games generalize repeated games. They are played on a tree in which the leaves point to the root (see Fig. 1 Left). A repeated bidding game is the special case of a tree of height 11. Recurrent games arise naturally, as illustrated in the mechanism for repeated fair resource allocation above. Moreover, recurrent bidding games served as a useful stepping stone towards solutions to general games; e.g., this was the case in [18]. For block strategies, we show that the path πblkπ^blk generated by two block strategies is ultimately periodic. Observe that the plots depicted in Fig. 2 do indeed hint that the paths are ultimately periodic, and it is interesting to note that the period, particularly in the Blue vs Red plot, is highly non-trivial. Our proof gives rise to an algorithm to compute the payoffs of πblkπ^blk. For budget strategies, we devise a sound algorithm to reason about the generated path in recurrent games and show that in repeated bidding games, the generated path is ultimately periodic. Our conceptual contribution — analyzing the interaction between optimal strategies — entails a careful mathematical analysis. Moreover, it is (crucially) tailored to the structure of the optimal strategies being used. Thus, the paper must first recall some technical aspects of these strategies. We defer most of the technicalities to the appendix, but still maintain analysis since it has merit in its own right; both the results themselves and illustrating the techniques, which are both novel to bidding games and will are challenging to extend beyond the settings that we consider. Related work. To the best of our knowledge, analyzing the outcome of two optimal strategies has not been studied before. A conceptually similar line of work, which has recently attracted considerable attention, analyzes the outcome of a repeated game, where players follow a fixed online-learning algorithm. For example, [21] shows that even though it is guaranteed that the time-average of the sequence of strategy profiles generated converges to an NE, surprisingly, the sequence itself does not converge to an NE, and in fact tends away from it. Similar to our eventually-periodic structural results, [22] establishes “recurrence” in the sequence of strategy profiles. In both our and these works, the analysis is technically challenging since it entails analyzing a dynamical system; in our case, a piece-wise linear dynamical system. 1 Preliminaries A mean-payoff bidding game is a tuple =⟨V,E,w1,w2⟩G= V,E,w_1,w_2 , where V is a set of vertices, E⊆V×VE V× V is a set of edges, for i=1,2i=1,2, wi:V→ℚw_i:V is a weight function for Player i. We restrict attention to strongly-connected games, i.e., ⟨V,E⟩ V,E is a strongly-connected graph. The neighbors of v∈Vv∈ V are (v)=u:E(v,u)N(v)= \u:E(v,u) \. A game is zero-sum when w1=−w2w_1=-w_2, i.e., the reward of Player 11 is the penalty for Player 22. In such games, we refer to Player 11 as Max, Player 22 as Min, and use only one weight function w=w1w=w_1. A configuration of a bidding game is a tuple ⟨v,B⟩ v,B meaning that the token is placed on v∈Vv∈ V and Player 11’s budget is B∈[0,1]B∈[0,1]. We normalize the sum of budgets to 11, thus implicitly Player 22’s budget is 1−B1-B. A strategy for Player i is a “recipe” that, given the history of the game, specifies an action for the player to take. Formally, a strategy for Player i is a function σi:(V×[0,1])+→V×[0,1] _i:(V×[0,1])^+→ V×[0,1], which given a history of configurations, returns an action ⟨u,b⟩∈(V×[0,1]) u,b ∈(V×[0,1]) meaning that Player i bids b and moves the token to u upon winning the bidding. We restrict to legal strategies that choose (1) a bid that does not exceed the available budget and (2) move the token to a neighboring vertex. An initial configuration c0∈(V×[0,1])c_0∈(V×[0,1]) and two strategies σ1 _1 and σ2 _2 give rise to a unique play, denoted (c0,σ1,σ2) play(c_0, _1, _2), which is an infinite sequence of configurations that is defined inductively as follows. For n∈ℕn , denote the n-th prefix of an infinite play π=c0,c1,…π=c_0,c_1,… by π≤n=c0,…,cnπ^≤ n=c_0,…,c_n. The first configuration of (c0,σ1,σ2) play(c_0, _1, _2) is c0c_0. Suppose that π≤jπ^≤ j is defined and ends in configuration cj=⟨vj,Bj⟩c_j= v_j,B_j . We define the next configuration cj+1c_j+1 as follows. For i∈1,2i∈ \1,2 \, let ⟨ui,bi⟩=σi(c0,…,cj) u_i,b_i = _i(c_0,…,c_j) be Player i’s next action. If b1≥b2b_1≥ b_2, Player 11 wins the bidding and the next configuration is cj+1=⟨u1,Bj−b1⟩c_j+1= u_1,B_j-b_1 , and otherwise Player 22 wins the bidding and cj+1=⟨u2,Bj+b2⟩c_j+1= u_2,B_j+b_2 . Note that we break bidding ties in favor of Player 11, and our analysis can easily be adapted to accommodate more involved tie-breaking mechanisms such as alternating turns, but the issue of tie breaking is orthogonal to the questions that we study. The path in G that corresponds to (c0,σ1,σ2)=⟨v0,B0⟩,⟨v1,B1⟩,… play(c_0, _1, _2)= v_0,B_0 , v_1,B_1 ,… is denoted (c0,σ1,σ2)=v0,v1,… path(c_0, _1, _2)=v_0,v_1,…. Definition 1. (Mean-payoff and energy). Let π≤n=c0,…,cnπ^≤ n=c_0,…,c_n with cj=⟨vj,Bj⟩c_j= v_j,B_j , for n∈ℕn and 0≤j≤n0≤ j≤ n. For i∈1,2i∈ \1,2 \, define Player i’s energy in π≤nπ^≤ n to be i(c0,…,cn)=∑0≤j<nwi(vj) energy_i(c_0,…,c_n)= _0≤ j<nw_i(v_j). Player i’s payoff in π is MPi(π)=lim infn→∞1ni(π≤n)MP_i(π)= _n→∞ 1n energy_i(π^≤ n). When G is zero-sum, we write MP(π)MP(π) for Max’s reward. The mean-payoff value in zero-sum games The guarantees that the strategies provide arise from results on zero-sum mean-payoff bidding games, which we briefly survey next. Consider a zero-sum game G. The mean-payoff value of G, denoted () val(G), is intuitively the optimal reward that Max can ensure. Quite surprisingly, it was shown in [9] that the () val(G) does not depend on the initial budgets and only on the structure of the game. Theorem 1. [9] Consider a strongly-connected zero-sum mean-payoff bidding game =⟨V,E,w⟩G= V,E,w , an initial vertex v0v_0, and ϵ,ϵ′>0ε,ε >0. There exists a value () val(G) such that • Max can guarantee payoff ()−ϵ val(G)-ε with any positive budget. Formally, Max has a strategy σ s.t. for any Min strategy τ, ensures MP((⟨v0,ϵ′⟩,σ,τ))≥()−ϵMP( play( v_0,ε ,σ,τ))≥ val(G)-ε. • Max cannot do better even with (almost) all the budget. Formally, there is a Min strategy τ such that for every Max strategy σ, we have MP((⟨v0,1−ϵ′⟩,σ,τ))≤()+ϵMP( play( v_0,1-ε ,σ,τ))≤ val(G)+ε. A corollary of Thm. 1 is that two optimal strategies are composable in the following sense. Consider a game =⟨V,E,w1,w2⟩G= V,E,w_1,w_2 , let i=⟨V,E,wi⟩G_i= V,E,w_i , for i∈1,2i∈ \1,2 \, be two zero-sum mean-payoff games, and σi _i be an ϵε-optimal strategy for Max in iG_i. Then, since σi _i requires only a positive initial budget to guarantee (i)−ϵ val(G_i)-ε, we can compose σ1 _1 with σ2 _2 by allocating, for example, a budget of 0.50.5 to each. Trivially, for π=(⟨v0,0.5⟩,σ1,σ2)π= play( v_0,0.5 , _1, _2), we have both MP1(π)≥(1)−ϵMP_1(π)≥ val(G_1)-ε and MP2(π)≥(2)−ϵMP_2(π)≥ val(G_2)-ε. We focus on games played on recurrent graphs (see Fig. 1), defined as follows. Definition 2. (Recurrent graphs). A recurrent graph ⟨V,E⟩ V,E is a strongly-connected graph given as a tree with root v0v_0, in which all leaves point to v0v_0, thus all cycles traverse v0v_0.111This restriction can be lifted to DAGs by duplicating vertices that are shared between paths that lead to the same leaf. We call a path from root to leaf a vine and a visit to v0v_0 a milestone. For a play π=c0,c1,…π=c_0,c_1,… let Mil=n1,n2,…Mil= \n_1,n_2,… \ be the indices in which π visits the root, i.e., for n∈Miln , we have cn=⟨v0,Bn⟩c_n= v_0,B_n for some BnB_n. For i≥1i≥ 1, the path vni…vni+1−1v_n_i… v_n_i+1-1 is a vine. In the next two sections we describe two explicit constructions of ϵε-optimal strategies in zero-sum games and analyze the play that arises from composing two strategies of the same type in a non-zero sum game. 2 Analyzing the Play Generated by Two Block Strategies In this section, we describe the construction of block strategies [9] and analyze the play generated by two such strategies. We show that in recurrent games, the path that the play forms is ultimately periodic. The proof gives rise to an algorithm that computes the payoff of the play. Finally, we identify a class of games for which we show that the play traverses at most two vines infinitely often. 2.1 The block strategy We describe the parts of the construction of a block strategy that are essential for this work. The full construction and its correctness proof is described in [9, Sec. 4.2.1]. The strategy chooses e0∈ℕe_0 , “pretends” that the initial energy is e0e_0, and ensures that the energy never drops to 0. It is not hard to see that this guarantees a non-negative mean-payoff. Note that in order to guarantee payoff c, one can simply follow a strategy in a game in which all weights are decreases by c. The strategy determines bids according to the accumulated rewards, defined as follows. Recall that Mil are the indices of the play that visit the root. For n∈Miln , the virtual energy of π≤nπ^≤ n, denoted e(π≤n)e(π^≤ n), can be thought of as the “current energy”; it is the change in energy added to the initial energy, e(π≤n)=e0+(π≤n)e(π^≤ n)=e_0+ energy(π^≤ n). Strategy structure. Suppose that the game is at vertex v following prefix π≤mπ^≤ m, and let n≤mn≤ m with n∈Minn be the last visit to the root. Then, the strategy chooses ⟨b,v′⟩ b,v , where v′v is a neighbor of v, and the bid b is of the form St(v)⋅γ(e(π≤n))St(v)·γ (e(π^≤ n) ), where St(v)St(v) is called the strength of v and γ(⋅)γ(·) is a normalization scheme that depends on the virtual energy. Importantly, the choices of v′v and St(v)St(v) are pre-computed and do not depend on the prefix of the play. The analysis in this paper only requires that they are constant. For completeness, we illustrate the definition in App. A. v0v_0,, [rgb]0,0,0 [named]pgfstrokecolorrgb0,0,0 @color@gray@stroke0 @color@gray@fill00, [rgb]1,0,0 [named]pgfstrokecolorrgb1,0,00, [rgb]0,1,1 [named]pgfstrokecolorrgb0,1,1 @color@cmyk@stroke1000 @color@cmyk@fill10002ℓ3 _3,, [rgb]0,0,0 [named]pgfstrokecolorrgb0,0,0 @color@gray@stroke0 @color@gray@fill02, [rgb]1,0,0 [named]pgfstrokecolorrgb1,0,02, [rgb]0,1,1 [named]pgfstrokecolorrgb0,1,1 @color@cmyk@stroke1000 @color@cmyk@fill10000v1v_1,−, [rgb]0,0,0 [named]pgfstrokecolorrgb0,0,0 @color@gray@stroke0 @color@gray@fill00, [rgb]1,0,0 [named]pgfstrokecolorrgb1,0,0-2, [rgb]0,1,1 [named]pgfstrokecolorrgb0,1,1 @color@cmyk@stroke1000 @color@cmyk@fill10003ℓ1 _1,, [rgb]0,0,0 [named]pgfstrokecolorrgb0,0,0 @color@gray@stroke0 @color@gray@fill01, [rgb]1,0,0 [named]pgfstrokecolorrgb1,0,01, [rgb]0,1,1 [named]pgfstrokecolorrgb0,1,1 @color@cmyk@stroke1000 @color@cmyk@fill10000ℓ2 _2−,−, [rgb]0,0,0 [named]pgfstrokecolorrgb0,0,0 @color@gray@stroke0 @color@gray@fill0-5,\!\! [rgb]1,0,0 [named]pgfstrokecolorrgb1,0,0-5, [rgb]0,1,1 [named]pgfstrokecolorrgb0,1,1 @color@cmyk@stroke1000 @color@cmyk@fill10000 Figure 3: Left: The three numbers in a vertex v, left to right, are: its weight w(v)w(v) (black), its potential Pot(v)Pot(v) ( red), and its strength St(v)St(v) ( cyan) (see App. A for details on the latter). Red edges depict Max’s choices upon winning a bidding; he proceeds to a neighbor with the maximal potential. Right: Energy blocks and virtual energies that belong to them. The normalization scheme We describe the normalization scheme of the block strategy, which is key in our analysis. The strategy chooses N∈ℕN and z>1z>1. The precise choice of the parameters N, z, and e0e_0 is insignificant for the analysis, we do not elaborate on it and refer the reader to [9] for details. Our only assumption is that N is larger than the sum of weights in any vine. We partition ℚQ into energy blocks of size N (see Fig. 3, Right), and the normalization factor is chosen based on the block to which the virtual energy resides in. Formally, for i∈ℕi , the i-th energy block is [Ni,N(i+1))∩ℚ[Ni,N(i+1)) . Note that the end points of the blocks are integers but the virtual energy can be rational. Denote by β the energy block that e(π≤n)e(π^≤ n) belongs to, thus β=⌊e(π≤n)/N⌋β= e(π^≤ n)/N . We call β the current energy block. Normalization: When the game is in vertex v and the current energy block is β, the bid is St(v)⋅z−βSt(v)· z^-β. Note that changes to the normalization factor occur only at the root. We emphasize that this exposition does not entirely clarify how block strategies behave, but merely gives the necessary information to carry on with our analysis. Example 2. Ex. 6 in App. A, demonstrates that σblkσ^blk guarantees that whenever the energy decreases, Max “gains” budget, and whenever the energy increases, Max “invests” budget. Suppose that the virtual energy is e(π≤n)=e1e(π^≤ n)=e_1, at some turn n∈Miln (see Fig. 3, Right). Then, in the next vine, Max chooses z−βz^-β as the normalization factor. Consider the case that Min bids 0 for several vines, thus Max draws the game to ℓ3 _3, and importantly for this example, the energy increases. Eventually, e(π≤n′)=e2e(π^≤ n )=e_2, at some turn n′∈Miln . Then, Max’s normalization factor decreases to z−(β+1)z^-(β+1). If Min now wins and repeatedly draws the game to ℓ2 _2, the energy will eventually reach e1e_1, and the normalization increases to z−βz^-β. The generated play. Consider a non-zero-sum recurrent game =⟨V,E,w1,w2⟩G= V,E,w_1,w_2 and an initial configuration c0=⟨v0,B1⟩c_0= v_0,B_1 . That is, the token is initially placed on the root, Player 11 is allocated B1>0B_1>0 and Player 22 is allocated B2=1−B1>0B_2=1-B_1>0. For i∈1,2i∈\1,2\, let i=⟨V,E,wi⟩G_i= V,E,w_i be a zero-sum game and construct the block strategy σiblkσ^blk_i for initial budget BiB_i as above. For ease of presentation, we assume that σ1blkσ^blk_1 and σ2blkσ^blk_2 choose the same parameters N and z, and in Rem. 1, we discuss the changes required to lift this assumption. In the remainder of this section, we analyze the generated play (c0,σ1blk,σ2blk) play(c_0,σ^blk_1,σ^blk_2). 2.2 The generated path is ultimately periodic In this section, we show that the path in G that corresponds to the play generated by block strategies is ultimately periodic. Figure 4: Right: four virtual energies and the energy blocks that they belong to. Left: the partition of ℚQ to difference intervals. Proof overview. We describe the main ingredients of the proof. A central quantity is the difference between the energy blocks in a prefix, which we use Δ to denote. To illustrate, Fig. 4 Right, depicts four virtual energies. For n1,n2∈Miln_1,n_2 and i∈1,2i∈ \1,2 \, at at turn nin_i, denote the virtual energy of the first coordinate by e1i=e1(π≤ni)e^i_1=e_1(π^≤ n_i) (depicted in Orange) and the second coordinate by e2i=e2(π≤ni)e^i_2=e_2(π^≤ n_i) (depicted in Blue). The energy-block difference Δ1=β2−β1=1 _1= _2- _1=1 corresponds to π≤n1π^≤ n_1 and Δ2=β3−β1=2 _2= _3- _1=2 corresponds to π≤n2π^≤ n_2. We show that the energy block difference, Δ , uniquely determines the next vine (Lem. 2). The proof idea is that the normalization factor, which is tied to the difference, is determined at the root and the other aspects of the strategy (the strengths) are constant. We partition ℚQ into intervals, and associate each interval with a leaf. When the token is at the root and energy-block difference is in an interval that corresponds to leaf ℓ , then ℓ is the next leaf that the token visits. To illustrate, Fig. 4 Left, depicts three intervals separated by dashed red lines. For example, the energy-block differences 0 and 11 correspond to the middle interval, which is associated with leaf ℓ2 _2, thus following prefix π≤n1π^≤ n_1 with energy-block difference Δ1 _1, the next leaf to be visited is ℓ2 _2. We think of the sequence of energy-block difference traversed by the play as a walk on ℤZ. We associate with each interval a direction, which marks the direction in which the walk “tends” to proceed to (Def. 5). For example, the directions in Fig. 4 are depicted beneath each interval. The middle interval corresponds to leaf ℓ2 _2, which might have w1(ℓ2)<w2(ℓ2)w_1( _2)<w_2( _2), meaning that the energy in the second coordinate ( Blue) increases faster than the first coordinate ( Orange), which causes the energy-block difference to “tend” to increase after visiting ℓ2 _2. This is the situation depicted in the right part of the figure: following prefix π≤n1π^≤ n_1, the energy-block difference is Δ1 _1 and it grows to Δ2 _2 in π≤n2π^≤ n_2. Finally, a key lemma (Lem. 6) shows that the walk does not fluctuate arbitrarily; that is, it either tends to ∞, −∞-∞, or it is bounded. In the unbounded case, the walk eventually stays in one of the outer intervals. Staying in one interval means that the same leaf is visited repeatedly. In the bounded case, we identify an equivalence relation between pairs of virtual energies with finitely many classes, and deduce that eventually a cycle of vines is formed (Lem. 7). 2.2.1 Determining the next vine We define the energy-block difference formally. Definition 3. For n∈Miln , the energy-block difference is Δ(π≤n)=β2(π≤n)−β1(π≤n) (π^≤ n)= _2(π^≤ n)- _1(π^≤ n). Next, we partition ℚQ according to the energy-block differences (Fig. 4, Left). Definition 4. (Difference interval). The definition is inductive on the depth. For the root, define l(v0)=(−∞,∞)l(v_0)=(-∞,∞). Next, suppose that l(v)l(v) is defined. For i∈1,2i∈ \1,2 \, let ui∈(v)u_i (v) be the choice of σiblkσ^blk_i upon winning the bidding at v. Let u∈(v)u (v). If St1z(v),St2z(v)≠0St^z_1(v),St^z_2(v)≠ 0, define the balance of v as Bal(v)=logz(St2z(v)St1z(v))Bal(v)= _z ( St^z_2(v)St^z_1(v) ) and define l(u)l(u) as l(u)=l(v))∩(−∞,Bal(v))if u≠u1 and u=u2l(v)∩[Bal(v),∞)if u=u1 and u≠u2l(v)if u=u1 and u=u2∅otherwisel(u)= casesl(v))∩(-∞,Bal(v))&if u≠ u_1 and u=u_2\\ l(v)∩[Bal(v),∞)&if u=u_1 and u≠ u_2\\ l(v)&if u=u_1 and u=u_2\\ &otherwise\\ cases If St1z(v)=0St^z_1(v)=0, we define l(u2)=l(v)l(u_2)=l(v). Otherwise St2z(v)=0St^z_2(v)=0, and we define l(u1)=l(v)l(u_1)=l(v). For every other u∈(v)u (v), define l(u)=∅l(u)= . Note that the boundaries of the intervals can be irrational numbers whereas we are interested in integer points within the intervals. The lemma below shows how the next vine is determined. Lemma 2. Let n∈Miln and a vertex v∈Vv∈ V. If Δ(π≤n)∈l(v) (π^≤ n)∈ l(v), then the next vine visits v. Proof. We prove by induction on the depth of v. The base case is trivial since every vine visits v0v_0. For the inductive step, let v′v be the parent of v. Since l(v)⊆l(v′)l(v) l(v ), we have Δ∈l(v′) ∈ l(v ), and by the induction hypothesis, the vine visits v′v . Consider the bidding at v′v . For i∈1,2i∈ \1,2 \, Player i bids bi=Stiz(vk)⋅z−βib_i=St^z_i(v_k)· z^- _i and proceeds to ui∈(v)u_i (v). Suppose that St1z(vk),St2z(vk)≠0St^z_1(v_k),St^z_2(v_k)≠ 0 and the other case is similar. Player 11 wins the bidding iff b1≥b2b_1≥ b_2 iff 1≥b2/b1=(St2z(v)⋅z−β2)/(St1z(v)⋅z−β1)1≥ b_2/b_1=(St^z_2(v)· z^- _2)/(St^z_1(v)· z^- _1). Rearranging, Player 11 wins the bidding iff Bal(v)≤ΔBal(v)≤ . If u1≠u2u_1≠ u_2, note that l(u1)l(u_1) and l(u2)l(u_2) are disjoint and for i∈1,2i∈ \1,2 \, Player i wins the bidding iff Δ∈l(ui) ∈ l(u_i), in which case the token moves to ui=vu_i=v. If u1=u2u_1=u_2, then l(v)=l(v′)l(v)=l(v ), and the game proceeds to v no matter the bidding outcome. ∎ 2.2.2 The energy-block difference walk In this section, we prove that the energy-block difference walk does not fluctuate arbitrarily. Formally, consider the sequence e2(π≤n)−e1(π≤n)n∈Mil \e_2(π^≤ n)-e_1(π^≤ n) \_n , then the walk is Δ1,Δ2,… _1, _2,… with Δj=Δ(π≤nj) _j= (π^≤ n_j), for nj∈Miln_j . The following definition intuitively guides the direction of the walk. Definition 5. (Interval directions). Let ℒL be the set of leaves in G. For ℓ∈ℒ , let v0,…,vk=ℓv_0,…,v_k= be the unique path from the root to ℓ , and define Wi(ℓ)=∑0≤j≤kwi(vj)W_i( )= _0≤ j≤ kw_i(v_j) be the sum of weights on the path. Define a labeling δ of the leaves where δ(ℓ)δ( ) is →/←/⊥→/←/ if W2(ℓ)−W1(ℓ)W_2( )-W_1( ) is positive/negative/zero, respectively. Intuitively, if for j≥1j≥ 1, the j-th vine ends in a right-leaning interval, i.e., ℓ∈ℒ ∈L having δ(ℓ)=→δ( )=→, the virtual-energy difference increases, thus we expect the walk to proceed “right”, i.e., Δj+1≥Δj _j+1≥ _j. This intuition is useful but not precise. We illustrate why. Suppose that e1(π≤j)e_1(π^≤ j) is close to the boundary of the β1 _1-th block whereas e2(π≤j)e_2(π^≤ j) is far from the boundary of the β2 _2-th block. Then, for W1(ℓ),W2(ℓ)>0W_1( ),W_2( )>0, it is possible that only one of the virtual energies changes blocks: e1(π≤j+1)e_1(π^≤ j+1) to the β1+1 _1+1 block while e2(π≤j+1)e_2(π^≤ j+1) stays in the β2 _2 block, which results in Δj+1<Δj _j+1< _j. We show the following lemma, which intuitively shows that when the walk enters an interval, the first index in the interval is not far from the boundary. Lemma 3. For j∈Milj and its successor j′∈Milj , we have |Δ(π≤j)−Δ(π≤j′)|≤2| (π^≤ j)- (π^≤ j )|≤ 2. Proof. We reason about another quantity: for n∈Miln , define Γ(π≤n)=⌊e2(π≤n)−e1(π≤n)N⌋ (π^≤ n)= e_2(π^≤ n)-e_1(π^≤ n)N . The following claim connects Γ and Δ . Its proof is technical and we omit it. Claim 4. For all x,y∈ℚx,y , the following holds: ⌊y−x⌋−1≤⌊y⌋−⌊x⌋≤⌊y−x⌋+1 y-x -1≤ y - x ≤ y-x +1 Therefore, for n∈Miln , we have Γ(π≤n)−1≤Δ(π≤n)≤Γ(π≤n)+1 (π^≤ n)-1≤ (π^≤ n)≤ (π^≤ n)+1. The following claim intuitively shows that updates to Γ agree with our intuition: in a right-leaning interval, Γ grows, and in a left-leaning interval, it shrinks. The lemma requires that Γ is far from the interval’s boundaries, guaranteeing that Δ belongs to the same interval. Claim 5. Consider an interval l(ℓ)l( ), for some ℓ∈ℒ ∈L. Let a∈ℤa such that a−1,a,a+1⊆l(ℓ) \a-1,a,a+1 \ l( ). For j∈Milj and its successor j′∈Milj we have: 1. if δ(ℓ)=(→)δ( )=(→) and Γ(π≤j)=a (π^≤ j)=a, then Γ(π≤j′)≥a (π^≤ j )≥ a, and 2. if δ(ℓ)=(←)δ( )=(←) and Γ(π≤j)=a (π^≤ j)=a, then Γ(π≤j′)≤a (π^≤ j )≤ a. Proof of claim: We prove the first part, and the proof for the other case is dual. Claim. 4 implies that Δ(π≤j)∈l(ℓ) (π^≤ j)∈ l( ). By Lem. 2, the next milestone ends in ℓ . Then, ⌊e2(π≤j′)−e1(π≤j′)N⌋=⌊e2(π≤j)−e1(π≤j)+W2(ℓ)−W1(ℓ)N⌋≥⌊e2(π≤j)−e1(π≤j)N⌋=a. split& e_2(π^≤ j )-e_1(π^≤ j )N \\ &= e_2(π^≤ j)-e_1(π^≤ j)+W_2( )-W_1( )N \\ &≥ e_2(π^≤ j)-e_1(π^≤ j)N =a. split The inequality follows from δ(ℓ)=(→)δ( )=(→). ∎(of claim) The proof of Lemma 3 now follows from our assumption that N is larger than the sum of weights in a path in G. Thus, if the energy block shifts, it shifts to a neighboring block, implying an upper bound on a step in the walk. ∎ We conclude this section by showing that the virtual-energy difference sequence does not fluctuate unboundedly. Lemma 6. The sequence e2(π≤n)−e1(π≤n)n∈Mil \e_2(π^≤ n)-e_1(π^≤ n) \_n either tends to ∞, to −∞-∞, or is bounded. Proof. We prove for the lemma for the sequence Γ(π≤n)n∈Mil \ (π^≤ n) \_n , which clearly implies the lemma. Denote the rightmost interval by l(ℓR)=[a,∞)l( _R)=[a,∞). We distinguish between the three possibilities of δ(ℓR)δ( _R). In the first case, δ(ℓR)=←δ( _R)=←. We show that sequence is bounded from above; namely, we show that for all n∈Miln , we have Γ(π≤n)≤maxΓ(π≤1),a+2 (π^≤ n)≤ \ (π^≤ 1),a+2 \. If Γ is within the interval l(ℓR)l( _R), it only decreases. Formally, for j∈Milj and its successor j′∈Milj , by Claim. 5, if Γ(π≤j)≥a+2 (π^≤ j)≥ a+2, then Γ(π≤j′)≤Γ(π≤j) (π^≤ j )≤ (π^≤ j). It is left to show that cannot enter l(ℓR)l( _R) in arbitrarily high indices. By Lem. 3, if Δ(π≤j′)∈l(ℓR) (π^≤ j )∈ l( _R) and Δ(π≤j)∉l(ℓR) (π^≤ j)∉ l( _R), then Δ(π≤j′)≤a+1 (π^≤ j )≤ a+1, and by Claim. 4, we have Γ(π≤j′)≤a+2 (π^≤ j )≤ a+2. For the other two cases, assume towards contradiction that the sequence fluctuates arbitrarily. Then, there exists j∈Milj with Γ(π≤n)≥(a+2) (π^≤ n)≥(a+2). By Claim. 4, we have Δ(π≤j)∈l(ℓR) (π^≤ j)∈ l( _R) and by Lem. 2, the next vine visits ℓR _R. Let j′∈Milj be the successor of j. If δ(ℓR)=⊥δ( _R)= , then Γ(π≤j)=Γ(π≤j′) (π^≤ j)= (π^≤ j ), meaning that the sequence stays constant. If δ(ℓR)=→δ( _R)=→, then by Claim. 5, Γ(π≤j′)≥a+2 (π^≤ j )≥ a+2, meaning that all next vines traverse ℓR _R, and the sequence grows indefinitely. Both contradict the assumption. ∎ 2.2.3 The generated path is ultimately periodic The next lemma is used to reason about the case that e2(π≤n)−e1(π≤n)n∈Mil \e_2(π^≤ n)-e_1(π^≤ n) \_n is bounded. It shows that the absolute virtual energy does not contribute to determining the next vine to be played, rather the key factor is the difference between virtual energies. The proof is a consequence of Lem. 2. Lemma 7. (Energy-block shift invariance). Let n,n′∈Miln,n such that there exists k∈ℕk for which ei(π≤n)=ei(π≤n′)+k⋅Ne_i(π^≤ n)=e_i(π^≤ n )+k· N, for i∈1,2i∈ \1,2 \. Then, the vine that is played following π≤nπ^≤ n and π≤n′π^≤ n is the same. It follows that the path in G that is traversed by the suffixes of π≤nπ^≤ n and π≤n′π^≤ n is the same. Proof. Observe that: Δ(π≤n)=⌊e2(π≤n)N⌋−⌊e1(π≤n)N⌋= (π^≤ n)= e_2(π^≤ n)N - e_1(π^≤ n)N = =⌊e2(π≤n)+kN⌋−⌊e1(π≤n)+kN⌋=⌊e2(π≤n′)N⌋−⌊e1(π≤n′)N⌋=Δ(π≤n′).= e_2(π^≤ n)+kNN - e_1(π^≤ n)+kNN = e_2(π^≤ n )N - e_1(π^≤ n )N = (π^≤ n ). Thus, Δ(π≤n) (π^≤ n) and Δ(π≤n′) (π^≤ n ) belong to the same interval and by Lem. 2, the same vine is played next. ∎ Our main result of this section is that the path in G that corresponds to the generated play is ultimately periodic. Theorem 8. For every initial configuration c0c_0 it holds that (c0, path(c_0, σ1blk,σ2blk)=τ1⋅τ2ωσ^blk_1,σ^blk_2)= _1· _2^ω, where τ1,τ2∈V∗ _1, _2∈ V^*. Moreover, let q∈ℚq be the granularity of the weights, i.e., all weights in G are of the form q⋅mq· m, for m∈ℤm . Then, the mean-payoff values of the generated play is computable in O(N2q2⋅(maxvBal(v)−minvBal(v)))O ( N^2q^2·( _vBal(v)- _vBal(v)) ). Proof. It follows from Lem. 6 that there are three possible outcomes for the block-difference sequence Δ1,Δ2,… _1, _2,…. The first two are that it eventually stays in one of the infinite intervals, in which case eventually, only one vine is played. We consider the case in which the sequence is bounded. Let n∈Miln . We associate with π≤nπ^≤ n an energy configuration ⟨d↓(π≤n),d↕(π≤n)⟩ d (π^≤ n),d (π^≤ n) , where d↕(π≤n)=(e2(π≤n)−e1(π≤n))d (π^≤ n)=(e_2(π^≤ n)-e_1(π^≤ n)) and d↓(π≤n)d (π^≤ n) is the distance from the lower virtual energy to the boundary of the energy block that it belong to, formally for e=mine1(π≤n),e2(π≤n)e= \e_1(π^≤ n),e_2(π^≤ n) \, assume that e belongs to the β-th energy block, then d↓(π≤n)=(e−β⋅N)d (π^≤ n)=(e-β· N). Observe that for n,n′∈Miln,n with equality between the energy configurations, i.e., ⟨d↓(π≤n),d↕(π≤n)⟩=⟨d↓(π≤n′),d↕(π≤n′)⟩ d (π^≤ n),d (π^≤ n) = d (π^≤ n ),d (π^≤ n ) , the pairs of energies are block shifted, i.e., there exists k∈ℕk such that ei(π≤n)=ei(π≤n′)+kNe_i(π^≤ n)=e_i(π^≤ n )+kN, for i∈1,2i∈ \1,2 \. Thus, by Lem. 7, the next vine that is played from both prefixes is the same. Finally, we count the number of energy configurations that a play with a bounded energy-block difference sequence traverses. Since the length of an energy block is N, there are N/qN/q possibilities for d↓d . As seen in Lem. 6, the maximal and minimal possible values of Δ are respectively maxvBal(v)+1 _vBal(v)+1 and minvBal(v)−1 _vBal(v)-1, thus there are at most (maxvBal(v)−minvBal(v))+2)⋅Nq( _vBal(v)- _vBal(v))+2)· Nq possible values for d↕d . Since both are finite, eventually an energy configuration repeats, from which point the same sequence of vines is traversed. We conclude with an algorithm to compute the payoffs of the generated play. Construct a graph in which each vertex corresponds to an energy configuration. As mentioned above, each d=⟨d↓,d↕⟩d= d ,d determines the next vine to be played M(d)M(d). The (unique) neighbor of d is the energy configuration that corresponds to the energy updates following M(d)M(d). More formally, suppose that a pair of energies ⟨e1,e2⟩∈ℚ2 e_1,e_2 ^2 is mapped to d, then the neighbor of d is the energy configuration that ⟨e1+W1(M(d)),e2+W2(M(d))⟩ e_1+W_1 (M(d) ),e_2+W_2 (M(d) ) is mapped to. We add two sinks that corresponds to unbounded walks. Once the graph is constructed, all that is left is to find the vertex d0d_0 that corresponds to the initial choice of energies given by the initial configuration c0c_0, and find the ultimately period path in the graph that starts from d0d_0. Let the path be τ1⋅τ2 _1· _2 with τ2=d1,…,dk _2=d_1,…,d_k. Then, for i∈1,2i∈ \1,2 \, we have MPi(c0,σ1blk,σ2blk)=∑1≤j≤kWi(M(dj))/∑1≤j≤k|M(dj)|MP_i(c_0,σ^blk_1,σ^blk_2)= _1≤ j≤ kW_i (M(d_j) )/ _1≤ j≤ k|M(d_j)|. ∎ We point to an interesting corollary of Thm. 8. Let C be the cycle of vines that the generated play converges to. Observe that if the energy difference is bounded, then 1(C)=2(C) energy_1(C)= energy_2(C) and Player i’s payoff is MPi(π)=i(C)/|C|MP_i(π)= energy_i(C)/|C|, for i∈1,2i∈ \1,2 \. Corollary 9. (Fair payoffs). Consider a game G such that e2(π≤n)−e1(π≤n)e_2(π^≤ n)-e_1(π^≤ n) is bounded. Then, MP1(π)=MP2(π)MP_1(π)=MP_2(π). Example 3. Recall the two generated plays that are described in Ex. 1. The walk when Blue plays against Orange is bounded, thus both payoffs are 0.50.5, however when Blue plays against Red, the walk is unbounded and the payoffs differ. Fig. 5 is similar to the plots in Fig. 2 only at a reduced granularity. This highlights the slopes of the plots, which coincide with the mean-payoff. Figure 5: The plots for generated plays as in Fig. 2 only that the simulation is for 10k turns rather than 500. Remark 1 (Choosing different parameters). We describe the changes needed to lift the assumption that the two block strategies choose the same parameters N and z. First, Def. 4 is used to anticipate which vine will be played next based on the energy-block difference of the strategies. The choice of z affects the normalization of the bids throughout the vine, and note that the normalization does not directly depend on N. Thus, when the two strategies choose different values of z, we need a more complicated expression in the definition: Bal(v)=(log(z2)/log(z1))⋅log(St2(v)/St1(v))Bal(v)=( (z_2)/ (z_1))· (St_2(v)/St_1(v)). Second, different choices of N mean that the upper bound on the number of block differences in Thm. 8 needs to grow. 2.3 Games with long intervals have small cycles In this section we assume that the intervals are large: for every leaf ℓ , we have |l(ℓ)∩ℤ|≥3|l( ) |≥ 3. We characterize the recurrent behavior of such games. Let (π) inf(π) denote the set of leaves that are visited infinitely often in π. Theorem 10. If for every leaf ℓ , we have |l(ℓ)∩ℤ|≥3|l( ) |≥ 3, then |(π)|≤2| inf(π)|≤ 2. Proof. Assume towards contradiction that π visits at least three vines infinitely often. Observe the walk Δ1,Δ2,… _1, _2,…. By Lem. 2, the walk must traverse three adjacent intervals l(ℓ1),l(ℓ2)l( _1),l( _2), and l(ℓ3)l( _3) infinitely often. Denote l(ℓ2)=[a,b]l( _2)=[a,b]. Due to symmetry, assume Wlog that δ(l(ℓ2))=(→)δ(l( _2))=(→) or δ(l(ℓ2))=⊥δ(l( _2))= . Let i∈Mili such that the walk visits l(ℓ3)l( _3), i.e. Δ(π≤i)≥a+3 (π^≤ i)≥ a+3. By the premise of the theorem, it holds that each leaf ℓ has |l(ℓ)∩ℤ|≥3|l( ) |≥ 3. Γ(π≤i)≥a+1 (π^≤ i)≥ a+1. We prove that for every k≥ik≥ i, we have Γ(π≤k)≥a+1 (π^≤ k)≥ a+1. By Claim. 4, Δ(π≤k)≥a (π^≤ k)≥ a. Thus, l(ℓ1)l( _1) is not reached, which is a contradiction. Assume towards contradiction that π visits at least three vines infinitely often. Observe the walk Δ1,Δ2,… _1, _2,…. By Lem. 2, the walk must traverse three adjacent intervals l(ℓ1),l(ℓ2)l( _1),l( _2), and l(ℓ3)l( _3) infinitely often. Denote l(ℓ2)=[a,b]l( _2)=[a,b]. Due to symmetry, assume Wlog that δ(l(ℓ2))=(→)δ(l( _2))=(→) or δ(l(ℓ2))=⊥δ(l( _2))= . Let i∈Mili such that Δ(π≤i)≥a+3 (π^≤ i)≥ a+3. By the premise of the theorem, it holds that Γ(π≤i)≥a+1 (π^≤ i)≥ a+1. It is now sufficient to prove that for every k≥ik≥ i, we have Γ(π≤k)≥a+1 (π^≤ k)≥ a+1. Indeed, by Claim. 4, Δ(π≤k)≥a (π^≤ k)≥ a. Thus, l(ℓ1)l( _1) is not reached, which is a contradiction. We prove this holds. If Γ(π≤k)≥a+1 (π^≤ k)≥ a+1 then Δ(π≤k)≥a (π^≤ k)≥ a, and thus either we visit l(ℓ2)l( _2) at iteration k and so Γ(π≤k+1)≥Γ(π≤k)≥a+1 (π^≤ k+1)≥ (π^≤ k)≥ a+1 by our assumption on δ(l(ℓ2))δ(l( _2)), or we visit l(ℓ3)l( _3) at the current step, thus Γ(π≤k)≥Δ(π≤k)−1≥a+2 (π^≤ k)≥ (π^≤ k)-1≥ a+2 but notice that by the choice of N we get that Γ(π≤k+1)≥Γ(π≤k)−1≥a+1 (π^≤ k+1)≥ (π^≤ k)-1≥ a+1. In all cases we proved that for every k≥ik≥ i it holds Γ(π≤k)≥a+1 (π^≤ k)≥ a+1 ∎ We characterize the payoffs below. For a leaf ℓ , let (ℓ) len( ) be the length of the vine from v0v_0 to ℓ . Theorem 11. Let i∈1,2i∈ \1,2 \. If (π)=ℓ inf(π)=\ \, then MPi(π)=Wi(ℓ)/(ℓ)MP_i(π)=W_i( )/ len( ). If (π)=ℓ1,ℓ2 inf(π)= \ _1, _2 \, then MPi(π)=αWi(ℓ1)+Wi(ℓ2)α(ℓ1)+(ℓ2)MP_i(π)= α W_i( _1)+W_i( _2)α len( _1)+ len( _2), where α=W1(ℓ1)−W2(ℓ1)W2(ℓ2)−W1(ℓ2)α= W_1( _1)-W_2( _1)W_2( _2)-W_1( _2). Proof. The case of one vine is easy to see. Suppose that two vines ℓ1 _1 and ℓ2 _2 are visited infinitely often. Observe that this implies that the energy difference is bounded, thus denoting by C the period of π, we have 1(C)=2(C) energy_1(C)= energy_2(C). Suppose that the number of times that C traverses ℓ1 _1 and ℓ2 _2 is k and t, respectively. Thus, i(C)=k⋅Wi(ℓ1)+t⋅Wi(ℓ2) energy_i(C)=k· W_i( _1)+t· W_i( _2), for i∈1,2i∈ \1,2 \. Using α as in the statement leads to k=α⋅tk=α· t and to the mean-payoff expression. Now suppose that inf(π)=l(v1),l(v2)inf(π)=\l(v_1),l(v_2)\, and assume that the cycle visits v1v_1 and v2v_2 k and t times respectively, then we enter a cycle C where W1(C)=W2(C)W_1(C)=W_2(C) such that Wi(C)W_i(C) is the added energy to player i through the cycle, since the energy difference is bounded. We can see that, ∀i∈1,2wi(C)=kwi(P1)+twi(P2)∀ i∈\1,2\w^i(C)=kw^i(P_1)+tw^i(P_2) and by the equality, denoting α=W2(v2)−W1(v2)W1(v1)−W2(v1)α= W_2(v_2)-W_1(v_2)W_1(v_1)-W_2(v_1) we get that k=α⋅tk=α· t. It is easy to see that every visit to vjv_j adds Wi(vj)W_i(v_j) to the energy of player i, and takes λ(vj)λ(v_j) steps. Since the prefix before the cycle and the suffix of a partial cycle are both finite, we can ignore them and compute the mean-payoff of the game as: MPi(π)=Wi(C)λ(C)=kWi(v1)+tWi(v2)λ(v1)k+λ(v2)tMP_i(π)= W_i(C)λ(C)= kW_i(v_1)+tW_i(v_2)λ(v_1)k+λ(v_2)t =αtWi(v1)+tWi(v2)(λ(v1)α+λ(v2))t=αWi(v1)+Wi(v2)λ(v1)α+λ(v2)= α tW_i(v_1)+tW_i(v_2)(λ(v_1)α+λ(v_2))t= α W_i(v_1)+W_i(v_2)λ(v_1)α+λ(v_2) ∎ Example 4. Consider the game depicted in Fig. 1. Note since two leaves are reachable, there are two non-empty intervals, both of which are unbounded, thus Thm. 10 applies. Plugging W1(ℓ1)=1W_1( _1)=1, W2(ℓ1)=2W_2( _1)=2, W1(ℓ3)=2W_1( _3)=2, W2(ℓ3)=0W_2( _3)=0, (ℓ1)=3 len( _1)=3, and (ℓ3)=2 len( _3)=2, thus α=2α=2 and MP1(π)=MP2(π)=2⋅2+02⋅3+2=0.5MP_1(π)=MP_2(π)= 2· 2+02· 3+2=0.5. 3 The Generated Path for Budget Strategies We now turn to analyze the path induced by budget strategies, introduced in [18]. Intuitively, in a budget strategy each player bids a constant fraction of their budget, based on the current vertex, and chooses the successor with the highest potential, if they win. We show that for recurrent games, such strategies yield a piecewise-linear dynamics of the budgets. We give a condition on these dynamics that guarantees the path that corresponds to the strategies is ultimately periodic (c.f. Thm. 14). However, showing this condition holds in the general case is currently out of reach. Nonetheless, we manage to show it holds for the subclass of recurrent games whose tree is of depth 11, called repeated bidding games. The budget strategy We describe the budget strategy σibgtσ^bgt_i for Player i, for i∈1,2i∈ \1,2 \, as constructed in [18]. The main difference from the block strategy is that the choice of normalization factor now depends on the current budget. The strategy proceeds as follows. Player i chooses a constant αi∈(0,1) _i∈(0,1) such that (1−αi)=(1+αi)−(1+ε)(1- _i)=(1+ _i)^-(1+ ), which is shown to always exist. When reaching vertex v with budget BiB_i, Player i bids bi=αiSti(v)Stmax⋅Bib_i= _i St_i(v)St_max· B_i, where StmaxSt_max is the maximal strength among Player i’s strengths, and upon winning the bidding, proceeds to v+v^+ that maximizes the potential similar to the block strategy (see App. A). As in the case of block strategies, we remark that the presentation of the budget strategies is condensed and does not clarify the entirety of the construction. We only include the bare minimum required to understand our analysis. 3.1 A semi-algorithm to find payoffs in general recurrent games Consider a recurrent game G with initial vertex v0v_0, and fix budget strategies σ1bgt,σ2bgtσ^bgt_1,σ^bgt_2 for the players. Given an initial budget c for Player 11, the strategies uniquely determine the next vine θ(c)θ(c). Definition 6. The budget-update function is :[0,1]→[0,1] B:[0,1]→[0,1] such that (c) B(c) is the budget at the next milestone when starting at v0v_0 with budget c. Observe that from an initial budget c0c_0, the sequence of budgets c0,c1,…c_0,c_1,… in the milestones of (c0,σ1bgt,σ2bgt) play(c_0,σ^bgt_1,σ^bgt_2) satisfies ci=i(c0)c_i= B^i(c_0), where i B^i is the composition of B with itself i times. Thus, the entire behavior of the play is determined by the dynamics induced by B. In the remainder of this section we study this dynamics. The first step is to show that B is piecewise-linear. Example 5. A repeated bidding game is a recurrent game with three vertices: a root v0v_0 with two children v1v_1 and v2v_2. We derive an explicit expression for B in such games. First observe that the root v0v_0 is the only possible vertex with St(v0)>0St(v_0)>0. Thus, Sti(v0)Stmax=1 St_i(v_0)St_max=1. Therefore, σibgtσ^bgt_i bids αix _ix at v0v_0 (where x is the budget). then from initial budget x, Player 11 wins the bidding if and only if α1x≥α2(1−x) _1x≥ _2(1-x), equivalently x≥α2α1+α2x≥ _2 _1+ _2. Then, the next budget if PlayerPlayer~1 wins is x−α1x=(1−α1)x- _1x=(1- _1)x, and otherwise x+α2(1−x)=(1−α2)x+α2x+ _2(1-x)=(1- _2)x+ _2. We thus have the following piecewise-linear form. (x)=(1−α2)x+α2 if x<α2α1+α2(1−α1)x if x≥α2α1+α2 B(x)= cases(1- _2)x+ _2& if x< _2 _1+ _2\\ (1- _1)x& if x≥ _2 _1+ _2\\ cases Example 5 can be extended by induction to general recurrent games to obtain the following. Lemma 12. For every recurrent game G the budget-update function B is piecewise-linear. Proof. Consider the tree representation of G. We construct B in a bottom-up fashion, starting from the leaves. Let StmaxSt_ be the maximal strength of a vertex in the game. For each leaf u, we set the function u(x)=x B_u(x)=x. Indeed, no bidding takes place in the leaves, and the budget when returning to v0v_0 does not change. Next, assume u1 B_u_1 and u2 B_u_2 are piecewise linear functions already defined for subtrees of a subtree rooted at u, we define u B_u similarly to example˜5, as follows. Assume u1u_1 (resp. u2u_2) is the maximal potential child of u for Player 11 (resp. Player 22) (if both players share the potential maximizer, then no bidding take place and one of the subtrees can be removed). Then, according to σibgtσ^bgt_i, Player i bids αiSti(u)Stmaxx _i St_i(u)St_ x given budget x. Denote ξi=αiSti(u)Stmax _i= _i St_i(u)St_ Thus, Player 11 wins the bidding if and only if ξ1x≥ξ2(1−x) _1x≥ _2(1-x), equivalently if x≥ξ2ξ1+ξ2x≥ _2 _1+ _2. The budget transferred to u1u_1 if Player 11 wins is then (1−ξ1)x(1- _1)x, and otherwise (1−ξ2)x+ξ2(1- _2)x+ _2 is transferred to u2u_2. It follows that the next budget at v0v_0 (starting from u with budget x) is u(x)=u2((1−ξ2)x+ξ2) if x<ξ2ξ1+ξ2u1((1−ξ1)x) if x≥ξ2ξ1+ξ2 B_u(x)= cases B_u_2((1- _2)x+ _2)& if x< _2 _1+ _2\\ B_u_1((1- _1)x)& if x≥ _2 _1+ _2\\ cases u B_u is then piecewise linear as a composition (by branches) of piecewise-linear functions. We can then conclude the claim with ≡v0 B≡ B_v_0. ∎ Intuitively, each linear “branch” of B corresponds to an interval of budgets for which σ1bgt,σ2bgtσ^bgt_1,σ^bgt_2 induce the same vine to the next milestone. By extension, notice that i B^i is also piecewise-linear for all i (as a composition of piecewise-linear functions), and each branch of i B^i corresponds to a specific sequence of i vines to be seen from an interval of budgets. We proceed to make this intuition formal. Define the set ⊆[0,1] bif [0,1] of bifurcation points of B to be the set of points where B changes its behavior from one linear branch to another (e.g., in example˜5 we have =α2α1+α2 bif=\ _2 _1+ _2\). We then extend this to i B^i for all i∈ℕi by defining 1= and i=i−1∪x∣(x)∈i−1 bif^1= bif and bif^i= bif^i-1∪\x B(x)∈ bif^i-1\ By definition we have i⊆i+1 bif^i bif^i+1. Thus, we can define the limit of this sequence as ∞=⋃i∈ℕi bif^∞= _i bif^i. Observe that i bif^i indeed captures the set of points where i B^i may change its linear branch. Lemma 13. Consider an interval I⊆[0,1]I [0,1] such that I∩=∅I∩ bif= , then there is a vine θ such that for every x∈Ix∈ I, the vine taken first in (x,σ1bgt,σ2bgt) path(x,σ^bgt_1,σ^bgt_2) is θ. Proof. Intuitively, notice that the set of bifurcations in B corresponds to the budget thresholds at every node in the tree of G. It follows that all x∈Ix∈ I induce the same vine in the tree. We proceed with the details, relying on the notation u B_u from the proof of lemma˜12. Consider x,y∈Ix,y∈ I. Starting from v0v_0, since I∩=∅I∩ bif= , it follows that both x and y take the same bifurcation of v0 B_v_0. This leads the play to either v1v_1 or v2v_2 (the children of v0v_0). Assume the game proceeds to v1v_1 (the case of v2v_2 is analogous). Then the budget with which v1v_1 is reached is (1−ξ1)x(1- _1)x and (1−ξ1)y(1- _1)y respectively. Recall that in this branch we have v0(x)=v1(1−ξ1)x B_v_0(x)= B_v_1(1- _1)x (and similarly for y). It follows that the bifurcations of v0 B_v_0 arising in this branch are at all b such that (1−ξ1)b(1- _1)b is a bifurcation of v1 B_v_1. This means that (1−ξ1)x(1- _1)x and (1−ξ1)y(1- _1)y are again in a single branch of v1 B_v_1, so we can continue the same reasoning by induction down to the leaves. ∎ We now show that if ∞ bif^∞ is finite, then (c,σ1bgt,σ2bgt) path(c,σ^bgt_1,σ^bgt_2) is ultimately periodic. Intuitively, this is because if an interval I with I∩∞=I∩ bif^∞= is visited twice, we can show that due to the piecewise linearity, it is visited periodically. Then, Lem. 13 gives us the result. Theorem 14. Let (c0,σ1bgt,σ2bgt)=v0,v1,… path(c_0,σ^bgt_1,σ^bgt_2)=v_0,v_1,…. If ∞ bif^∞ is finite, then there exists N0,k∈ℕN_0,k such that for every n>N0n>N_0 it holds that vn=vn+kv_n=v_n+k. Proof. Since ∞ bif^∞ is finite, let N1∈ℕN_1 such that for all n≥N1n≥ N_1 we have n=n+1=∞ bif^n= bif^n+1= bif^∞. We then have n=n+1=n∪x∣(x)∈n bif^n= bif^n+1= bif^n∪\x B(x)∈ bif^n\, and in particular x∣(x)∈n⊆n\x B(x)∈ bif^n\ bif^n. In the contrapositive, we get that if x∉nx∉ bif^n, then (x)∉n B(x)∉ bif^n. Therefore, for every interval I⊆[0,1]I [0,1] such that I∩∞=∅I∩ bif^∞= we have that (I)∩∞=∅ B(I)∩ bif^∞= . For every i∈ℕi , let ci=i(c0)c_i= B^i(c_0) be the budget after i milestones. For every n≥N1n≥ N_1, let In⊆[0,1]I_n [0,1] be the maximal interval (with respect to containment) such that cn∈Inc_n∈ I_n and In∩∞=∅I_n∩ bif^∞= (i.e., InI_n is the “entire branch” of n B^n where cnc_n lies). Since ∞ bif^∞ is finite, there exist N0≥N1N_0≥ N_1 and k>0k>0 such that IN0=IN0+kI_N_0=I_N_0+k. Then, we claim that for every n≥N0n≥ N_0 it holds that In=In+kI_n=I_n+k, i.e., that the intervals visited after N0N_0 are visited periodically. Indeed, since cn∈Inc_n∈ I_n, then cn+1=(cn)∈(In)c_n+1= B(c_n)∈ B(I_n), but B is linear when restricted to InI_n, and therefore (In) B(I_n) is an interval, and moreover (In)∩∞=∅ B(I_n)∩ bif^∞= (since n≥N1n≥ N_1 and therefore no additional bifurcations are introduced). It follows that (In)⊆In+1 B(I_n) I_n+1. In particular, (IN0+k)⊆IN0+k+1 B(I_N_0+k) I_N_0+k+1 but also (IN0+k)=(IN0)⊆IN0+1 B(I_N_0+k)= B(I_N_0) I_N_0+1. We depict this idea in fig.˜6. Since the intervals under consideration are maximal, it follows that IN0+1=IN0+k+1I_N_0+1=I_N_0+k+1, and we can proceed by induction to conclude the claim. Finally, by Lem. 13 we have that the ultimately periodic sequence of intervals induces an ultimately periodic sequence of vines visited from N0N_0, which concludes the proof. ∎ xxN0(x) B^N_0(x)00.20.40.60.81 B B B B Figure 6: N0 B^N_0 maps “whole intervals” to “whole intervals”, and thus jumps between the intervals defined by ∞ bif^∞ until returning to some interval, which is then mapped again into the cycle regardless of the specific budget with which the interval is reached. The proof of Thm. 14 suggests a semi-algorithm for computing the mean payoff of the players in the play: given an initial budget B1B_1 keep track of i bif^i until it converges. If it does, keep track of the intervals until a period is reached. From there, evaluating the mean payoff amounts to evaluating the weights in the period of vines. 3.2 The generated path is ultimately periodic in repeated bidding games Analyzing the dynamics governed by piecewise-linear functions is notoriously difficult [23], and is typically handled only for simple cases, e.g., [24, 25]). In this section, we show that ∞ bif^∞ is finite for repeated bidding games (c.f., example˜5), thus showing that the mean-payoff in this case is computable. Recall from example˜5 the form of (x) B(x) in a repeated bidding game. Specifically, we have that 1=α2α1+α2 bif^1=\ _2 _1+ _2\. For every i∈ℕi denote Ai=x∣(x)∈i−1A_i=\x B(x)∈ bif^i-1\ (i.e., Ai=−1(i−1)A_i= B^-1( bif^i-1)), and note that i=i−1∪Ai bif^i= bif^i-1∪ A_i. In order to prove that ∞ bif^∞ is finite, it suffices to prove that Ai=∅A_i= for all i≥N0i≥ N_0 for some N0N_0, or equivalently that AN0=∅A_N_0= for some N0N_0 (so the claim follows by induction). Consider the inverse relation −1 B^-1 and some x∈[0,1]x∈[0,1]. In order to compute −1(x) B^-1(x) we use the explicit formulation of B: we see that y∈−1(x)y∈ B^-1(x) if either (1) 0≤y<α2α1+α20≤ y< _2 _1+ _2 and x=(1−α2)y+α2x=(1- _2)y+ _2 or (2) 1≥y≥α2α1+α21≥ y≥ _2 _1+ _2 and x=(1−α1)yx=(1- _1)y. Rearranging the above, we define the “domains” of the conditions as I1=[α2,α2α1+α2+α1α2α1+α2)I_1=[ _2, _2 _1+ _2+ _1 _2 _1+ _2) and I2=[α2α1+α2−α1α2α1+α2,1−α1]I_2=[ _2 _1+ _2- _1 _2 _1+ _2,1- _1] We can then capture −1 B^-1 using two functions: R1(x)=x−α21−α2 if x∈I1 and R2(x)=x1−α1 if x∈I2R_1(x)= x- _21- _2 if x∈ I_1 and R_2(x)= x1- _1 if x∈ I_2 Indeed, we now have that −1(x)=R1(x),R2(x) B^-1(x)=\R_1(x),R_2(x)\ (by ignoring undefined values), and so Ai=R1(i−1)∪R2(i−1)A_i=R_1( bif^i-1)∪ R_2( bif^i-1). We now present a simple technical lemma from the theory of attractors in linear dynamical systems, which we use to analyze the behavior of R1R_1 and R2R_2. Lemma 15. Let y(x)=ax+by(x)=ax+b be a linear function and let x0∈ℝx_0 be the (unique) fixed point of y, i.e. y(x0)=x0y(x_0)=x_0. Then, ∀x∈ℝ:y(x)−x0=a(x−x0)∀ x :y(x)-x_0=a(x-x_0). In particular, if a>1a>1 and x≠x0x≠ x_0, then limn→∞|yn(x)−x0|=∞ _n→∞|y^n(x)-x_0|=∞. Proof. First, we have that y(x)−x0=y(x)−y(x0)=ax+b−ax0−b=a(x−x0).y(x)-x_0=y(x)-y(x_0)=ax+b-ax_0-b=a(x-x_0). Next, observe that x0x_0 is also a fixed point of yny^n, where yn(x)=anx+b′y^n(x)=a^nx+b where b′b is some constant depending on a,b,na,b,n. Thus, if a>1a>1, we have yn(x)−x0=an(x−x0)y^n(x)-x_0=a^n(x-x_0), so limn→∞|yn(x)−x0|=limn→∞an|x−x0|=∞. _n→∞|y^n(x)-x_0|= _n→∞a^n|x-x_0|=∞. ∎ We are now ready to prove that ∞ bif^∞ is finite. Theorem 16. In the notations above, for a repeated bidding game, ∞ bif^∞ is finite. Moreover, there exists N0=O(maxlogαiαi+αjlog1−αj)N_0=O ( _i _i+ _j 1- _j ) for i≠j∈1,2i≠ j∈\1,2\ such that N0=∞ bif^N_0= bif^∞. Proof. Notice that R1R_1 and R2R_2, thought of as ℝ→ℝR functions, are linear. Moreover, their unique fixed points are x01=1x_0^1=1 and x02=0x_0^2=0, respectively (indeed, R1(1)=1R_1(1)=1 and R2(0)=0R_2(0)=0). Consider some x∈(0,1)x∈(0,1). By applying Lem 15 to R1R_1 we get that R1(x)−x01=11−α2(x−x01)<x−x01R_1(x)-x^1_0= 11- _2(x-x^1_0)<x-x^1_0 (since α2∈(0,1) _2∈(0,1) and x−x01<0x-x^1_0<0), and therefore R1(x)<xR_1(x)<x, i.e., R1R_1 is “left shifting”. Moreover, by Lem. 15 we have that limn→∞R1n(x)=−∞ _n→∞R_1^n(x)=-∞. A similar analysis shows that R2R_2 is “right shifting” and limn→∞R2n(x)=∞ _n→∞R_2^n(x)=∞. For brevity, denote τ=α2α1+α2τ= _2 _1+ _2 and χ=α1α2α1+α2χ= _1 _2 _1+ _2. We show that there exists N0∈ℕN_0 such that AN0=∅A_N_0= . Intuitively, the idea is as follows: R1R_1 is left shifting, and its domain is below τ+χτ+χ. Therefore, any points in AiA_i above τ+χτ+χ can no longer decrease, and eventually escape beyond 11, and therefore do not generate further bifurcation points. Similarly, R2R_2 is right shifting, and its domain is above τ−χτ-χ, so any points below it escape to below 0. It is thus left to show that after a finite number of iterations, points indeed go outside these intervals (See Fig. 7). We first show that A2⊆R1(τ),R2(τ)A_2 \R_1(τ),R_2(τ)\ contains at most two points, one to the left of I2I_2 and one to the right of I1I_1. Since R2R_2 is right shifting and R1R_1 is left shifting, it follows that these two points eventually (after some N0N_0 iterations) escape the interval (0,1)(0,1), at which stage we have AN0=∅A_N_0= . Recall that 1=τ bif^1=\τ\. We first show that if τ∈I1τ∈ I_1 then R1(τ)R_1(τ) falls to the left of I2I_2. Indeed: τ−α21−α2<τ−χ τ- _21- _2<τ-χ ⇔ α2α1+α2−α21−α2<α2α1+α2−α1α2α1+α2 _2 _1+ _2- _21- _2< _2 _1+ _2- _1 _2 _1+ _2 ⇔ α2α1+α2−α2<(1−α2)(1−α1)(α2α1+α2) _2 _1+ _2- _2<(1- _2)(1- _1) ( _2 _1+ _2 ) ⇔ −1<(α1α2−(α1+α2))(1α1+α2) -1<( _1 _2-( _1+ _2)) ( 1 _1+ _2 ) ⇔ 0<α1α2 0< _1 _2 which always holds. Similarly, if τ∈I2τ∈ I_2 then R2(τ)R_2(τ) falls to the right of I1I_1. Indeed: τ1−α1>τ+χ τ1- _1>τ+χ ⇔ α2α1+α21−α1>α2α1+α2+α1α2α1+α2 _2 _1+ _21- _1> _2 _1+ _2+ _1 _2 _1+ _2 ⇔ α2α1+α2>(1+α1)(1−α1)(α2α1+α2) _2 _1+ _2>(1+ _1)(1- _1) ( _2 _1+ _2 ) ⇔ 1>1−α12⇔α12>0 1>1- _1^2 _1^2>0 which always holds. Finally, the bound on N0N_0 follows by bounding the number of applications of R1R_1 (resp. R2R_2) to τ before it escapes (0,1)(0,1). Let n be the number of iterations after which R2n(τ)≤1R_2^n(τ)≤ 1, then by Lem. 15 it holds that (11−α1)nτ>1 ( 11- _1 )^nτ>1. Rearranging we get n≤τlog(1−α1)n≤ τ (1- _1), and by similar analysis for R1R_1 we get the upper bound. ∎ Figure 7: The domains I1,I2 [rgb]1,0,0 [named]pgfstrokecolorrgb1,0,0I_1, [rgb]0,0,1 [named]pgfstrokecolorrgb0,0,1I_2 and the dynamics governed by R1,R2 [rgb]1,0,0 [named]pgfstrokecolorrgb1,0,0R_1, [rgb]0,0,1 [named]pgfstrokecolorrgb0,0,1R_2 starting from τ. After a single iteration, R1(τ) [rgb]1,0,0 [named]pgfstrokecolorrgb1,0,0R_1(τ) is to the left of I2 [rgb]0,0,1 [named]pgfstrokecolorrgb0,0,1I_2, and R2(τ) [rgb]0,0,1 [named]pgfstrokecolorrgb0,0,1R_2(τ) is to the right of I1 [rgb]1,0,0 [named]pgfstrokecolorrgb1,0,0I_1. After several iterations, the points escape (0,1)(0,1).I1I_1I2I_2τα2 _2τ+χτ+χτ−χτ- 1−α11- _1()()R2R_2R2R_2R2R_2R1R_1R1R_1R1R_1 By Thms. 14 and 16 we have that for repeated bidding games, the algorithm always halts, and we have a bound on N0N_0. This enables us to conclude the following. Corollary 17. Given a repeated bidding game, MPi(π)MP_i(π) is computable in time polynomial in O(maxlogαiαi+αjlog1−αj)O( _i _i+ _j 1- _j) for i≠j∈1,2i≠ j∈\1,2\. 4 Discussion We analyze the path generated by the two types of known explicit optimal strategies in mean-payoff bidding games, show that it is ultimately periodic in certain graphs, and develop algorithms to reason about its performance. Interestingly, the discrete nature of the block strategy is an advantage in our study whereas in the study of all-pay bidding [18], for which the budget strategies were first constructed, the continuous nature of the latter was essential. We list several directions for future work. First, we leave open questions; e.g., analyzing general strongly-connected graphs and tightening the computational complexity. Second, analyzing the generated play is a general phenomenon and can be studied in any game. The analysis is technically interesting in mean-payoff bidding games since optimal strategies are succinctly represented, and it is interesting to analyze games with other bidding mechanisms for which explicit constructions are known [26, 18]. Finally, the strategies that we consider are designed offline to optimize against an adversary. An interesting direction for future research is to develop strategies that adapt online to the competitor they are paired with. We expect that the novel analysis techniques that we develop here will be useful to develop such strategies. Acknowledgments This work was supported in part by the Israel Science Foundation, grant numbers 989/22 and 1679/21. References Kolumbus and Nisan [2022] Kolumbus, Y., Nisan, N.: Auctions between regret-minimizing agents. In: Proc. 31st W, p. 100–111. ACM (2022) Hart and Mas-Colell [2003] Hart, S., Mas-Colell, A.: Uncoupled dynamics do not lead to nash equilibrium. American Economic Review 93(5), 1830–1836 (2003) Alur et al. [2002] Alur, R., Henzinger, T.A., Kupferman, O.: Alternating-time temporal logic. J. ACM 49(5), 672–713 (2002) Pnueli and Rosner [1989] Pnueli, A., Rosner, R.: On the synthesis of a reactive module. In: Proc. 16th POPL, p. 179–190 (1989) Rabin [1969] Rabin, M.O.: Decidability of second order theories and automata on infinite trees. Transaction of the AMS 141, 1–35 (1969) Lazarus et al. [1999] Lazarus, A.J., Loeb, D.E., Propp, J.G., Stromquist, W.R., Ullman, D.H.: Combinatorial games under auction play. Games and Economic Behavior 27(2), 229–264 (1999) Lazarus et al. [1996] Lazarus, A.J., Loeb, D.E., Propp, J.G., Ullman, D.: Richman games. Games of No Chance 29, 439–449 (1996) Zwick and Paterson [1996] Zwick, U., Paterson, M.: The complexity of mean payoff games on graphs. Theor. Comput. Sci. 158(1&2), 343–359 (1996) Avni et al. [2019] Avni, G., Henzinger, T.A., Chonev, V.: Infinite-duration bidding games. J. ACM 66(4), 31–13129 (2019) Amanatidis et al. [2022] Amanatidis, G., Birmpas, G., Filos-Ratsikas, A., Voudouris, A.A.: Fair division of indivisible goods: A survey. In: Raedt, L.D. (ed.) Proc. 31st IJCAI, p. 5385–5393. ijcai.org (2022) Aziz et al. [2022] Aziz, H., Li, B., Moulin, H., Wu, X.: Algorithmic fair allocation of indivisible items: a survey and new questions. SIGecom Exch. 20(1), 24–40 (2022) Meir et al. [2018] Meir, R., Kalai, G., Tennenholtz, M.: Bidding games and efficient allocations. Games and Economic Behavior 112, 166–193 (2018) https://doi.org/10.1016/j.geb.2018.08.005 Babaioff et al. [2021] Babaioff, M., Ezra, T., Feige, U.: Fair-share allocations for agents with arbitrary entitlements. In: Proc. 21st EC, p. 127. ACM (2021) Gorokh et al. [2021] Gorokh, A., Banerjee, S., Iyer, K.: The remarkable robustness of the repeated fisher market. In: Proc. 22nd EC, p. 562. ACM (2021) Avni et al. [2026] Avni, G., Henzinger, T.A., Mallik, K., Sadhukhan, S., Thejaswini, K.S.: Decoupled planning for multiple omega-regular objectives. In: Proc. 38th CAV (2026) Avni et al. [2024] Avni, G., Mallik, K., Sadhukhan, S.: Auction-based scheduling. In: Proc 30th TACAS. Lecture Notes in Computer Science, vol. 14572, p. 153–172. Springer (2024) Daskalakis et al. [2006] Daskalakis, C., Goldberg, P.W., Papadimitriou, C.H.: The complexity of computing a nash equilibrium. In: Proc. 38th STOC, p. 71–78. ACM (2006) Avni et al. [2021] Avni, G., Jecker, I., Žikelić, Đ.: Infinite-Duration All-Pay Bidding Games. In: Proc. 32nd SODA, p. 617–636 (2021) Kreps et al. [1982] Kreps, D.M., Milgrom, P., Roberts, J., Wilson, R.: Rational cooperation in the finitely repeated prisoners’ dilemma. Journal of Economic Theory 27(2), 245–252 (1982) Aumann et al. [1995] Aumann, R.J., Maschler, M., Stearns, R.E.: Repeated Games with Incomplete Information. MIT press (1995) Bailey and Piliouras [2018] Bailey, J.P., Piliouras, G.: Multiplicative weights update in zero-sum games. In: Proc. 19th EC, p. 321–338. ACM (2018) Mertikopoulos et al. [2018] Mertikopoulos, P., Papadimitriou, C.H., Piliouras, G.: Cycles in adversarial regularized learning. In: Czumaj, A. (ed.) Proc. 29th SODA, p. 2703–2717. SIAM (2018) Pettit et al. [1997] Pettit, N., Wellstead, P., Wilson-Jones, R.: The analysis and stability of piecewise linear dynamical systems. In: IUTAM Symposium on Interaction Between Dynamics and Control in Advanced Mechanical Systems: Proceedings of the IUTAM Symposium Held in Eindhoven, The Netherlands, 21–26 April 1996, p. 279–286 (1997). Springer Freire et al. [1998] Freire, E., Ponce, E., Rodrigo, F., Torres, F.: Bifurcation sets of continuous piecewise linear systems with two zones. International Journal of Bifurcation and Chaos 8(11), 2073–2097 (1998) Laurent and Nogueira [2012] Laurent, M., Nogueira, A.: Approximation to points in the plane by SL (2, z)-orbits. J. Lond. Math. Soc. 85(2), 409–429 (2012) Avni et al. [2018] Avni, G., Henzinger, T.A., Ibsen-Jensen, R.: Infinite-duration poorman-bidding games. In: Proc. 14th WINE. LNCS, vol. 11316, p. 21–36. Springer (2018) Puterman [2005] Puterman, M.L.: Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley & Sons, Inc., New York, NY, USA (2005) Appendix A Vertex importance; strengths and potentials The strength of a vertex, denoted St:V→ℚSt:V , intuitively measures its importance; if St(v)<St(u)St(v)<St(u), then winning a bidding in u is more important than in v. Definition 7. (Potentials and strengths). The potential is a function Pot:V→ℚPot:V that for every vertex v∈Vv∈ V, satisfies Pot(v)=Pot(v+)+Pot(v−)2+w(v)−MP(RT())Pot(v)= Pot(v^+)+Pot(v^-)2+w(v)-MP(RT(G)) where v+=argmaxu∈(v)Pot(u)v^+= _u (v)Pot(u) and v−=argminu∈(v)Pot(u)v^-= _u (v)Pot(u). For v∈Vv∈ V, the strength is a non-negative quantity based on the potential in (v)N(v). Specifically: St(v)=Pot(v+)−Pot(v−)2St(v)= Pot(v^+)-Pot(v^-)2 The existence of a potential function is guaranteed following results on stochastic games [27]. Example 6. We illustrate the idea behind the definition of strengths. The details, which are orthogonal to this paper, can be found in [9]. Consider the game G that is depicted in Fig 3. We have MP(RT())=0MP (RT(G) )=0. It is not hard to verify that the potentials and strengths satisfy the requirements. For example, Pot(v0)=12⋅(Pot(v1)+Pot(ℓ3))=12⋅(−2+2)=0Pot(v_0)= 12·(Pot(v_1)+Pot( _3))= 12·(-2+2)=0 and St(v0)=12⋅(Pot(ℓ3)−Pot(v1))=12⋅(2−(−2))=2St(v_0)= 12·(Pot( _3)-Pot(v_1))= 12·(2-(-2))=2. Max’s strategy ties between changes in energy and changes in budget. To illustrate, assume that there are no budget requirements, Max bids St(v)St(v) at v∈Vv∈ V, and follows the outgoing red edge upon winning the bidding. We describe two Min responses. First, Min wins the bidding at v0v_0, proceeds to v1v_1, and pays Max at least 22 units of budget, then Max wins the bidding at v1v_1, pays Min 33 units of budget, and proceeds to ℓ1 _1, where the energy increases by 11. All in all, Max “invests” 11 unit of budget in order to increase the energy by 11. Second, Min wins both biddings, i.e., she pays Max at least 22 at v0v_0 and 33 at v1v_1 for a total of 55. The game reaches ℓ2 _2 where the energy decreases by 55. Thus, Max “gains” 55 units of budget when the energy decreases by 55. One can verify that the last vine satisfies this property.