Game Theory

The best introduction to game theory is by way of examples. In this chapter we start with a global definition of the field in Sect. 1.1, collect some historical facts in Sect. 1.2, and present examples in Sect. 1.3. In Sect. 1.4 we briefly comment on the distinction between cooperative and noncooperative game theory.

This chapter deals with two-player games in which each player chooses from finitely many pure strategies or randomizes among these strategies, and the sum of the players’ payoffs or expected payoffs is always equal to zero. Games like the ‘Battle of the Bismarck Sea’ and ‘Matching Pennies’, discussed in Sect. 1.3.1 belong to this class.

In Sect. 2.1 the basic definitions and theory are discussed. Section 2.2 shows how to solve 2 × n and m × 2 games, and larger games by elimination of strictly dominated strategies.

In this chapter we consider two-player games where each player chooses from finitely many pure strategies or randomizes among these strategies. In contrast to Chap. 2 it is no longer required that the sum of the players’ payoffs is zero (or, equivalently, constant). This allows for a much larger class of games, including many games relevant for economic or other applications. Famous examples are the ‘Prisoners’ Dilemma’ and the ‘Battle of the Sexes’ discussed in Sect. 1.3.2.

In Sect. 3.1 we introduce the model and the concept of ‘Nash equilibrium’. Section 3.2 shows how to compute Nash equilibria in pure strategies for arbitrary games, all Nash equilibria in games where both players have exactly two pure strategies, and how to use the concept of strict domination to facilitate computation of Nash equilibria and to compute equilibria also of larger games. The structure of this chapter thus parallels the structure of Chap. 2. For a deeper and more comprehensive analysis of finite two-person games see Chap. 13.

Most games derived from economic or political situations have in common with most parlor games (like card games and board games) that they are not ‘one-shot’: players move sequentially, and one and the same player may move more often than once. Such games are best described by drawing a decision tree which tells us whose move it is and what a player’s information is when that player has to make a move.

In this chapter these so-called ‘games in extensive form’ are studied. Attention here is restricted to games with finitely many players (usually two), finitely many decision moments and finitely many moves. See Sect. 1.3.3 for a few examples. We also assume that each player has ‘complete information’, which – formally – boils down to either there being no chance move in the game or, if a chance move occurs, each player becoming informed about the outcome of that chance move. This excludes, for instance, the game of entry deterrence with incomplete information in Sect. 1.3.3: for the analysis of games with incomplete information see Chap. 5. Chapter 14 extends the analysis of the present and the next chapter.

The first section of this chapter introduces games in extensive form. In order to avoid a load of cumbersome notation the treatment will be somewhat informal but – hopefully – not imprecise. In Sect. 4.2 we define strategies and the ‘strategic form’ of a game: the definition of Nash equilibrium for extensive form games is then practically implied. The focus in this chapter is on pure Nash equilibrium.

In the third section the concept of Nash equilibrium is refined by considering subgame perfection (first introduced in [117] and [118]) and backward induction. A further important refinement, called ‘perfect Bayesian equilibrium’, is treated in the fourth section.

In a game of imperfect information players may be uninformed about the moves made by other players. Every one-shot, simultaneous move game is a game of imperfect information. In a game of incomplete information players may be uninformed about certain characteristics of the game or of the players. For instance, a player may have incomplete information about actions available to some other player, or about payoffs of other players. Following Harsanyi [50], we model incomplete information by assuming that every player can be of a number of different types. A type of a player summarizes all relevant information (in particular, actions and payoffs) about that player. Furthermore, it is assumed that each player knows his own type and, given his own type, has a probability distribution over the types of the other players. Often, these probability distributions are assumed to be consistent in the sense that they are the marginal probability distributions derived from a basic commonly known distribution over all combinations of player types.

In this chapter we consider games with finitely many players, finitely many types, and finitely many strategies. These games can be either static (simultaneous, one-shot) or dynamic (extensive form games). A Nash equilibrium in this context is also called ‘Bayesian equilibrium’, and in games in extensive form an appropriate refinement is perfect Bayesian equilibrium. As will become clear, in essence the concepts studied in Chaps. 3 and 4 are applied again.

In Sect. 5.1 we present a brief introduction to the concept of player types in a game. Section 5.2 considers static games of incomplete information, and Sect. 5.3 discusses so-called signaling games, which is the most widely applied class of extensive form games with incomplete information.

