Chapter 2:
Simultaneous Games

The writer Ephraim Kishon describes in his story "Jewish Poker" how a man called Ervinke convinces the narrator to play a game called "Jewish Poker" with him. "You think of a number, I also think of a number" Ervinke explains. "Whoever thinks of a higher number wins. This sounds easy, but it has a hundred pitfalls." Then they play. It takes the narrator some time until he realizes that it is better to let Ervinke tell his number first. [Kishon 1961] Obviously this is a game that doesn't seem very fair unless both move simultaneously.

In this chapter we will start our journey through Game Theory by considering the maybe simplest type of games, games where each player moves only once, and all these moves are done simultaneously. We will see that these games can be described nicely in a table (called Normal Form below). Then we discuss different approaches that allow the player to decide which move they will choose, culminating in the famous "Nash equilibrium" concept. Although many simple games already fall into this category, the chapter is also important for other games, as we will see later that every finite game can be formulated as an equivalent simultaneous game.

• 1. Normal Form---Bimatrix Description
  • 1.1 Two Players
  • 1.2 Two Players, Zero-sum
  • 1.3 Three or more Players
  • 1.4 Symmetric Games
• 2. Which Option to Choose
  • 2.1 Maximin and Security Level
  • 2.2 Dominated Moves
  • 2.3 Best Response
    • 2.3.1 Condensed Best Response Digraphs for Symmetric Games
    • 2.3.2 Best Response for Three Players
  • 2.4 Equilibria
    • 2.4.1 Dominant Move Equilibrium
    • 2.4.2 IEWD and IESD Equilibria
    • Modeling Note 2: Additivity of utilities from different features
    • 2.4.3 Nash Equilibria
    • Historical Remark: John Forbes Nash
  • 2.5 2-Player Zero-sum Symmetric Games
• References
• Exercises and Projects

Imagine you want to describe a simultaneous game to somebody. By definition we already know that each player has only one move, and that all these moves are performed simultaneously. What else is necessary to tell? First of all, of course, the number of players. Secondly, for each player the possible moves have to be listed. Note that different players may have different roles and as such may have different options for moves. We assume here that each player has only finitely many options. If each player selects a certain move, this determines a certain outcome of the game. Finally, the payoffs have to be described for each player for each possible outcome.

How many outcomes are possible? Each combination of moves of the players generates a different outcome. Note that when moves X and Y are chosen by players A and B we get different outcomes depending on whether player A chooses move X or move Y. Therefore, if there are n players, and player 1 has k₁ possible moves, player 2 has k₂ possible moves, and so on, then there are k₁·k₂· ... ·k_n possible outcomes. For each of these outcomes, n numbers would describe the payoffs for player 1, player 2, and so on.

If each player has infinitely many options, methods of Calculus of functions with two variables may be applied, as discussed on a later page. Also, simultaneous games with randomness involved are described later.

Let me give an example of a simultaneous 2-players game:

Whenever we have two players in this text, we very often name them Ann and Beth. Assume Ann has k₁ options and Beth has k₂ options. We want to display the different payoffs for Ann and Beth, depending on the different choices they have. Obviously there are k₁·k₂ different outcomes, every combination of an option for Ann and an option for Beth produces one. Each of these outcomes has payoffs for Ann and Beth attached. Usually this is visualized in a table with n rows, corresponding to Ann's options, and m columns, corresponding to Beth's options. Such a table is called a n × m bimatrix. The entries in the cells are payoffs for Ann and Beth provided the corresponding options are chosen, both numbers separated by a comma.

Recall from the introduction that a game is called zero-sum if the sum of all payoffs of all players equals zero for any outcome. That means that the win of the winning players is totally paid by the loss of the losing players. Casino and parlor games are very often zero-sum. Real-world games are almost never zero-sum---it is possible that the society as a whole wins or loses.

For zero-sum two-player games, the bimatrix representation of the game can be simplified: The payoff of the second player doesn't have to be displayed, since it is just the opposite of the payoff of the first player.

We will later see that zero-sum two-player games are one of the types of games that can be "solved" mathematically completely and satisfactory.

If we have more than two players, we need another systematic way to generate the needed k₁·k₂· ... ·k_n cells corresponding to the different outcomes, into which we write the n payoffs for the n players. Let me give an example:

