# «Contents. 1 Nash Equilibrium in Extensive Form Games 2 1.1 Selten’s Game......... 1.2 The Little Horsey....... 1.3 Giving Gifts.. ...»

2. If 2 ever bids $3.00 she will win the auction and lose $2.00. If she bids $2.90, then 1 has to bid $3.00 in order to win. If 1’s previous bid was $2.00 or less, then 1 will not outbid 2’s $2.90 because doing so (and winning) means losing $2.00 instead of whatever 1’s last bid is, which is at most that (this is where the assumption comes into action). But the same logic applies for 2’s bid of $2.80 because 1 cannot bid $2.90 and expect to win: in this case 2 will do strictly better by outbidding him with $3.00 and losing only $2.00 instead of $2.80.

Therefore, 1 can only win by bidding $3.00 but this means losing $2.00. Therefore, if 2 bids $2.80, then 1 will pass if his last bid was $2.00 or less. In fact, any bid of $2.10 or more will beat any last bid of $2.00 or less for that very reason. So, whoever bids $2.10 ﬁrst establishes a credible threat to go all the way up to $3.00 in order to win. This player has already lost $2.10, but it is worth spending $.90 in order to win the dollar.

Therefore, a bid of $2.10 is “the same” as a bid of $3.00. This means that in order to beat a $2.00 bid, it is suﬃcient to bid $2.10, nothing more. By a similar logic, $2.00 beats all bids of $1.10 or less. Since beating $2.00 involves bidding $2.10, if the player’s last bid was for $1.10 or less, there is no reason to outbid a $2.00 bid because doing so yields at most a loss of $1.10, which is at most equal to the player’s current bid. In fact, even $1.20 is suﬃcient to beat a bid of $1.10 or less. This is because once someone bids $1.20, it is worthwhile for that player to continue up to $2.10 to guarantee a victory (in which case they will stand to lose $1.10 instead of $1.20).

Therefore, a bid of $1.20 is “the same” as a bid of $2.10, which is “the same” as a bid of $3.00. By this logic, a bid of $1.10 beats bids of 20 cents or less. Because beating $1.10 involves bidding $1.20, if the player’s last bid was for 20 cents or less, there is no reason to win. Only a player who bids 30 cents has a credible threat to go up to $1.20. So, any amount down to 30 cents beats a bid of 20 cents or less. If someone bids 30 cents, no one with a bid of 20 cents or less has an incentive to challenge.

Therefore, the ﬁrst player to bid should bid 30 cents and the auction should end. How does that correspond to our outcome? (Probably not too well.) Let’s look at an extensive-form representation of a simpler variant, where two players have $3.00 each but they can only bid in dollar increments in an auction for $2.00.

$3 Pass −1, 0 0, 0 $1 $2

−1, 0 −1, −2 We begin with the longest terminal history, ($1, $2), and consider 1’s decision there. Since 1 is indiﬀerent between Passing and bidding $3, both are optimal (we do not use the indifference assumption as in the informal example). If he passes, then player 2 is indiﬀerent between passing and bidding $2 at the decision node following history ($1). If, on the other hand player 1 bids $3, then player 2’s best course is to pass. So, the subgame beginning at the information set ($1) has three SPE in pure strategies: (Pass, Pass), ($2, Pass), and (Pass, $3).

At the decision node following history ($2), player 2’s unique optimal action is to pass, and so the subgame perfect equilibrium there is (Pass). Therefore, player 2’s strategy must specify Pass for this decision node in any SPE.

Consider now player 1’s initial decision. If the players’ strategies are such that they play the (Pass, Pass) SPE in the subgame after history ($1), then player 1 does best by bidding $1 at the outset. Therefore, ($1, Pass), (Pass, Pass) is an SPE of the game.

If the strategies specify the SPE ($2, Pass), then player 1’s best actions are to bid $2 or Pass at the initial node. There are two SPE: ($2, Pass), ($2, Pass) and (Pass, Pass), ($2, Pass).

If the strategies specify the SPE (Pass, $3), then player 1’s best action is again to bid $1, and so there is one other SPE: ($1, $3), (Pass, Pass).

