6
$\begingroup$

This is a simple 2 player game on which each player has an individual "pool" of finite money or points, and every round they must decide how many points they want to risk for a chance to get a directly proportional reward. I've been trying to solve this problem for a while, but I still know very little about game theory and I can't seem to even find the proper place to start. I'd be thankful if anyone could help me.

The Game:

Two players, A and B, start the game with \$500 each.

In every round, a single, 6 faced die is tossed. Both players have to gamble an integer value from \$1 to \$99 (inclusive). If the die shows the number one, both players get their respective bets back and earn 5x the amount they gambled. All earnings are added to the amount available for gambling.

If the die rolls any other number, both players lose the amount they gambled.

The amount of money remaining for each player is revealed to their opponent at the end of every round.

The game ends when one of the players has no money left, or after 1000 rounds. The winner is the player with the most money.

Example:

  1. Round 1 begins
  2. Player A bets \$1, Player B bets \$2
  3. Die rolls a 5
  4. Player A now has \$499, Player B now has \$498
  5. Round 1 ends
  6. Round 2 begins
  7. Player A bets \$1, Player B bets \$2
  8. Die rolls a 1
  9. Player A gets his \$1 back, plus another \$5. He now has \$504. Player B gets her \$2 back, plus another \$10. She now has \$508.
  10. Round 2 ends

What is the best strategy the players can play to win the game?

Any help is appreciated.

$\endgroup$
  • 1
    $\begingroup$ An accurate question must involve statistics, which I'm not good at. So I just tell you what I think intuitively. Assume the dice is perfect, it means after 6 times you bet the same money, you get nothing. So I think you should bet 500/6 in 6 times, If you win one in 5 first rounds, you should stop doing that, it'll give you advantage. The worst case is when you win in the six round, you won't lose a single dime. And continue this strategy. Of course, just to remind you, it only works if we admit the dice is perfect. The worst of the worst case is you lose all your money after 6 rounds :v. $\endgroup$ – chí trung châu Dec 23 '16 at 12:18
  • 1
    $\begingroup$ Bets must be integer numbers, I presume That is, if you are on your last \$1, must you bet it? You may not bet $0.5? $\endgroup$ – Rolazaro Azeveires Dec 23 '16 at 22:29
  • $\begingroup$ That is correct, I will add that to the problem description, thank you. $\endgroup$ – Paco.628 Dec 23 '16 at 23:10
  • 1
    $\begingroup$ Also want to thank you, chí trung châu. Sorry I didn't have time to write a proper reply earlier. When I first encountered the problem, I thought the safest way to play would be to work out the longest possible sequence of bets for which winning at any point in the sequence would produce a return equivalent to your total loss. You would start by betting the first amount, and move one step for every consecutive loss. Every win you would return to step one. However, given the objective and limited number of rounds, a player playing more aggressively might have an advantage. I truly don't know. $\endgroup$ – Paco.628 Dec 24 '16 at 2:49
  • 2
    $\begingroup$ They know how much money each other had available at the end of the previous round, but have no information on their opponent’s bet on the current round. Thanks for asking, I’ll update the original post. $\endgroup$ – Paco.628 Jun 6 '18 at 1:28
1
$\begingroup$

This game is a two-player symmetric (almost) zero-sum finite-horizon simultaneous game with perfect-information. The set of subgame-perfect equilibria (SGE) can be derived via backward induction. Solving this particular game will take quite a bit of computation.


Setting up the game: It is useful to describe your game in slightly greater generality, to see how it can be solved in general, from an arbitrary point. Since the game is symmetric we can consider it from the perspective of a single “acting” player in an arbitrary game state, which can be described by the following variables:

$$\begin{matrix}{} \text{Remaining rounds} \quad \quad & & & k \in \mathbb{N}, \\ \text{Wealth of acting player} & & & a \in \mathbb{N}, \\ \text{Wealth of opponent} \quad \text{ } \text{ } & & & b \in \mathbb{N}. \end{matrix}$$

