Bidding combinatorial games

Normal play combinatorial games are sequential games, usually played under the alternating move convention, and where “the player who moves last wins” [1, 2, 7]. Or wait, should we rather say, “a player who cannot move loses”? Of course, in alternating play, these statements are equivalent playing from a non-terminal position. The former is more intuitive from a recreational play perspective, but the latter is the correct one, from a recursive point of view; the neutral element, the 0-game, has no move options for either player and so the current player loses. Moreover, if $0$ is the starting position, there is no “last player”. The recursive point of view is fundamental to the theory, in computing perfect play outcomes via backward induction.

We generalize alternating play Combinatorial Game Theory (CGT) into an infinite class of game families under the normal play convention, by combining the standard game forms with a certain bidding convention, the so-called Richman auction [6]. As usual, the players are called Left (female) and Right (male). If a game $G$ is played by the discrete bidding convention [3, 5], then there is a total budget $\mathrm{TB}\in\mathbb{N}_{0}=\{0,1,\ldots\}$ partitioned between the players as $(p,q)$, with $p+q=\mathrm{TB}$, and where Left’s part of the budget is $p$. The player who bids more moves next, and if bids are equal then a tiebreaker determines the current player (as in standard CGT we identify ‘next’ with ‘current’).

At each stage of play, exactly one of the players holds a tiebreaker, a tiebreaking marker, and this is denoted by $(G,\widehat{p})$ (Left holds the marker in the game $G$) or $(G,p)$ (if Right holds the marker). If a player wins a bid strictly, then this player hands over the bidding amount to the other player and plays their move. If bids are equal then the player with the marker wins the bid, they play their move, and the marker together with the bid shifts over to the other player.

The marker holder can also choose to explicitly announce the marker with the bid. In this case, if the marker holder wins the bid, they play their move, and the marker together with the bid shifts to their opponent. This additional rule will be important in restoring some familiar normal play properties. To illustrate this, consider the game $*=\left\{0\!\mid\!0\right\}$. In this game both Left and Right have only one option, which is to end the game.¹¹1In this paper we use some of the well known symbols from alternating normal play, such as $*,\uparrow$ and so on. Here they refer to literal form games and never ‘game values’. This game should be favourable to the currently ‘stronger’ player (first player in alternating play). Without this rule, since no player wants the tiebreaker if they have no move, the marker holder would benefit from a tie, and the other player would benefit from a strict win or loss of the bid. This situation is a normal form (matrix) game with no pure equilibrium. Thus we cannot use any familiar tool from normal play theory. We will also see that this additional rule establishes that “last move wins” is the same as saying “cannot move loses”. Examples 2 and 3 in Section 3 elaborate on this theme.

The main results of this paper state that, given any total budget, a perfect play outcome must satisfy a defined feasibility (Section 6). And each feasible outcome class appears as the outcome of a bidding game (Section 7).

Given a total budget $\mathrm{TB}$, let us define $\mathcal{B}=\{0,\ldots,\mathrm{TB},\widehat{0},\ldots,\widehat{}\mathrm{TB}\}$, the set of all feasible player budgets. Here the word “budget” includes the information of the marker holder. A game is a triple $(\mathrm{TB},G,\widetilde{p})$, where we take a note of Left’s part of the budget, $\widetilde{p}\in\mathcal{B}$. If $\mathrm{TB}$ is understood, we write $(G,\widetilde{p})$. If we do not wish to specify $\widetilde{p}$, we may write $(\mathrm{TB},G)$ or just $G$. Game forms are recursively defined, with $G=\left\{G^{\mathcal{L}}\!\mid\!G^{\mathcal{R}}\right\}$, where $G^{\mathcal{L}}$ is the set of all Left options and $G^{\mathcal{R}}$ is the set of all Right options. If $G^{\mathcal{L}}=\varnothing$ or $G^{\mathcal{R}}=\varnothing$ then $G$ is Left terminal or Right terminal respectively, i.e., the current player, Left or Right, cannot move. In the case when $G^{\mathcal{L}}=G^{\mathcal{R}}=\varnothing$, then $G=0$ is terminal irrespective of move order. A typical Left (Right) option of a game form $G$ is written $G^{L}$ ($G^{R}$). In a play situation, we include Left’s part of the budget in the notion of an option. Games are finite and contain no cycles. That is, each game has finitely many options, and the birthday (rank of game tree) is finite, implying that each play sequence is finite; this is also known as ‘short games’ [7]. The game $H$ is a subgame/follower of a game $G$ if there exists a path of moves, perhaps empty, (in any order of play) from $G$ to $H$.