The game has four subgame perfect equilibria in pure strategies. It only has three outcomes: (a) player 1 bids $1 and player 2 passes, yielding player 1 a gain of $1 and player 2 a payoﬀ of $0; (b) player 1 passes and both get $0; (c) player 1 bids $2 and player 2 passes, and both get $0.

Now suppose we introduce our assumption, which states that if a player is indiﬀerent between passing now and bidding something that will yield him the same payoﬀ later given the other player’s strategy, then the player passes. This means that in the longest history player 1 will Pass instead of bidding $3, which further implies player 2 will Pass at the preceding node, and so this subgame will have only one SPE: Pass, Pass. But now player 1 has a unique best initial action, which is to bid $1. Therefore, the unique SPE under this assumption is ($1, Pass), (Pass, Pass). The outcome is that player 1 bids $1 and player 2 passes.

This corresponds closely to the outcome in our discussion above.

There is a general formula that you can use to calculate the optimal size of the ﬁrst bid, which depends on the amount of money available to each bidder, the size of the award, and the amount of bid increments. Let the bidding increment be represented by one unit (so the unit in our example is a dime). If each player has b units available for bidding, and the award is v units, the the optimal bid is ((b − 1) mod (v − 1)) + 1. In our example, this translates to (30 − 1) mod (10 − 1) + 1 = 3 units, which equals 30 cents, just as we found.

It is interesting to note that the size of the optimal bid is very sensitive to the amount each player has available for bidding. If each player has $2.80 instead of $3.00, then the optimal bid is (28 − 1) mod (10 − 1) + 1 = 1, or just 10 cents. If, however, each has $2.70, then the optimal bid is (27 − 1) mod (10 − 1) + 1 = 9, or 90 cents.

The Dollar Auction was ﬁrst described by Martin Shubik who reported regular gains from playing the game in large undergraduate classes. The game is a very useful thought experiment about escalation. At the outset, both players are trying to win the prize by costly escalation, but at some point the escalation acquires momentum of its own and players continue paying costs to avoid paying the larger costs of capitulating. The requirement that both highest bidders pay the cost captures the idea of escalation. The general solution (the formula for the size of the optimal bids) was published by Barry O’Neill.

** **

4.3 Multi-Stage Games with Observed Actions

There is a very special but useful class of extensive form games, which have “stages” such that (a) in each stage every player knows all the actions taken by any player at any previous stage, and (b) players move simultaneously within each stage. So, “multi-stage games with observed actions” is just a fancy name for the class of extensive form games, where the players move simultaneously within each stage and know the actions that were chosen in all past stages. Most, but not all, of the games we have seen so far fall into this category.

4.3.1 Sophisticated Voting and Agenda Control Suppose there are three players, I = {1, 2, 3}, who must choose one from three alternatives

**X = {x, y, z}. Their preferences are as follows:**

They must make their choice through majority rule voting in a two-stage process. They ﬁrst vote on two of the alternatives and the winner is then pitted against the remaining alternative in the second round. Players cast their votes simultaneously in each of the two rounds. Suppose player 2 controls the agenda—that is, she can decide which two alternatives are to be voted on in the ﬁrst round. What is her choice?

We need to ﬁnd the SPE. Clearly, player 2 will set an agenda that ensures that y is the winner if that’s possible. We have to consider the three possible situations, depending on which two alternatives are selected in the ﬁrst round. To ﬁnd the subgame-perfect equilibrium, we have to ensure that the strategies are optimal in all subgames. There are three generic subgames that begin with the second round: depending on the winning alternative in the ﬁrst round, the second round can involve a vote on (x, y), or (x, z), or (y, z). So let’s analyze each of these subgames.

Note ﬁrst that because there are only two alternatives and three players, it follows that in any PSNE, at least two players must vote for the same alternative. Observe now that casting a sincere vote—that is, voting for the preferred alternative—is weakly dominant for each player. If the other two players vote for diﬀerent alternatives, then the third player’s vote is decisive, and it is strictly better to cast it sincerely. If, on the other hand, the two other players vote for the same alternative, then the third player’s vote cannot change the outcome.

