Prerequisites: Chapters 1, 2, 3, and the pages on Doctor Location Games and Restaurant Location Games
In real life, where the rules are not always carved in stone, a player in a simultaneous 2-player game may have the possibility of either moving a little earlier than the other, or delaying the move slightly until he or she sees what the other player played. Even if moving earlier is not possible, sometimes it is possible to publicly announce what you will play, to make a (hopefully convincing) commitment. If the other player believes you, it is as if you would have moved first. In any case, the former simultaneous game is transformed into a sequential game.
Obviously there are two roles in the sequentialization of a two-player game, moving first or moving second, and which one is preferred is probably often decided by the temperament of the players. Some like to move first and dictate the action, and others prefer to wait and see what the other has played, leaving the other in the dark about their intentions. But actually this question of whether it is better to move first or last in a sequentialization should not be left to temperament but to an analysis of the game.
In this chapter we discuss the sequential versions of the location games whose simultaneous versions have been discussed here in the doctor location version and here in the restaurant location version.
In the sequential version of the game, Ann chooses a location first, and after that Beth decides where to put her location.
Will the results differ from those in the simultaneous version, and who will gain from having to move sequentially?
Both simultaneous location games are symmetric--- both players have the same options, and the games are fair insofar as if both players switch their options chosen, then the payoffs will also switch. Thus symmetric games are fair, although the pure Nash equilibria do not necessarily have the same payoff for both players. Still, if there is a Nash equilibrium with a payoff of a for Ann and b for Beth, then there is also a Nash equilibrium with reversed payoffs of b for Ann and a for Beth. Because of this fairness feature, whether the sequential version of a symmetric game has a first mover advantage or a second mover advantage is pretty easy to determine---we just compare Ann's and Beth's payoff in the backward induction outcome of the sequential version. If Ann's payoff is higher, we say we have a first mover advantage, if both are equal we call the sequential version of the game fair, and if Beth's payoff is higher we call it a second mover advantage.
Backward analysis of the sequential version carries over to bimatrix notation quite easily: If Ann moves first and Beth second, then Ann determines the row with her move. Each row corresponds to a situation Beth may face, and in each row, Beth obviously would choose the cell maximizing her payoff. This is her best response to Ann's move. We color all these cells. Note that the colored cells include all pure Nash equilibria, since the condition for coloring is just one of two (both moves being best response to the other) required for pure Nash equilibria. Note also that every row contains at least one colored cell. Here we assume that Beth is indifferent to Ann, meaning that if she faces a position---a row---with several outcomes with the same maximum payoff for Beth, she will just select any of these. So in each row, any of the colored cells could occur as outcome. If, on the other hand, Beth would be slightly hostile or slightly friendly to Ann, we would only color the occurring outcomes in each cell.
We finish backward induction as follows: Since Ann knows how Beth would react in each position, Ann will choose the move/row giving her the highest payoff. If every row contains just one colored cell, she would select the row where Ann's payoff in the colored cell is highest. If some cells contain multiple colored cell, Ann would look at the averages of her payoff in the colored cells in each row, and compare these.
| swerve | not | |
| swerve | -1, -1 | -2, 2 |
| not | 2, -2 | -100, -100 |
Why do these two games behave so differently? Both are symmetric games. Both are zero-sum games. In both cases, there is only one best response to any move---in every row, only one cell is colored in the backwards induction analysis. Why does CHICKEN have a first mover advantage and ROCK-SCISSORS-PAPER a second mover advantage?
This game seems to have a second mover advantage. No matter where Ann moves, Beth can always get a payoff of at least 5. Since this is a constant-sum game, Ann will therefore achieve at most 4.
Here is the payoff bimatrix, with Beth's best responses to Ann's moves highlighted.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
| 1 | 4.5, 4.5 | 4.5, 4.5 | 5, 4 | 4.5, 4.5 | 4, 5 | 4.5, 4.5 | 6, 3 | 5.5, 3.5 | 5, 4 |
| 2 | 4.5, 4.5 | 4.5, 4.5 | 4.5, 4.5 | 4, 5 | 4.5, 4.5 | 5, 4 | 6, 3 | 5, 4 | 5.5, 3.5 |
| 3 | 4, 5 | 4.5, 4.5 | 4.5, 4.5 | 4.5, 4.5 | 5, 4 | 4.5, 4.5 | 5, 4 | 6, 3 | 5.5, 3.5 |
| 4 | 4.5, 4.5 | 5, 4 | 4.5, 4.5 | 4.5, 4.5 | 4.5, 4.5 | 4, 5 | 5.5, 3.5 | 6, 3 | 5, 4 |
| 5 | 5, 4 | 4.5, 4.5 | 4, 5 | 4.5, 4.5 | 4.5, 4.5 | 4.5, 4.5 | 5.5, 3.5 | 5, 4 | 6, 3 |
| 6 | 4.5, 4.5 | 4, 5 | 4.5, 4.5 | 5, 4 | 4.5, 4.5 | 4.5, 4.5 | 5, 4 | 5.5, 3.5 | 6, 3 |
| 7 | 3, 6 | 3, 6 | 4, 5 | 3.5, 5.5 | 3.5, 5.5 | 4, 5 | 4.5, 4.5 | 4.5, 4.5 | 4.5, 4.5 |
| 8 | 3.5, 5.5 | 4, 5 | 3, 6 | 3, 6 | 4, 5 | 3.5, 5.5 | 4.5, 4.5 | 4.5, 4.5 | 4.5, 4.5 |
| 9 | 4, 5 | 3.5, 5.5 | 3.5, 5.5 | 4, 5 | 3, 6 | 3, 6 | 4.5, 4.5 | 4.5, 4.5 | 4.5, 4.5 |
By the remarks above, Ann will choose the row for which her average highlighted payoff is highest. This is equal to 4 in the first six rows, and equal to 3 in the remaining three rows, so she will choose any of the first six rows/moves. Therefore Ann's payoff in the sequential version equals 4 and Beth's payoff 5; there is a second mover advantage in the sequential version for this graph.
Note that the simultaneous version on this graph does not have pure Nash equilibria.
Since producing these payoff bimatrices is tedious, from now on we will use Excel sheet LocationGame.xls for this task. Not only does it produce the payoff bimatrix for the doctor location game and also the restaurant location game belonging to this graph, it also calculates all pure Nash equilibria for both versions and the backward induction solution of the sequential versions of the games.
 |
 |
