Mean-Payoff and Energy Discrete-Bidding Games

The central quantity that we study in mean-payoff games is threshold budgets, which we define as follows: for a target payoff $c$ for Max, the threshold budget is necessary and sufficient for guaranteeing payoff $c$. Before elaborating on our results, we point to an inherent distinction between mean-payoff discrete- and continuous-bidding games: in strongly-connected games, under continuous-bidding, Max can guarantee the same payoff for every initial budget, whereas the following example shows that this is not the case under discrete bidding.

Technically, we study energy games, and the results directly apply to mean-payoff bidding games, similar to turn-based games (e.g., [17]). An energy bidding game is played between Consumer (Cons) and Preserver (Pres) on a weighted graph. A play $\pi$ corresponds to an infinite sequence of weights. Fix an initial energy $M\in \mathbb{N}$. Cons’s goal is to “consume” the energy; formally, Cons wins iff there is a prefix of length $m$ such that .

We study two types of thresholds in energy games. First, we show existence of energy thresholds; for every initial vertex $v$, for every initial budget $B$, we show that there exists an initial energy, denoted $\text{Energy}(v,B)$ that is both necessary and sufficient for Pres to guarantee winning. We point out that existence of energy thresholds implies determinacy, namely from each initial configuration, one of the players has a (pure) winning strategy. Bidding games are formally a subclass of concurrent games [2], the latter are not determined; e.g., neither player has a winning strategy in “matching pennies”. Still, we show that energy bidding games are a determined subclass of concurrent games (see also [1, 16]). Second, we define threshold budgets in energy bidding games. Before describing the definition, note that at $v$, there could be a budget $B$ for which Pres loses with every initial energy. A simple example is a sink with a negative self loop. In such cases, $\text{Energy}(v,B)=\mathrm{\infty }$. Further note that $\text{Energy}(v,B)$ increases as $B$ decreases. We define the threshold in a vertex $v$, denoted $\mathrm{𝑇ℎ}(v)$, as the minimal budget $B$ such that $\text{Energy}(v,B)$ is finite.

A key result in the paper shows that $\mathrm{𝑇ℎ}$ satisfies the average property. This is an important ingredient in constructing concise budget agnostic strategies, which ignore “excess” budget; more formally, at vertex $v$, for budget $B\ge \mathrm{𝑇ℎ}(v)$, a budget agnostic strategy acts in $B$ and $B^{\ast }$ as if the budget is $\mathrm{𝑇ℎ}(v)$ and $\mathrm{𝑇ℎ}{(v)}^{\ast }$, respectively. Existence of winning budget agnostic strategies is key in proving that finding threshold budgets³³3Formally, given a game, a vertex $v$, and a value $t$, decide whether $\mathrm{𝑇ℎ}(v)\ge t$. is in NP and coNP.

A bidding game is formally, a succinctly represented concurrent game. We define concurrent games, and then describe the concurrent game that a bidding game corresponds to.

Intuitively, a concurrent game is a two-player game that is played on a graph, where each vertex is associated with a set of allowed actions for each player. The game proceeds as follows. A token is initially placed on a vertex. In each turn, the players simultaneously choose an allowed action, and their joint actions determine the next vertex the token moves to. This generates an infinite path, which determines the winner of the game.

Formally a concurrent game is played on an arena $⟨A,Q,\lambda ,\delta ⟩$, where $A$ is a set of actions, $Q$ is a set of states, $\lambda :Q\times \{1,2\}\to 2^A\setminus \mathrm{\varnothing }$ specifies the allowed actions for each player at a state, and the transition function is $\delta :Q\times A\times A\to Q$. The neighbors of $q\in Q$ are $N(q)=\{q^{\prime }\in Q:\exists a_1,a_2\in A\text{ such that }{q}^{\prime }\in \delta (q,a_1,a_2)\}$. For an infinite path $\pi =q_0,q_1,\mathrm{\dots }$, we denote the prefix of length $m\in \mathbb{N}$ by ${\pi }^{\le m}=q_0,\mathrm{\dots },q_m$.