Therefore, there are two possible PSNE in these subgames: either all players vote sincerely or they all vote for the same alternative. Technically, this means that when x is pitted against y, it is possible to get y to win: the strategy proﬁle in which all players vote for y is a Nash equilibrium. However, this PSNE requires two of the players to vote against their preferred alternative and expect that they do so, which seems highly implausible. In this instance, I would rule out the PSNE involving weakly dominated strategies. Using only weakly dominant

**strategies then yields a unique PSNE with sincere voting for each of the subgames, as follows:**

In other words, we know that in SPE the second round will involve sincere voting and produce a winner accordingly.

Going back to our original question, how is player 2 to set the agenda? Clearly, if y is ever to emerge as the winner given that the 2nd round will involve sincere voting, it will have to be pitted there against z because against x it will lose. Since z defeats x in sincere voting, then perhaps choosing (x, z) as the ﬁrst round agenda would work?

The answer is that it will not. Suppose player 2 set the agenda with (x, z) in the ﬁrst round and everyone voted sincerely. Then the winner would be z, and in the second round the winner would be y. But players can anticipate this outcome. In particular, player 3 knows that the winner of the ﬁrst comparison would go on to compete with y and if y prevails in the 2nd round, he will get his worst possible alternative. Since y will beat z with sincere voting, this means that he really does not want z to win in the ﬁrst round. Of votes are cast sincerely in the ﬁrst round, then player 1 is voting for x while players 2 and 3 are voting for z. However, if player 3 deviated and cast a sophisticated vote for x instead, then x will win the ﬁrst round, and in the second round the sincere vote on (x, y) would leave x as the winner. Although the sophisticated vote does not enable player 3 to get his most preferred alternative, it does enable him to avoid the worst possible one.10 This now means that whatever player 2 chooses, her agenda has to be invulnerable to sophisticated voting. Well, as they say, if you can’t beat them, join them: player 2 will exploit the sophistication of the players by setting the agenda for the ﬁrst round to (x, y). Observe that with sincere voting, x would defeat y. However, this would pit x against z in the 2nd round, in which case z will prevail. Player 1 can foresee this and since z is his worst possible alternative, he will cast a sophisticated vote for y against her preference for x over y. Doing so would ensure that y will go on to the 2nd round and defeat z, which gives him the secondbest outcome. Of course, our devious player 2 can now enjoy her most preferred alternative.

Therefore, the proﬁle (y, xy), (y, z, y), (x, zz) is a subgame-perfect equilibrium when (x, y) is the pair in the ﬁrst round. The strategies are speciﬁed as a triple over the (x, y) choice in the ﬁrst round, and then the (x, z) and (y, z) possible subgames in the second round. In this SPE player 1 is casting a sophisticated vote (note that player 2’s manipulation pays oﬀ even though she votes sincerely). Alternative y defeats x, and then goes on to defeat z in a sincere vote in the 2nd round. Since this SPE yields player 2 her most preferred alternative, the overall SPE of the game involves her setting the agenda such that (x, y) are the two competing alternatives in the ﬁrst round.

We know from McKelvey’s Chaos Theorem that if players vote sincerely using majority rule to select winners in pairwise comparisons, then any outcome is possible provided no equilibrium position exists. (That is, for any two alternatives, one can always ﬁnd an agenda that guarantees that one beats the other.) With sophisticated voting, this chaos is a bit reduced: for any two alternatives, there will be an agenda that guarantees that one defeats Of course, there are also the PSNE in which two players vote sincerely and the third, whose vote is irrelevant, also votes for the same alternative. For instance, in (x, y), there is PSNE in which all players vote for x. Since player 3’s choice cannot aﬀect the outcome, he might as well vote insincerely.

Here, as before, there are equilibria in which all three players vote for the same alternative and two of them vote against their preferences. For instance, in (x, z) this would require them all to vote for x. Coupling this with any PSNE in the 2nd round will yield an SPE, but the solution is implausible for the same reasons we discussed already.