All examples so far are symmetric: All players have the same options, and if the two players interchange their moves, the payoffs are also interchanged. More formally, for a 2-player game, let m₁, m₂ be moves and let a(m₁, m₂) and b(m₁, m₂) be Ann's and Beth's payoffs if Ann plays m₁ and Beth plays m₂. Then a(m₁,m₂)=b(m₂,m₁) and b(m₁, m₂)=a(m₂, m₁) for symmetric games. That means that the entries in the j's row and the i's column is obtained from the entries in the i's row and j's column by interchanging both payoffs. For symmetric 3-player games, a(m₁,m₂,m₃)=b(m₂,m₁,m₃)= b(m₃,m₁,m₂) = c(m₂,m₃,m₁) =c(m₃,m₂,m₁), and so on, with corresponding notation. Symmetric games are popular since they are fair by design, giving the same chances to every player.

Nobody would deny the usefulness of having a way to describe simultaneous games by a bimatrix, but what players of such a game really expect of game theory is to give them advice of how to play. Ideally game theory should (and will in some cases) provide players with a mechanism---a rather mechanical procedure---to find this advice of which move is "best" on their own, given the description of the game in normal form.

Note that, as always with mathematical models, these mechanisms would refer to the bimatrix only, without reasoning with the specific circumstances of the actual situations. In other words, the "solution" such a mechanism gives would be the same no matter whether we face a specific casino game or a cold or hot war scenario, provided the corresponding matrices are the same. Naturally that would imply the "essence" of the game sitting just in this numbers in the bimatrix.

Such mechanisms are the content of Section 2 of this chapter. Actually we will not only give one, but rather three or four of them. Like advice from different well-meaning uncles, these mechanisms have all a good and convincing point, but since they concentrate on different features of the game, they don't always lead to the same conclusion. We will discuss them first separately before investigating the relation between these concepts.

Some people always expect the worst. No matter what she plays, a player, let's call her Ann again, may assume that the other players will always respond with moves that minimize Ann's payoff. This pessimistic belief may be justified in case of a two-players zero-sum game if Ann is so predictable that the other player always anticipate her move, in other cases the belief borders the paranoid, since the other players will not be interested in harming Ann but will instead rather concentrate on their own payoffs when acting rationally. Still, our pessimistic Ann will evaluate her own strategies in light of this worst expected case. She would concentrate, for any of her options, on the smallest possible payoff for her. And if she believes that this is what she would get in each case, then Ann would choose the option with highest such value. This value is called the maximin value or security level. Ann's corresponing option she will play is called a maximin move (strategy), since it maximizes the minimum possible payoff. Playing the maximin move, the player can guarantee a payoff of at least the maximin value, no matter how the others are playing. Note that for choosing the maximin move, the player doesn't even have to know the payoffs of the other players.

Obviously in a two-player game the first player, Ann, would look at the different rows of the bimatrix and in each row highlight the cell with lowest payoff for Ann. Then she would select the row with the highest number highlighted. In the same way, the second player, Beth, when playing the maximin strategy would in each column mark the cell with lowest payoff for Beth, and then select the column with the highest number marked.

How do we treat ties, if two or more rows have the same minimum payoff for Ann? Ann could choose just one of these moves, or alternate randomly between such moves. The latter leads to the concept of "mixed strategies" that is covered in a later chapter.

There are a number of mechanisms for selecting a move attached to the concept of domination of moves. Different to the Maximin mechanism discussed above, these mechanisms don't necessarily arrive at a recommendation for selecting a move; rather they may only restrict the number of moves available by labeling some of them as "unreasonable".

A move, M1, for player Ann strictly dominates another one, let's call it M2, if M1 always, for every choice of the opponents' moves, results in a higher payoff for Ann than M2. Then having played move M2, Ann will always regret having chosen that option, since M1 would have gotten her a higher payoff. Therefore a rational player would never play a move that is strictly dominated by another one. This is the first mechanism attached to the concept of domination, and as mentioned above it doesn't tell what to play but rather what not to play. In the rare case where one of Ann's moves strictly dominates all her other moves, this mechanism would turn into positive advice---in this case Ann would, according to that principle, play the move dominating all other moves.

It is no coincidence that the advice given by the Maximin mechanism and the advice given by the rule not to play strictly dominated moves are the same for this example. Actually it is rather obvious that a player's Maximin move is never strictly dominated by any of her other moves.

Advise for players could go further than just to disregard their strictly dominated moves. In particular, if player Ann would accept that all other players would also obey this rule, then we may go further and disregard all strictly dominated moves in that game, not only for Ann but for all other players. However, this assumption about the other players' behavior is far from automatic. It requires the conviction that all players are rational and moreover clever or experienced enough. Next, under the assumption that all players accept this belief in the rationality and sophistication of all players, we know that all players make this mental step of reducing the game by eliminating all strictly dominated moves for all players. But then, in this reduced game, strict domination may occur where it has not been the case, and the same round of eliminations--- eliminating all strictly dominated moves in the reduced game---could be done to reduce the game even further. This process of repeatedly reducing the game, as well as its result, a game that cannot be reduced any further since there are no strictly dominated moves, is denoted by IESD---iterated elimination of strictly dominated moves. But note that again, except in cases where the IESD result is a game with just one option for Ann, IESD is a method of excluding moves rather than telling what move to choose.