A strategy is intuitively a recipe for playing the game. For $i\in \{1,2\}$, a strategy for $\mathrm{𝑃𝑙𝑎𝑦𝑒𝑟}i$ is a function ${\sigma }_i:Q^{\ast }\to A$, which prescribes which action to take given a history of the game. We restrict to strategies that choose only allowed actions, that is for a history $h\in Q^{\ast }$, a $\mathrm{𝑃𝑙𝑎𝑦𝑒𝑟}i$ strategy chooses an action $a_i\in \lambda (q,i)$. The play that two strategies ${\sigma }_1$ and ${\sigma }_2$ and an initial vertex $q_0$ give rise to, denoted $\text{play}(q_0,{\sigma }_1,{\sigma }_2)$, is defined inductively as follows. The play starts from $q_0$. Suppose that the prefix ${\pi }^{\le m}$ of length $m\ge 1$ of $\text{play}(q_0,{\sigma }_1,{\sigma }_2)$ is defined, $\mathrm{𝑃𝑙𝑎𝑦𝑒𝑟}i$ takes action $a_i^j={\sigma }_i({\pi }^{\le m}\cdot q_j)$, for $i\in \{1,2\}$, then the next state is $q_{j+1}=\delta (q_j,a_1^j,a_2^j)$. We say that a play $\pi$ is consistent with ${\sigma }_1$ from $q_0$ if there is ${\sigma }_2$ such that $\pi =\text{play}(q_0,{\sigma }_1,{\sigma }_2)$, and similarly for ${\sigma }_2$.

For $i\in \{1,2\}$, we say $\mathrm{𝑃𝑙𝑎𝑦𝑒𝑟}i$ controls a state $q\in Q$, if intuitively, the next state is determined solely based on their choice of action. Formally, $\mathrm{𝑃𝑙𝑎𝑦𝑒𝑟}\mathit{1}$ controls state $q$ if for any $a_1\in \lambda (q,1)$ and $a_2,a_2^{\prime }\in \lambda (q,2)$, we have $\lambda (q,a_1,a_2)=\lambda (q,a_1,a_2^{\prime })$. The definition is dual for $\mathrm{𝑃𝑙𝑎𝑦𝑒𝑟}\mathit{2}$. Turn-based games are a special case of concurrent games, where each state $q$ is controlled by one of the players. Note that a concurrent game which is not turn-based may still have some states which are controlled by one of the players.

A discrete bidding game is played on an arena $⟨V,E,k⟩$, where $V$ is the set of vertices, $E$ is the set of edges, and $k\in \mathbb{N}$ is the total budget in the game. The neighbors of a vertex $v$, denoted $N(v)$, are $N(v)=\{u:(v,u)\in E\}$.

We introduce notation to formalize the tie-breaking mechanism, called advantage-based tie-breaking [20]. We denote the advantage with $\ast$. Thus, when a player’s budget is $B^{\ast }$, this means that the player has a budget of $B\in \mathbb{N}$ and holds the advantage. Similarly, when we say that a player bids $b^{\ast }$, we mean that they bid $b\in \mathbb{N}$, and in case a tie occurs, they will use the advantage. Denote ${\mathbb{N}}^{\ast }=\{0,0^{\ast },1,1^{\ast },\mathrm{\dots }\}$ and $[k]=\{0,0^{\ast },1,1^{\ast },\mathrm{\dots }k,k^{\ast }\}$. The integral part of $B\in {\mathbb{N}}^{\ast }$ is denoted $|B|$. We define two operators $\oplus$ and $\ominus$ over ${\mathbb{N}}^{\ast }$. We describe how the operators are used. Suppose that $\mathrm{𝑃𝑙𝑎𝑦𝑒𝑟}\mathit{1}$’s budget is $m^{\ast }$ and the players bid $b_1$ and $b_2$, respectively. Recall that the higher bidder pays the lower bidder. Thus, when $b_1>b_2$, $\mathrm{𝑃𝑙𝑎𝑦𝑒𝑟}\mathit{1}$’s budget is updated to $m^{\ast }\ominus b_1$, and when $b_2>b_1$, $\mathrm{𝑃𝑙𝑎𝑦𝑒𝑟}\mathit{1}$’s budget is updated to $m^{\ast }\oplus b_2$. Note that $x^{\ast }\oplus y^{\ast }$ and $x\ominus y^{\ast }$, for $x,y\in \mathbb{N}$, will not occur in the setting above, still it is useful to define both for convenience and completion. Formally,