In Chaps. 2–5 we have studied noncooperative games in which the players have finitely many (pure) strategies. The reason for the finiteness restriction is that in such games special results hold, like the existence of a value and optimal strategies for two-person zerosum games, and the existence of a Nash equilibrium in mixed strategies for finite nonzerosum games.

The basic game-theoretical concepts discussed in these chapters can be applied to much more general games. Once, in a game-theoretic situation, the players, their possible strategies, and the associated payoffs are identified, the concepts of best reply and of Nash equilibrium can be applied. Also the concepts of backward induction, subgame perfection, and perfect Bayesian equilibrium carry over to quite general extensive form games. In games of incomplete information, the concept of player types and the associated Nash equilibrium (Bayesian Nash equilibrium) can be applied also if the game has infinitely many strategies.

The bulk of this chapter consists of various, diverse examples verifying these claims. The main objective of the chapter is, indeed, to show how the basic game-theoretic apparatus can be applied to various different conflict situations; and, of course, to show these applications themselves.

In Sect. 6.1 we generalize some of the concepts of Chaps. 2–3. This section serves only as background and general framework for the examples in the following sections. Concepts specific to extensive form games and to incomplete information games are adapted later, when they are applied. In Sects. 6.2–6.7 we discuss, respectively, Cournot competition with complete and incomplete information, Bertrand competition, Stackelberg equilibrium, auctions with complete and incomplete information, mixed strategies with objective probabilities, and sequential bargaining. Variations on these topics and various other topics are treated in the problem section.

In the famous prisoners’ dilemma game the bad (Pareto inferior) outcome, resulting from each player playing his dominant action, cannot be avoided in a Nash equilibrium or subgame perfect Nash equilibrium even if the game is repeated a finite number of times, cf. Problem 4.8(a)–(c). As we will see in this chapter, this bad outcome can be avoided if the game is repeated an infinite number of times. This, however, is going to have a price, namely the existence of a multitude of outcomes attainable in equilibrium. Such an embarrassment of richness is expressed by a so-called Folk theorem.

In an evolutionary game, players are interpreted as populations – of animals or individuals. The probabilities in a mixed strategy of a player in a bimatrix game are interpreted as shares of the population. Individuals within the same part of the population play the same pure strategy. The main ‘solution’ concept is the concept of an evolutionary stable strategy.

Evolutionary game theory originated in the work of the biologists Maynard Smith and Price [77]. Taylor and Jonker [133] and Selten [120], among others, played an important role in applying the developed evolutionary biological concepts to boundedly rational human behavior, and to establish the connection with dynamic systems and with game-theoretic concepts like Nash equilibrium. A relatively recent and comprehensive overview can be found in Weibull [147].

This chapter presents a short introduction to evolutionary game theory. For a somewhat more advanced continuation see Chap. 15.

In Sect. 8.1 we consider symmetric two-player games and evolutionary stable strategies. Evolutionary stability is meant to capture the idea of mutation from the theory of evolution. We also establish that an evolutionary stable strategy is part of a symmetric Nash equilibrium. In Sect. 8.2 the connection with the so-called replicator dynamics is studied. Replicator dynamics intends to capture the evolutionary idea of selection based on fitness. In Sect. 8.3 asymmetric games are considered. Specifically, a connection between replicator dynamics and strict Nash equilibrium is discussed.

The implicit assumption in a cooperative game is that players can form coalitions and make binding agreements on how to distribute the proceeds of these coalitions. A cooperative game is more abstract than a noncooperative game in the sense that strategies are not explicitly modelled: rather, the game describes what each possible coalition can earn by cooperation. In a cooperative game with transferable utility it is assumed that the earnings of a coalition can be expressed by one number. One may think of this number as an amount of money, which can be distributed among the players in any conceivable way – including negative payments – if the coalition is actually formed. More generally, it is an amount of utility and the implicit assumption is that it makes sense to transfer this utility among the players – for instance, due to the presence of a medium like money, assuming that individual utilities can be expressed in monetary terms.

This chapter presents a first acquaintance with the theory of cooperative games with transferable utility.¹ A few important solution concepts — the core, the Shapley value, and the nucleolus – are briefly discussed in Sects. 9.2–9.4. We start with examples and preliminaries in Sect. 9.1.