A player obviously does not want to win a bid if they cannot move. And if they do not hold the marker they must pass in any such situation, that is, they must bid zero.

Consider a non-terminal position $(G,\widehat{p})$ (Left holds the marker). There are four cases to establish the next position:

• •

  $(G,\widehat{p})\rightarrow(G^{L},\savestack{\tmpbox}{\stretchto{\scaleto{\scalerel*[width("p-\ell")]{\kern-0.7pt\bigwedge\kern-0.7pt}{\rule[-505.89pt]{4.30554pt}{505.89pt}}}{}}{0.5ex}}\stackon[1pt]{p-\ell}{\tmpbox})$; a Left move after bidding more, i.e. $\ell>r$.

• •

  $(G,\widehat{p})\rightarrow(G^{L},p-\ell)$; a Left move after bidding more, i.e. $\ell>r$, and including the marker.

• •

  $(G,\widehat{p})\rightarrow(G^{L},p-\ell)$; a Left move after winning a tie, i.e. $\ell=r$.

• •

  $(G,\widehat{p})\rightarrow(G^{R},\savestack{\tmpbox}{\stretchto{\scaleto{\scalerel*[width("p+r")]{\kern-0.7pt\bigwedge\kern-0.7pt}{\rule[-505.89pt]{4.30554pt}{505.89pt}}}{}}{0.5ex}}\stackon[1pt]{p+r}{\tmpbox})$; a Right move after bidding more, i.e. $\ell<r$.

Observe that in case of a tie, the marker is transferred. This automatic rule is at the core of our generalization of alternating play. Namely $\mathrm{TB}=0$ corresponds to alternating normal play rules.

In the classical continuous Richman auctions [6], the tiebreaker has infinitesimal value with respect to any bid, and so the theory is not sensitive to variations on tiebreaker transfer. We adopt a discrete bidding convention, which is more natural from a recreational play point of view, but where the analysis of the tiebreaker becomes non-trivial. In fact, the normal play winning implication in the first paragraph of this paper does not a priori hold, and moreover ambiguity on a winning strategy may appear, so traditional requirements for combinatorial games such as pure strategy subgame perfect equilibria may break. With some care of picking a sound tiebreaking convention this issue will be remedied, so that standard backward induction techniques (Section 4) will produce optimal outcomes that generalize normal play outcomes with new lattice structures (Section 8).

Let us review why the tiebreaking rule used in [5] would require mixed strategies in equilibrium in this study. A basic observation is that, independently of specifics of rule, the $0$-game is losing for the player who holds the tiebreaking marker. Namely, the player without the marker will bid 0, in a successful attempt to lose that bid. And indeed, this resembles alternating normal play, where the set of 0-games is the unique equivalence class of zugzwang positions, where no player has incentive to move.

Let us dwell a bit more on the choice of tiebreaker. Two motivating examples will guide us further up the road.

Moreover, this bidding rule gives too much emphasis on the marker; both players’ goal of the game would be to not hold the marker when the game ends, rather than focusing on “who moves last”. But the marker was introduced merely as a device to resolve ties. Hence, in this paper we will adapt the bidding convention in Example 3, where Left can assure a win of the game $*$ by going all in at the second last bid; the last move wins.

Let us mention a couple of possibilities for discrete bidding and its tie-breaking marker.

1. (a)

   a player who wins the bid decides who is the current player;

2. (b)

   a player who wins the bid is the current player;

3. (i)

   the marker alternates between the players;

4. (ii)

   the marker holder may include it in the bid;

5. (iii)

   the marker stays with one of the players;

6. (iv)

   the marker holder shifts if and only if it has been used to resolve a tie.

7. (v)

   if the marker holder wins the bid, the marker gets transferred.

In [3], they study the variation (a), and in [5], (b) is combined with (iv).

Let us begin by proving that, for every game $G$, our variation (b) together with (ii) has pure strategy subgame perfect bidding equilibria.

From now on, we will study the variation (b) together with (ii).

By this result, henceforth we will refer to perfect play with the meaning perfect pure bids and a perfect move by the player who wins the bid.

