This was just bumped to the homepage by Community ♦ because it had only unvoted answers. Since it turns out that these were wrong, here's a new one:
In (b), every strategy below $\$5$ is strictly dominated by $\$5$, since that always wins exactly $\$5$ independent of the other player's strategy.
On the other hand, no strategy above $\$5$ has a best response. If $s_1\gt5$, then if $s_2\ge s_1$, Player $2$ can improve by switching to $s_2=s_1-\epsilon$; whereas if $s_2\lt s_1$, Player $2$ can improve by switching to $\frac{s_1+s_2}2$.
Thus the only pure-strategy Nash equilibrium is $(5,5)$, where deviating in either direction reduces the payoff.
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.
Best Answer
An extreme equilibrium $(x,y)$, where $x$ and $y$ are the mixed strategies of players 1 and 2, is a Nash equilibrium where for both players mixed strategies cannot be described as convex combinations of other mixed strategies that form equilibria.
Fact: There are always finitely many extreme equilibria.**
For a mixed strategy $x$, let the support of $x$ be defined as the set of pure strategies that $x$ uses with positive probability, i.e.,
$$\text{support}(x) := \{ i : x_i > 0 \}.$$
A game is called non-degenerate game if for all mixed strategies $x$, if $|\text{support}(x)| = k$ then the number of best responses against $x$ is at most $k$.
Fact: Every non-degenerate game has only extreme equilibria.
For a simple example of a game with non-extreme equilibria consider a $2\times 2$ game where both players get $0$ for all strategy profiles. In this case, all four pure profiles are extreme equilibria and all strict mixtures are non-extreme Nash equilibria. For a less trivial example, consider any $2 \times 2$ bimatrix game where there is no strict dominance for either player but exactly one of the players has a weakly dominant strategy. Then, the game is degenerate and the game will have infinitely many equilibria. As an example, consider the following game.
$$A = \left( \begin{array}{ccc} 1 & 0 \\ 0 & 1 \\ \end{array} \right) \quad B = \left( \begin{array}{ccc} 1 & 1 \\ 1 & 0 \\ \end{array} \right) $$
The game has exactly two extreme equilibria. Here is the output from the online game solver http://banach.lse.ac.uk, which shows these two extreme equilibria:
2 x 2 Payoff matrix A: 1 0 0 1 2 x 2 Payoff matrix B: 1 1 1 0 EE = Extreme Equilibrium, EP = Expected Payoff Decimal Output EE 1 P1: (1) 1.0 0.0 EP= 1.0 P2: (1) 1.0 0.0 EP= 1.0 EE 2 P1: (1) 1.0 0.0 EP= 0.5 P2: (2) 0.5 0.5 EP= 1.0 Rational Output EE 1 P1: (1) 1 0 EP= 1 P2: (1) 1 0 EP= 1 EE 2 P1: (1) 1 0 EP= 1/2 P2: (2) 1/2 1/2 EP= 1 Connected component 1: {1} x {1, 2}The final line of this output shows that against the unique equilibrium strategy of player 1 (top row), player 2 can play any convex combination of $(1,0)$ and $(1/2,1/2)$.
For a thorough technical exposition, which covers both finding extreme equilibria and then from these all equilibria of bimatrix games, see, e.g.,
David Avis, Gabriel D. Rosenberg, Rahul Savani, and Bernhard von Stengel (2010).
Enumeration of Nash equilibria for two-player games.
Economic Theory, 42:9–37.
On the relationship between correlated equilibria and Nash equilibria:
Fact:: The set of correlated equilibrium distributions of an $n$-player noncooperative game is a convex polytope that includes all the Nash equilibrium distributions. In fact, the Nash equilibria all lie on the boundary of the polytope.
See:
Robert Nau, Sabrina Gomez Canovas, and Pierre Hansen (2004).
On the geometry of Nash equilibria and correlated equilibria.
International Journal of Game Theory 32: 443-453.