Mathematical Foundations of Game Theory

This chapter is devoted to a general introduction to strategic interactions. A collection of examples (matching, bargaining, congestion, auctions, vote, evolution, repetition, etc) shows the variety of situations involved and the kind of problems that occur. The formal definition of a normal form game, notations and basic concepts are introduced.

This chapter studies zero-sum games, where the sets of strategies are finite. We prove the minmax theorem of von Neumann, which states that if a game is played with mixed strategies (probability distribution on strategies) then the value exists, as well as an optimal mixed strategy for each player. We then consider extensions such as Loomis’ theorem and Ville’s theorem. Finally, we introduce and study the convergence of the learning process “Fictitious Play”, where the initial game is repeated and each player plays at every period a best response to the average of the strategies played by his opponent in the past.

This chapter considers general zero-sum games and proves various minmax theorems. We start with Sion’s theorem with geometrical and topological assumptions on the game: convex compact strategy sets and payoff functions quasi-concave upper semi-continuous in the first variable and quasi-convex lower semi-continuous in the second variable. Then we prove the standard minmax theorem in mixed strategies for measurable bounded payoff functions, extending von Neumann’s theorem, under topological assumptions: compact Hausdorff strategy sets and payoff functions upper semi-continuous in the first variable and lower semi-continuous in the second variable. We conclude the chapter with the introduction of the value operator and the notion of a derived game, which play an important role in the operator approach to repeated games.

This chapter deals with N-player games (general-sum games). The standard notions of best response, weak and strict dominations are introduced. We then define the concept of rationalizable strategies and prove an existence theorem (Bernheim and Pearce). Next we present the central notion of Nash equilibria. The existence of a mixed strategy Nash equilibrium in finite games is then proved, using Brouwer’s fixed point theorem. Section 4.7 deals with generalizations to continuous games. The existence of an equilibrium is proved under topological and geometrical assumptions, for compact, continuous and quasi-concave games, and the existence of a mixed equilibrium is shown under the topological conditions. Then, the characterization and uniqueness of a Nash equilibrium are presented for smooth games where the strategy sets are convex subsets of Hilbert spaces. Section 4.8 deals with Nash and approximate equilibria in discontinuous games and notably studies Reny’s better-reply security. In Sect. 4.9 we explain that the set of mixed Nash equilibria of a finite game is semi-algebraic and define the Nash components of a game. Lastly, Sect. 4.10 discusses several notions (feasible payoffs, punishment level, threat point, focal point, Nash versus prudent behavior, common knowledge of the game) and Sect. 4.11 proves the standard fixed-point theorems of Brouwer (via Sperner’s Lemma) and Kakutani (for a multi-valued mapping from a convex compact subset of a normed vector space to itself).

This chapter describes concave games, potential games, population games and Nash/Wardrop equilibria and introduces the characterization of equilibria via variational inequalities. We then study the equilibrium manifold, where the finite strategy sets are fixed and the payoff functions vary. We prove the structure theorem of Kohlberg and Mertens, then show that every game has an essential component of Nash equilibria, and that for generic payoffs, the set of mixed equilibria is finite and its cardinality is odd. We also introduce Nash vector fields and game dynamics, such as the replicator dynamics, the Smith dynamics, the best response dynamics and the Brown–von Neumann–Nash dynamics. We conclude this chapter with an analysis of evolutionary stable strategies (ESS) and their connection with replicator dynamics.

This chapter deals with games in extensive form. Here an explicit evolution of the interaction is given, describing precisely when each player plays, what actions are available and what information is available to each player when he makes a decision. We start with games with perfect information (such as chess) and prove Zermelo’s theorem for finite games. We then consider infinite games à la Gale–Stewart: we show that open games are determined and that under the axiom of choice, there exists an undetermined game. Next we introduce games with imperfect information and prove Kuhn’s theorem, which states that mixed and behavioral strategies are equivalent in games with perfect recall. We present the standard characterization of Nash equilibria in behavioral strategies and introduce the basic refinements of Nash equilibria in extensive-form games: subgame-perfection, Bayesian perfect and sequential equilibria, which impose rational behaviors not only on the equilibrium path but also off-path. We prove the existence of sequential equilibrium (Kreps and Wilson). For normal form games as in Chap. 4 we introduce the standard refinements of Nash equilibrium: perfect equilibrium (Selten) and proper equilibrium (Myerson). We prove that a proper equilibrium of a normal form game G induces a sequential equilibrium in every extensive-form game with perfect recall having G as normal form. Finally we discuss forward induction and stability (Kohlberg and Mertens).

This chapter starts with the concept of correlated equilibrium due to Aumann, an extension of Nash equilibrium with interesting properties from a strategic, geometric and dynamics viewpoint. In a learning framework, we then introduce no-regret procedures and calibrated strategies, and prove existence results. Next we show that in a repeated game: (1) if a player follows a strategy with no external regret, the empirical distribution of moves converges a.s. to its corresponding Hannan set, and (2) if each player follows a procedure with no internal regret, convergence to the set of correlated equilibrium distributions occurs. We conclude this chapter with games with incomplete information (Bayesian games), where the players have different information on the game they have to play, and we introduce the corresponding extension of Nash equilibrium (called Bayesian equilibrium).

This chapter deals with repeated games. It first considers the simplest model (with observed moves) and introduces: finitely repeated games where the payoff is the average of the stage payoffs over finitely many stages, discounted games where the payoff is the (infinite) discounted sum of the stage payoffs, and uniform games where players consider the payoff in any long enough game (or in any discounted game with low enough discount factor). We present the Folk theorem, which states that the equilibrium payoffs of a uniform game are precisely the vector payoffs which are feasible (achievable) and individually rational (above the punishment level for each player). The message is simple: if players are patient enough, any reasonable payoff can be achieved at equilibrium. Folk theorems for discounted games and finitely repeated games are also exposed and proved. The last section presents extensions of the model in three directions: repeated games with signals (imperfect observation of moves), stochastic games where the “Big Match” is studied, and repeated games with incomplete information where we prove the cav(u) theorem of Aumann and Maschler.

This chapter contains hints to the solutions of the exercises. The topics include stable matchings, Vickrey auctions, Blackwell approachability, Farkas’ lemma, duality in linear programming, duels, Cournot competition, supermodular games and Tarski’s fixed point theorem, convex games, potential games, dissipative games, fictitious play and the Shapley triangle, the game of Chomp, a poker game, bargaining, a double auction, the possibly negative value of information, strategic transmission of information, correlated equilibrium distribution via minmax, comparison between correlated and Nash equilibria, the prisoner’s dilemma with a blind player, the battle of the sexes in the dark, jointly rational payoffs, subgame-perfect equilibrium payoffs for discounted games and quitting games.