The game $G(N,M)$ is played:


$N$ ($N\geq 2$) is the number of players, labeled $1$~$N$. In the beginning they have a pot with some chips in it. Players move alternatively in the order from $1$ to $N$. In their move, a player announces an integer $C$ and toss a fair coin: if head, $C$ more chips are added to the pot; if tail, $C$ chips are removed from the pot, where $1\leq C\leq $ the current number of chips in the pot.


The game ends on two conditions:


1. The pot is empty after a player's move, in which case that player loses the game, and everyone else wins.
2. There're $M$ or more chips in the pot, in which case everyone wins.


Communication is not allowed, and **we assume a player's choice of integer $C$ is a function only of the current number of chips in the pot**. Formally, in game $G(N,M)$ a player's strategy is a function $f: \{1,2,...,M-1\} \longmapsto \{1,2,...,M-1\}$, with the restriction $f(x)\leq x, \forall x$.


**Question:** Is there always an equilibrium for $G(N,M)$? If so, what can we say about the equilibria? Is it feasible to search for an equilibrium of, say $G(3,1000)$?




---


**Edit**: Notice that the strategy of always betting all but one chips can't be an equilibrium for many games. For example in $G(3,5)$, if the other 2 players stick to that strategy and there are 4 chips, you're better off betting 1 rather than 3.



Is there an equilibrium for this non-zero-sum game?
Edited on 24-July-2021 to reflect the requirement that the equilibrium is in pure stationary strategies.


The game you present is a stochastic game: the number of chips in the pot and the identity of the player whose turn it is to move serve as a state variable. Since the number of chips in the pot is bounded (between 0 and M), there are finitely many states and actions to each player. In fact, the game is a stochastic game with perfect information: the players move alternately, so there are no simultaneous moves.


Such games have (a) an equilibrium that do not involve randomization, that is, the choice of the number of chips is deterministic yet it depends on past play, see Thuijsman and Raghavan, Perfect Information Stochastic Games and Related Classes, International Journal of Game Theory, 1997, 26, 403-408.
They also have (b) a symmetric stationary equilibrium that involves randomization, that is, the choice of the number of chips is random and depends only on the current state, see Fink, Equilibrium in a Stochastic
n-Person Game, Journal of Science of the Hiroshima University, Series A (mathematics), 1964, 28(1), 89-93.


You, however, are interested in stationary equilibria that involve no randomization. The theory does not guarantee that such equilibria exist.