In each round, each player simultaneously chooses an action $\mathbf{p}_{k,a,b}$, which is a probability-vector over the allowable bets $\{ 1, 2, ..., w \}$. The chosen action will depend on the number of remaining rounds and the present wealth for the acting player and his opponent.$^\dagger$

A strategy for the game is a set of probability vectors for all possible values of these arguments:

$$\mathscr{S} = \{ \mathbf{p}_{k,a,b} \in \Delta_{a,w} | k \in \mathbb{N}, a \in \mathbb{N}, b \in \mathbb{N} \},$$

where $\Delta_{a,w} \equiv \{ (p_1, \cdots, p_w) | \sum p_i = 1, (\forall i): p_i \geqslant 0, (\forall i > a): p_i = 0 \}$ is the simplex of all probability-mass functions on the allowable bets. (This is always taken to be a vector with length $w$, but the player is not able to bet more than his current wealth, so any values over this amount must have zero probability.)

You have not specified what happens in the event of a draw (i.e., both players have the same wealth once $k=0$), so I will assume that this constitutes a loss for both players (i.e., they both get nothing). This means that each player will choose a strategy to maximise the probability of winning the game. (It is not quite a zero-sum game because of the way I am treating a draw.) Since the game is symmetric with respect to the two-players, there will be a set of optimal strategies (subgame-perfect equilibria), which are optimal reactions to all other optimal strategies. These will be optimal in the sense that they maximise the probability of winning the game, under the assumption that the other player also plays optimally.


Solving the game: Solving the game requires us to calculate the “value function” for any game-state $(k,a,b)$ (up to some specified maximum values for a particular implementation of the game). The value is for the acting player, so it is the probability that the acting player wins, under optimal play (by both players) from a particular game-state:

$$\upsilon (k,a,b) \equiv \mathbb{P}( \text{Acting player wins} | k,a,b).$$

To solve the game using backward induction we start at the termination points of the game, which occur when $k=0$ or $a=0$ or $b=0$. At any of these points the value for the game is:

$$\begin{array} \upsilon \upsilon (0,a,b) = \mathbb{I}(a>b), \\[6pt] \upsilon (k,0,b) = 1, \\[6pt] \upsilon (k,a,0) = 0, \\[6pt] \end{array}$$

To find the remaining outcomes of the value function we proceed recursively, by moving away from these “edges”. To do this, let $\mathbf{p} \in \Delta_{a,w}$ be the action chosen by the acting player, and assume that the opponent takes the optimal action from his perspective, which is $\hat{\mathbf{p}}(k,b,a)$. This gives us recursive equations for the optimal action:

$$\upsilon (k,a,b) = \max_{\mathbf{p} \in \Delta_{a,w}} \upsilon_\mathbf{p} (k,a,b),$$

where:

$$\begin{equation} \begin{aligned} \upsilon_\mathbf{p} (k,a,b) &\equiv \mathbb{P}(\text{Acting player wins} | \mathbf{p}, k,a,b) \\[6pt] &= \sum_{x = 1}^{\min(a,w)} \sum_{y=1}^{\min(b,w)} p_{k,a,b}(x) \hat{p}_{k,b,a}(y) [ \tfrac{1}{6} \upsilon (k,a+5x,b+5y) + \tfrac{5}{6} \upsilon (k,a-x,b-y) ]. \end{aligned} \end{equation}$$

These recursive equations can be combined with the base cases to obtain the value function for each game-state $(k,a,b)$. This is a complicated non-linear programming problem, so it will require some finesse. I will leave it to you to look at how to program this optimisation problem, but in any case, once you have the value function at each game-state of interest, you will easily be able to obtain the optimal strategy, and the probability that each player wins (or the probability of a draw) when both players play optimally.


$^\dagger$ Technically the game-state and actions may also depend on the actual round number (not just the number of remaining rounds) and the wealth levels of the players in past rounds, but there is no reason to take this into account, since the optimal strategy will be "memory-less" in this game. Hence, we restrict attention to the class of actions that ignore this irrelevant information.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.