Bids are typically simultaneous, but in view of perfect play and Theorem 4, the order of bidding is irrelevant.

Consider a given stage of play. A player who has the larger part of the budget, or half the budget together with the marker, is called the (currently) dominating player. A player is strictly dominating if they have a strictly larger budget than their opponent.

Now we establish that “last move wins” is the same as “cannot move loses”.

By this lemma, we may use the term last move wins with the same meaning as in alternating normal play. Henceforth, we adapt the following wording convention: alternating play means the classical normal play games [1], and bidding play is our generalization of those games. All our games will be normal play; we vary the move order convention, but not the winning condition.

Standard outcome classes in alternating combinatorial game theory are

Left wins, the Next player wins, the Previous player wins, and Right wins, respectively [7].

Let $G$ be an impartial game. That is, for all followers $H$ of $G$, $H^{\mathcal{L}}=H^{\mathcal{R}}$. For impartial games, in alternating play, only the outcomes $\mathscr{N}$ and $\mathscr{P}$ apply. The following result about impartial bidding games encouraged us to take a closer look at the full class of partizan bidding games. We will prove a more general result in Theorem 8.

Consider the following generalization of impartial games, to symmetric ending games. If one of the players has a terminal move, then so has the other player. And if one of the players cannot move then neither can the other player. That is, $G$ is a symmetric ending game if for all followers $H$, $0\in H^{\mathcal{L}}$ if and only if $0\in H^{\mathcal{R}}$, and $H^{\mathcal{L}}=\varnothing$ if and only if $H^{\mathcal{R}}=\varnothing$.

The family of symmetric ending games is larger than the impartial games in that it admits the alternating play outcomes $\mathscr{L}$ and $\mathscr{R}$. For example, the literal form $\uparrow_{\mathrm{sym}}=\left\{\left\{*\!\mid\!*\right\}\!\mid\!*\right\}$ has outcome $\mathscr{L}$. Note that the alternating play equivalent form $\left\{0\!\mid\!*\right\}=\;\uparrow$ does not have a symmetric ending.

Recall that the dicot game forms are defined recursively by: if one of the players has a move, then so does the other, and each option is a dicot. The family of dicots contributes a major step from impartial games towards the full family of partizan games. In alternating play, the symmetric ending games are equivalent to the dicots. To see this, note that each Left move to $0$, where Right does not have a move to $0$ (and vice versa) may be replaced with a move to the game $\{*|*\}$ (this does not hold any longer in generic bidding play). We have the following inclusion diagram:

impartial $\subset$ symmetric ending $\subset$ dicot $\subset$ partizan.

The point here is that the symmetric ending condition permits a similar induction proof as that for impartial bidding games (Theorem 6).

The alternating play outcomes generalize in a word notation, where $\mathscr{L}=\mathrm{L}\mathrm{L},\mathscr{N}=\mathrm{L}\mathrm{R},\mathscr{P}=\mathrm{R}\mathrm{L},\mathscr{R}=\mathrm{R}\mathrm{R}$. For example “$\mathrm{L}\mathrm{R}$” means that Left wins when Left starts and Right wins when Right starts. This can also be visualized as an outcome (as defined below) for bidding play when $\mathrm{TB}=0$, as discussed in Theorem 1. In general, given a game $(\mathrm{TB},G,\widetilde{p})$, the winner is either L (Left) or R (Right), with the usual total order $\mathrm{L}>\mathrm{R}$. This induces a partial order of outcomes that generalizes alternating play; see Definition 10.

For example, with $\mathrm{TB}=1$, one might envision 16 partially ordered candidate outcome classes, in word notation, with the largest (smallest) outcome LLLL (RRRR), and so on. Here the leftmost letter symbolizes the outcome in perfect play when Left has budget 1 and the marker; the second letter corresponds to the result in perfect play when Left has the marker but no budget, and symmetrically for the last two letters. An example of an incomparable pair of outcomes would be LRLR and RLRL.

Our notion of outcome is a $2(\mathrm{TB}+1)$ tuple of pure subgame perfect equilibria, representing, given any budget partition, who is the winner in perfect play. The pure subgame perfect equilibrium of a game $(\mathrm{TB},G,\widetilde{p})$ is denoted by $o(G,\widetilde{p})=o_{\mathrm{TB}}(G,\widetilde{p})$. Sometimes we refer to this as a ‘partial outcome’.

