Note: I do not expect a clean closed-form solution to this, and would be very surprised if one existed, but I figured I'd ask to see what ideas other people had.
There is a \$100 bill up for auction. There are $n$ players, each of which is allowed to bet an integer amount between \$0 and \$99, inclusive.
However, this is a very strange auction. The winning bid is the largest number that no one else guessed. If no one guessed a unique number, no one wins the bill.
Under the following assumptions:
- Every player follows the same strategy (which must be true by symmetry)
- The goal of each player is to maximize expected profit. Since this is an auction, if a player doesn't win, they get their bid back with net profit $0$.
- No single player can get higher expected profit by deviating from the strategy.
- If there are multiple such strategies satisfying all the above, players follow the strategy with maximal expectation. If multiple strategies are tied in that too, then players follow the strategy that maximizes the chance of some player winning.
what is the optimal strategy?
My intuition is that this is ridiculously intractable – I only know the solution for $n = 2$. For $n = 3$ I have a strategy if you restrict the bids to $0$ or $99$ (optimal is bidding \$0 $\frac{10}{11}$ of the time). So far, I have no apporaches for the general $n = 3$ game that avoid ridiculous computation.
Best Answer
I think $n=3$ will just involve a lot of equations. Here's my sketch.
It must be that a player gets an equal payoff from all actions specified in their strategy. Note that the lowest bid, 0, wins only if the other two bid the same thing. Let $x=(x_0,x_1,\dots,x_{99})$ be the weight each player places on each action (naturally $x_0$ is the weight on 0, etc). So the expected payoff is
$$100\sum_{i=1}^{99}x_i^2$$
Let's skip the bid of 1 for now.
For the bid 2, a player only wins if the others bid the same thing or below 2.
$$(100-2)( \sum_{i\neq 2}x_i^2 + 2x_0x_1)$$
Now for a general $j$. A player wins if the others bid the same thing or all below $j$.
$$(100-j)[ \sum_{i=j+1}^{99} x_i^2 + (\sum_{i=0}^{j-1} x_i)^2 ]$$
Finally, this vector lives in the simplex. $\sum_{i=0}^{99}x_i=1$.
This gives $100$ equations for $100$ unknowns, so you should be able to solve. Here, the player is indifferent between all strategies, so it must be a best response, and we have an equilibrium.