Game Theory, Alive

Anna R. Karlin and Yuval Peres

Description:

This is a broad introduction to many of the flavors of game theory. One aim is to promote game theoretic thinking: while choosing your actions to optimize your outcome, consider that other participants, be they opponents or allies, are doing their own optimization, and their choices may have an effect on your reward as well. This type of thinking is crucial in economics, and is also of growing importance in computer science.

The book starts with combinatorial games in Chapter 1, and continues to the basic theory of zero sum and general sum games with prescribed payoffs in Chapters 2-5.. The von Neumann minimax Theorem and the existence of Nash equilibria are proved, via an explanation of the roles of convexity and fixed-point theorems, respectively.

Games with general payoffs where players alternate moves are presented in chapter 6, and evolutionary stable strategies, that arose from mathematical biology, are described in Chapter 7. The price of anarchy, discussed in chapter 8, measures the ratio of the rewards obtained by players which optimize for themselves, to global optimization.

The second part of the book switches from the perspective of a player to that of a mechanism designer. Several types of matching markets are studied, and the basic theory of auctions is developed. Chapter 11 concerns fair division, a.k.a. cake-cutting, while different voting methods are compared in Chapter 13.

Adaptive learning is the subject of Chapter 18: viewing the learning process as a game between the learner and an adversary is quite fruitful.

The book originated in courses taught by the authors at Berkeley and the University of Washington. It can be used for an undergraduate as well as a graduate course via a suitable selection of topics.