Let me give an example for the successful application of the IESD procedure:

A weaker condition is weak domination. Ann's move weakly dominates another one of her moves if it yields at least the same payoff for Ann in all cases generated by combinations of moves of the other players, and in at least one case even a better payoff. So the weakly dominating move is never worse than the weakly dominated one, and sometimes it is better. The common opinion is that iterated elimination of weakly dominated moves, IEWD is not something that should performed automatically. One has to be a little more hesitant here; weakly dominated moves may still be played, in particular in cases where the only difference is in a combination of moves which is known not to occur. This opinion is also based on different behavior of Nash equilibria (discussed in Section 2.4) under IEWD and IESD.

Assume you are supposed to play one of these one-round simultaneous games against your friend tomorrow. Your friend thinks about her move a long time, finally arrives on a decision what move to play, and writes it on a piece of paper to not forget it until tomorrow. You happen to get a look on this paper without your friend noticing it. By this, in a sense the game changes from simultaneous to sequential with perfect information. The move you play under these conditions is called the best response to the move of your friend.

Let us start with two players. Ann's best response to Beth's move M is a move of Ann yielding the highest payoff for Ann, given Beth's move M. Of course there may be several best responses to a given move. Similar to the maximin approach, to find Ann's best response to Beth's move M, we don't even have to know Beth's payoffs.

The best response concept does not provide the players with a recipe how to play, but it allows us to express Nash equilibria that are discussed in the next section in a simple way, and also provides us with a simple and quick method to find these (pure strategy) Nash equilibria.

You find the best responses for the first player's (Ann's) moves by looking at the different rows of the bimatrix one by one and selecting in each row the cell where the second entry is maximum. The label of the corresponding column is the best response to the move corresponding to that row. In the same way, to find best responses against the second player's (Beth's) moves we consider the columns and pick in each column the cell with maximum first entry. The label of the corresponding row is the corresponding best response for the move corresponding to that column.

In case of a 2-player game, the best response information for a game can be displayed graphically: The bipartite best response digraph for two-player games is defined as follows: For every possible move of player 1 we draw a blue circle and for every possible move of player 2 we draw a red circle. These circles are called the "vertices" of the digraph. Now from every blue vertex we draw an arrow, a so-called "arc" towards all red vertices which are best responses to the corresponding move of player 1. In the same way, arcs are drawn from all red vertices towards all best response blue vertices. For Example 5, the best response digraph is shown to the right.

In symmetric games, like ADVERTISING and TWO BARS above, it even suffices to display a condensed version of the best response digraph. For every move (of either player---remember the game is supposed to be symmetric, therefore both players have the same moves as options) we draw just one vertex, in one color, and we draw an arc from move X to move Y if Beth's Y is a best response to Ann's X (and of course, therefore also Ann's move Y is a best response to Beth's move X). See the figure to the right for the condensed best response digraph of the symmetric TWO BARS game.

The best response concept makes also sense for games with three or more players, but the graphical representation as best response digraph is no longer possible. For detecting the best response moves of Beth, we look at the second entries (Beth's payoffs) in each column and mark the highest value in each column. To detect the best response moves for the third player (let's call her Cindy) we look at the third entries of the rows and mark in each row the highest entry. Only for Ann the method is a little more complicated to explain. Here we look at first entries only, and compare all cells having the same position in the different matrices, like "upper left", for instance.

In this section we concentrate not only on advice for an individual player; rather we will identify outcomes---combinations of one selected move for each player--- that may occur more likely than others. These outcomes are called equilibria.

If all players have a move strictly dominating all their other moves, then it is obvious how all the players will move. This is called a dominant move equilibrium. As example we take the famous PRISONER'S DILEMMA, whose strange name will be explained later, when we discuss the game in detail.

Not every simultaneous game has a dominant move equilibrium, but for those that have, everything is settled completely. In this case, playing the dominant move also means playing the maximin move.

A sequential game where after the IEWD (respectively the IESD) procedure only one move remains for every player has an IEWD (respectively IESD) equilibrium. Note that every dominant move equilibrium is an IEWD equilibrium, and every IEWD equilibrium is a IESD equilibrium. We illustrate the concept by another folklore example.

