Chapter 9: Matrix Games
Two player zero-sum games describe strictly competitive situations involving two players. Matrix games are two player zero-sum games with finite strategy sets. Matrix games are interesting in many ways and their analysis is tractable due to their simplicity and special structure. It was shown by von Neumann and Morgenstern that linear programming can be used to solve these games. In this chapter, we first provide several examples of matrix games. Next we analyze matrix games in the context of pure strategies through key notions such as security level, security strategies, and saddle points. We show that pure strategy Nash equilibria, if they exist, are precisely the saddle points. Following this, we analyze matrix games in the context of mixed strategies. We show that the optimal strategies for the two players can be described by linear programs which are duals of each other. This leads to the main result in this chapter, the minimax theorem, which shows that every matrix game is guaranteed to have a mixed strategy Nash equilibrium.