Introduction
Mostly for the Instructor
My goal is to present the basic concepts of noncooperative and cooperative game theory and expose students to a very important application of mathematics. In addition, this course introduces students to an understandable theory created by geniuses in many different fields that even today has a low cost of entry.
My experience is that the students who enroll in game theory are primarily mathematics students interested in applications, with about one-third to one-half of the class majoring in economics or other disciplines (such as biology or biochemistry or physics). The modern economics and operations research curriculum requires more and more mathematics, and game theory is typically a required course in those fields. For economics students with a more mathematical background, this course is set at an ideal level. For mathematics students interested in a graduate degree in something other than mathematics, this course exposes them to another discipline in which they might develop an interest and that will enable them to further their studies, or simply to learn some fun mathematics. Many students get the impression that applied mathematics is physics or engineering, and this class shows that there are other areas of applications that are very interesting and that opens up many other alternatives to a pure math or classical applied mathematics concentration.
Game theory can be divided into two broad classifications: noncooperative and cooperative. The sequence of main topics in this book is as follows:
This is generally more than enough to fill one semester, but if time permits (which I doubt) or if the instructor would like to cover other topics (duels, auctions, economic growth, evolutionary stable strategies, population games), these are all presented at some level of depth in this book appropriate for the intended audience. Game theory has a lot of branches and these topics are the main branches, but not all of them. Combinatorial game theory is a branch that could be covered in a separate course but it is too different from the topics considered in this book to be consistent. Repeated games and stochastic games are two more important topics that are skipped as too advanced and too far afield.
This book begins with the classical zero sum two-person matrix games, which is a very rich theory with many interesting results. I suggest that the first two chapters be covered in their entirety, although many of the examples can be chosen on the basis of time and the instructor’s interest. For classes more mathematically oriented, one could cover the proofs given of the von Neumann minimax theorem. The use of linear programming as an algorithmic method for solving matrix games is essential, but one must be careful to avoid getting sucked into spending too much time on the simplex method. Linear programming is a course in itself, and as long as students understand the transformation of a game into a linear program, they get a flavor of the power of the method. It is a little magical when implemented in Maple or Mathematica, and I give two ways to do it, but there are reasons for preferring one over the other when doing it by hand. I skip the simplex method.
The generalization to nonzero sum two-person games comes next with the foundational idea of a Nash equilibrium introduced. It is an easy extension from a saddle point of a zero sum game to a Nash equilibrium for nonzero sum. Several methods are used to find the Nash equilibria from the use of calculus to full-blown nonlinear programming. A short introduction to correlated equilibrium is presented with a conversion to a linear programming problem for solution. Again, Maple/Mathematica is an essential tool in the solution of these problems. Both linear and nonlinear programs are used in this course as a tool to study game theory, and not as a course to study the tools. I suggest that the entire chapter be covered.
It is essential that the instructor cover at least the main points in Chapters 1–7. Chapter 5 is a generalization of two-person nonzero sum games with a finite number of strategies (basically matrix games) to games with a continuum of strategies. Calculus is the primary method used. The models included in Chapter 5 involve the standard economic models, the theory of duels, which are just games of timing, and the theory of auctions. An entire semester can be spent on this one chapter, so the instructor will probably want to select the applications for her or his own and the class’s interest. Students find the economic problems particularly interesting and a very strong motivation for studying both mathematics and economics.
When cooperative games are covered, I present both the theory of the core, leading to the nucleolus, and the very popular Shapley value. Students find the nucleolus extremely computationally challenging because there are usually lots of inequalities to solve and one needs to find a special condition for which the constraints are nonempty. Doing this by hand is not trivial even though the algebra is easy. Once again, Maple/Mathematica can be used as a tool to assist in the solution for problems with four or more players, or even three players. In addition, the graphical abilities of software permit a demonstration of the actual shrinking or expanding of the core according to an adjustment of the dissatisfaction parameter. On the other hand, the use of software is not a procedure in which one simply inputs the characteristic function and out pops the answer. A student may use software to assist but not solve the problem.1 Chapter 6 ends with a presentation of the theory of bargaining in which nonlinear programming is used to solve the bargaining problem following Nash’s ideas. In addition, the theory of bargaining with optimal threat strategies is included. This serves also as a review section because the concepts of matrix games are used for safety levels, saddle points, and so on.
Chapter 7 serves as a basic introduction to evolutionary stable strategies and population games. If you have a lot of biology or biochemistry majors in your class, you might want to make time for this chapter. The second half of the chapter does require an elementary class in ordinary differential equations. The connection between stability, Nash equilibria, and evolutionary stable strategies can be nicely illustrated with the assistance of the Maple/Mathematica differential equation packages, circumventing the need for finding the actual solution of the equations by hand. Testing for stability is a calculus method. One possible use of this chapter is for projects or extra credit.
My own experience is that I run out of time with a 14-week semester after Chapter 6. Too many topics need to be skipped, but adjusting the topics in different terms makes the course fresh from semester to semester. Of course, topics can be chosen according to your own and the class’s interests. On the other hand, this book is not meant to be exhaustive of the theory of games in any way.
The prerequisites for this course have been kept to a minimum. This course is presented in our mathematics department, but I have had many economics, biology, biochemistry, business, finance, political science, and physics majors. The prerequisites are listed as a class in probability, and a class in linear algebra, but very little of those subjects are actually used in the class. I tell students that if they know how to multiply two matrices together, they should do fine; and the probability aspects are usually nothing more than the definitions. The important prerequisite is really not being afraid of the concepts. I have had many students with a background of only two semesters of calculus, no probability or linear algebra, or only high school mathematics courses. Students range from sophomores to graduate students (but I have even taught this course to freshman honors students). As a minor reference I include appendixes on linear algebra, probability, a more detailed explanation of some of the Maple commands, and a translation of the major procedures in the text to Mathematica.
The use of software in this class is also optional, but then it is like learning multivariable calculus without an ability to graph the surfaces. It can be done, but it is more difficult. Why do that when the tool is available? That may be one of the main features of this book, because before the technology was available, this subject had to be presented in a very mathematical way or a very nonmathematical way. I have tried to take the middle road, and it is not a soft class. On the other hand, the new Chapter 4 on extensive games absolutely requires the use of GAMBIT because the interesting models are too complex to do by hand. I feel that this is appropriate considering that GAMBIT is free and runs on all machines. It is also possible for an instructor to skip this chapter entirely if so desired.
There are at least two important websites in game theory. The first is
gametheory.net,
which is a repository for all kinds of game theory stuff. I especially like the notes by T. Ferguson at UCLA, H. Moulin at Rice University, W Bialis at SUNY Buffalo, and Y. Peres, at the University of California, Berkeley. The second site is
which contains the extremely useful open-source software GAMBIT, which students may download and install on their own computers. Gambit is a game-solving program that will find the Nash equilibria of all N-person matrix games with any number of strategies. It may also be used to solve any zero sum game by entering the matrix appropriately. Students love it. Finally, if a user has Mathematica, there is a cooperative game solver available from the Wolfram website, known as TuGames, written by Holgar Meinhardt, that can be installed as a Mathematica package. TuGames can solve any characteristic function cooperative game, and much more. There is also a MatLab package written by Professor Meinhardt for solving cooperative games. The MatLab package is available at http://www.mathworks.com/matlabcentral/fileexchange/35933-mattugames.
As mentioned in the preface, I will post on my website various Maple and Mathematica programs for this course.
I would be grateful for any notification of errors, and I will post errata on my website
I will end this introduction with an intriguing quote that Professor Avner Friedman included in his book Differential Games that he had me read for my graduate studies. The quote is from Lord Byron: “There are two pleasures for your choosing; the first is winning and the second is losing.” Is losing really a pleasure? I can answer this now. The answer is no.
1 On the other hand, the recent result of Leng and Parlar (2010) has explicit formulas for the nucleolus of any three player game. The software doing the calculation is a black box.