The most general equilibrium concept was introduced by John Nash around 1949/1950. Remember that the outcomes of the games, the cells in the Normal Form, are uniquely determined by any combination of moves, one from each player, Such an outcome is called a pure Nash equilibrium provided nobody can gain a higher payoff by deviating from the move, assuming that all other players stick to their choices. Higher payoff for a player may be possible, but only if more than one player change their moves. In other words, an outcome, a combination of moves, is a pure Nash equilibrium if each one single one of these moves is the best response to the other moves. A cell in the Normal Form is a pure Nash equilibrium if each entry is marked (underlined in our examples) as being the best response to the other moves.

The word "pure" in the above definition refers to the fact that we are not mixing moves or strategies yet, in a later chapter mixed Nash equilibria will be introduced.

For two-player games, Nash equilibria may be easiest be recognize from the Best Response Digraph. Any pair of moves with arcs between them, one being the best response of the other, is a Nash equilibrium. For symmetric 2-person games, any pair of arcs between to vertices, or any loop, starting at a vertex and pointing to itself, gives rise to a pure Nash equilibrium. The latter ones, stemming from loops, are symmetric insofar as both players use the same move in them. In symmetric games they may seem more natural than asymetric Nash equilibria.

The concept generalizes that of a IESD equilibrium; every IESD equilibrium is a Nash equilibrium.

On the other hand, Nash equilibria need not to survive EWD actions, but they survive ESD actions. Therefore their resulting reduced bimatrix after the IESD process still contains all Nash equilibria.

Nash equilibria are self-enforcing agreements. If some (non-binding) negotiation has taken place before the game is actually played, each player does best (assuming that the other players stick to the agreement) to do the same. Although the choice of moves D in PRISONER's DILEMMA above with payoffs of only 1 may seem counterintuitive if negotiations can take place in advance, note that the results of these negotiations are non-binding and cannot be enforced. It would be useless to agree on move C in advance, since each of the players would feel a strong urge to deviate (cheat). A very likely outcome in such a case would be C and D, or even D and D, if both cheat. With binding agreements possible, of course, both would agrees on the C-C combination, reaching a higher payoff. Thus the somehow paradoxical result in the PRISONER's DILEMMA that players will play something which results in a lower payoff for both than possible is partly due in the rules of the game disallowing binding agreements that can be enforced.

We have already seen that games may have more than one pure Nash equilibria, but they may also have none. Games where more than one occurs are sometimes called "coordination games", since if pregame negotiations are allowed they have to agree on one of them.. The high-love version of BATTLE OF THE SEXES is an example. In this case, the obvious question is: Which Nash equilibrium is the "best". One idea is to concentrate on Pareto-optimal or efficient Nash equilibria only. That are those where no other Nash equilibrium yields higher or equal payoffs, higher for at least one player. In the BATTLE OF THE SEXES example, both Nash equilibria are Pareto-optimal. If there is no (pure Nash equilibrium, we may want to look into mixed Nash equilibria, but this topic will be discussed later.

For games with more than two players, we would use the marking (underlining) procedure as described in the section on best responses. Then the cells with all entries underlined are the pure Nash equilibria.

One feature used in the analysis of simultaneous games is still missing. It is the topic of mixing moves and is discussed later in the Mixed Strategies chapter.

For a very special class of games, defined by the 3 attributes, Nash equilibria, if existing, have a very easy shape, and the Maximin point of view equals the Nash equilibrium view.

Of course, there follows that a 2-player zero-sum symmetric game has no pure Nash equilibria provided the security level is less than 0. An example is ROCK-SCISSORS-PAPER.

What's next?

Of course most games are not simultaneous. In the next chapter we will discuss a different type of games: Sequential Games

• Ephraim Kishon, Jewish Poker, 1961, http://www.ephraimkishon.de/my_favorite_stories.htm
• Sylvia Nasar, A Beautiful Mind, Simon & Schuster, (1998).
• R. Duncan Luce and Howard Raiffa, Games and Decisions: Introduction and critical Survey, Wiley, New York (1957).
• Marek Kaminski, Lecture 6, Sequential Games, in "Introduction to Game Theory" Course, https://webfiles.uci.edu/mkaminsk/www/gtp/06%20Sequential%20Games.pdf, accessed in August 2007.
• Branislav Slantchev, Game Theory: Dominance, Nash Equilibrium, Symmetry, pdf script, http://www.polisci.ucsd.edu/~bslantch/courses/gt/04-strategic-form.pdf , accessed in August 2007.
• William Poundstone, Prisoner's dilemma, Anchor Books, New York, 1993. (Fowler 510.092 P86p)