cBART - Game theoretic analysis

Balloon	Player x: \(x_{p} = 2\)	Player y: \(y_{p} = 5\)
1	0	5
2	2	0
3	2	0
4	2	5
5	0	5
Total	6	15

Conclusions

When the number of balloons is low (i.e.; $N = 1$), then the best response depends on one’s expectations of their opponent.
- If you believe that your opponent will pump 1 time, you should pump 2 times – if you expect he will pump 2 times you should pump 3 times. This continues until your expect your opponent to pump 5 times or more. In these cases, you should only pump once. This is because when an opponent pumps say 7 times, then it’s better to pump once and hope that his pops.
As the number of balloons increases, then the best response becomes closer to 5, regardless of how much you expect your opponent to pump.
- For example, if you play $N = 100$ balloons, then you should always pump 5 times. The reason for this is that, if one plays infinitely many balloons, then one should simply try to maximize their expected rewards, regardless of the other player’s strategy.
It is (almost) never optimal to pump more than 50% of the time (i.e.; 5 out of 10 is the maximum).
These results suggest that the time horizon (i.e. number of game opportunities) matters when deciding how to adjust your risk in a competitive task. In a game with a very short time horizon (i.e. $N = 1$), then only pumping a few times can be optimal given certain expectations of one’s opponent. However, in games with very long time horizons (i.e., $N = 100$, then it is almost always optimal to use an individual payoff maximization strategy.)

Definitions

Parameter	Definition
$N$	Total number of ballooons
$max$	Maximum number of pumps per balloon
$x_{p}$	Pumps by player x
$y_{p}$	Pumps by player y

Each balloon is equally likely to pop anywhere from 1 to $max$.
If a balloon pops, the player earns no points. If the balloon does not pop, the player earns $p$ points, where $p$ is the number of pumps he made.
Whichever player has the most points after $N$ balloons wins an all-or-nothing bonus. If players tie, one is randomly determined to be the winner.

Formulas

A player’s earnings on each balloon is $x_{p}$ with probability $1 - \frac{x_{p}}{max}$, or $0$ with probability $\frac{x_{p}}{max}$
- For example, given a balloon with a maximum of 10 pumps, a player who pumps 5 times will earn 5 with probability $1 - 5/10 = .5$, and 0 with probability $5/10$
A player’s distribution of earnings across $N$ balloons is given by a binomial distribution with $p = 1 - \frac{x_{p}}{max}$, and $N = N$, where each success has a value of $x_{p}$}

Ex: N = 1, max = 10, x.p = 5

For example, consider a game with $N = 1$, $max = 10$, $x_{p} = 5$. Here, the player always pumps 5 times (the optimal). There are only two possible outcomes: a 50% chance of the balloon popping (for a reward of 0), and a 50% chance of saving the balloon (for a reward of 5)

The distribution of reward outcomes when N = 1, max = 10, x.p = 50

Outcome distribution for N = 1, max = 10, x.p = 5
points	prob
0	0.5
5	0.5

Ex: N = 10, max = 10, x.p = 5

Now, let’s increase the number of games to $N = 10$. Now there is a wider distribution of outcomes because more games are played.

Outcome distribution for N = 10, max = 10, x.p = 5
points	prob
0	0.001
5	0.010
10	0.044
15	0.117
20	0.205
25	0.246
30	0.205
35	0.117
40	0.044
45	0.010
50	0.001

Ex: N = 10, max = 10, x.p = {1, 2, 3, 4, 5, 6, 7, 8, 9}

We can also perform similar calculations when a player does not have a constant pumping rate, but rather a stochastic one. Here, we use simulations instead of an arithmetic solution.

Here are the distributions of outcomes from a player who is equally likely to pump anywhere from 1 to 9 times. As we will see, this player has an expected earnings of 18.29, which is less than a player who always pumps 5 times and had an expected earning of 25.

Competition

Now, we calculate the probability of winning a game given two players $x$ and $y$. At the start of the game, players x and y decide on their pumping values $x_{p}$, $y_{p}$. They then play $N$ balloons. Players are not told how many points the other player earns over the course of the game (e.g.; as sequential balloons are played). When the game is finished, and all $N$ balloons are completed, the player with the most points across all balloons wins an all-or-nothing bonus while the other player earns nothing.

We can calculate the probability that a player wins after $N$ balloons by comparing each player’s earning distributions after $N$ balloons. For example, consider a player x who pumps 5 times ($x_{p} = 5$) and a player y who pumps 8 times ($y_{p} = 8) playing $N = 10$ balloons. Here are their expected earnings:

We can calculate the probability that x wins by comparing the two distributions directly (ie.; what is the summed probability of all outcomes where x wins?). Here, the probability that player x wins is 76%, and the probability that y wins is 24%.

Now, we calculate the probabiliy that x wins given all combinations of $x_{p}$ and $y_{p}$ for different numbers of balloons $N$.

Ex: N = 1, max = 10

We’ll start with a game with one balloon. That is, a one-shot game. Here, we see that a player’s best response depends very much on his expectation of the other player. For example, if player y will pump just once, then player x should pump 2 times for a probability of winning of 80%. In contrast, if player y pumps 9 times, then player x should only pump 1 time for an 81% probability of winning. Finally, if player y pumps 5 times, then player y should pump just 1 time again.
There is no Nash equilibrium in this short-horizon game as players should always adjust their strategy for every behavior of their opponent.

Probability of player x winning a game with N = 1 balloon given each combination of x.p and y.p

If your opponent is equally likely to pump anywhere from 1 to 9 times, then you should pump 2, 3 or 4 times

Ex: N = 2, max = 10

When the number of balloons increases to 2, then the best response to a competitor with moderately high pumping values increases from 1. The biggest jump is when y.p = 5. Here, the best response is now x.p = 6.
There is still no Nash equilibrium. Players should cycle between 4, 5 and 6 pumps.
If your opponent is equally likely to pump anywhere from 1 to 9 times, then you should pump 3 or 4 times

Probability of player x winning a game with N = 2 balloons given each combination of x.p and y.p

If your opponent is equally likely to pump anywhere from 1 to 9 times, then you should pump 4 times

Ex: N = 5, max = 10

When the number of balloons increases to 5, the best response for all y.p values greater than 2 is now either 5 or 6.
Still no equilibrium
If your opponent is equally likely to pump anywhere from 1 to 9 times, then you should pump 5 times.

Probability of player x winning a game with N = 5 balloons given each combination of x.p and y.p

If your opponent is equally likely to pump anywhere from 1 to 9 times, then you should pump 4 or 5 times

Ex: N = 100, max = 10

Finally, when the number of balloons increases to 100, the best response is always 5.
In a long-horizon game, the Nash equilibrum is the individual maxization strategy.
If your opponent is equally likely to pump anywhere from 1 to 9 times, then you should pump 5 times.

Probability of player x winning a game with N = 100 balloons given each combination of x.p and y.p

If your opponent is equally likely to pump anywhere from 1 to 9 times, then you should pump 4 or 5 times