Since this notation can be quite lengthy, we instead adopt word notation. For example, instead of $(\mathrm{R},\mathrm{R},\mathrm{L},\mathrm{L})$ we simply write RRLL.

In alternating play, each zugzwang (a game where no player has an incentive to move) belongs to the outcome class $\mathscr{P}$. Here, we define a zugzwang as: no player wants to win the bid. Therefore, it is not the monetary strength, but the marker ownership, that defines the zugzwang concept; obviously both players will bid $0$, whenever they do not want to move, and the marker will decide who is the current player (i.e. in perfect play, the losing player). Therefore, with $\mathrm{TB}=1$, the only zugzwang is the outcome RRLL, because this corresponds to “Right wins when Left has the marker” and “Left wins when Right has the marker”. An outcome such as RLRL would be rare, if it appears at all, since Right wins without either money or marker, but loses if he is given a dollar. Next, we prove that such outcomes are impossible; outcomes are monotone.

If these monotone properties hold, the outcome is monotone.

Observe that in our bidding convention, a player is never forced to become the current player via monetary advantage, since the 0-bid is always available. However, if a player with a nonzero budget is not allowed to bid $0$, then monotonicity may break. To see this consider the total budget $\mathrm{TB}=1$, and Right cannot bid $0$, unless his budget is $0$. Then we will have $o(0,\widehat{0})=\mathrm{L}$, but $o(0,\widehat{1})=\mathrm{R}$. Thus, here we study games where if Left’s budget is $p$ then all bids $0,\ldots,p$ are available to her, and analogously for Right.

Next, to find the number of monotone outcomes, fix a $\mathrm{TB}\in\mathbb{N}_{0}$. Consider the case when Left holds the marker. The only possible monotone sequences of $\mathrm{TB}+1$ partial outcomes are $\mathrm{L}\mathrm{L}\!\cdots\!\mathrm{L}$, $\mathrm{L}\mathrm{L}\!\cdots\!\mathrm{L}\mathrm{R}$, $\ldots$, $\mathrm{R}\mathrm{R}\!\cdots\!\mathrm{R}$. The number of such monotone sequences of partial outcomes is $\mathrm{TB}+2$.

Similarly, when Right holds the marker, we will have $\mathrm{TB}+2$ possible monotone sequences of $\mathrm{TB}+1$ partial outcomes. Thus, from the definition of an outcome, by the independency of such half outcomes there are $(\mathrm{TB}+2)^{2}$ possible monotone outcomes.

For example, with $\mathrm{TB}=1$, the monotone outcomes are LLLL, LLLR, LLRR, LRLL, LRLR, LRRR, RRLL, RRLR and RRRR.

Now the question is, do all monotone outcomes appear? Can we find a game form for each $\mathrm{TB}$ and each monotone outcome? For $\mathrm{TB}=0$ all outcomes are trivially monotone, and indeed, all appear by day 1, namely $o(0)=\mathscr{P}$, $o(1)=\mathscr{L}$, $o(-1)=\mathscr{R}$ and $o(*)=\mathscr{N}$ (see Table 3). For $\mathrm{TB}=1$ all monotone outcomes, except LLRR, appear for games born by day 2, which can be seen in Table 3 by also using symmetry. Observe that for this outcome, in particular a player loses with a dollar budget, but wins with the marker alone. The immediate question is: Can the marker be worth more than a dollar? The answer is no.

We can view an outcome as a string of $\mathrm{L}^{\prime}s$ and $\mathrm{R}^{\prime}s$. From Outcome Monotonicity and Marker Worth, Theorems 11 and 13, we see that not all such strings can appear as an outcome of a game. Thus, let us define the notion of a feasible outcome.

It can be convenient to think of an outcome, without the mention of an underlying game. Thus, the relevance of the set $\mathcal{O}$.

Let us count the number of feasible outcomes for a given $\mathrm{TB}$. Let $a$ be the lowest Left budget for which $o(G,\widehat{a})=\mathrm{L}$ and $a=\mathrm{TB}+1$ if no such $a\in\{0,\ldots,\mathrm{TB}\}$ exists. When Left holds the marker, by Outcome Monotonicity, corresponding to each $a$ there is only one half-outcome. Next, when Right holds the marker, by Marker Worth, for any $a$, $\max(\mathrm{TB}-a,0)$ number of half-outcomes are not possible. Thus if we denote the triangular numbers by $\Delta(n)=1+\cdots+n$, then for a given total budget $\mathrm{TB}$, there are $(\mathrm{TB}+2)^{2}-\Delta(\mathrm{TB})$ feasible outcomes.

