Game Theory: Session 1: Matrix Games

Prepared by:

Joseph Malkevitch
Department of Mathematics and Computer Studies
York College (CUNY)
Jamaica, New York

email:

malkevitch@york.cuny.edu

web page:

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

The best way to reach me between classes is via email:

malkevitch@york.cuny.edu

Games are a big part of growing up in a variety of different countries and cultures. Children learn about "life" from playing games like monopoly, poker, tic-tac-toe, oware, and nim. Games involve players, payoffs, conflict, and excitement about winning or getting some valuable payoff. However, there are also conflict situations that play out on a broader and more important stage. Thus, there are "games" between labor and management involving the negotiation over a new contract. A union involved must decide whether or not to conduct a strike if its member workers do not get the results they want. There are "games" between nations that involve the jockeying for influence on the "world stage." The Cold War involved a "cat and mouse" game between the US and the Former Soviet Union over superiority in nuclear weapons technology and spy satellites. Game Theory issues arise in a broad class of real world situations ranging from drivers choosing which of several alternative bridges to use in driving from one location to another to auctions for art. (See "As Art Values Rise, So Do Concerns about Market's Oversight, NY Times, Monday, January 28, 2013, Page A1 and Page A14.) A sample of the many aspects of game theory can be explored via the many articles related to game theory available via Wikipedia. A template for these terms which allows one to go on to an article related to a particular term is available here. WIki also has a survey article about equity in economics.

Many games involve the need for a randomization device in order to carryout a move or action on the part of some player. One can use a spinner as a randomization device but also one can use a "die." Typical dice are Platonic Solids (regular cube, regular tetrahedron, regular dodecahedron, regular octahedron, and regular icosahedron) or convex polyhedra which have symmetries which are transitive on the faces. Such dice have the potential to be fair. Transitive on the faces means that there is a symmetry of the die which will take any face to any other face. Perhaps surprisingly those convex polyhedra that can serve as a fair die are not completely known. You can find a discussion of fair dice here. Despite some claims that a complete collection of fair dice is known, I have not seen a scholarly defense of this claim.

Matrix games are a broad class of games that can be used to model many conflict situations. We will consider the case of 2 players and where each player has two choices of actions. The players will be called Row and Column. When Row moves, he/she picks one of the available rows. When Column moves he/she picks of of the available columns. Matrix games are games of perfect information. At each stage of the game both players know the options and payoffs to the other player. In some games there may be uncertainty about what actions one's opponent can take, and even if one knows all of the actions the opponent has available there may be uncertainty about the payoffs from these these actions.

Here is an example of a 2x2 matrix game.


  Column I Column II
Row 1 (+8, -8) (-1, +1)
Row 2 (-2, +2) (-5, +5)



Figure 1

How is the game in Figure 1 played? Row picks either Row 1 (R1) or Row 2 (R2) without disclosing to Column what his/her action will be. Row and Column may or may not have discussed how they might play the game or come to an agreement about how they will play against each other - what choice or rows or columns to make. It is important for now, however, that neither of the players makes a move before the other. They play as if each is independently reaching a decision which they keep secret and that their moves are simultaneous. You can think of this as being done by each player writing on a piece of paper in secret the move they plan, handing these papers to a totally reliable "referee" who then based on what he reads from the papers given him assigns the payoffs based on the matrix entries to the players. For example suppose Row played R1 and Column played CII. the referee would ask Row to give C a payoff of $1. Row loses $1 and Column gains $1. (For simplicity we will assume the payoffs are in dollars. More generally you can think of the payoffs as being satisfaction units, often referred to as utiles.)

How might one expect this game to be played? Here is how Row could/should reason. If Column plays Column I, I am better off playing Row 1 because I would rather win 8 than lose 2. On the other hand if Column plays Column II, I am better off playing Row 1 since I would rather lose one than lose 5. Hence, no matter what my opponent does I am better off playing Row 1! Column can argue in a similar way resulting in the fact whatever Row does, Column is better off playing Column II. So one would expect that every time this game is played that the outcome would be that Row loses a dollar and Column gains a dollar. So this does not seem like a "fair" game - Column always wins, but one would be surprised to see the game played in any other way.

In analyzing this game we say that from Row's perspective Row 1 dominates Row 2 while Column II dominates Column I. The notion of row and column dominance can be extended to zero-sum games with m rows and n columns.

Here is another way to see that one would expect Row to play Row 1 and Column to play Column II. Suppose this game is being played many times and Row observes that column is always playing Column II and hence might expect him/her to play Column II again on the next play of the game. If Column indeed plays column II and Row switches from Row 1 to Row 2, Row does worse and Column does better! A similar argument applies to Column. Thus, if this game is played many times one could expect the outcome to be the payoff in the cell in the first row and second column. Thus, we can think of -1 as the value of the game to Row and +1 as the value of the game to column. This outcome is also an "equilibrium" since deviating from the action that leads to this outcome by only one of the players makes matters worse for that player.

The analysis of the best way to play the game in Figure 2 is equally interesting but much more subtle. For convenience below when Row plays row a and Column plays column b, we will indicate the payoff cell or outcome of this way of playing by (a, b).


 

Column I

Column II
Row 1 (+8, -8) (-3, +3)
Row 2 (-2, +2) (4, -4)



Figure 2


First notice that neither row dominates the other nor does either column dominate the other. Suppose on some play of the game the outcome is (1, 1) that is Row plays Row 1 and Column plays column I. Column might reason, if Row continues to play Row 1 in the next play of the game then Column will want to switch to Column II, because the outcome in (1, 2) is better for column than the outcome in (1, 1). However, anticipating this Row might decide to play Row 2 so that if column did play Column II the outcome would be to obtain the (2,2) outcome rather than the (2, 1) outcome. This results in a complex "chain" of thoughts about how to play.

In this game for any of the 4 possible outcomes (cells of the matrix) if this outcome occurs in the i-th play of the game, there is always a better outcome for one of the players, assuming that the other player does not change his/her move in the (i+1)-st play of the game. For example, suppose the outcome is cell (2,1) - second row, 1st column. Then Row loses 2 and Column gains 2 - pleasing Column but not pleasing Row. If Column continues to play Column I in the next play of the game then Row will do better in the next play by playing Row 1 rather than Row 2.

So what advice would you give Row and Column about how to play this game if it is played only once? What about if the game if played many times? What is needed is some new idea!