Expected Value Puzzle – A Thought-Provoking Open-Ended Stat Puzzle

binomial distributionexpected valuegame theoryprobabilitypuzzle

A fair coin is flipped $200$ times and each time it lands on heads, $1$ dollar is added to a pot. After this process is over, an auction is held for the pot. There is exactly one other person at the auction who happen to know the results of the first $20$ coin flips. The only possible compensation you get is that you win bids that are draws. How much should you bet? The bids are restricted to integers.

Thoughts: There are $21$ distinct results that can come from the $20$ coin flips ($0$ heads, $1$ head, $2$ heads, …, $20$ heads). Each of these has a binomial probability associated with it, say $p_i$ is the probability of $i$ heads in the first $20$ flips.

If there are $i$ heads in the first $20$ flips, then the expected value of the pot is $90 + i$ dollars. To make a profit, he would bet $1$ lower than this, so for $i$ heads, he would bet $89 + i$. However, for $i > 10$, this amount would be $\ge 100$. He knows that we will never bid more than $99$ because then we would not be making any profit in the long run. As he loses draws, he would bet exactly $100$ for all $i > 10$.

So then there are $12$ distinct amounts he can bet depending on the flips:
$89 + i$ for $0 \le i \le 10$ and $100$ for $i \ge 10$.

Fix a value $X$, our bidding value. Calculate the expected profit when we bet $X$. We can do this by considering each of the 12 configurations, as well as weighing by the appropriate probabilities. Once this profit is found as a function of $X$, we can just maximize it with calculus.

Is this correct? I'd be curious to actually know what the result is when we vary the number of flips seen by the other person.

Best Answer

I am not sure this is a complete answer, but it may point you in a useful direction. This is not a zero-sum game, so there is an incentive for collusion between the bidders.

If you assume that the two players are not colluding, then presumably the player with partial information will aim to bid $1$ more than the player with less information, unless such a bid would lead to a zero or negative expected gain.

The player with less information would take the other player's strategy into account, and base their bid on this. As far as I can tell, they would bid $96$ and win the auction whenever the partial information shows $7/20$ or fewer heads, and lose the auction when there are $8/20$ or more when the player with partial information bids $97$.

The expected gain for the $96$ bidder with no information is then $$\sum\limits_{n=0}^7 (n+\tfrac{180}2-96){20 \choose n}2^{-20} = 0.0458145141601562$$

while the expected gain for the bidder with partial information is $$\sum\limits_{n=8}^{20} (n+\tfrac{180}2-97){20 \choose n}2^{-20} =3.08577346801757$$

I do not see an easy way of getting to this $96$ figure beyond calculating the expected gain for the no-information bidder for different possible bids, taking into account the partial-information bidder's likely strategy.

Related Question