Consider the natural order $\prec$ over ${\mathbb{N}}^{\ast }$ as $0\prec 0^{\ast }\prec 1\prec 1^{\ast }\prec \mathrm{\dots }$. We will frequently use the successor and predecessor according to this order: for $B\in {\mathbb{N}}^{\ast }$, the successor of $B$ is $B\oplus 0^{\ast }$ and its predecessor is $B\ominus 0^{\ast }$.

Consider an arena $𝒜=⟨V,E,k⟩$ of a bidding game. The configurations of $𝒜$ are $𝒞=\{⟨v,B⟩:v\in V,B\in [k]\cup \{k+1\}\}$, where $⟨v,B⟩\in 𝒞$ means that the token is placed at vertex $v$ and $\mathrm{𝑃𝑙𝑎𝑦𝑒𝑟}\mathit{1}$’s current budget is $B$. Implicitly, $\mathrm{𝑃𝑙𝑎𝑦𝑒𝑟}\mathit{2}$’s budget is $k^{\ast }\ominus B$. The arena of the corresponding concurrent game is $⟨[k]\times V,𝒞,\lambda ,\delta ⟩$, where we define the allowed actions $\lambda$ and transitions $\delta$ next. Choosing an action $⟨b,v⟩\in [k]\times V$ corresponds to bidding $b$ and moving to $v$ upon winning the bidding. Consider a configuration $⟨v,B⟩$. Define $\lambda (⟨v,B⟩,1)=\{0,\mathrm{\dots },B\}\times N(v)$, that is $\mathrm{𝑃𝑙𝑎𝑦𝑒𝑟}\mathit{1}$ must choose a bid within his budget and must move to a neighbor of $v$ upon winning the bidding. Similarly, $\lambda (⟨v,B⟩,2)=\{0,\mathrm{\dots },k^{\ast }\ominus B\}\times N(v)$. We define $\delta$ next. Suppose that the token is placed on $c=⟨v,B⟩$, and $\mathrm{𝑃𝑙𝑎𝑦𝑒𝑟}i$ chooses $⟨b_i,v_i⟩$, for $i=\{1,2\}$. If $b_1>b_2$, then the token moves to $⟨v_1,B\ominus b_1⟩$; that is, $\mathrm{𝑃𝑙𝑎𝑦𝑒𝑟}\mathit{1}$ wins the bidding, pays $\mathrm{𝑃𝑙𝑎𝑦𝑒𝑟}\mathit{2}$, and moves the token. Dually, if $b_2>b_1$, then the token moves to $⟨v_2,B\oplus b_2⟩$. The remaining case is $b_1=b_2$. Note that this occurs only when the player with the advantage does not use it. In this case, the other player wins the bidding, and the token moves as in the above.

As above, two strategies ${\sigma }_1$ and ${\sigma }_2$ and an initial configuration $c_0=⟨v_0,B_0⟩$ give rise to an infinite play $\text{play}(c_0,{\sigma }_1,{\sigma }_2)=c_0,c_1,\mathrm{\dots }\in {𝒞}^{\omega }$. We use $\text{path}(c_0,{\sigma }_1,{\sigma }_2)=v_0,v_1,\mathrm{\dots }$ to refer to the path in $⟨V,E⟩$ that corresponds to the play, assuming $c_j=⟨v_j,B_j⟩$, for $j\ge 0$.

Both mean-payoff and an energy bidding games are played on an arena $⟨V,E,k,𝗐⟩$, where $⟨V,E,k⟩$ is as above, and $𝗐:E\to \{-W,\mathrm{\dots },W\}$ is a function that assigns integer weights to edges, $W$ being the largest absolute weight. Consider an infinite path $\pi =v_0,v_1,\mathrm{\dots }$. We call the sum of weights traversed by the prefix ${\pi }^{\le m}$ as its energy, . We define below which player wins in $\pi$ under the two objectives, and later, in Thm. 15, we will show an equivalence between the two objectives.

We seek succinct winning strategies, which intuitively choose bids ignoring excess budget.

