A Course in Game Theory

The following sections are included:

• Preface
• Introduction
• Contents

Combinatorial games are two-person games with perfect information and no chance moves, and with a win-or-lose outcome. Such a game is determined by a set of positions, including an initial position, and the player whose turn it is to move. Play moves from one position to another, with the players usually alternating moves, until a terminal position is reached. A terminal position is one from which no moves are possible. Then one of the players is declared the winner and the other the loser…

The most famous take-away game is the game of Nim, played as follows. There are three piles of chips containing x₁, x₂, and x₃ chips respectively. (Piles of sizes 5, 7, and 9 make a good game.) Two players take turns moving. Each move consists of selecting one of the piles and removing chips from it. You may not remove chips from more than one pile in one turn, but from the pile you selected you may remove as many chips as desired, from one chip to the whole pile. The winner is the player who removes the last chip. You can play this game on the web at http://www.tomsferguson.com/Games/Nim.html.

We now give an equivalent description of a combinatorial game as a game played on a directed graph. This will contain the games described in Chaps. 1 and 2. This is done by identifying positions in the game with vertices of the graph and moves of the game with edges of the graph. Then we will define a function known as the Sprague-Grundy function that contains more information than just knowing whether a position is a P-position or an N-position.

Given several combinatorial games, one can form a new game played according to the following rules. A given initial position is set up in each of the games. Players alternate moves. A move for a player consists in selecting any one of the games and making a legal move in that game, leaving all other games untouched. Play continues until all of the games have reached a terminal position, when no more moves are possible. The player who made the last move is the winner…

We have mentioned the game called Turning Turtles in Exercise 2.6.4 as a disguised version of nim. This form of the game of nim is a prototype of a class of other games that have similar descriptions. These ideas are due to H. W. Lenstra. In particular, the extension of these games to two dimensions leads to a beautiful theory involving nim multiplication which, with the definition of nim addition, makes the nonnegative integers into a field…

The game of Hackenbush is played by hacking away edges from a rooted graph and removing those pieces of the graph that are no longer connected to the ground. A rooted graph is an undirected graph with every edge attached by some path to a special vertex called the root or the ground. The ground is denoted in the figures that follow by a dotted line…

The individual most closely associated with the creation of the theory of games is John von Neumann, one of the greatest mathematicians of the 20th century. Although others preceded him in formulating a theory of games — notably Émile Borel — it was von Neumann who published in 1928 the paper that laid the foundation for the theory of two-person zero-sum games. Von Neumann’s work culminated in a fundamental book on game theory written in collaboration with Oskar Morgenstern entitled Theory of Games and Economic Behavior (1944). Other discussions of the theory of games relevant for our present purposes may be found in the textbook, Game Theory by Guillermo Owen, 2nd edition (1982), and the expository book, Game Theory and Strategy by Philip D. Straffin (1993)…

A finite two-person zero-sum game in strategic form, (X, Y, A), is sometimes called a matrix game because the payoff function A can be represented by a matrix. If X = {x₁, …, x_m} and Y = {y₁, …, y_n}, then by the game matrix or payoff matrix we mean the matrix

For a matrix game with m×n matrix A, if Player I uses the mixed strategy p = (p₁, …, p_m)^T and Player II uses column j, Player I’s average payoff is ${\displaystyle {\sum }_{i=1}^m{p}_i{a}_{ij}}$. If V is the value of the game, an optimal strategy, p, for I is characterized by the property that Player I’s average payoff is at least V no matter what column j Player II uses, i.e.

Consider an arbitrary finite two-person zero-sum game, (X, Y, A), with m×n matrix, A. Let us take the strategy space X to be the first m integers, X = {1, 2, …, m}, and similarly, Y = {1, 2, …, n}. A mixed strategy for Player I may be represented by a column vector, (p₁, p₂, …, p_m)^T of probabilities that add to 1. Similarly, a mixed strategy for Player II is an n-tuple q = (q₁, q₂, …, q_n)^T. The sets of mixed strategies of players I and II will be denoted respectively by X^* and Y^*,

The strategic form of a game is a compact way of describing the mathematical aspects of a game. In addition, it allows a straightforward method of analysis, at least in principle. However, the flavor of many games is lost in such a simple model. Another mathematical model of a game, called the extensive form, is built on the basic notions of position and move, concepts not apparent in the strategic form of a game. In the extensive form, we may speak of other characteristic notions of games such as bluffing, signaling, sandbagging, and so on. Three new concepts make their appearance in the extensive form of a game: the game tree, chance moves, and information sets.

The following sections are included:

• Matrix Games with Games as Components
• Multistage Games
• Recursive Games. ϵ-Optimal Strategies
• Stochastic Movement Among Games
• Stochastic Games
• Approximating the Solution
• Exercises

In this chapter, we treat infinite two-person, zero-sum games. These are games (X, Y, A), in which at least one of the strategy sets, X and Y, is an infinite set. The famous example of Exercise 10.8.3, he-who-chooses-the-larger-integer-wins, shows that an infinite game may not have a value. Even worse, the example of Exercise 10.8.5 shows that the notion of a value may not even make sense in infinite games without further restrictions. This latter problem will be avoided when we assume that the function A(x, y) is either bounded above or bounded below.

