Notes on Modeling: Session XII: Non-Zero-Sum Games and Nash Equilibria

Prepared by:

Joseph Malkevitch
Mathematics Department
York College (CUNY)
Jamaica, NY 11451

email: 

malkevitch@york.cuny.edu

web page: 

http://york.cuny.edu/~malk/

Although matrix games can be used to model a large variety of conflict situations there is another approach to modeling game situations which offers more flexibility and the possibility of taking account of ideas that can not be easily captured using matrices (initially). These ideas include the notation of a dynamical quality to a game; player 1 moves before player 2 and must specify as part of his/her action plan what to do depending on what player 1 does. Games where one player reacts to the action of another can be modeled via this approach. There are other issues about how much information a player has when a decision is being made. Perhaps one is sure of one's own payoffs but not those of one's opponent; perhaps one has a probability distribution over what the outcomes might be rather than certainty.

The so-called extensive form of a game enables one to deal with quite general situations, though often the extensive form can eventually be used to construct a matrix form for the game at hand. Sometimes this matrix form is known as the "normal" form of a game.

The basic idea is to use a labeled "tree diagram" (use graph theory) to model the moves and information sets of the players. Usually in graph theory a tree is a connected graph (a graph is connected if it consists of one piece) and has no circuits (a circuit in a graph a collection of distinct edges that can be used to go from a starting vertex back to the vertex along edges that are not repeated. The diagram below shows a general graph which has circuits, and below it, a tree which has no circuits.

(a connected graph with circuits)



(a tree)

Strictly speaking game graphs are usually taken to be oriented graphs (a special kind of digraph, or directed graph), graphs with a direction (arrow) on the edges but we will suppress these arrows. Our game diagram are to be read down from the root at the top, towards the 1-valent vertices, often called the leaves of the tree.

In the game diagram below player one can at the root (top vertex) either go left or right. The second player reacts to this by being "nice" to player 1 (denoted by N) or by being "not nice" to player 1 (denoted by N'). Player 1 knows that player two will have the option of treating her nicely or not nicely. These two alternatives correspond to going either left or right in the diagram at the two decision nodes (one to the left and one to the right) as shown in the diagram.

The payoffs to the players vary with both the choice of player 1 and player two. However, the payoffs will differ according to what action player 2 makes in response to what player 1 has done.

What are the "strategies," action choices that are available to player 2? Player 2 can be nice to player 1 is she goes to the left and player 2 can be nice to player 1 if she goes right; player 2 can be nice to player 1 if she goes left while player while player 2 can be not nice to player 1 if she goes to the right; player 2 can be not nice to player 1 if goes to left and nice to player 1 if she goes to the right; player 2 can be not nice to player one if she goes to the left and also not nice if player 1 goes to the right.

We will denote these 4 approaches to playing the game that player 2 must decide in advance from as N/N, N/N', N'/N, N/N'. Thus, N/N' means player two will be nice to player 1 if she goes to the left and not nice if she goes to the right while N/N means player 2 will be nice to player 1 if she goes to the left and nice if she goes to the right.

Using the tree with the payoffs at the leaves and the actions for the players (2 choices for player 1; 4 choices for player 2) we can move through the tree and get the payoffs shown in the matrix below. (In more general extensive games the same procedure is followed to obtain the matrix entries from the tree of the game; there can not be more different payoff pairs then there are leaves in the tree associated with payoffs. However, the number of leaves need not divide the number of cells in the matrix.)

	N/N	N/N'	N'/N	N'/N'
L	(6,2)	(6,2)	(2,7)	(2,7)
R	(4,2)	(0,0)	(4,2)	(0,0)

Where are the Nash equilibria in this game? They are outcomes (2,7) in column (N'/N') in row L, and the outcome (4,2) in the column (N'/N) and the row R. However, Reinhard Selten, who won the Noble Memorial Prize in economics in part for his work in game theory related to Nash Equilibra has observed that it does not seem reasonable to see the (2,7) outcome in the last column actually arise. This is because if one restricts ones attention to the two possible outcomes that can happen at the vertex on the right in the tree where player 2 makes a decision, why would player 2 ever choose the not nice move? In this little "subgame" player 2 does better by picking the move to the left (this gives 2 units to player 2 instead of 0 units). Hence, the threat of player 2 on the right is not "believable." Hence, it seems reasonable to assume that player 1 would choose to go right rather than left, and that player 2 would choose the (N'/N) strategy, resulting in the outcome of 4 to player 1 and 2 to player 2!


Reference:

Kreps, D., Game Theory and Economic Modeling, Oxford U. Press, Oxford, 1990.