Lowest unique bid auctions became popular in recent years. In such an auction, a prize of value $M (a car, an elecronic gudget, etc.) is offered for sale. Each participant can purchase any number of natural numbers at the price of $c per natural number. The winner is the participant who purchased the minimal number among all the numbers that were purchased by a single player. He pays his winning bid (that is, the minimal number that was purchased only by him) and gets the object. If no number was purchased by a single player, no-one wins the object. I explained this game in more details in this post.
This game has a symmetric equilibrium. Indeed, in equilibrium no player will purchase more than M/c numbers, and no player will purchase a number higher than M (actually, no player will purchase M as well). Therefore the set of pure strategies that one should consider for an equilibrium is finite (all subsets of the set {1,2,…,M-1} that contains at most M/c numbers), so that by Nash’s theorem the game has an equilibrium in mixed strategies. Since the game is symmetric, there is in fact a symmetric equilibrium in mixed strategies.
Consider the following variation, in which the winner does not pay his winning bid. Now the set of all pure strategies that can be selected in equilibrium is infinite: it consists of all subsets of the set of natural numbers that include at most M/c numbers. Does this game have an equilibrium? A symmetric equilibrium? When there are two participants the answer is positive. What about more than two participants? I have no idea. Anyone can find the answer?
2 comments
May 24, 2012 at 10:53 am
Evan
For any combination of M/c and number of players, choose some number N and restrict my opponents place positive probabilities only on numbers less than (or equal to) N.
As N grows, the probability of winning with a bid of N+1 shrinks to 0 (in the limit).
Therefore, for some (potentially very large) N, it will be an epsilon-best response for me to place positive probabilities only on numbers less than or equal to N. Thus we will shall have the existence of an epsilon-equilibrium to the game, with strategies arbitrarily “close” to a NE.
I have a feeling that we should be able to show that for large enough N, N+1 is never a best response, but can’t see how at the moment.
May 24, 2012 at 12:35 pm
Eilon
This is indeed an epsilon equilibrium, but I am looking for an exact equilibrium. I tried your approach as well, but somehow the equilibrium seems to run away.