The simplest case to consider beyond two-person zero-sum games are the two-person non-zero-sum games. Examples abound in Economics: the struggle between labor and management, the competition between two producers of a single good, the negotiations between buyer and seller, and so on. Good reference material may be found in books of Owen and Straffin already cited. The material treated in Part III is much more oriented to economic theory. For a couple of good references with emphasis on applications in economics, consult the books, Gibbons (1992) and Bierman and Fernandez (1993).

Two-person general-sum games and n-person games for n > 2 are more difficult to analyze and interpret than the zero-sum two-person games of Part II. The notion of “optimal” behavior does not extend to these more complex situations. In the noncooperative theory, it is assumed that the players cannot overtly cooperate to attain higher payoffs. If communication is allowed, no binding agreements may be formed. One possible substitute for the notion of a “solution” of a game is found in the notion of a strategic equilibrium.

The examples given of the noncooperative theory of equilibrium have generally shown the theory to have poor predictive power. This is mainly because there may be multiple equilibria with no way to choose among them. Alternately, there may be a unique equilibrium with a poor outcome, even one found by iterated elimination of dominated strategies as in the prisoner’s dilemma or the centipede game. But there are some situations, such as the prisoner’s dilemma played once, in which strategic equilibria are quite reasonable predictive indicators of behavior. We begin with a model of duopoly due to Cournot (1838).

In one version of the noncooperative theory, communication among the players is allowed but there is no machanism to enforce any agreement the players may make. The only believable agreement among the players would be a Nash equilibrium because such an agreement would be self-enforcing: no player can gain by unilaterally breaking the agreement. In the cooperative theory, we allow communication among the players and we also allow binding agreements to be made. This requires some mechanism outside the game itself to enforce the agreements. With the extra freedom to make enforceable binding agreements in the cooperative theory, the players can generally achieve a better outcome. For example in the prisoner’s dilemma, the only Nash equilibrium is for both players to defect. If they cooperate, they can reach a binding agreement that they both use the cooperate strategy, and both players will be better off…

We now consider many-person cooperative games. In such games there are no restrictions on the agreements that may be reached among the players. In addition, we assume that all payoffs are measured in the same units and that there is a transferrable utility which allows side payments to be made among the players. Side payments may be used as inducements for some players to use certain mutually beneficial strategies. Thus, there will be a tendency for players, whose objectives in the game are close, to form alliances or coalitions. The structure given to the game by coalition formation is conveniently studied by reducing the game to a form in which coalitions play a central role. After defining the coalitional form of a many-person TU game, we shall learn how to transform games from strategic form to coalitional form and vice versa.

In cooperative games, it is to the joint benefit of the players to form the grand coalition, N, since by superadditivity the amount received, v(N), is as large as the total amount received by any disjoint set of coalitions they could form. As in the study of 2-person TU games, it is reasonable to suppose that “rational” players will agree to form the grand coalition and receive v(N). The problem is then to agree on how this amount should be split among the players. In this section, we discuss one of the possible properties of an agreement on a fair division, that it be stable in the sense that no coalition should have the desire and power to upset the agreement. Such divisions of the total return are called points of the core, a central notion of game theory in economics.

We now treat another approach to n-person games in characteristic function form. The concept of the core is useful as a measure of stability. As a solution concept, it presents a set of imputations without distinguishing one point of the set as preferable to another. Indeed, the core may be empty…

Another interesting value function for n-person cooperative games may be found in the nucleolus, a concept introduced by Schmeidler (1969). Instead of applying a general axiomatization of fairness to a value function defined on the set of all characteristic functions, we look at a fixed characteristic function, v, and try to find an imputation x = (x₁, …, x_n) that minimizes the worst inequity. That is, we ask each coalition S how dissatisfied it is with the proposed imputation x and we try to minimize the maximum dissatisfaction.

The following sections are included:

• Appendix 1 Utility Theory
• Appendix 2 Owen’s Proof of the Minimax Theorem
• Appendix 3 Contraction Maps and Fixed Points
• Appendix 4 Existence of Equilibria in Finite Games

The following sections are included:

• Solutions to Exercises of Part I
  • Solutions to Chap. 1
  • Solutions to Chap. 2
  • Solutions to Chap. 3
  • Solutions to Chap. 4
  • Solutions to Chap. 5
  • Solution to Chap. 6
• Solutions to Exercises of Part II
  • Solutions to Chap. 7
  • Solutions to Chap. 8
  • Solutions to Chap. 9
  • Solutions to Chap. 10
  • Solutions to Chap. 11
  • Solutions to Chap. 12
  • Solutions to Chap. 13
• Solutions to Exercises of Part III
  • Solutions to Chap. 14
  • Solutions to Chap. 15
  • Solutions to Chap. 16
  • Solutions to Chap. 17
• Solutions to Exercises of Part IV
  • Solutions to Chap. 18
  • Solutions to Chap. 19
  • Solutions to Chap. 20
  • Solutions to Chap. 21
• Solutions to Exercises of Appendix 1

The following sections are included:

• References
• Index