In this chapter a few other cooperative game theory models are discussed: bargaining problems in Sect. 10.1, exchange economies in Sect. 10.2, matching problems in Sect. 10.3, and house exchange in Sect. 10.4.

Social choice theory studies the aggregation of individual preferences into a common or social preference. It overlaps with several social science disciplines, such as political theory (e.g., voting for Parliament, or for a president) and game theory (e.g., voters may vote strategically, or candidates may choose positions strategically). For a general overview see [3] and [4].

In the classical model of social choice, there is a finite number of agents who have preferences over a finite number of alternatives. These preferences are either aggregated into a social preference according to a so-called social welfare function, or result in a common alternative according to a so-called social choice function.

The main purpose of this chapter is to review two classical results, namely Arrow’s [2] Theorem and Gibbard’s [44] and Satterthwaite’s [112] Theorem. The first theorem applies to social welfare functions and says that, if the social preference between any two alternatives should only depend on the individual preferences between these alternatives and, thus, not on individual preferences involving other alternatives, then the social welfare function must be dictatorial. The second theorem applies to social choice functions and says that the only social choice functions that are invulnerable to strategic manipulation are the dictatorial ones. These results are often referred to as ‘impossibility theorems’ since dictatorships are generally regarded undesirable.

Both results are closely related: indeed, the proof of the Theorem of Gibbard and Satterthwaite in [44] uses Arrow’s Theorem. The presentation in this chapter closely follows that in Reny [108], which is both simple and elegant, and which shows the close relation between the two results. The approach in [108] is itself based on a few other sources: see [108] for the references.

Section 11.1 is introductory. Section 11.2 discusses Arrow’s Theorem and Sect. 11.3 the Gibbard–Satterthwaite Theorem.

In this chapter we study finite two-person zerosum games – matrix games – more rigorously. In particular, von Neumann’s Minimax Theorem [140] is proved. The chapter builds on Chap. 2 in Part I, and the reader is advised to read this chapter and in particular Definition 2.1 before continuing.

Section 12.1 presents a proof of the Minimax Theorem, and Sect. 12.2 shows how a matrix game can be solved – optimal strategies and the value of the game can be found – by solving an associated linear programming problem.

This chapter builds on Chap. 3, where we studied finite two person games – bimatrix games. The reader is advised to (re)read this chapter before continuing. The present chapter offers a more rigorous treatment of finite games, i.e., games with finitely many players — often two — who have finitely many pure strategies over which they can randomize.

In Sect. 13.1 a proof of Nash’s existence theorem is provided. Section 13.2 goes deeper into bimatrix games. In Sect. 13.3 the notion of iterated dominance is studied, and its relation with rationalizability indicated. Sections 13.4–13.6 present some basics about refinements of Nash equilibrium. Section 13.7 is on correlated equilibrium in bimatrix games, and Sect. 13.8 concludes with an axiomatic characterization of Nash equilibrium based on a reduced game (consistency) condition.

A game in extensive form specifies when each player in the game is to move, what his information is about the sequence of previous moves, which chance moves occur, and what the final payoffs are. Such games are discussed in Chaps. 4 and 5, and also occur in Chaps. 6 and 7. The present chapter extends the material introduced in the first two mentioned chapters, and the reader is advised to (re)read these chapters before continuing.

Section 14.1 formally introduces extensive form structures and games, and Sect. 14.2 introduces behavioral strategies and studies the relation between behavioral and mixed strategies. Section 14.3 is on Nash equilibrium and its main refinements, namely subgame perfect equilibrium and sequential equilibrium. For more about refinements and some relations with refinements of Nash equilibrium in strategic form games see [138] and [102].

In this chapter we go somewhat deeper into evolutionary game theory. The concepts of evolutionary stable strategy and replicator dynamics, introduced in Chap. 8, are further explored, and proofs of results mentioned in that chapter are provided. We advise the reader to study Chap. 8 first, although the present chapter is largely self-contained.

This chapter is based mainly on [147]. In Sect. 15.1 we briefly review symmetric two-player games. Section 15.2 discusses evolutionary stable strategies and Sect. 15.3 replicator dynamics.

In a game with transferable utility (TU-game) each coalition (subset of players) is characterized by its worth, i.e., a real number representing the payoff or utility that the coalition can achieve if it forms. It is assumed that this payoff can be freely distributed among the members of the coalition in any way desired.

