I'm trying to understand Exercise 18.2 from Martin J. Osborne and Ariel Rubinstein A Course in Game Theory about finding pure Nash equilibria in a first-price auction.
There are $n$ players, named $\{1,2,\dots,n\}$ participating in a sealed-bid auction. They all simultaneously submit their bids, and the player with the highest bid receives the prize, all other players receive nothing. Player, who receives the prize, pays the bid, other players don't pay anything. If $2$ players submit the same bid, and this bid is the highest, then the prize goes to the player with lower index, e.g. if both player1 and player2 bid the same amount of money, the prize goes to player1. Players value the object differently, playeri valuation is $v_i$, and $v_1> v_2> \dots > v_n$. Find all Nash equilibria.
My reasoning is as follows. There is a finite number of players. Every player has a valuation of an object, and player with lower index values object higher than player with higher index. To be better off, payment for object $<$ valuation. If player pays the same amount of money they value the object, they are indifferent between this amount of money and the object. This means that payoff equals $0$, if the person doesn't receive the prize, or equals $v_i − b_i$, where $b_i$ is the bid of playeri. How to figure out payoffs for every player, given their actions (bids)? Payoff is $v_i − b_i$, if playeri's bid is the highest (all other bids $<$), or if out of all players with equal highest bids, $i$ is the lowest. Otherwise payoff is $0$.
There are infinitely many bids (and therefore actions), and theoretically any player could pay millions for the object. But they would never pay more than their value, because between negative payoff and $0$ they would choose $0$. Playeri pays $b_i\le v _i$. Player1 doesn't want to lose to player2, so $b_1 \ge b_2$. As no player except player2 will pay $v_2$, player1 pays $v_2$ and every other player is forced to lose. The Nash equilibria is when player1 pays $v_2$ (their payoff is $v_1 − v_2$), and every other player pays whatever they want $\le v_2$ (as they are indifferent between bids as long as player1 wins, their payoff is always $0$). There are infinite Nash equilibria, in every of which player1 wins.
However, the solution, published by the authors, claims that Nash equilibrium exists, if $b_1 \in [v_2, v_1], b_j \le b_1$ for all $j \neq 1$, and $b_j = b_1$ for some $j \neq 1$. In other words, the highest bid is not $v_2$, but can be anywhere between $v_2$ and $v_1$.
I don't understand it. By definition, Nash equilibrium is when no player can benefit (increase payoff) by deviating from a strategy. Player $2$ can't improve payoff by paying a little bit more than $v_2$. So how can Nash equilibrium be with $b_1$ being $> v_2$?
Added on 29/05/2017: I was confused. The key condition for the NE is $b_j = b_1$ for some $j \neq 1$. Player1 will pay exactly the same amount of money as some other player, and no more. I thought authors claimed that if player1 pays a little more (but still below valuation), then this is also a NE. This, of course, is not true, $b_1$ has to equal the bid of some other player, but other than that all other players can pay anywhere between 0 and $b_1$, they'll lose anyway. Therefore no player has incentive to deviate.
Best Answer
In a Nash equilibrium, no player has incentive to change their action, holding fixed the actions of the others. Here, actions are bids.
Take the action profile proposed by Osborne and Rubinstein. Does player one have incentive to increase bid? No, he will still win but pay more. Does he have incentive to lower it? No, he will lose the auction, and give up the surplus (at least zero) he is current receiving.
Do other's have incentive to lower their bids? No, they will continue to lose the auction. Do others have incentive to increase their bids? No, either they will continue to lose the auction, or if they raise it enough, they will win, but at a price that is at least as high as their valuation since $b_1 \geq v_2$.
Now, we consider your proposed strategy: player 1 pays $v_2$ and every other players bid whatever they want $b_i ≤ v_2$. This may not be a Nash equilibrium. If other's all bid zero for instance, than player 1 has incentive to lower his bid to zero, he will continue to win and pay nothing! In fact, if the other's leave player 1 and room to lower his bid, he will. That's why, in equilibrium we need someone else to bid what player one bids in equilibrium.
But, why are these the only equilibrium? Well, suppose someone else wins. If it is an equilibrium, they must have bid no more than their valuation. Otherwise, they would be better off losing the auction and so they would have incentive to bid zero. But, if the winning bidder isn't player 1 and is bidding a value no higher than their own valuation, player 1 has incentive to raise his bid to just above the currently winning bid and win the auction at a price that gives him a positive surplus. Thus, in equilibrium, player 1 has to win.