Guess the smallest number

Question

Three people play a game where each of them writes down a positive integer at the same time. The one who writes a unique and smallest number wins one dollar from every other person. This means if two people happen to write down the same number, then the third one gets one dollar from each of them regardless. Now what number would you put if you were to play this game?

Answer 1

Empirically, if two of the three individuals each writes down a positive integer $N_i$ independently with probability $$P(N_i=n)=2^{-n}$$ then whatever the third writes, the expected outcome for each of the three is $0$ and so the third may as well follow this strategy too (in which case there would then be a tie with probability $\frac17$).

It also seems that the first two follow a different iid strategy then the strategy above will produce a positive expected outcome for the third. So it looks like the optimal strategy in the absence of collusion.

The first two can develop a collusive strategy: suppose the first always writes $1$ and the second $2$, with them sharing the winnings after the game. The third player would then always lose.

Answer 2

This is a problem in Game Theory. Clarification: The statement of the problem seems to imply that if all 3 pick the same number then no money changes hands. I will assume that.

Henry has come up with the solution. The following is the justification.

The goal is to maximize the player's expected profit. Each player acts independently of the others. This problem is a special case of one that was solved in 2007-2008. It is called the Least Unique Bid Auction. About 10 years ago a special promotion was used in Europe. They "auctioned" off an item, for example a $\$100$ bill. The special rules: You can make a sealed bid in multiples of a unit (assume a dollar). The winning bidder is the one with the smallest unique bid out of $n$ players. The person with the winning bid must also pay his bid amount. So a winning bid of $\$b$ has a $\$100$-b profit. The problem posed here is much simpler since the profit doesn't depend on the value of my bid (only its relative size compared to other bids.)

There is no pure strategy Nash equilibrium to the posed problem. That means when each player picks a fixed number. If all three pick number 1 for example, any one player would prefer (after the fact) to pick number 2 (with others still picking 1) and would win all the time. This means all 1's is not an equilibrium since not all players are happy with the status quo. So instead we look for a mixed strategy Nash equilibrium (NE). So we want to choose a probability distribution over the choices 1,2,3...

We notice that it doesn't matter what number we choose as long as we win. That is, the winning payoff is a constant $\$2$ rather than $\$100$-b in the general case. Therefore our behavior should be "the same" at each possible number choice since the problem looks the same. (This can be made precise using an absorbing state Markov chain.) This requires a bit of explanation.

Each player specifies his probability distribution. Then a referee (or auctioneer) can use those distributions to generate a "bid". If the distribution is $p_1,p_2,...$ for one of the players then we flip a coin with probability $p_1$ of heads. If it lands heads, we select number 1. But if tails, we do not select 1 and wait for the next round. If the game continues past number 1 (depending on the other choices) we then decide whether to select number 2. $p_2/(1-p_1)$ is the probability of selecting 2 given I did not select 1. From our previous comment, this probability should be the same as $p_1.$ Therefore,

$$ p_1=\frac{p_2}{1-p_1} \text{ or } p_2=p_1(1-p_1)$$

We can continue this logic to conclude the distribution must be geometric. So when looking for a mixed strategy NE we can restrict ourselves to geometric distributions. This is huge simplification. (When solving the general problem in 2007, I did not realize that this special case of the problem allowed one to restrict the search for a NE to geometric distributions. I only realized it today.)

Let the distributions for player A, B and C be denoted: $$ a(1-a)^{k-1}, b(1-b)^{k-1}, c(1-c)^{k-1}. $$

Let’s find the probability that player A wins on games decided with the first bid: $ a(1-b)(1-c)+(1-a)bc. $ The first term is the case when player A makes a choice of 1 and B and C do not while the second term is for the case where he does not choose 1 but both B and C do. In addition, there is a probability $g:=(1-a)(1-b)(1-c)$ that no one chooses 1 and the game continues to round 2. As mentioned previously, the game is identical from that stage forward. Therefore, the probability that player A wins on bid $k$ is: $[a(1-b)(1-c)+(1-a)bc]g^{k-1}.$ Therefore the win probabilities for the whole game are: $$ P(A)=\frac{a(1-b)(1-c)+(1-a)bc}{1-g} $$

$$ P(B)=\frac{(1-a)b(1-c)+a(1-b)c}{1-g} $$

$$ P(C)=\frac{(1-a)(1-b)c+ab(1-c)}{1-g} $$

Assume we are player C. We want to maximize our expected profit. We would like to find a $symmetric$ mixed strategy NE, namely with $a=b=c.$ This is because all players are equivalent and it is hard to justify different actions in equilibrium. We start by assuming our opponents have selected $a=b.$ Then if we choose any value $c$ our expected profit is $ E(C)= 2P(C)-2P(A).$ Then, after some algebra: $$ \frac{\partial E( C )}{\partial c}=\frac {2(1-2a)[1-(1-a)^3]} {[1-(1-a)^2(1-c)]^2} $$

We want that partial to be $0$ so player C would not want to change his current value of $c.$

if $a=0.5$ then every $c$ is a solution. This means $a=b=0.5$ and any $c$ will be an asymmetric NE and they all get expected profit $0$. This a bit surprising, but the symmetric case $a=b=c=0.5$ is of primary interest. So if they all play strategy 0.5, no single player will want to change his strategy since the partial is $0$.

if $a\ne 0.5$ then no value of $c$ is a solution.

In summary, player C (and every player is player C) should choose $c=0.5 .$ If his opponents are smart they will also choose $0.5$ and all players get expected profit $0$. If the opponents are not smart, player C will achieve positive expected payoff. Furthermore, C could adjust his strategy to increase his expected profit by observing (estimating) the opponents’ strategy over repeated play. By using the partial derivative, for example, if the opponents use $a=b=0.4$ or anything less than $0.5$ then C should use $c=1$ which means play bid 1 for certain. And if $a=b=0.6$ or anything greater than $0.5,$ then C should choose $c=0$ which means never make a bid (or make a very large bid.)