1
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ "You win bids that are draws" suggests a situation with more constraints than you have described. Why shouldn't your opponent negate your apparent advantage simply by adding a random positive infinitesimal amount to their optimal bid in this game? That would make a draw almost surely not happen. Is there some restriction on the values that can be bid? $\endgroup$
    – whuber
    Aug 19, 2021 at 16:14
  • 1
    $\begingroup$ @whuber - some of the wording suggests that bids are restricted to integers $\endgroup$
    – Henry
    Aug 20, 2021 at 6:15
  • $\begingroup$ @Henry Thank you for pointing that out. I was responding to the statement of the problem in the first paragraph. I wonder whether that should be the question we need to answer or whether we should answer it according to the implied interpretation in the "thoughts." $\endgroup$
    – whuber
    Aug 20, 2021 at 11:04
  • 1
    $\begingroup$ @whuber I've added that the bids are indeed restricted to integers $\endgroup$
    – John
    Aug 20, 2021 at 17:10
  • 2
    $\begingroup$ Thank you. Why, though, do you suppose the coin has different chances $p_i$ of heads on each flip? That possibility would make this situation much more difficult to analyze, because of how little information it reveals about the last 180 flips. The question, as stated, suggests assuming all the $p_i$ are equal -- and perhaps it is intended to apply only to a fair coin where this common value is known to be $1/2.$ Which interpretation do you want us to address? $\endgroup$
    – whuber
    Aug 20, 2021 at 17:14

1 Answer 1

2
$\begingroup$

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.

$\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.