Strategy maximizing expected winnings for a simple probabilistic game

expected valuegame theoryprobability

I'm looking for an optimal strategy as well as the derivation of this strategy for a simple game.

The game

  1. Let there be $N$ white balls and one black ball in a pouch.
  2. Upon entering the game, the player pays an entry fee $c_e$.
  3. The player makes a decision:
    • end the game $\rightarrow$ the player collects all the gained rewards and the game ends. Therefore, the player has won the sum of these rewards minus $c_e$ (which she paid before the game started).
    • continue
  4. The player draws one ball from the pouch, randomly.
    • If the ball is white, she gains a reward $c_i$ where $i$ is the number of the round. Repeat from step 3.
    • If the ball is black, the player loses all the gained reward and the game ends. Therefore, the player has won nothing and lost the entry fee $c_e$ (which she paid before the game started).

All parameters – $N$, $c_e$, $c_i$ for each $i$ – are known to the player.

The strategy (i.e. the merit of this question)

I would like to construct a strategy (i.e. a mapping from the game state to the decision whether continue/end) which maximizes the expected total winnings from the game. What is such strategy and how to derive it? Possible de-generalization is that all $c_i$ are equal.

Note: it's not a homework question, I actually want to conduct this game and would like to know some properties of it but I'm not very good at probability and statistics.

Best Answer

This is more of a discussion point than an answer. Let us assume $c_e < \sum_{i=1}^Nc_i$, otherwise this is a game nobody would play. It would also be illogical to terminate before the player has made the money $c_e$ back during the game (otherwise the player would just not play). Let $R_j=\sum_{i=1}^jc_i$, and let $1 \leq r \leq N$ be the minimum value for which $R_r=\sum_{i=1}^qc_i > c_e$. Let us consider what happens for the strategy "terminate after $k\geq r$ wins".

Notice that for this strategy there are only two outcomes, either the player wins $R_k-c_e$ with probability $p_k=\frac{N}{N+1}\times \cdots \frac{N-k+1}{N-k}=\frac{N-k+1}{N+1}$, or 'wins' $-c_e$ with probability $q_k=1-p_k=\frac{k}{N+1}$. So for each $k$ considered, we find ourselves a bernoulli distribution (on $\{C_k-c_e, -c_e\}$) with probability of success $p_k=\frac{N-k+1}{N+1}$.

At this point, we can look at the expected value $W_k$ for each of these strategies to get $$W_k = R_k\frac{N-k+1}{N+1} - c_e$$

if for any $k \geq r$ we get $W_k>0$, then our strategy is to find the largest $W_k$ and then terminate at $k$ and repeat. That is, if the player is allowed to play this game infinitely many times, then this would be a profitable strategy. This is kind of like playing the lottery, suppose the lottery gave a positive expected return (which it doesn't in reality), then playing the lottery infinitely often should result in a net profit over time, though playing it once is highly likely to result in a net loss.

So now suppose the player is only allowed to play the game once, then now it's a matter of a single bernoulli trial. Notice that for our strategy to terminate at $k$, $p_k$ is monotone decreasing in $k$, so we want to use the smallest posible value $k$. However, we also do not want to make any losses, so the smallest possible value of $k$ for which we still can make a profit is $r$, i.e we should terminate as soon as we win more money than we paid to play the game. Having said this, if $p_r$ is quite small (say $10\%$) then we win with only $10\%$ chance and it may not be worthwile for the player to play the game in the first place. One could argue that a large $R_r$ might make the game worthwile, but now this is a matter of personal opinion. Would you like to bet $£100$ say to win $£1001$ with $10\%$ chance? How about to win $£10001$ with $1\%$ chance?. Of course if we can play the game infinitely often, then these numbers are worthwile, but if we can only play once, most people would not play.

If say we are a casino trying to implement this game, we should ensure

  1. $W_k$ is never positive for any $k\geq r$
  2. $r$ is fairly large. i.e for anyone using the strategy to terminate after $r$ wins, the probability of them making money is $p_r=\frac{N-r+1}{N+1}$, where if $r$ is large then $p_r$ is small
Related Question