You are here

Game Theory, Alive

Anna R. Karlin and Yuval Peres
American Mathematical Society
Publication Date: 
Number of Pages: 
[Reviewed by
Mark Hunacek
, on

This is an attractive candidate as a text for a mathematically rigorous course in game theory at the upper undergraduate or elementary graduate level. It offers an appealing and versatile selection of topics (including some modern ones), clear and well-motivated exposition, a good selection of examples, and a nicely-chosen selection of exercises (some but not all of which have solutions in the back of the book).

The text should be accessible to majors not just in mathematics but also in related fields such as computer science, economics or statistics. The reader is assumed to have some background in linear algebra and probability (and, in some sections, analysis). Prior exposure to linear programming would of course be a definite plus, but, for those who don’t have it, this material is developed, more or less from scratch, in an appendix.

Another recent AMS text, Game Theory: A Playful Introduction by DeVos and Kent, has some features in common with the Karlin and Peres text, but also has some differences. Karlin and Peres begins, as does Playful Introduction, with a chapter on combinatorial games, in which the players move sequentially with full knowledge of previous play, and where the outcome is determined solely by these moves; the discussion here is shorter and more succinct, however, than in Playful Introduction. And, again in common with Playful Introduction, this chapter is followed by several on classical game theory; these are the games where the players move simultaneously, with outcomes recorded in a matrix. The authors discuss both zero-sum and non-zero sum games, but for the moment limit themselves to games with two people. The existence of a Nash equilibrium is proved. The authors tie this material in with the first chapter by also discussing games in extensive form, given by a “game tree”, this time with no assumption that the players have perfect information.

One feature that struck me as interesting and unusual was the inclusion of a chapter discussing games on graphs. This chapter included not just a statement but also a proof of Hall’s Marriage Theorem, a result that I’ve seen before in a number of combinatorics texts but have not, to the best of my recollection, ever encountered before in a game theory text.

These chapters are only the tip of the iceberg, however. This book takes things further than Playful Introduction, and is written in a somewhat more sophisticated way. Playful Introduction, for example, devoted a section in the final chapter to voting theory and a proof of Arrow’s Impossibility Theorem; this text offers an entire chapter on the subject, including not only a proof of Arrow’s theorem but also a proof of another impossibility result, the Gibbard-Satterthwaite theorem, which essentially states that any voting system satisfying certain mild conditions must be manipulable.

There is also a chapter on fair division. Both fair division and voting theory are topics that can be discussed at a very elementary level; I cover them both in a freshmen-level “quantitative literacy” course that I occasionally teach. Needless to say, however, the way I cover them in that class bears little resemblance to the way they are covered here. Instead of spending a chapter discussing numerous methods of fair division (see, for example, Tannenbaum’s Excursions in Modern Mathematics for a very elementary account), this book focuses on theory. The authors use Sperner’s Lemma to prove the existence of an envy-free division of a continuous object (like a cake, the traditional metaphor for the thing being divided) for three or more players. (For two players, there is a relatively easy specific fair division protocol called the Selfridge-Conway algorithm, not discovered until around 1960; the authors mention this is in passing but do not provide the details of it.)

Other chapters in the text cover games with random moves, evolutionary games, stable matchings, auctions, cooperative games (and the Shapley value), and other topics.

There is certainly more material in this text than can be covered in a one-semester course. However, the chapters seem to be written with flexibility in mind, and the authors provide a very good dependence chart for the benefit of an instructor who needs to organize a course.

There is also a very extensive bibliography. Most of the items referenced in it are articles (some in languages other than English), rather than textbooks.

One thing did strike me as odd: there is a strange disconnect between the level of the text and its appearance. The book is oversized, and filled with drawings, pictures and cartoons (some black and white, some in full color); at first glance, it looks like a text for a much more elementary class, perhaps even at the “general education” level. This is definitely not the case, however! The reader here will find precise definitions, statements of theorems, and proofs. Presumably the pictures and cartoons were included to make the book friendly and inviting to students, but I wonder if some graduate course (or even some upper-level undergraduate course) instructors might find the appearance of this text to be almost insultingly childish.

But, if you shouldn’t judge a book by its cover, you probably shouldn’t judge it by its illustration content either. People who teach, or simply have an interest in, game theory, will certainly find this book worth a look.


Buy Now

Mark Hunacek ( teaches mathematics at Iowa State University.

See the table of contents in the publisher's webpage.