In fact, in Rem. 40, we will show existence of winning positional budget agnostic strategies.

We proceed as follows. A function $T$ that satisfies the average property gives rise to a partial budget-agnostic strategy $f_T$; namely it assigns to each configuration $⟨v,B⟩$ a pair $⟨b,S⟩$, where $b$ is a bid and $S\subseteq V$ is a set of allowed vertices to move to upon winning the bidding. Intuitively, a strategy that agrees with $f_T$ maintains a budget invariant (see Lem. 23 below). In subsequent sections, we will construct winning budget-agnostic strategies ${\sigma }_{\text{agn}}$ and ${\tau }_{\text{agn}}$ for Pres and Cons, respectively, that agree with a partial strategy $f_T$, namely the strategies choose the same bid as $f_T$ and choose one of the allowed vertex, thus they maintain a budget invariant. We define the bids and allowed vertices below.

Intuitively, Pres “attempts” to bid $b^T(v)$ at $⟨v,B⟩$. If $b^T(v)$ requires the advantage and $B$ does not have it, Pres bids $|b^T(v)|+1\in \mathbb{N}$, which does not require the advantage.

Next, we define the allowed vertices as the neighbors of $v$ that minimize $T$.

Consider a configuration $⟨v,B⟩$ with $B\ge T(v)$. The following lemma shows that choosing an action $⟨b,u⟩$ with $b={\text{bid}}^T(v,B)$ and $u\in {\text{A}}^T(v)$, maintains a budget invariant: no matter how the opponent acts, in the next configuration $⟨v^{\prime },B^{\prime }⟩$, we have $B^{\prime }\ge T(v^{\prime })$. In particular, this implies that a ${\text{bid}}^T(v,B)$ is a legal bid, i.e., ${\text{bid}}^T(v,B)\le B$.

Intuitively, our budget-agnostic strategy has two features. First, its bids match the bids derived from ${\mathrm{𝑇ℎ}}^{\prime }$ (Def. 21), thus it maintains a budget invariant as in Lem. 23. Second, its actions follow some winning strategy ${\tau }_{\text{VI},n}$ in a truncated game ${𝒢}_n$. This means that it maintains an energy invariant, which implies energy consumption. In this section, we establish properties of ${\tau }_{\text{VI},n}$ that enable these features.

We denote by ${\text{Energy}}_n^{\prime }$ the energy threshold in ${𝒢}_n$ from Cons perspective, namely from $⟨v,B^{\prime }⟩$, Cons can consume ${\text{Energy}}_n^{\prime }(v,B^{\prime })$ units of energy within $n$ turns, but cannot consume ${\text{Energy}}_n^{\prime }(v,B^{\prime })+1$ units. Formally, ${\text{Energy}}_n^{\prime }(v,B^{\prime })={\text{Energy}}_n(v,B)-1$ where $B=k^{\ast }\ominus B^{\prime }$.

Recall that ${\mathrm{𝑇ℎ}}^{\prime }$ is defined such that ${\text{Energy}}^{\prime }(v,{\mathrm{𝑇ℎ}}^{\prime }(v))=\mathrm{\infty }$ but ${\text{Energy}}_n^{\prime }(v,{\mathrm{𝑇ℎ}}^{\prime }(v))$ is finite, for every $n\in \mathbb{N}$. Intuitively, the following lemma (see the proof in the full version [13]) states that for every energy $e$, there is a truncated game $G_N$ in which Cons $e$-wins from $⟨v,{\mathrm{𝑇ℎ}}^{\prime }(v)⟩$.

Let $n\in \mathbb{N}$. We denote by ${\tau }_{\text{VI},n}$, a Cons strategy that ${\text{Energy}}_n^{\prime }(v,{\mathrm{𝑇ℎ}}^{\prime }(v))$-wins from $⟨v,{\mathrm{𝑇ℎ}}^{\prime }(v)⟩$ in $𝒢$. In Lem. 7, we show that ${\tau }_{\text{VI},n}$ exists, moreover, it operates on an arena in which each vertex is $(v,e,m)$, where $v$ is a vertex, the current energy is $e$, and $m\le n$ is a counter that marks the remaining turns. In the full version [13], we establish the following properties.