1
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • $\begingroup$ What if after the move of player N there are 0<x<M chips left in the pot? Do they start another round from player 1? $\endgroup$
    – Pietro Majer
    Commented Jul 21, 2021 at 15:26
  • $\begingroup$ @PietroMajer Yes, they do. $\endgroup$
    – Eric
    Commented Jul 21, 2021 at 15:27
  • 1
    $\begingroup$ The obvious play is to bet all but one of the chips if there's more than one. You can't lose immediately, and if you throw tails you have 50% odds that the player after you loses. If everyone does this (and by symmetry the best strategy is the same for everyone) then with large $N$ it's increasingly likely that someone will lose before it comes back to you. $\endgroup$
    – Peter Taylor
    Commented Jul 21, 2021 at 15:38
  • $\begingroup$ @PeterTaylor That sounds reasonable. But if $M\gg N$, will it be better to bet $M-K$ chips if the current number of chips $K$ is very close to $M$? $\endgroup$
    – Eric
    Commented Jul 21, 2021 at 15:57
  • 1
    $\begingroup$ I would like to comment on the part "by symmetry the best strategy is the same for everyone". It is true that this is a symmetric game, hence there is a symmetric equilibrium. But a player's equilibrium strategy depends on the current number of chips in the pot, and it is not clear that for K (where K is the number of chips in the pot) the symmetric equilibrium strategy will dictate the same behavior (same is whatever meaning you would want). $\endgroup$
    – Eilon
    Commented Jul 22, 2021 at 5:29

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ I don't quite follow the 2nd paragraph. Are you defining a player's strategy as a function of the current number of chips in the pot as well as the history of how others have played? $\endgroup$
    – Eric
    Commented Jul 22, 2021 at 5:46
  • $\begingroup$ Eric, in stochastic games, a strategy is a function from finite histories (the sequence of past states and past choices of the players) to lotteries over actions. There was a typo in my original answer: by Thuijsman and Raghavan (1997), the equilibrium strategies of the players are deterministic and depend on the current state as well as on the history of the play. $\endgroup$
    – Eilon
    Commented Jul 23, 2021 at 6:10
  • 1
    $\begingroup$ That's different with what I had in mind though. In my setup of the game players have no memories and their choices of bet depend only on the current number of chips. I've edited the question to give a formal definition of what I mean by a player's strategy. Does the theorems still hold in this case? $\endgroup$
    – Eric
    Commented Jul 23, 2021 at 6:46

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .