JULIUS SENSAT
GAME THEORY AND RATIONAL DECISION∗
ABSTRACT. In its classical conception, game theory aspires to be a determinate decision theory for games, understood as elements of a structurally specified domain. Its aim is to determine for each game in the domain a complete solution to each player’s decision problem, a solution valid for all real-world instantiations, regardless of context. “Permissiveness” would constrain the theory to designate as admissible for a player any conjecture consistent with the function’s designation of admissible strategies for the other players. Given permissiveness and other appropriate constraints, solution sets must contain only Nash equilibria and at least one pure-strategy equilibrium, and there is no solution to games in which no symmetry invariant set of pure-strategy equilibria forms a Cartesian product. These results imply that the classical program is unrealizable. Moreover, the program is implicitly committed to permissiveness, through its common-knowledge assumptions and its commitment to equilibrium. The resulting incoherence deeply undermines the classical conception in a way that consolidates a long series of contextualist criticisms.
1. INTRODUCTION
In the classical conception of game theory, a game is an element in a structurally defined domain of multi-agent decision situations, and game theory is its decision theory. The theory aims at a complete solution for each game in the domain: for each player, a set of alternative actions each of which would count as a fully rational strategy, given his concern to promote his outcome values. Were this ideal to be achieved, then in any real-world instantiation of the game, regardless of the circumstances not reflected in the game’s structure, a player could rationally choose any of his specified solution strategies. Though game theory is currently thriving in its applications and interdisciplinary forays, this founding conception is problematic. Serious conceptual and intuitive difficulties began accumulating as early as the seminal contributions of von Neumann and Morgenstern (1953 [1944]) and Nash (1951), and there have been forceful systematic critiques (e.g. Schelling (1960), Aumann (1974) and Spohn (1982)). Nonetheless, there are still strong proponents (e.g. Harsanyi and Selten (1988)), and matters remain unresolved. Erkenntnis 47: 379–410, 1998. © 1998 Kluwer Academic Publishers. Printed in the Netherlands.
380
JULIUS SENSAT
Foundational disputes can promote basic and prolific advances, but only if they enter significantly into the self-consciousness of normal theoretical practice. This reflective engagement has been lacking in game theory. The classical sense of the discipline tends to enjoy naive acceptance, along with its more specific current orientations toward states of common knowledge and refinements of Nash equilibrium. Not only is this attitude too narrow for nonfoundational research; it has impeded the foundational critique itself, preventing the identification of a fundamental internal incoherence. The classical conception has been opposed by a contextualist one that views rational action as sometimes depending on extra-game circumstances, such as the history of past interactions, existing customs and practices, or contingently salient features of the particular instantiation of the game.1 Initially, contextualists restricted their critique to the scope of determinacy, not challenging the classical conception on that portion of the domain where it was able to propose determinate solutions. Rather, the focus was on games that gave the classical conception trouble because they seemed to require some contingent agreement or coordination for the players to reach equilibrium. Prominent examples are Battle of the Sexes, Chicken, and what Schelling (1960, pp. 84ff) calls games of pure coordination. Though this early limited focus maintains a presence even today, contextualism has not stood still. Applying Bayesian decision-theoretic ideas in their analysis, some theorists have questioned the justifiability of Nash equilibrium, for example (Aumann (1974), Aumann (1981), Aumann (1987a), Bernheim (1984), Bernheim (1986), Pearce (1984), Spohn (1982)). But refinements of decision theory and the structural characterization of a game remain open as ways to try to meet these objections. For example, theorists such as Harsanyi (1977) have sought to strengthen decision-theoretic strictures on games in order to restrict players’ admissible expectations about each other as well as their admissible actions. Moreover, insofar as games are characterized by common knowledge of rationality, this move also counts as a structural refinement. The basic idea is this: A solution function should designate as admissible for a player precisely those expectations or conjectures that are rationally permissible, given the information provided to him by the defining parameters. Moreover, actions should count as admissible precisely when they are rational relative to some admissible conjecture. If there is a solution function that legitimately narrows admissible conjectures enough so that no matter which one a rational player adopts about the actions of the oth-
GAME THEORY AND RATIONAL DECISION
381
ers, all his admissible actions are rational relative to that conjecture, then determinacy can be achieved. One can assess the prospects of this approach by formulating determinacy itself as a constraint on solution functions and exploring its compatibility with other appropriate constraints. A constraint I call “permissiveness” requires that all conjectures be admissible that are consistent with the function’s specification of admissible actions. Section 3.3 contains proofs that given determinacy, permissiveness and other appropriate conditions: 1. Profiles of admissible strategies must be Nash equilibria. 2. At least one such profile must be a pure-strategy equilibrium. 3. There is no solution to games in which no symmetry-invariant set of pure-strategy Nash equilibria forms a Cartesian product. Propositions 2 and 3 settle the initial dispute: a significant subclass of the aforementioned games do not have classical solutions, for example.2 Moreover the results extend unsolvability to a major part of the original bedrock, namely two-person zero-sum games without a saddle point in pure strategies. But the results have a deeper significance. Often the strongest defense of the assumptions underlying impossibility results rests on arguments that are independent of the program being criticized, thereby leaving some formal space for an effective response. However, there are many sources for permissiveness in the classical conception itself. Notice, for example, that permissiveness secures equilibrium (1), the classical solution concept, but by 2 and 3 it also generates impossibility results. If the classical program cannot plausibly secure equilibrium without permissiveness, then it carries an internal incoherence, rooted not only in the commitment to a refinement of equilibrium but also in the assumptions of common knowledge of the strategic structure and the game-theoretic rationality of the players. But these elements are fundamental to the classical program: its solution concept and a basic part of the structural definition of its domain. It might be able to remedy structural insensitivities to factors relevant to rational decision through suitable refinements, which have indeed been made since the adoption of equilibrium as the target solution concept and have recently been explored ways of accommodating contextual factors.3 But if indeterminacy is rooted in an internal incoherence, then this strategy won’t work. A major reconceptualization is required, and the viability of the classical approach is much more doubtful. Section 2 sketches relevant historical background. Section 3 presents the basic results both informally and formally. Readers not interested in
382
JULIUS SENSAT
the formal treatment need read only Section 3.1. However, some of the notation of Section 3.2 is needed for parts of Section 4, which argues that the classical program implicitly requires permissiveness. Section 5 discusses related research and draws a final conclusion. 2. HISTORICAL BACKGROUND
In 1928 von Neumann launched modern game theory by posing the following question:
G
n players, S1 , S2 , . . . , Sn , play a given game of strategy . How must one of these players, Sn , play, in order thereby to achieve a result as favorable as possible [um dabei ein möglichst günstiges Resultat zu erzielen]?
The specified task of the theory clearly conforms to our characterization: the aim is to provide a decision function on a structurally defined domain. Von Neumann goes on to remark that both the structure of the decision problem and the form of the desired solution need clarification: 1. “What, exactly, is a game of strategy?” 2. Because “the fate of each player depends not only on his own actions but also on those of the others,” the expression “Sm seeks to achieve a result as favorable as possible” is “a very obscure one.” 4 Strangely, although he immediately tackles the first problem by constructing a formal definition, he nowhere explicitly addresses the second problem. Presumably, we are supposed to glean a clarification from the solution concept that he develops. For the two-person, zero-sum case, he proposes the one he and Morgenstern later defend: a player should maximize his security level by choosing a strategy with a best worst outcome. But how is a player acting to achieve a result “as favorable as possible” by choosing such a strategy? Perhaps there are two reasons why von Neumann and Morgenstern believe they have the right interpretation: First, although the theory gives advice to each player, it advises them singly, not as a group. So the maximum to be achieved, this “most favorable result,” has to be a level that each player can guarantee through his own action alone. Second, the rules of rational behavior have to cover “all conceivable situations” that might arise, including the possibility that the opponent fails to follow these rules himself. Hence for a solution concept to count as specifying the requirements of rational action, it cannot work to the disadvantage of a conforming player faced with a nonconforming opponent:
GAME THEORY AND RATIONAL DECISION
383
[T]he rules of rational behavior must provide definitely for the possibility of irrational conduct on the part of others. . . . Imagine that we have discovered a set of rules for all participants – to be termed as “optimal” or “rational” – each of which is indeed optimal provided that the other participants conform. Then the question remains as to what will happen if some of the participants do not conform. If that should turn out to be advantageous to them – and, quite particularly, disadvantageous to the conformists – then the above “solution” would seem very questionable.
The maximin solution satisfies the first condition: a player can achieve his maximum security level no matter what the other player does. And the authors claim that it also satisfies the second: a conforming player is never disadvantaged by his opponent’s nonconformance, which cannot drop him below his maximum security level and may in fact yield him more (von Neumann and Morgenstern (1953 [1944], pp. 32–33)). Nonetheless, that higher payoff may itself be much lower than the one associated with a best response to the other player’s chosen strategy. In such a case, is it clear that he has not been disadvantaged? Suppose that he strongly expects the other player to choose a particular noncompliant strategy. Is it clear then that in sticking to maximin he does what is rational for someone who seeks to “achieve a most favorable result”? Perhaps choosing a best response to what the other player chooses is the right interpretation of acting “in order to achieve thereby a result as favorable as possible.” 5 Of course, this interpretation is not without its own problems. To vindicate it one has to develop it into an adequate solution concept. One has to explore under what conditions it is even feasible for each player to choose a best response to the strategies chosen by the other players and how players could rationally form expectations that would warrant such choices, given their concern to advance their outcome values. These are questions about the existence and rationality of equilibrium. As it happened, game theory pursued a path of development set by these questions, perhaps because of the very limited determinacy achievable on the von Neumann– Morgenstern interpretation. Consequently, major changes occurred in the structural characterization of games and in the conception of an adequate solution. Nash (1951) worked out a generalized concept of equilibrium for finite n-person games. It differs from the stable set, von Neumann and Morgenstern’s own (indeterminate) n-person generalization. Nash regards their solution as belonging to cooperative theory, which he characterizes as “based on an analysis of the interrelationships of the various coalitions which can be formed by the players of the game.” In contrast, he assumes that “each participant acts independently, without any collaboration or communication with any of the others” (p. 286). His paper thus laid the foundation for noncooperative theory as the heir to von Neumann’s origi-
384
JULIUS SENSAT
nal question: how must an individual player act in order to “achieve a result that is most favorable”? Nash made it possible to focus on equilibrium as the key to an answer. A second crucial development was the adoption and refinement of assumptions about the knowledge or beliefs of the players – assumptions that could, it was hoped, ground the rationality of a player’s expectation that the other players will choose their components of an equilibrium solution. Eventually, common knowledge of the strategic structure and of the rationality of the players (including game-theoretic principles of rationality) came to be seen as part of the game situation itself. Though this development took a while,6 it is somewhat surprising that the stark differences from the original conception did not receive much discussion.7 After Nash’s contribution, efforts focused on justifying equilibrium on the basis of information and expectations of the players and on searching for appropriate refinements. It is at this point that contextualism began to develop. As I stated in Section 1, initially the critique was fairly narrowly focused, and not diametrically opposed to the classical program. Nonetheless, no matter how mild in its content, contextualism accepts the possibility that a game is unsolvable given just the game-theoretic parameters but is nonetheless solvable on the basis of extrinsic factors. For the classical program, on the other hand, a game not solvable on the basis of game-theoretic parameters simply has no rational solution. This methodological difference could produce deep substantive differences concerning both the correctness of particular solutions and solvability altogether. For example, a contextualist might claim that game-theoretic rationality is nothing more than Bayesian rationality applied to games, understood as situations characterized by common knowledge of the strategic structure and common knowledge of (Bayesian) rationality. On this view a game presents each player with a Bayesian decision problem. Each of these problems is to be solved on the basis of the same postulates of rational decision that apply in single-agent contexts: the player is to choose an action that maximizes expected utility relative to a probability assignment to underlying states of nature. What distinguishes the game situation is not the relevance of new principles of rationality but rather the situation’s strategic structure and each player’s information that the structure and the decision-theoretic (Bayesian) rationality of the players are common knowledge. These factors, rather than the coming into play of new standards of rationality, are what make the game a special type of decision situation. The solution concept corresponding to this conception is (correlated) rationalizability.8 A player’s strategy is rationalizable if it maximizes his
GAME THEORY AND RATIONAL DECISION
385
expected utility relative to a probability assignment consistent with his information that it is common knowledge that all players are choosing expected-utility maximizing strategies relative to assignments consistent with their information. In finite games of complete information in strategic form, the rationalizable strategies are the ones that survive the iterated deletion of strictly dominated strategies. Even two-person zero-sum games with a unique, strict equilibrium in pure strategies will typically have rationalizable strategies that don’t form part of the maximin, equilibrium solution. Few have explicitly taken contextualism this far.9 Yet even this strong version does not foreclose the debate, because it leaves open the possibility that the classical approach might come up with an appropriate refinement that would vindicate determinacy and equilibrium. The following arguments attempt to close this gap.
3. BASIC RESULTS
The basic results proved below appeal to the following adequacy constraints on solution functions: determinacy, Bayesian rationality, support inclusion, invariance under isomorphism and permissiveness (or, alternatively, weak permissiveness). Before giving formal definitions and proofs, I shall discuss these constraints informally, along with a few others needed in later sections. 3.1. Informal Discussion A solution function (Definition 2 in Section 3.2) associates with each game in its domain a solution set (Definition 1) of profiles of expectations and strategies – those the function designates as admissible for the game. A strategy is specified as admissible relative to an expectation designated as admissible. Determinacy (Definition 3) requires that admissible strategies be admissible relative to each admissible expectation. Only if players can rationally choose any admissible action, no matter which admissible expectation they adopt, does rational action depend only on their “intrinsic” information – information provided by the defining parameters of the game – and not on any other, “extrinsic” information they might have. Given determinacy, a player might be able to appeal to extrinsic information to exclude an admissible expectation as irrational, but doing so will not eliminate any admissible actions, since any action admissible relative to that expectation is admissible relative to the remaining ones. Action rational relative to intrinsic information is thus rational relative to total information, and game theory and intrinsic information suffice to solve each player’s
386
JULIUS SENSAT
decision problem. On the other hand, without determinacy there will be cases in which there is an admissible expectation and an action that is admissible, but not relative to that expectation. Without ruling out that expectation (which the solution function does not do), the player cannot legitimately consider the action as rational in his circumstances. So game theory fails to provide him with a definite solution. Strong determinacy (Definition 3) adds to determinacy the requirement that admissible strategies form a payoff-equivalent set of profiles. Very strong determinacy (Definition 3) requires a unique profile. The basic results rest only on determinacy, but the stronger versions are relevant to possible rationales for equilibrium (Section 4.2.1). Bayesian rationality (Definition 4) requires that actions admissible relative to an expectation be best responses – i.e. expected-utility maximizing responses – to that expectation.10 Expectation consistency (Definition 5) requires admissible expectations to be “solution-consistent”, that is, consistent with admissible strategies.11 Strategies are formalized below as probability distributions over pure strategies. Expectations held by a player concerning a second player’s choice are likewise formalized as probability distributions over the second player’s pure strategies. Expectation consistency requires the first player’s admissible expectations to lie in the convex hull of the second player’s admissible strategies. For a rationale, note that if the second player chooses an admissible strategy, he will not play any pure strategy with a probability lying outside this convex hull. So given common knowledge of the solution set and of the rationality of the players, a player would contradict his intrinsic information were he to assign to another’s pure strategies probabilities that lie outside of the boundaries set by the convex hull of that player’s admissible strategies. While expectation consistency requires that only solution-consistent expectations be admissible, permissiveness (Definition 6) requires that they all be. If a player’s expectations are consistent with the other players’ admissible strategies, then they should count as admissible. There is a weaker version of permissiveness perhaps more likely to satisfy a proponent of determinacy. The issue concerns n-person games with n > 2, in which a player’s overall expectation about the actions of the other players might represent those actions as correlated rather than stochastically independent.12 Permissiveness as defined requires expectations representing correlation to be admissible, so long as they are solutionconsistent. The less stringent version, weak permissiveness (Definition 6), requires only consistent expectations expressing independence to be
GAME THEORY AND RATIONAL DECISION
387
admissible. All three of the basic results go through as stated, modulo the substitution of weak permissiveness for permissiveness.13 The support of a probability distribution over a finite set is the subset of set elements assigned positive probability by the distribution. Support inclusion (Definition 7) requires that all strategies in the support of an admissible strategy be admissible. The rationale is that if a mixture of pure strategies is rational relative to an admissible expectation then any of the pure strategies of which it is the mixture is rational relative to that expectation. Spohn (1982, p. 249) points out that if rationality orders a set of alternatives, then whether or not it makes two alternatives comparable, a mixture of them cannot be better than both. Moreover, as Chernoff (1954, pp. 437–438) notes, it is just hard to see how the act of performing a randomization can give a strategy any rationality that the strategy does not have on its own. A player chooses a strategy against a background of expectations about the other players’ choices. Randomization itself does not change those expectations. After the randomization, what then can have changed whose effect is to accord a given pure strategy with a measure of rationality that it did not have before the randomization? The upshot is that although actual randomization may not be irrational relative to given expectations, it is never rationally required relative to those expectations. Invariance under isomorphism (Definition 8) aims at insuring that the value of the solution function does not depend on extraneous or incidental features of a game’s representation. For example, if we replace a utility function with one related to it by a positive affine transformation, we don’t really change the game, since the utility functions only carry cardinal significance and interpersonal comparisons are irrelevant to an agent concerned only to identify the rational implications of his own outcome evaluations. Consequently, the value of the solution function should not change across such transformations. Similarly, listing the players’ strategy sets and their utility functions in a different order or simply relabeling them shouldn’t change the solution. This requirement really just enforces the structural definition of the domain. Without it, the intended type of determinacy would not be insured. A symmetry of a game is an isomorphism from that game to itself. A set of strategy profiles is symmetry invariant (Definition 9) if every symmetry of the game maps that set onto itself. The basic results are the following: Proposition 1: If a solution function satisfies determinacy, Bayesian rationality and permissiveness over a class of games, then for each game in this class, all profiles of admissible strategies are Nash equilibria.
388
JULIUS SENSAT
Proposition 2: If in addition the solution function satisfies support inclusion, then each game’s set of profiles of admissible strategies includes a pure-strategy equilibrium. Proposition 3: For any game, if no symmetry invariant set of pure-strategy equilibria forms a Cartesian product, then there is no solution function satisfying determinacy, Bayesian rationality, support inclusion, permissiveness and invariance under isomorphism over any class containing that game. 3.2. Formal Definitions For any finite set Y , 1(Y ) is the set of probability distributions on Y . We regard 1(Y ) as a simplex whose vertices are the elements P of Y and therefore identify q ∈ 1(Y ) with the linear combination y∈Y q (y) y. = the support For X ⊆ 1(Y ), its convex hull is X. For q ∈Q1(Y ), supp(q) Q n of q = {y ∈ Y : q(y) > 0}. Where Y = i=1 Yi , Y−i = j 6=i Yj , with Q typical member y−i . Also, if X ⊆ ni=1 Yi , Xi and X−i are the projections of X into Yi and Y−i , respectively. If x and y are n-tuples, then x/yi is the n-tuple that results when x is modified by replacing xi , its ith component, with yi , the ith component of y. Throughout we restrict attention to finite games of complete information in strategic form. Such Qn a game G is a triple (n, S, ), where n is the number of players, S = i=1 Si is the space of pure-strategy n-tuples, and is the n-tuple (1 , . . ., n ) of the players’ preference relations over lotteries on S. 1(Si ) is player i’s set of available mixed strategies. Regarding 1(Si ) as a simplex, we identify the pure strategy si ∈ Si with the element qi ∈ 1(Si ) such that qi (si ) = 1. The i are assumed to satisfy the axioms of von Neumann–Morgenstern utility, so that they are representable by utility functions ui such that ui (q) is the expected value of ui (s) with respect to 5i qi, the product distribution derived from the qi . Accordingly, G may also be represented as (n, S, U ) , where U = (u1 , . . ., un ). The “complete information” assumption is that not only the components of (n, S, U ) but the rationality of the players – whatever that turns out to mean – are common knowledge. The content of this knowledge constitutes the players’ intrinsic information. Where q = (q1 , . . ., qn ) , qi ∈ 1 (Si ) and pi ∈ 1(S−i ): Br(qi , pi ) iff qi is a best response to pi , i.e. qi maximizes the expected value of ui (q) with respect to pi . In this notation, q is a Nash equilibrium iff for each i, Br qi , 5j 6=i qj . For pi ∈ 1(S−i ), pij is the marginal distribution on Sj determined by pi .
GAME THEORY AND RATIONAL DECISION
389
DEFINITION 1. AQsolution set for Q game G = (n, S, U )is a nonempty subset X of ni=1 1 (Si ) × ni=1 1(S−i ) satisfying the following interchangeability condition:14 (q, p), (q 0 , p 0 ) ∈ X → ∀i (q/q 0 i , p/pi0 ) ∈ X . DEFINITION 2. A solution function L with domain D is a mapping that associates with every game G ∈ D a solution set L(G). The intended interpretation of “(q, p) ∈ L(G)” is that according to L, for each player i, expectations represented by pi are admissible and qi is admissible relative to pi , in the game G. Henceforth, unless otherwise noted, L is a solution Q function, C is a subset of the domain of L, G = (n, S, U ) and p ∈ i 1 (S−i ) . DEFINITION 3. L satisfies determinacy on C if for all G ∈ C, (1)
L(G) = L(G)1 × L(G)2
L satisfies strong determinacy on C if for all G ∈ C, in addition to 1 L satisfies ∀q∀q 0 q, q 0 ∈ L(G)1 → ∀i ui (q) = ui q 0
L satisfies very strong determinacy on C if for all G ∈ C, L (G)1 is a singleton. DEFINITION 4. L satisfies Bayesian rationality on C if for all G ∈ C, (q, p) ∈ L(G) → ∀i Br (qi , pi ) . DEFINITION 5. L satisfies expectation consistency on C if for all G ∈ C and for all p: p ∈ L (G)2 → ∀i ∀j 6 = i pij ∈ L (G)1 j . DEFINITION 6. L satisfies permissiveness on C if for all G ∈ C and for all p: (2)
∀i ∀j 6 = i pij ∈ L (G)1 j → p ∈ L (G)2 .
390
JULIUS SENSAT
If for all G ∈ C, L satisfies 2 for all p such that pi = 5j 6=i pij , then L satisfies weak permissiveness on C. DEFINITION 7. L satisfies support inclusion on C if for all G ∈ C, (q, p) ∈ L (G) & si ∈ supp (qi ) → (q/si , p) ∈ L (G) DEFINITION 8. Where G = (n, S, U ) and G0 = n, S 0 , U 0 , a bijection Q Q f : i 1 (Si ) → i 1 Si0 is an isomorphism from G to G0 if (1) there exists a permutation σ of {1, . . ., n} and bijections gi : 1 (Si ) → 1 Sσ0 (i) , comprising the basis of f , such that for each i, gi maps Si onto Sσ0 (i) , gi (qi ) Q Q P = x∈Si qi (x) gi (x) and for all q ∈ i 1 (Si ) and r ∈ i 1 Si0 , f (q) = r ↔ gi (qi ) = rσ (i) for all i, and (2) for all i, i and 0σ (i) , the underlying preference relations represented by ui and u0σ (i) , are isomorphic. The games G and G0 are isomorphic if at least one isomorphism from G to G0 exists. L is invariant under isomorphism on C if for all G, G0 ∈ C and for every isomorphism f from G to G0 , f maps the set of L-admissiblestrategies in G onto the corresponding set in G0 , i.e. f (L (G)1 ) = L G0 1 . DEFINITION Q9. A symmetry of G is an isomorphism from G to itself. A subset X of i 1 (Si ) is symmetry invariant if for every symmetry f of G, f (X) = X. A solution function L is symmetry invariant on C if for all G ∈ C, the set of profiles of L-admissible strategies in G is symmetry invariant, i.e. for every symmetry f of G, f (L (G)1 ) = L (G)1 . 3.3. Proofs PROPOSITION 1. Suppose L satisfies determinacy, Bayesian rationality and permissiveness (weak permissiveness)15 on C. Then for every G in C, q ∈ L (G)1 only if q is an equilibrium point. Proof. Suppose q ∈ L (G)1 . For each i, let pi = 5j 6=i qj and let p = (p1 , . . ., pn ). Since for each i, pi ∈ 1 (S−i ) and pij = qj for each j 6 = i, by permissiveness (weak permissiveness) p ∈ L (G)2 . Then by determinacy, (q, p) ∈ L (G), and by Bayesian rationality, Br(qi , pi ) for each i. Since for each i, pi = 5j 6=i qj , q is an equilibrium point. PROPOSITION 2. Suppose L satisfies determinacy, Bayesian rationality, permissiveness (weak permissiveness) and support inclusion on C. Then for all G in C, L (G)1 contains a pure-strategy equilibrium.
GAME THEORY AND RATIONAL DECISION
391
Proof. Let (q, p) ∈ L (G). For each i, let si be a pure strategy in supp (qi ) and let s = (s1 , . . . , sn ). By support inclusion, s ∈ L (G)1 , and by Proposition 1, s is an equilibrium point. The following two lemmas are straightforward consequences of our definitions: LEMMA 1. L is symmetry invariant on any class on which it is invariant under isomorphism. Q LEMMA 2. Let X be a subset of i 1 (Si ) and Y be the set of purestrategy profiles in X. Then X is symmetry invariant if and only if Y is. PROPOSITION 3. Let G have the following property: no symmetry invariant set of pure-strategy Nash equilibria forms a Cartesian product. Let D be any set of games containing G. Then there is no solution function satisfying determinacy, Bayesian rationality, support inclusion, permissiveness (weak permissiveness) and invariance under isomorphism on D. Proof. Suppose L satisfies the listed conditions on D. By Proposition 2, L (G)1 must include a nonempty subset of pure-strategy equilibria. Consider the maximal such subset. Invariance under isomorphism requires it to be symmetry invariant, and therefore, by assumption, not to form a Cartesian product. But then L (G) violates the interchangeability condition on solution sets, contrary to assumption.
4. PERMISSIVENESS
The two basic theoretical moves of the classical program after von Neumann and Morgenstern – the turn to Nash equilibrium and the common knowledge assumptions – themselves support a commitment to permissiveness. Thus there are internal sources for the program’s undoing. 4.1. Common Knowledge Game theory has “done its work” for a player when it has identified his admissible strategies; they are what survive the constraints of his intrinsic information on the strategies he can rationally choose. There are no game-theoretic requirements concerning how he is to select among these surviving strategies, and this fact is common knowledge. Accordingly, the theory cannot ground a more stringent restriction on others’ expectations than consistency with the information that the player will play a pure strategy as the outcome of one of his admissible mixed strategies. Expectations
392
JULIUS SENSAT
consistent with this information must be admissible; solution functions must satisfy permissiveness. Permissiveness prohibits “brute demands” on players’ expectations – “brute” in the sense of not founded on available intrinsic information. Such demands impose an arbitrary asymmetry between admissible strategies and admissible expectations: given common knowledge that the theory provides no constraint on how one is to select a strategy from his admissible set, how can it legitimately constrain others’ expectations concerning this selection? This argument can be strengthened by assuming determinacy as well as common knowledge. Then the set of admissible strategies should be convex. For under determinacy, if qi and ri are both admissible for player i, then they are equally and fully rational responses to any of i’s admissible expectations. Hence any randomization αqi + (1 − α) ri must also be a fully rational response to any admissible expectation. Hence it ought to count as admissible in the game. To deny permissiveness is then to claim that game theory can legitimately declare it intrinsically irrational to expect a player to play a strategy that the theory itself certifies as rational regardless of his own expectations and extra-game circumstances.
4.2. Nash Equilibrium Can the classical program provide a rationale for equilibrium without relying on or committing itself to permissiveness? To treat this question adequately, we must consider both the original interpretation of equilibrium as an equilibrium of strategies and the newer “equilibrium of beliefs” interpretation. 4.2.1. Equilibrium of Strategies A frequently made claim is that game theory must recommend an equilibrium because any other recommendation would be self-defeating by providing some players with a reason for departing from it (Luce and Raiffa (1957, p. 63), Harsanyi and Selten (1988, p. 3), Harsanyi (1992, p. 356)). Though this argument-sketch has an intuitive appeal, it is not clear how to fill it out in order to substantiate it. What enables the solution function to generate the expectations that would give a player a reason not to follow its recommendation? Simply the constraints of expectation consistency and Bayesian rationality for example, or is something else required? Does the argument require very strong determinacy, or will some weaker version suffice? This section arrives at some answers, and it explores their implications for the permissiveness requirement.
GAME THEORY AND RATIONAL DECISION
393
Equilibrium does not follow from determinacy, Bayesian rationality and expectation consistency, even for two-person, zero-sum games in which only pure strategies are available. Here’s a counterexample:
(3)
s1 t1 u1
s2 5 4 1
t2 4 4 1
u2 6 5 8
Designate s1 and t1 as admissible strategies for player 1 and s2 and t2 as admissible for player 2, but restrict admissible expectations to t2 for player 1 and t1 for player 2. For each player, his admissible strategies are all best responses to his single admissible expectation, so both determinacy and Bayesian rationality are satisfied.16 Expectation consistency is satisfied because admissible expectations do not assign positive probability to the inadmissible strategies u1 and u2 . Yet although the solution set contains the two pure-strategy equilibria that constitute the classical maximin solution ((s1 , t2 ) and (t1 , t2 )), it also contains the nonequilibria (s1 , s2 ) and (t1 , s2 ). With strong determinacy instead of determinacy we can get the desired result for 2-person but not for n-person games. Here is a 3-person counterexample:
(4)
s1 t1
t2 1,0,1 1,0,1
s2 1,1,1 1,1,1
s1 t1
s2 1,1,1 1,1,1
s3
t2 0,2,0 0,2,0 t3
The admissible-strategy profiles are the components of the left-hand column of each matrix: (s1 , s2 , s3 ), (t1 , s2 , s3 ), (s1 , s2 , t3 ) and (t1 , s2 , t3 ). Admissible expectations: player 1 expects (s2 , s3 ) with certainty; player 2 expects s1, s3 ; player 3, (s1 , s2 ). Strong determinacy, Bayesian rationality and expectation consistency are satisfied, but (s1 , s2 , t3 ) and (t1 , s2 , t3 ) are not equilibria.17 Even very strong determinacy will not work for the general case. For example:
(5)
s1 t1
t2 0,0,0 1,1,1
s2 1,1,1 0,0,0 s3
s1 t1
s2 1,1,0 0,0,2
t2 0,0,2 1,1,0 t3
394
JULIUS SENSAT
Let the only profile of admissible strategies be (.5s1 + .5t1 , .5s2 + .5t2 , s3 ). Let admissible expectations be as follows: Player 1: Player 2: Player 3:
p1 (s2 , s3 ) = p1 (t2 , s3 ) = .5 p2 (s1 , s3 ) = p2 (t1 , s3 ) = .5 p3 (s1 , s2 ) = p3 (t1 , t2 ) = .5
The marginals of each of these distributions on the strategies of the other players are equal to the respective components of the admissible strategy profile, so expectation consistency is satisfied. Uniqueness of admissible strategies implies very strong determinacy. And each admissible strategy is a best response to the corresponding expectation, so Bayesian rationality is satisfied. However, the admissible-strategy profile is not an equilibrium. The counterexample rests on the correlation that player 3’s overall conjecture expresses between the strategy choices of player 1 and player 2. Limiting admissible expectations to those expressing stochastic independence would rule the solution function out. DEFINITION 10. L satisfies stochastic independence on C if for all G ∈ C, if p ∈ L (G)2 , then pi = 5j 6=i pij for each i. PROPOSITION 4. Suppose L satisfies very strong determinacy, Bayesian rationality, expectation consistency and stochastic independence on C. Then for every G in C, q ∈ L (G)1 only if q is an equilibrium point. Proof. By very strong determinacy, L (G)1 is a singleton. Let q be its unique element, and let p ∈ L (G)2 . Then (q, p) ∈ L (G), and by Bayesian rationality, Br(qi , pi ) for each i. By expectation consistency, for each i and for each j 6 = i, pij is in the convex hull of L (G)1 j . But that set contains only qj . So pij = qj for each i and for each j 6 = i. By stochastic independence, then, pi = 5j 6=i pij = 5j 6=i qj for each i. So for each i, Br qi , 5j 6=i qj , i.e. q is an equilibrium point of G. It may seem that we have finally been able to derive Nash equilibrium without committing the theory to permissiveness. But closer inspection leads to a different conclusion. In the case of n-person games satisfying very strong determinacy and stochastic independence, expectation consistency is satisfied if and only if weak permissiveness is, since there is exactly one profile of stochastically independent solution-consistent expectations. So weak permissiveness is implied by the hypothesis of Proposition 4. And as we have seen, the basic results can all be established on the basis of weak permissiveness. A formal inconsistency therefore threatens any theory that endorses very strong determinacy.18
GAME THEORY AND RATIONAL DECISION
395
Since very strong determinacy leads to this problem, it is worth noting that it is a necessary assumption in Proposition 4. To show it cannot be weakened to strong determinacy, use the game specified in counterexample 4. Leave the admissible strategies as specified, but to remove any doubt about independence let admissible expectations be product distributions based on the following marginals: Player 1: Player 2: Player 3:
p12 (s2 ) = 1.0 p13 (s3 ) = 1.0 p21 (s1 ) = 0.5 p23 (s3 ) = 1.0 p31 (s1 ) = 0.5 p32 (s2 ) = 1.0
Aumann (1987b, p. 479) reports that Nash equilibrium can be axiomatized on the basis of an intergame consistency constraint and the requirement that “in one-person maximization problems, the maximum be chosen.” He does not provide a formalization or proof. I shall first provide these for our framework and then discuss their significance. DEFINITION 11. Q Let G = (n, S, U ), I = {I1 , . . . , Ik } ⊂ {1, . . . , n} (k ≥ 1) and q ∈ i 1 (Si ). The subgame of G determined by I and q is the game G (I, q) = |I | , SI , UI | QIk 1 S ×{q c } I i=I1 ( i ) where SI =
k Y
SIj
j =1
I c = {1, . . . , n} − I = {Ik+1 , . . ., In } qI c = qIk+1 , . . ., qIn UI = uI1 , . . ., uIk UI |QIk
i=I1
1(Si ) ×{qI c }
=
uI1 |QIk
i=I1 1(Si ) × qI c
{ }
!
, . . ., uIk | Q 1 S × q ( Ii ( Ii )) { I c }
DEFINITION 12. Suppose L is defined on G. L is reduction consistent on G if for every subgame G (I, q) such that q ∈ L (G)1 : L (G (I, q)) is defined
396
JULIUS SENSAT
and (q, p) ∈ L (G) → (qI , pI |qI c ) ∈ L (G (I, q)) where qI = qI1 , . . . , qIk , pI |qI c = pI1 (·|qI c ) , . . . , pIk (·|qI c ) and pIi (·|qI c ) is the conditionalization of pIi with respect to the event that the players in I c play their component strategies in q. L is reduction consistent on C if it is reduction consistent on every game in C. DEFINITION 13. Let L be defined on G. If for every q ∈ L (G)1 and every subgame G (I, q) such that I is a singleton ({I1 }), L (G (I, q)) is defined and (qI , pI (·|qI c )) ∈ L (G (I, q)) → Br qI1 , 5j 6=I1 qj , then L satisfies the maximum condition on G. PROPOSITION 5. If L is reduction consistent and satisfies the maximum condition on G, then (q, p) ∈ L (G) → q is a Nash equilibrium of G Proof. Suppose (q, p) ∈ L (G). By reduction consistency, for each singleton I ⊂ {1, . . ., n}: (qI , pI |qI c ) ∈ L (G (I, q)) By the maximum condition we then have Br qI1 , 5j 6=I1 qj for each singleton I ⊂ {1, . . ., n}, i.e. for I1 = 1, . . ., n. Thus q is a Nash equilibrium of G. So Nash equilibrium can be axiomatized by reduction consistency and the maximum condition. To assess reduction consistency as a constraint, consider first a violation of it. Let G be the game:
s1 t1
t2 1,0,2 1,0,2
s2 1,1,1 1,1,1 s3
s1 t1
s2 1,1,1 1,1,1
t2 0,2,0 2,2,0 t3
GAME THEORY AND RATIONAL DECISION
397
Consider the subgame G ({1, 2} , t3 ):
s1 t1
s2 1,1 1,1
t2 0,2 2,2
Let L (G) be as follows: Player 1 2 3
Admissible Strategies s1, t1 s2 s3, t3
Admissible Expectations p1 (s2 , s3 ) = 1 p2 (s1 , s3 ) = 1 p3 (s1 , s2 ) = 1
Now consider the following value for L (G ({1, 2} , t3 )): Player 1 2
Admissible Strategies t1 t2
Admissible Expectations p1 (t2 ) = 1 p2 (t1 ) = 1
The following table summarizes the status of L on {G, G ({1, 2} , t3 )} with respect to the conditions we have examined so far: Condition determinacy Bayesian rationality expectation consistency independence permissiveness Nash equilibrium reduction consistency
Satisfied? strong yes yes yes no no no
Permissiveness and Nash equilibrium fail to be satisfied (both are violated by L (G)), but except for reduction consistency, all of the conditions proposed so far to secure Nash equilibrium without permissiveness are satisfied. Reduction consistency would secure equilibrium, but L vio/ lates reduction consistency because (s1 , s2 , t3 ) ∈ L (G)1 while (s1 , s2 ) ∈ L (G ({1, 2} , t3 ))1 . What is wrong with such a violation? One might claim that the problem lies with the admissibility of t3 in G. If t3 were not admissible then
398
JULIUS SENSAT
L (G ({1, 2} , t3 )) would be irrelevant to the question of L’s reduction consistency. But why should t3 not be admissible? One cannot say: because (s1 , s2 , t3 ) and (t1 , s2 , t3 ) are not equilibria. That would beg the question, because what is at issue is whether reduction consistency is a reason for equilibrium. Perhaps the thought is that t3 should not be admissible because it is not an optimal choice for player 3. With t3 player 3 risks getting 0 instead of 2 if player 2 plays t2 , for no possible gain. However, t2 is not admissible for player 2; for player 3 to be allowed to assign any positive probability to t2 would be to violate expectation consistency. Contrary to the central idea of this objection, t3 is in fact optimal for player 3, relative to his admissible expectations. One might reply that t2 ought to be admissible for player 2, because he ought to be allowed to expect t3 with some positive probability, since t3 is admissible for 3. However, this reply invokes permissiveness and would once again beg the question, since we are looking for ways of securing Nash equilibrium without assuming permissiveness. Without a noncircular criticism of L (G), the only way to defend reduction consistency is to criticize L (G ({1, 2} , t3 ))1 . One can try to support the inclusion of (s1 , s2 ), either with or without (t1 , t2 ). But the first violates determinacy, while the second is implausible. Aumann (1987b, p. 478) says that reduction consistency makes it possible to confine one’s attention to small worlds. If consistency is required, he says, it doesn’t matter much how the player set is chosen. One can just as well work with a smaller as a larger player set. However, this claim does not appear to be correct. Suppose we bring L into consistency by making L (G)1 = {(s1 , s2 , s3 ) , (t1 , s2 , s3 )} and L (G (1, 2) , s3 )1 = {(s1 , s2 ) , (t1 , s2 )}. Suppose 1 and 2 find themselves in a situation that is either G ({1, 2} , s3 )or G ({1, 2} , t3 ) depending on whether 3, for whatever reason, is going to choose s3 or t3 and suppose they face some uncertainty about this. Then they face the problem of small worlds. To resolve it they have to determine whether to put 3 into the player set or on what nonrational contingency his choice depends. 4.2.2. Equilibrium of Beliefs The “equilibrium of beliefs” interpretation of Nash equilibrium is supposed to remedy several difficulties with the original conception, for instance that a mixed-strategy component of an equilibrium requires intentional randomization even though every pure strategy in the support of the mixed strategy is a best response to the other players’ equilibrium strategies (Aumann (1987b, pp. 477–478)). The beliefs interpretation treats a player’s component of the equilibrium not as a strategy but rather as
GAME THEORY AND RATIONAL DECISION
399
the common, stochastically independent conjecture of the other players about his choice of strategy. So whereas we have been concerned with the justifiability of (6)
q comprises admissible strategies → q is a Nash equilibrium
now we are concerned with (7)
p comprises admissible expectations → p comprises Nash expectations
where Nash expectations are defined as follows: Qn DEFINITION 14. Let G = (n, S, U ). An element p ∈ i=1 1(S−i ) comprises Nash expectations if for each i, pi = 5j 6=i pij and there is a Nash equilibrium q of G such that for each i and for each j 6 = i, pij = qj . Even if successful, this move carries significant cost. Consider again example 3. The solution function satisfies 7 but not 6. It violates permissiveness; simply strengthening consistency to permissiveness would secure 6 as well as 7. Since the game is two-person zero-sum, refusing to do so and instead weakening the concept of equilibrium breaks continuity with the von Neumann–Morgenstern theory. Not that this example displays a general rationale for Nash expectations: it doesn’t, since determinacy, Bayesian rationality and consistency are insufficient for games with more than two players. An earlier counterexample (5) works here as well. To guarantee Nash expectations we have to insure that the conjectures pij on the actions of individual players are concordant and represented by the overall conjectures pi as stochastically independent. The simplest method is to turn these requirements into adequacy conditions for solution functions. We can then discuss what might justify them. See Definition 10 for the independence constraint. For concordance: DEFINITION 15. L satisfies concordance of expectations on C if for all G ∈ C, if p ∈ L (G)2 , then for each i and for each j, k 6 = i, pj i = pki . If we add these two conditions to determinacy, Bayesian rationality and expectation consistency, then we can derive Nash expectations. PROPOSITION 6. Suppose L satisfies determinacy, Bayesian rationality, expectation consistency, stochastic independence and concordance of expectations on C. Then for every game G in C, p ∈ L(G)2 only if p comprises Nash expectations.
400
JULIUS SENSAT
Proof. Suppose p ∈ L(G)2 . By concordance, for each i there is a qi ∈ 1(Si ) such that for each j 6 = i, pj i = qi. Let q = (q1 , . . . , qn ). By expectation consistency, qi is in the convex hull of i’s admissible strategies, for each i. Then for each player i, there are admissible strategies ri and ri0 , not necessarily distinct, such that for some α ∈ [0, 1], qi = αri + (1 − α) ri0 . By determinacy and Bayesian rationality, ri and ri0 must each be best responses to pi . Hence qi is a best response to pi as well. But by independence, for each i, pi = 5j 6=i pij = 5j 6=i qj . Hence for each i qi is a best response to 5j 6=i qj , and q is a Nash equilibrium. Hence p comprises Nash expectations. However, there are situations in which independence and concordance are implausible. Consider the following game, for example:
s1 t1
t2 0,0,-1 1,1,-1
s2 1,1,2 0,0,-1 s3
s1 t1
s2 1,1,-1 0,0,-1
t2 0,0,-1 1,1,2 t3
Players 1 and 2 confront each other in the game of “narrow road”: to avoid a collision, each must swerve left (their s options) or each must swerve right (their t options). Player 3 does not know that they are in fact in England (left matrix), where the custom is to drive on the left. But he does know that they are either in England or in Germany, where the custom is to drive on the right, and he knows that they have common knowledge of their location. The respective customs are common knowledge among all three. Player 3’s highest payoff is 2, which he receives in the upper-left and lower-right cells of matrices 1 and 2, respectively. All other payoffs for player 3 are −1. Thus player 3 “wins” if either he chooses s3 and players 1 and 2 swerve left or he chooses t3 and they swerve right. Otherwise he loses. In the described circumstances it seems plausible that the players would adopt the following expectations: Player 1:
p1 (s2 , s3 ) = p1 (s2 , t3 ) = .5 p12 (s2 ) = 1 p13 (s3 ) = p13 (t3 ) = .5
Player 2:
p2 (s1 , s3 ) = p2 (s1 , t3 ) = .5 p21 (s1 ) = 1 p23 (s3 ) = p23 (t3 ) = .5
GAME THEORY AND RATIONAL DECISION
Player 3:
401
p3 (s1 , s2 ) = p3 (t1 , t2 ) = .5 p31 (s1 ) = p31 (t1 ) = .5 p32 (s2 ) = p32 (t2 ) = .5
These are not Nash expectations. Player 3’s overall conjecture expresses correlation, and the various marginals are not concordant. Principles of rational decision, since they are practical principles, have to be pragmatically feasible: they have to be capable of functioning in a regulative way in real domains of action. The classical program should accept this test, not only because it is reasonable, but also because of the method of justification it has in fact adopted. The early work of von Neumann and the “direct argument” of von Neumann and Morgenstern may suggest a belief in the possibility of a priori proof, but subsequent justification has followed a reflective-equilibrium method involving mutual adjustment of solution concepts, general principles, criteria of adequacy, and judgments about particular cases. A full application of this method must include consideration of whether a proposed normative conception is capable of functioning in real circumstances. The conception must be both reflectively acceptable from the agent’s point of view and pragmatically stable in not being easily undermined by its own use or external interferences. Nash expectations can be subject to serious pragmatic instabilities in the absence of permissiveness, especially given the classical program’s constraints on solution functions. Consider again the “narrow road” structure:
s1 t1
s2 1, 1 0, 0
t2 0, 0 1, 1
Call this game G. Suppose L satisfies determinacy, invariance under isomorphism, Bayesian rationality, expectation consistency and support inclusion on {G}. Then L must designate as admissible all the pure strategies and restrict admissible expectations to the profile in which each player assigns a 0.5 probability to each of the other’s pure strategies. These are Nash expectations corresponding to the unique mixed-strategy equilibrium. L violates permissiveness, since for each player both pure strategies are admissible but the other player may not expect either with a probability other than 0.5. Suppose players 1 and 2 are prisoners in a concentration camp where decision-theoretic experiments are imposed on the inmates. Players 1 and
402
JULIUS SENSAT
2 are forced to play G. They are kept isolated from each other but are assured that G’s strategic structure and the L-rationality of each player are common knowledge between them. If they both choose their s strategies or both choose their t strategies, they will be allowed to live for at least another day. If their choices fail to match in this way, they will be hanged at noon. Since it is common knowledge that each endorses L, each player regards both of his own pure strategies as admissible and adopts a uniform distribution over those of the other player. Suppose that however they go about making the selection, each chooses his s strategy. They are safe for at least another day. But a few days later, they are run through the ordeal again. Once again, they match on s. Over the next few weeks, the game is played a half dozen times, and as it turns out, on each of these occasions they match on s. It is quite plausible that at some point during this sequence each will abandon his commitment to L and will expect the other to do so as well. In light of the extrinsic information that they have acquired about the history of their interactions – information they have good reason to regard as common knowledge between them – each will come to assign a probability greater than .5 that the other will choose his s strategy, and relative to that assignment, the s strategy carries a higher expected utility than the t strategy. If either of them has been flipping a coin to decide between s and t, at this point he will stop doing so and simply choose s. If he is offered a special breakfast in return for choosing t, he will not be moved. That they are both facing similar pressures to revise their expectations, and that this fact is common knowledge, is in fact partly constitutive of those pressures. The revision in expectations is quite easy for each player, since to make it he need not violate L in his choices in the game, since s is an L-admissible strategy. An easy transition out of L is possible through a process in which no one ever violates L in his choices. L is simply too unstable to serve as an acceptable conception of rationality. The strains of commitment are too great.19 Consider the following variant. As a vindictive response to a request to listen to music, the guards intermittently transmit nearly deafening radio reception to the prisoners’ quarters. Players 1 and 2 have spent countless hours together trying to correlate these episodes with other data (moods of the guards, who is on duty, the weather, etc.) in order to come up with an account that would explain them. Thus it is common knowledge between them that each is highly aware of off times and on times and on the alert for correlating circumstances. In the initial rounds of G, 1 and 2 match on s when the radio is on and on t when the radio is off. This sequence could
GAME THEORY AND RATIONAL DECISION
403
also severely strain their commitment to L. Each would face increasing pressure to view the other’s choice as correlated with the transmissions. Though the two players are acting independently in the sense that counts for noncooperative game theory, someone else could rationally regard their actions as correlated. Suppose a third person is currently in solitary confinement, out of reach of the transmissions, though he knows about them and the attempts of players 1 and 2 to make sense of them. Players 1 and 2 play the same game, but he is told that he must choose s3 if he thinks they will match and t3 if not. If he is correct, he will be allowed to live for at least another day. Otherwise he will be hanged at noon. Here is the structure:
s1 t1
t2 0,0,0 1,1,1
s2 1,1,1 0,0,0 s3
s1 t1
s2 1,1,0 0,0,1
t2 0,0,1 1,1,0 t3
Consider a solution function that designates all strategy profiles as admissible but permits only the single profile p of distributions such that for each player i, pi (x, y) = .25 for each profile (x, y) of the other players’ strategies. These are Nash expectations, which is what we should expect given the conditions of Proposition 6. Yet independence and concordance introduce new possibilities of destabilization. Suppose that in each play, player 3 chooses s3 and players 1 and 2 indeed match, sometimes on s and sometimes on t, in correlation with the radio transmissions. Players 1 and 2 will face the same pressures to change their conjectures about each other. They will also be inclined to increase their expectations that player 3 will choose s3 , though what he does has no effect on their payoffs. But they face no pressure to introduce correlation: player 1 has no reason to view player 2’s choice as correlated with player 3’s, nor player 2 player 1’s. However, though player 3 may not be inclined to alter his individual assignments of .5 to the choices of 1 and 2, since he cannot hear the radio, he may feel increasingly confident that they will match. Pressure in this direction could originate in the history of play and in his background knowledge of the other players’ fascination with the radio transmissions. If he changes his overall conjecture about 1 and 2 accordingly, his distribution will express correlation. Concordance and independence will both thereby be undermined, and Nash expectations along with them. It would be wrong to read these examples as simply illustrating the instability of mixed-strategy equilibria. Though the examples do illustrate
404
JULIUS SENSAT
the instability of such equilibria even under the “equilibrium of beliefs” interpretation – a significant fact, given that the interpretation was developed largely to deal with stability problems – the underlying problem is the instability of Nash expectations in general (not just “mixed” expectations), in the absence of permissiveness. The well known formal or internal instability of mixed-strategy equilibria is defined in terms of the payoff structure. But our focus is not on formal instability but on the pragmatic instability of solution functions that violate permissiveness. Pragmatic instabilities have to do with the susceptibility of regulative conceptions to be undermined in real contexts of action. Formal instabilities can facilitate such instabilities, but they are different nonetheless. Here is an example of pragmatic instability that does not depend on the formal instability of mixed-strategy equilibria:
s1 t1
t2 1,0,1 1,0,1
s2 1,1,1 1,1,1
s1 t1
s2 1,1,1 1,1,1
s3 Player 1 2 3
t3
Admissible Strategies s1, t1 s2 s3, t3
Condition determinacy Bayesian rationality consistency independence concordance Nash equilibrium Nash expectations permissiveness
t2 0,2,0 2,2,2
Admissible Expectations p1 (s2 , s3 ) = 1 p2 (s1 , s3 ) = 1 p3 (s1 , s2 ) = 1
Satisfied? strong yes yes yes yes no yes no
Suppose the players play (t1 , s2 , t3 ) the first few times the game is played. Soon player 2 will move them to (t1 , t2 , t3 ), outside the admissible set. There is a formal instability underlying the pragmatic one – the existence of nonequilibria in the admissible set – but it is not that of mixed-strategy
GAME THEORY AND RATIONAL DECISION
405
equilibria. The pragmatic instability of Nash expectations without permissiveness is supportable by a variety of formal instabilities, and it is the former that is our concern.20
5. CONCLUSION
Our basic formal results (Propositions 1, 2 and 3) block the achievement of determinacy. It is the permissiveness constraint that leads to these results. But the classical program cannot adopt a take-it-or-leave-it attitude to permissiveness. To the extent that it makes the common-knowledge assumptions and endorses Nash equilibrium, it is implicitly committed to permissiveness. Thus it carries an internal incoherence rooted in the fundamental assumptions that give it substance. Since it envisages game theory as a determinate theory of rational decision for a structurally definable domain, it must clearly specify the structural parameters and the corresponding solution concept. It adopted the common-knowledge assumptions and the Nash equilibrium concept to meet these requirements. Thus for it to be viable, it must respecify these elements. Until it does so, its fundamental task lacks sufficient articulation. This conclusion meshes supportively with other research. We have already cited direct criticisms of Nash equilibrium (Section 1). Several studies have cast doubt on the common-knowledge assumptions (Kreps, Milgrom, Roberts and Wilson (1982), Aumann (1992), Bacharach (1992), Rubinstein (1992), Pettit and Sugden (1989), Reny (1992) and Bicchieri (1989)). Agents can have an interest in clouding the status of their rationality or beliefs about it, and thus in destroying or preventing common knowledge thereof. Moreover, seemingly small departures from common knowledge can make a very big difference in the outcome of the game. And finally, in studies of “interactive belief systems,” some contextualists have explicitly shifted from a normative to an “analytical” perspective, recommending the models for analysis of how rationality functions in a variety of situations rather than for prescriptive purposes (Aumann (1992, p. 215), Aumann and Brandenburger (1995, pp. 1174–1175)). This development is salutary and may mark the beginning of a more complete liberation of game theory from its concerns with normative structural determinacy.21 Game theory may have to take what normative force it has from decision theory and confine itself to investigating how decision-theoretic rationality plays itself out in various social situations. Though it might facilitate normative insight for agents in such situations, its primary tasks would be analysis and explanation of social behavior. Since these tasks are crucial in social-theoretic evaluation of systems, the theory would still
406
JULIUS SENSAT
be an important player in normative endeavors. But it would put aside its founding conception, which has played a significant role in its development while nonetheless providing it with its most long-standing and serious difficulties. NOTES ∗ Supported by National Science Foundation Grant No. DIR 88-22024 and by The Gradu-
ate School and The Center for Twentieth Century Studies of The University of Wisconsin – Milwaukee. 1 This distinction is somewhat stylized; I don’t mean to imply that no one has been of two minds. Fairly pure examples are von Neumann ([1928] 1963) and Harsanyi and Selten (1988) for determinacy and Schelling (1960) and Aumann (1974) for contextualism. 2 For example, Battle of the Sexes, Chicken, and any two-person game in which each player has the same number of strategies and which is isomorphic to a game that awards each player 1 on each cell of a diagonal of the payoff matrix and 0 on off-diagonal cells. 3 See Sugden (1995) and the references cited there. 4 von Neumann ([1928] 1963, pp. 1, 13). I have altered the translation in von Neumann ([1928] 1959, pp. 13, 17) slightly. 5 In my view this ambiguity vitiates the “direct” argument for the maximin solution (von Neumann ([1928] 1963, pp. 8–9), von Neumann ([1928] 1959, pp. 21–22); von Neumann and Morgenstern (1953 [1944], secs. 14.5, 17.6)). McClennen (1976) and Spohn (1982) offer other criticisms. 6 Lewis (1969) provided the first explicit discussion of the concept of common knowledge and Aumann (1976) the first formal treatment. 7 Prior to presenting their “direct” argument in favor of their solution, von Neumann and Morgenstern (1953 [1944], secs. 14.5, 17.6) do engage in “indirect” reasoning about a hypothetical situation in which player 2, say, knows player 1’s action and therefore will choose his strategy so as to make player 1’s payoff as low as possible, so if 1 is rational he will choose a maximin strategy. At this point in their analysis, the fact that maximin strategies are in equilibrium comes into play, albeit only implicitly. However, they regard their indirect reasoning as a heuristic for discovery, not a justification. It can effectively exclude some possibilities, but even a sole surviving theory must still be justified by a direct argument (pp. 147–148, 148n). Moreover, their heuristic reflections concern just one contingent situation in which knowledge of the theory and of the rationality of the players is present; they don’t claim that such knowledge is a necessary feature of the game situation itself. In fact they deny it (p. 160). So the structural incorporation of such knowledge and the focus on equilibrium are major changes. 8 Rationalizability was originally introduced into the literature by Bernheim (1984) and Pearce (1984). The concept specified here differs from theirs in not requiring stochastic independence. Brandenburger and Dekel (1987) discuss both concepts. See also Brandenburger and Dekel (1989). 9 Among those that do are perhaps Spohn (1982, p. 252), Bernheim (1984) and Pearce (1984) (Bernheim and Pearce require stochastic independence, but this condition is vacuously satisfied in two-person games). There are simple intuitive grounds for suspicion of the standard two-person zero-sum theory. The discussion by Luce and Raiffa (1957, pp. 64–65) notwithstanding, a commander who always maximized his side’s security level could hardly count as a brilliant military strategist.
GAME THEORY AND RATIONAL DECISION
407
10 A stronger conception of Bayesian rationality would claim that all best responses to
an admissible expectation are rational relative to that expectation and thus should be admissible. Because this stronger constraint implies support inclusion (yet to be discussed), the following is a straightforward corollary to Proposition 3: Let G be any game having the following property: no symmetry invariant set of pure-strategy Nash equilibria forms a Cartesian product. Let C be any set of games containing G. There is no solution function satisfying determinacy, strong Bayesian rationality, permissiveness and invariance under isomorphism on C. Furthermore, if the classical program is committed to strong Bayesian rationality, then we can dispense with support inclusion as an independent assumption in Proposition 2 by replacing Bayesian rationality with strong Bayesian rationality. Doing so would allow the generation of further problematic results. For example, designating the components of mixed-strategy equilibria as admissible without their support violates the support condition, but designating as admissible the pure strategies that form the components of weak equilibria but not the strategies payoff-equivalent to them does not, though it does violate strong Bayesian rationality. On the other hand, allowing the payoff-equivalent strategies as admissible can result in non-equilibrium solutions (McClennen (1992)). 11 Bernheim (1986) uses a version of this requirement. 12 Bernheim (1986, pp. 479–480) and others theorists object to correlated expectations as inconsistent with the independent decision-making characteristic of a noncooperative game. I agree with Aumann (1974, pp. 86–88) that the game situation leaves room for players’ decisions to be viewed as correlated because pegged to information about the same random variable, provided that the correlation is compatible with their incentives. See also Aumann (1987, pp. 16–17). One might object that this information cannot be intrinsic, and therefore permissiveness begs the question against determinacy. But permissiveness does not require game theory to leave space for the operation of extrinsic factors. It merely insists that if that space is to be closed, the operative constraint must be consistency of expectations with admissible strategies. However, this issue can be sidestepped, as indicated in the text. 13 In fact, similar results can be achieved with very weak permissiveness, requiring only that if a mixed strategy qj is admissible for player j , then the other players have admissible expectations that assign qj -probabilities to j ’s pure strategies. Proposition 3 can stand as is with very weak permissiveness substituted for permissiveness in its conditions. Instead of Proposition 2, the proof would appeal to the following: Suppose L is a solution function satisfying determinacy, Bayesian rationality, very weak permissiveness and the support condition on C. Then for every game G in C, L (G)1 contains a profile of pure strategies, and every such profile is a pure-strategy equilibrium. Through these propositions, very weak permissiveness excludes the same games from the reach of determinacy that permissiveness does through Propositions 2 and 3. 14 The function of the interchangeability condition is to establish admissibility as fundamentally a property of a single player’s strategies and expectations rather than multi-agent profiles of them; an admissible profile of strategies, for example, is simply a profile of admissible strategies. 15 I indicate in parentheses the possible (correlated) substitutions of weak permissiveness mentioned earlier. 16 The admissible strategies are also the only best responses, so strong Bayesian rationality wouldn’t help. 17 Since mixed strategies are available, strong Bayesian rationality is not satisfied, but it would not do any good to amplify the set of admissible strategies so as to satisfy this condition.
408
JULIUS SENSAT
18 The theory would also have to endorse support inclusion and – to face the full brunt
of the propositions in Section 3.3 – invariance under isomorphism as well. Note that Harsanyi and Selten (1988, p. 1) espouse very strong determinacy. And certainly they are committed to the other conditions in the hypothesis of Proposition 4. They also endorse invariance under isomorphism (Harsanyi and Selten (1988, p. 73)). Support inclusion has an independent warrant based on the arguments already offered. However, Harsanyi and Selten accept the normative claim expressed by support inclusion, namely that intentional randomization is not rationally required. It is because they accept this claim that they interpret mixed-strategy equilibria as representing in the formalism of games of complete information certain pure-strategy solutions in games of incomplete information – solutions in which the players do not intentionally randomize. Is their theory infected by formal inconsistency, then? It is hard to say, precisely because for them the way to handle the illegitimacy of treating intentional randomization as rationally required is not to impose support inclusion on the complete-information formalism but to move first to the more general level of games of incomplete information. However, Spohn (1982, pp. 263–264), McClennen (1978, p. 367) and others have offered trenchant criticism of this proposal. 19 One might object that because of the repetition the game is not really G but a different game. It is true that if a player expected the game to be repeated, then he would have to consider what his choice would communicate to the other about choices he might make in the future, and such considerations would give the players additional reason to stick with s. To the extent that the players understand themselves to be in such a situation, the right model is that of a supergame, in which sticking with s and expecting the other to do so do not violate L. However, there are situations in which players quite legitimately act repeatedly without considering possible strategic links between plays. For example, suppose that in virtue of what they have been told, for the first two rounds the prisoners believe that they have been randomly selected for each round from a large population, so that they assign a negligible probability to meeting again. When they are selected for the third round, the experimenters offer a new explanation, say that something went wrong with the equipment and they have to do the experiment over. These three rounds might be enough to induce the instability described in the text, without changing the game into a supergame. Moreover, consider player 3 in the example to follow. There are no forwardlooking considerations that would put him into a supergame. 20 Thus Harsanyi and Selten’s attempt to explain away the instability of mixed-strategy equilibria is at best of limited relevance to our argument. Given the existing cogent criticisms of their view (cf. note 18), I will simply let speak for itself its implication that inmates 1 and 2 should expect random variations in each other’s mood or sudden urges of sufficient significance to warrant sticking with the 50-50 expectations prescribed by the solution function. 21 Even here however the old view intrudes. Aumann and Brandenburger (1995, pp. 1162– 1163) use an interactive belief system to prove that common knowledge of conjectures is sufficient, along with mutual knowledge of rationality and of the game, for Nash equilibrium. In explaining the result, they stress that contrary to what has usually been thought, common knowledge of rationality is not needed (see also Brandenburger (1992, p. 96)). This remark suggests more of a continuity with determinacy and normative concerns than their result actually has. As they explain, since the interactive belief systems include the agents’ actions in their state descriptions, they are suitable for analysis but not for the prescriptive purpose of advising players what to do. This purpose however provided the context of and rationale for connecting common knowledge of rationality with equilibrium. On the other hand, the authors also stress a continuity with decision-theoretic approaches
GAME THEORY AND RATIONAL DECISION
409
to game theory: the common-knowledge assumptions are decision-theoretic insofar as they add a specification of the agent’s epistemic state to the assumption of rationality (p. 1161). There is that continuity, but given the history of the discipline it is not the one to stress. There are always multiple continuities, but they are not all equally important. After all, interactive belief systems stem from models of games of incomplete information developed by Harsanyi, the arch determinacy theorist. Lest there be any doubt about the contextualism of interactive belief systems, Aumann (1992, p. 216) remarks that “[e]ach player makes some definite choice of a pure strategy, based on whatever he knows or believes about customs, history, personalities of the other players, and so on – in brief, based on the state of his information.”
REFERENCES
Aumann, R.: 1974, ‘Subjectivity and Correlation in Randomized Strategies’, Journal of Mathematical Economics 1, 67–96. Aumann, R.: 1976, ‘Agreeing to Disagree’, Annals of Statistics 4, 1236–1239. Aumann, R.: 1981, ‘Survey of Repeated Games’, in Essays in Game Theory and Mathematical Economics in Honor of Oskar Morgenstern, Wissenschaftsverlag, Bibliographisches Institut, Mannheim, Vienna and Zurich, pp. 11–42. Aumann, R.: 1987a, ‘Correlated Equilibrium as an Expression of Bayesian Rationality’, Econometrica 55, 1–18. Aumann, R.: 1987b, ‘Game Theory’, in M. Milgate and P. Newmann (eds.), The New Palgrave: A Dictionary of Economics, Vol. 2, The Stockton Press, New York, pp. 460– 82. Aumann, R.: 1992, ‘Irrationality in Game Theory’, in A. P. Dasgupta (ed.), Economic Analysis of Markets and Games, MIT Press, Cambridge, Mass., pp. 214–227. Aumann, R. and Brandenburger, A.: 1995, ‘Epistemic Conditions for Nash Equilibrium’, Econometrica 63(5), 1161–1180. Bacharach, M.: 1992, ‘The Acquisition of Common Knowledge’, in C. Bicchieri and M. L. D. Chiara (eds.), Knowledge, Belief and Strategic Interaction, Cambridge University Press, Cambridge, pp. 285–316. Bernheim, B. D.: 1984, ‘Rationalizable Strategic Behavior’, Econometrica 52, 1007–1028. Bernheim, B. D.: 1986, ‘Axiomatic Characterization of Rational Choice in Strategic Environments’, Scandinavian Journal of Economics 88, 473–488. Bicchieri, C.: 1989, ‘Self-refuting Theories of Strategic Interaction: A Paradox of Common Knowledge’, Erkenntnis 30, 69–85. Brandenburger, A.: 1992, ‘Knowledge and Equilibrium in Games’, Journal of Economic Perspectives 6(4), 83–101. Brandenburger, A. and Dekel, E.: 1987, ‘Rationalizability and Correlated Equilibria’, Econometrica 55, 1391–1402. Brandenburger, A. and Dekel, E.: 1989, ‘The Role of Common Knowledge Assumptions in Game Theory’, in F. Hahn (ed.), The Economics of Missing Markets, Information and Games, Clarendon Press, Oxford, pp. 46–61. Chernoff, H.: 1954, ‘Rational Selection of Decision Functions’, Econometrica 22, 422– 443. Harsanyi, J. C.: 1977, Rational Behavior and Bargaining Equilibrium in Games and Social Situations, Cambridge University Press, Cambridge.
410
JULIUS SENSAT
Harsanyi, J. C.: 1992, ‘Game Solutions and the Normal Form’, in C. Bicchieri and M. L. D. Chiara (eds), Knowledge, Belief, and Strategic Interaction, Cambridge University Press, Cambridge, pp. 355–376. Harsanyi, J. C. and Selten, R.: 1988, A General Theory of Equilibrium Selection in Games, The MIT Press, Cambridge, Mass. and London. Kreps, D. M., Milgrom, P., Roberts, J. and Wilson, R.: 1982, ‘Rational Cooperation in the Finitely Repeated Prisoners’ Dilemma’, Journal of Economic Theory 27, 245–252. Lewis, D. K.: 1969, Convention: A Philosophical Study, Harvard University Press, Cambridge, Mass. Luce, R. D. and Raiffa, H.: 1957, Games and Decisions, John Wiley and Sons, New York. McClennen, E.: 1992, ‘The Theory of Rationality for Ideal Games’, Philosophical Studies 65, 193–215. McClennen, E. F.: 1976, ‘Some Formal Problems with the von Neumann and Morgenstern Theory of Two-Person, Zero-Sum Games, i: The Direct Proof’, Theory and Decision 7, 1–28. McClennen, E. F.: 1978, ‘The Minimax Theory and Expected Utility Reasoning’, in J. L. C. Hooker and E. F. McClennen (eds.), Foundations and Applications of Decision Theory, Vol. I, R. Reidel, Dordrecht. Nash, J. F.: 1951, ‘Noncooperative Games’, Annals of Mathematics 54, 286–295. Pearce, D.: 1984, ‘Rationalizable Strategic Behavior and the Problem of Perfection’, Econometrica 52, 1029–1050. Pettit, P. and Sugden, R.: 1989, ‘The Backward Induction Paradox’, The Journal of Philosophy 86(4), 169–182. Reny, P. J.: 1992, ‘Rationality in Extensive-Form Games’, Journal of Economic Perspectives 6(4), 103–118. Rubinstein, A.: 1992, ‘The Electronic Mail Game: Strategic Behavior under “Almost Common Knowledge” ’, in C. Bicchieri and M. L. D. Chiara (eds.), Knowledge, Belief, and Strategic Interaction, Cambridge University Press, Cambridge, pp. 317–326. Schelling, T. C.: 1960, The Strategy of Conflict, Harvard University Press, Cambridge, Massachusetts. Spohn, W.: 1982, ‘How to Make Sense of Game Theory’, in W. Stegmuller, W. Balzer and W. Spohn (eds.), Studies in Contemporary Economics, Vol. 2: Philosophy of Economics, Springer-Verlag, Berlin, Heidelberg, New York. Sugden, R.: 1995, ‘A Theory of Focal Points’, The Economic Journal 105, 533–550. von Neumann, J.: [1928] 1959, ‘On the Theory of Games of Strategy’, Annals of Mathematics Studies (40), 13–42. Trans. Sonya Bargmann. von Neumann, J.: [1928] 1963, ‘Zur Theorie der Gesellschaftsspiele’, in A. H. Taub (ed.), Collected Works, Vol. VI, Pergamon Press, Oxford, pp. 1–26. von Neumann, J. and Morgenstern, O.: 1953 [1944], Theory of Games and Economic Behavior, third edn., Princeton University Press, Princeton. Manuscript submitted January 5, 1996 Final version received October 28, 1997 Department of Philosophy University of Wisconsin – Milwaukee P. O. Box 413 Milwaukee, WI 53201
[email protected]