For some examples the reader is referred to Chap. 1. Chapter 9 presents a first acquaintance with transferable utility games. Although the present chapter and the following ones are self-contained, it may be helpful to study the relevant parts of Chaps. 1 and 9 first.

In this chapter the focus is on the core of a transferable utility game. Section 16.1 starts with a weaker concept, the imputation set, and introduces the concept of domination. Section 16.2 introduces the domination core and the core. Section 16.3 studies these solution concepts for a special class of TU-games called simple games. In Sect. 16.4 we briefly review von Neumann and Morgenstern’s stable sets, which are also based on the concept of domination. Section 16.5, finally, presents a characterization of games with non-empty cores in terms of balancedness.

In Chap. 16 set-valued solution concepts for games with transferable utilities were studied: the imputation set, core, domination core, and stable sets. In this chapter, a one-point (single-valued) solution concept is discussed: the Shapley value. It may again be helpful to first study the relevant parts of Chaps. 1 and 9.

Section 17.1 introduces the Shapley value by several formulas and presents (a variation on) Shapley’s axiomatic characterization using additivity. In Sect. 17.2 we present three other characterizations of the Shapley value: a description in terms of Harsanyi dividends; an axiomatic characterization of Young based on strong monotonicity; and Owen’s formula for the Shapley value based on a multilinear extension of games. Section 11.3 discusses Hart and Mas-Colell’s approach to the Shapley value based on potential and reduced games.

In Chap. 17 we have seen that the Shapley value of a game does not have to be in the core of the game, nor even an imputation (Problem 17.5). In this chapter we introduce a set-valued extension of the Shapley value, the Weber set, and show that it always contains the core (Sect. 18.1). Next, we study so-called convex games and show that these are exactly those games for which the core and the Weber set coincide. Hence, for such games the Shapley value is an attractive core selection (Sect. 18.2). Finally, we study random order values (Sect. 18.3), which fill out the Weber set, and the subset of weighted Shapley values, which still cover the core (Sect. 18.4).

The core of a game with transferable utility can be a large set, but it can also be empty. The Shapley value assigns to each game a unique point, which, however, does not have to be in the core.

The nucleolus (Schmeidler [116]) assigns to each game with a nonempty imputation set a unique element of that imputation set; moreover, this element is in the core if the core of the game is nonempty. The pre-nucleolus always exists (and does not have to be an imputation, even if this set is nonempty), but for balanced games it coincides with the nucleolus.

In this chapter, which is partially based on the treatment of the subject in [100] and [98], we consider both the nucleolus and the pre-nucleolus. The reader is advised to read the relevant part of Chap. 9 first.

In Sect. 19.1 we start with an example illustrating the (pre-)nucleolus and Kohlberg’s balancedness criterion (Kohlberg [65]). Section 19.2 introduces the lexicographic order, on which the definition of the (pre-)nucleolus in Sect. 19.3 is based. Section 19.4 presents the Kohlberg criterion, which is a characterization of the (pre-) nucleolus in terms of balanced collections of coalitions. Computational aspects are discussed in Sect. 19.5, while Sect. 19.6 presents Sobolev’s [127] characterization of the pre-nucleolus based on a reduced game property.

In this chapter we consider several classes of games with transferable utility which are derived from specific economic (or political) models or combinatorial problems. In particular, we study assignment and permutation games, flow games, and voting games.

The game-theoretic literature on bargaining can be divided in two strands: the cooperative and the noncooperative approach. Here, the focus is on the cooperative approach, which was initiated by Nash [90] and which is axiomatic in nature. A seminal article on noncooperative bargaining is Rubinstein [110]. The basic idea of that paper is briefly repeated below, see Sect. 6.7 for a more elaborate discussion. We conclude the chapter with a few remarks on games with non-transferable utility (NTU-games).

This chapter collects some mathematical tools used in this book: (direct) convex separation results in Sects. 22.2 and 22.6; Lemmas of the Alternative, in particular Farkas’ Lemma in Sect. 22.3; the Linear Duality Theorem in Sect. 22.4; the Brouwer and Kakutani Fixed Point Theorems in Sect. 22.5; the Krein-Milman Theorem and the Birkhoff-von Neumann Theorem in Sect. 22.6; and the Max-Flow Min-Cut Theorem of Ford and Fulkerson in Sect. 22.7.