Why is there never a first mover advantage in such doctor location games? Since they are constant-sum, and Beth can always get half of the possible total payoff by placing her doctor in the same village as Ann. Thus Beth can easily always achieve as much as Ann. Sometimes more.
Can we tell from the structure of the graph which games have are fair and which have a second mover advantage? Is there a feature of the graph which implies fairness or second mover advantage? Maybe, but I am not aware of any such characterization. But if we stop staring on the graph, and instead look at the Nash equilibria, we can answer the questions. Not only for doctor location graphs but for arbitrary constant-sum symmetric simultaneous games.
In sequential versions of constant-sum games, Ann just gets what her security level in the simultaneous version was. Since the colored cells in each row---Beth's, highest payoffs in each row, Beth's best responses---are the moves of minimum payoff for Ann in each row. So the above coloring cells in rows and selecting the row with the best outcome of the colored cell for Ann corresponds exactly the maximin procedure in simultaneous games.
And we have seen in the Chapter on Simultaneous Games that zero-sum games have exactly then a pure Nash equilibrium if the security level equals 0, if the fair payoff of 0 for both can be achieved by Ann's maximin strategy. Similar, constant-sum games with constant sum of c have a Nash equilibrium exactly if Ann's security level reaches c/2. Which means, by the remarks above, that the sequential version of the game is fair.So this is the reason why sequential ROCK-SCISSORS-PAPER has a second mover advantage.
The Excel sheet LocationGame.xls can also be used for restaurant location games.
 |
 |
| Graph 11 | Graph 4 |
Graph 11 has already been analyzed in the Restaurant Location Games page. It has four Nash equilibria: Vertex 1 versus vertex 5, and also vertex 5 versus vertex 6 (and both reversed cases). In the sequential version, Ann will play vertex 5, and Beth will play vertices 1 or 6. This way, Ann gets a payoff of 2.5 and Beth a payoff of 2. There is a first mover advantage.
Graph 4 has six Nash equilibria: Vertex 2 versus vertex 4, vertex 5 versus vertex 8, and vertex 6 versus vertex 9 (and the reverse cases). In the sequential version, Ann plays vertex 2 or 4, and Beth plays vertex 4 or 2, respectively. The game is fair---both get a payoff of 3.
We have seen above that sequential versions of doctor location games have never a first mover advantage. Based on the examples we have, couldn't it be just the opposite for restaurant location games?
We know that all simultaneous restaurant location games have pure Nash equilibria, see here. And we suspect, based on a number of examples, that restaurant location games have never a second mover advantage. Could there be some connection? Remember that we showed above that constant-sum symmetric games with Nash equilibria have no second mover advantage (since they are fair), which fits into the picture so far. So, is it true that symmetric games with pure Nash equilibria have no second mover advantage? If this were true, the conjecture above would follow as a special case. We try the same approach as before, moving to a larger class of games, from restaurant location games to symmetric games with pure Nash equilibria.
It turns out that under one simple additional condition, it is true. We assume that in each row only one cell is colored. We call this property unique response for Beth. Then all pure Nash equilibria are among the colored cells, and Ann can choose any of them by choosing the row move. So assume Ann chooses the Nash equilibrium maximizing her payoff among all Nash equilibria, and this gives a to Ann and b to Beth. Then a is as least as large as b, since there is also a Nash equilibrium giving b to Ann and a to Beth---the one where Ann and Beth exchange moves. If Ann chooses a row with no Nash equilibrium in it, then only since this row promises at least a to Ann as payoff.
Very often the first condition fails. People are often indifferent between options. In particular, for restaurant location games we rarely have this property.
But if we assume that Beth decides in these cases looking at Ann's payoff, as discussed in the previous subsection, this first condition is valid. The second condition is necessary since presently we don't have a solution concept yet if there are no Nash equilibria in pure strategies. Later, when we allow and discuss mixed strategies, we will see whether this condition remains necessary. The third condition makes it possible to compare Ann's and Beth's payoffs.
Look at the following symmetric game, where both player's moves are called "C", "D", and "E". The colored cells are the outcomes with best response for Beth:
| C | D | E | |
| C | 1, 1 | 3, 2 | 3, 1 |
| D | 2, 3 | 6, 6 | 2, 6 |
| E | 1, 3 | 6, 2 | 2, 2 |
What happens in the same game with hostile or friendly Beth? We model these cases by assuming that one percent of Ann's payoff is subtracted (in the hostile version) or added (in the friendly version) to Beth's payoff.
| hostile Beth | friendly Beth | ||||||||||||||||||||||||||||||||
|
|
Analyze the sequential version of restaurant location on Graph 6 shown to the right,
under the assumption that in case of ties, option are chosen with equal probability.