A challenge will be to demonstrate that all feasible outcomes appear for some game form. We resolve this in Theorem 21.

Now we see that, for $\mathrm{TB}=1$, all feasible outcomes appear by day 2, namely take the rows 1, 2, 3, 4 and 6 in Table 3 and include the conjugates³³3An outcome-conjugate is obtained when the Ls and Rs are reversed and swapped symmetrically. of rows 3, 4 and 6. What about the outcomes for $\mathrm{TB}=2$? There are 13 feasible outcome classes. But, will games born by day 2 suffice? For example, what about the feasible outcome LLRLLL? The ‘nearest’ in Table 3 is $o_{2}(\left\{*\!\mid\!\varnothing\right\})=$ LRRLLL. It turns out that a solution is a game of day 3; namely $\left\{\uparrow\;\!\mid\!\varnothing\right\}$ has the desired outcome $o_{2}(\left\{\uparrow\;\!\mid\!\varnothing\right\})=\mathrm{L}\mathrm{L}\mathrm{R}\mathrm{L}\mathrm{L}\mathrm{L}$. Here Right wins if and only if he has budget $\$2$ and no marker. Clearly, if Right has the marker he loses. If he does not have the marker, he will pass, and so Left will play to $\uparrow\;=\left\{0\!\mid\!*\right\}$ and hand over the marker. Now, he wins if and only if he wins two consecutive bids, which is possible if and only if he has budget $\widehat{2}$.

Another feasible outcome that does not appear in Table 3 is LRRLRR. Again, a game of day 3 has this outcome, namely $o_{2}(\left\{*\!\mid\!\;\downarrow\right\})=\mathrm{L}\mathrm{R}\mathrm{R}\mathrm{L}\mathrm{R}\mathrm{R}$. That is, Left wins if and only if she has budget $p=2$, with or without the marker. With budget $2$, she starts by bidding $0$, and wins the marker. Right has to move to down. Now Left has $\widehat{2}$, and wins the next two bids to win the game. If Left starts with budget $\widehat{2}$, then she wins two bids, moving to $*$ and then $0$. Right wins any other game. When Right has budget $1$, he begins by bidding 0  and gets either the marker or another dollar. Thus he wins after Left’s move to $*$. If he starts with $\widehat{1}$, then he begins by bidding 0. If Left bids 0, he plays to $(\downarrow\,,\widehat{1}\,)$. Now Right will again bid 0 and take the game to either $(*,1)$ or $(*,0)$ or $(*,\widehat{0})$, where he is the dominating player and wins using Theorem 8. Thus Left cannot afford to lose the first move, and so she bids $1$. Right gets all budget and wins from $(*,0)$. The other cases follow by monotonicity.

Together with the games in Table 3 and conjugate forms, we have now found games for all outcomes with $\mathrm{TB}=2$. Below, in Table 4, we will find game forms for all budget partitions with $\mathrm{TB}=3$. Greater total budgets offer more challenges; however, in Theorem 21 we will provide a general construction. But before that we will define two key tools of our game construction: short form feasible outcome (Definition 16) and terminating Left budget pair (Definition 19).

Consider a short form $(a,b)\in\mathcal{O}$. Then, by Theorem 13,

Recall, an outcome-conjugate is obtained when the Ls and Rs are reversed and swapped symmetrically. Hence, a conjugate short form of $(a,b)$ is $(\mathrm{TB}+1-b,\mathrm{TB}+1-a)$. Note that outcome-conjugation preserves feasibility.

We support the next definition with an example.

For any given $\mathrm{TB}$ and any feasible outcome, using the process in this example, we will construct a game form with this outcome.

In Lemma 20, we prove that $\tau$ is finite for any given total budget. Additionally, we show that, at termination, Left becomes the dominating player in the base sequence that started with her larger budget.

From the proof of Lemma 20 it is clear that, given $\mathrm{TB}$, $\tau$ is uniquely defined by the pair $(p_{0},p_{0}^{\prime})$, and it is independent of the given game form.

Every game has a feasible outcome, i.e. it satisfies Outcome Monotonicity and Marker Worth. Let us now prove the other direction.