1.0 IntroductionVon Neumann and Morgenstern posed a mathematical problem in 1944: Does every game have a solution, where a solution is defined in their sense? W. F. Lucas solved this problem in 1967. Not all games have such a solution. (It is known that such a solution need not be unique. In fact, the solution to the three person game I use below to illustrate the Von Neumann and Morgenstern solution is not unique.)
I may sometime in the future try to explain the game with ten players Lucas presents as a counterexample, assuming I can grasp it better than I do now. With this post, I try to explain some concepts of cooperative game theory so as to have this post for reference when and if I do. The Nash equilibrium and refinements are notions from the different theory of non-cooperative game theory.
2.0 Definition of a GameRoughly, a game is specified by:
- The number of players
- The strategies available for each player
- The payoffs to each player for each combination of player strategies
How a strategy is described depends on the specification of the game - whether it is in extensive form, normal form, or characteristic function form. Von Neumann and Morgenstern hoped that all three forms would be equivalent, with less data needing to be specified in the later forms in this series. This hope has arguably not worked out.
2.1 Extensive FormA game in extensive form is specified as a tree. This is most easily seen for board games, like backgammon or chess. Each node in the tree is a board position, with the root of the tree corresponding to the initial position.
The specification of a node includes which player is to move next, as well as the board position. Each possible move the player whose turn it is can make is shown by a link leading from the node to a node for the board position after that choice of a move. Random moves are specified as moves made by a fictitious player, who might be named "Mother Nature". The roll of a pair of dice or the deal of a randomly selected card are examples of random moves. With a random move, the probability of each move is specified along the line connecting one node to another. Since a move by an actual player is freely chosen, the probabilities of any move by an actual player are not specified in the specification of a game.
The above description of the specification of a game cannot yet handle games like poker. In poker, not every player knows every card that is dealt. Von Neumann and Morgenstern introduce the concept of "information sets" to allow one to specify that, for instance, a player only knows all the cards in his hands and, perhaps, some of the cards in the other players' hands. An information set at a node, specifies for the player whose turn it is, which of the previous choices of moves in the game he has knowledge of. That is, an information set is a subset of the set of links in the tree leading from the initial position to the current node position. Since some of these moves were random, this specification allows for the dealing of hands of cards, for example.
The final element in this specification of a game occurs at the leaves of the tree. These are the final positions in the games. Leaves have assigned the values of the payouts to each player in the game.
It is easy to see how to define a player's strategy with this specification of a game. A strategy states the player's choice of a move at each node in the game denoting a position in which it is the player's move. A play of the game consists of each player specifying their strategy and the random selection of a choice from the specified probability distributions at each node at which a random move is chosen. These strategies and the random moves determine the leaf at which the game terminates. And one can then see the payouts to all players for the play.
One can get rid of the randomness, in some sense, by considering an infinite number of plays of the game for each combination of players' strategies. This will result in a probability distribution for payouts. The assumption is that each player is interested in the expected value, that is, the mean payout, to be calculated from this probability distribution. (All these descriptions of calculations have abstracted from time and space computational constraints.)
2.2 Normal FormOne abstracts from the sequence of moves and from random moves in specifying a game in normal form. The extensive form allows for the definition of strategies for each player, and each strategy can be assigned an arbitrary label. A game in normal form consists of a grid or table. A player's strategies are listed along one dimension of the table, and each dimension corresponds to a player. Each entry in the table consists of a ordered tuple, where the elements of the tuple are the expected payouts to the players for the specified combination of strategies.
Table 1 shows a simple example - the children's game, "Rock, Paper, Scissors." The rules specify the winner. Rock crushes scissors, scissors cut paper, and paper covers rock. This is a two-person zero-sum game. The payouts are shown in the table for the player whose strategies are listed for each row to the left. The payouts to the column player are, in this case, the additive inverse of the table entries.
Table 1: Rock, Paper, Scissors | Rock | Scissors | Paper |
| Rock | 0 | +1 | -1 |
| Scissors | -1 | 0 | +1 |
| Paper | +1 | -1 | 0 |
By symmetry, no pure strategy in Rock, Paper, Scissors is better than any other. A mixed strategy is formed for a player by assigning probabilities to each of that player's pure strategies. Probabilities due to states of nature are removed in the analysis of games by taking mathematical expectations. But probabilities reappear from rational strategization. I also found interesting Von Neumann and Morgenstern's analysis of an idealized form of poker. One wants one's bluffs to be called in bluffing on occasion so that players will be willing to add more to the pot when one raises on a good hand.
Each player's best mixed strategy in a two-person zero-sum game can be found by solving a Linear Program (LP). Let
p1,
p2, and
p3 be the probabilities that the row player in Table 1 chooses strategies Rock, Scissors, and Paper, respectively. The value of the game to the row player is
v. The row player's LP is:
Choose p1, p2, p3, v
To Maximize v
Such that
-p2 + p3 ≥ v
p1 - p3 ≥ v
-p1 + p2 ≥ v
p1 + p2 + p3 = 1
p1 ≥ 0, p2 ≥ 0, p3 ≥ 0
The interest of the column player is to minimize the payout to the row player. The left-hand sides of the first three constraints show the expected value to the row player when the column player plays Rock, Scissors, and Paper, respectively. That is, the coefficients by which the probabilities are multiplied in these constraints come from the columns in Table 1. Given knowledge of the solution probabilities, the column player can guarantee the value of the game does not exceed these expected values by choosing the corresponding column strategy. That is, the column player chooses a pure strategy to minimize the expected payout to the row player.
The column player's LP is the dual of the above LP. As a corollary of duality theory in Linear Programming, a minimax solution exists for all two-person zero-sum games. This existence is needed for the definition of the characteristic function form of a game.
2.3 Characteristic Function FormThe characteristic function form of a game is defined in terms of coalitions of players. An
n-person game is reduced to a two-person game, where the "players" consist of a coalition of true players and the remaining players outside the coalition. The characteristic function for a game is the value of the corresponding two-person zero-sum game for each coalition of players. The characteristic function form of the game specifies the characteristic function.
As an illustration, Von Neumann and Morgenstern specify the three-person game in Table 2. In this game, coalitions of exactly two people win a unit.
Table 2: Canonical Three Person Game| Coalition | Value |
| { } | v( { } ) = 0 |
| {1} | v( {1} ) = -1 |
| {2} | v( {2} ) = -1 |
| {3} | v( {3} ) = -1 |
| {1, 2} | v( {1, 2} ) = 1 |
| {1, 3} | v( {1, 3} ) = 1 |
| {2, 3} | v( {2, 3} ) = 1 |
| {1, 2, 3} | v( {1, 2, 3} ) = 0 |
3.0 A Solution ConceptDefinition: An
imputation for an
n-person game is an
n-tuple (
a1,
a2, ...,
an) such that:
- For all players i, the payout to that player in the imputation does not fall below the amount that that player can obtain without the cooperation of any other player. That is, ai ≥ v( {i} ).
- The total in the imputation of the payouts over all players is the payout v( {1, 2, ..., n} ) to the coalition consisting of all players.
Definition: An imputation
a = (
a1,
a2, ...,
an)
dominates another imputation
b = (
b1,
b2, ...,
bn) if and only if there exists a set of players
S such that:
- S is a subset of {1, 2, ..., n}
- S is not empty
- The total in the imputation a of the payouts over all players in S does not exceed the payout v( S ) to the coalition consisting of those players
- For all players i in S, the payouts ai in a strictly exceed the payouts bi in b
Definition: A set of imputations is a
solution (also known as a
Von Neumann and Morgenstern solution or a
stable set solution) to a game with characteristic function
v( ) if and only if:
- No imputation in the solution is dominated by another imputation in the solution
- All imputations outside the solution are dominated by some imputation in the solution
Notice that an imputation in a stable set solution can be dominated by some imputation outside the solution. The following set of three imputations is a solution to the three-person zero-sum game in Table 2:
{(-1, 1/2, 1/2), (1/2, -1, 1/2), (1/2, 1/2, -1)}
This solution is constructed by considering all two-person coalitions. In each imputation in the solution, the payouts to the winning coalition are evenly divided.
The above is not the only solution to this game. An uncountably infinite number of solutions exist. Another solution is the following uncountable set of imputations:
{(a, 1 - a, -1) | -1 ≤ a ≤ 2}
This solution can be understood in at least two ways:
- Player 3 is being discriminated against.
- The above is a solution to the two-person, non-constant game with the characteristic function in Table 3. A fictitious third player has been appended to allow the game to be analyzed as a three-person zero-sum game.
Von Neumann and Morgenstern present both interpretations.
Table 3: A Two-Person Game With Variable Sum| Coalition | Value |
| { } | v( { } ) = 0 |
| {1} | v( {1} ) = -1 |
| {2} | v( {2} ) = -1 |
| {1, 2} | v( {1, 2} ) = 1 |
The above has defined the Von Neumann and Morgenstern solution to a game. Mathematicians have defined at least one other solution concept to a cooperative game, the core, in which no imputation in the solution set is dominated by any other imputation. I'm not sure I consider the Shapley value as a solution concept, although it does have the structure, I guess, of an imputation.
References- W. F. Lucas, "A Game With No Solution", Bulletin of the American Mathematical Society, V. 74, N. 2 (March 1968): 237-239
- John von Neumann and Oskar Morgenstern, Theory of Games and Economic Behavior, Princeton University Press (1944, 1947, 1953)
Posts
