Solutions for Chapter 2 of "A course in game theory" (Osborne and Rubinstein)

Solution Set 11 - Introduction to Game Theory

1. (First price auction)

The set of actions of each player i is [0, ¥) (the set of possible bids) and the payoff of player i is v_i- b_i if his bid b_i is equal to the highest bid and no player with a lower index submits this bid, and 0 otherwise.

The set of Nash equilibria is the set of profiles b of bids with b₁ Î [v₂, v₁], b_j £b₁ for all j ¹ 1, and b_j = b₁ for some j ¹ 1.

It is easy to verify that all these profiles are Nash equilibria. To see that there are no other equilibria, first we argue that there is no equilibrium in which player 1 does not obtain the object. Suppose that player i ¹ 1 submits the highest bid b_i and b₁ < b_i. If b_i > v₂ then player i's payoff is negative, so that he can increase his payoff by bidding 0. If b_i£ v₂ then player 1 can deviate to the bid b_i and win, increasing his payoff.

Now let the winning bid be b*. We have b* ³v₂, otherwise player 2 can change his bid to some value in (v₂,b*) and increase his payoff. Also b* £v₁, otherwise player 1 can reduce her bid and increase her payoff. Finally, b_j = b* for some j ¹ 1 otherwise player 1 can increase her payoff by decreasing her bid.

Comment An assumption in the exercise is that in the event of a tie for the highest bid the winner is the player with the lowest index. If in this event the object is instead allocated to each of the highest bidders with equal probability then the game has no Nash equilibrium.

If ties are broken randomly in this fashion and, in addition, we deviate from the assumptions of the exercise by assuming that there is a finite number of possible bids then if the possible bids are close enough together there is a Nash equilibrium in which player 1's bid is b₁Î [v₂, v₁] and one of the other players' bids is the largest possible bid that is less than b₁.

Note also that, in contrast to the situation in the next exercise, no player has a dominant action in the game here.

2. (Second price auction)

The set of actions of each player i is [0, ¥) (the set of possible bids) and the payoff of player i is v_i- b_j if his bid b_i is equal to the highest bid and b_j is the highest of the other players' bids (possibly equal to b_i) and no player with a lower index submits this bid, and 0 otherwise.

For any player i the bid b_i = v_i is a dominant action. To see this, let x_i be another action of player i. If max_j¹ib_j ³v_i then by bidding x_i player i either does not obtain the object or receives a nonpositive payoff, while by bidding b_i he guarantees himself a payoff of 0. If max_j¹ib_j < v_i then by bidding v_i player i obtains the good at the price max_j¹ib_j, while by bidding x_i either he wins and pays the same price or loses.

An equilibrium in which player j obtains the good is that in which b₁ < v_j, b_j > v₁, and b_i = 0 for all players iÏ {1,j}.

3. (War of attrition)

The set of actions of each player i is A_i = [0,¥) and his payoff function is

u_i(t₁,t₂) =

-t_i if t_i < t_j

v_i/2 -t_i if t_i = t_j

v_i -t_j if t_i > t_j

where j Î {1,2}\{i}. Let (t₁, t₂) be a pair of actions. If t₁ = t₂ then by conceding slightly later than t₁ player 1 can obtain the object in its entirety instead of getting just half of it, so this is not an equilibrium. If 0 < t₁<t₂ then player 1 can increase her payoff to zero by deviating to t₁ = 0. Finally, if 0 = t₁ < t₂ then player 1 can increase her payoff by deviating to a time slightly after t₂ unless v₁- t₂£ 0. Similarly for 0 = t₂ < t₁ to constitute an equilibrium we need v₂ -t₁ £ 0. Hence (t₁, t₂) is a Nash equilibrium if and only if either 0 = t₁ < t₂ and t₂³ v₁ or 0 = t₂ < t₁ and t₁ ³v₂.

Comment An interesting feature of this result is that the equilibrium outcome is independent of the players' valuations of the object.

4. (Location game)

[Correction to first printing of book: The first sentence on page 19 of the book should be amended to read "There is a continuum of citizens, each of whom has a favorite position; the distribution of favorite positions is given by a density function f on [0,1] with f (x) > 0 for all x Î [0,1]."]

There are n players, each of whose set of actions is OutÈ [0,1]. (Note that the model differs from Hotelling's in that players choose whether or not to become candidates.) Each player prefers an action profile in which he obtains more votes than any other player to one in which he ties for the largest number of votes; he prefers an outcome in which he ties for first place (regardless of the number of candidates with whom he ties) to one in which he stays out of the competition; and he prefers to stay out than to enter and lose.

Let F be the distribution function of the citizens' favorite positions and let m = F ^-1(1/2) be its median (which is unique, since the density f is everywhere positive).

It is easy to check that for n = 2 the game has a unique Nash equilibrium, in which both players choose m.

The argument that for n = 3 the game has no Nash equilibrium is as follows.

There is no equilibrium in which some player becomes a candidate and loses, since that player could instead stay out of the competition. Thus in any equilibrium all candidates must tie for first place.
There is no equilibrium in which a single player becomes a candidate, since by choosing the same position any of the remaining players ties for first place.
There is no equilibrium in which two players become candidates, since by the argument for n = 2 in any such equilibrium they must both choose the median position m, in which case the third player can enter close to that position and win outright.
There is no equilibrium in which all three players become candidates:

if all three choose the same position then any one of them can choose a position slightly different and win outright rather than tying for first place;
if two choose the same position while the other chooses a different position then the lone candidate can move closer to the other two and win outright.
if all three choose different positions then (given that they tie for first place) either of the extreme candidates can move closer to his neighbor and win outright.

Comment If the density f is not everywhere positive then the set of medians may be an interval, say [m*, m**]. In this case the game has Nash equilibria when n = 3; in all equilibria exactly two players become candidates, one choosing m* and the other choosing m**.

5. (Symmetric games)

Define the function F : A₁® A₁ by F (a₁) = B₂(a₁) (the best response of player 2 to a₁). The function F satisfies the conditions of Lemma 20.1, and hence has a fixed point, say a₁*. The pair of actions (a₁*, a₁*) is a Nash equilibrium of the game since, given the symmetry, if a₁* is a best response of player 2 to a₁* then it is also a best response of player 1 to a₁*.

A symmetric finite game that has no symmetric equilibrium is Hawk--Dove (Figure 17.2).

Comment In the next chapter of the book we introduce the notion of a mixed strategy. From the first part of the exercise it follows that a finite symmetric game has a symmetric mixed strategy equilibrium.