Interactive Epistemology

The following sections are included:

• Contents
• Introduction

Two people, 1 and 2, are said to have common knowledge of an event E if both know it, 1 knows that 2 knows it, 2 knows that 1 knows it, 1 knows that 2 knows that 1 knows it, and so on.

Formal Interactive Epistemology deals with the logic of knowledge and belief when there is more than one agent or “player.” One is interested not only in each person’s knowledge about substantive matters, but also in his knowledge about the others’ knowledge. This paper examines two parallel approaches to the subject. The first is the semantic approach, in which knowledge is represented by a space Ω of states of the world, together with partitions ℐ_i of Ω for each player i; the atom of ℐ_i containing a given state ω of the world represents i’s knowledge at that state — the set of those other states that i cannot distinguish from ω. The second is the syntactic approach, in which knowledge is embodied in sentences constructed according to certain syntactic rules. This paper examines the relation between the two approaches, and shows that they are in a sense equivalent.

In game theory and economics, the semantic approach has heretofore been most prevalent. A question that often arises in this connection is whether, in what sense, and why the space Ω and the partitions ℐ_i can be taken as given and commonly known by the players. An answer to this question is provided by the syntactic approach.

Formal Interactive Epistemology deals with the logic of knowledge and belief when there is more than one agent or “player.” One is interested not only in each person’s knowledge and beliefs about substantive matters, but also in his knowledge and beliefs about the others’ knowledge and beliefs. This paper examines two parallel approaches to the subject. The first is the semantic, in which knowledge and beliefs are represented by a space Ω of states of the world, and for each player i, partitions ℐ_i of Ω and probability distributions π_i(·; ω) on Ω for each state ω of the world. The atom of ℐ_i containing a given state ω represents i’s knowledge at that state—the set of those other states that i cannot distinguish from ω; the probability distributions π_i(·; ω) represent i’s beliefs at the state ω. The second is the syntactic approach, in which beliefs are embodied in sentences constructed according to certain syntactic rules. This paper examines the relation between the two approaches, and shows that they are in a sense equivalent.

In game theory and economics, the semantic approach has heretofore been most prevalent. A question that often arises in this connection is whether, in what sense, and why the space Ω, the partitions ℐ_i, and the probability distributions π_i(·; ω) can be taken as given and commonly known by the players. An answer to this question is provided by the syntactic approach.

In interactive contexts such as games and economies, it is important to take account not only of what the players believe about substantive matters (such as payoffs), but also of what they believe about the beliefs of other players. Two different but equivalent ways of dealing with this matter, the semantic and the syntactic, are set forth. Canonical and universal semantic systems are then defined and constructed, and the concepts of common knowledge and common priors formulated and characterized. The last two sections discuss relations with Bayesian games of incomplete information and their applications, and with interactive epistemology — the theory of multi-agent knowledge and belief as formulated in mathematical logic.

The first symposium question is, “Is there an important distinction between information and knowledge?” Of course, it depends on what is meant by these terms. An advantage (disadvantage?) of formal reasoning is that there, that kind of question does not arise. You must first define your terms, and then it’s usually easy to tell whether there is or is not an important distinction. Some people might say that even informally, the question has no substance until you’ve said what you mean…

The following sections are included:

• Introduction
• Examples
• The Formal Model
• Preliminaries and Generalities
• Equilibrium Points in Two-Person Games
• Two-Person Zero-Sum Games
• Proof of the Propositions of Section 4
• A Posteriori Equilibria
• Discussion
• Acknowledgement
• References

Correlated equilibrium is formulated in a manner that does away with the dichotomy usually perceived between the “Bayesian” and the “game-theoretic” view of the world. From the Bayesian viewpoint, probabilities should be assignable to everything, including the prospect of a player choosing a certain strategy in a certain game. The so-called “game-theoretic” viewpoint holds that probabilities can only be assigned to events not governed by rational decision makers; for the latter, one must substitute an equilibrium (or other game-theoretic) notion. The current formulation synthesizes the two viewpoints: Correlated equilibrium is viewed as the result of Bayesian rationality; the equilibrium condition appears as a simple maximization of utility on the part of each player, given his information.

A feature of this approach is that it does not require explicit randomization on the part of the players. Each player always chooses a definite pure strategy, with no attempt to randomize; the probabilistic nature of the strategies reflects the uncertainty of other players about his choice. Examples are given.

A player i’s actions in a game are determined by her beliefs about other players; these depend on the game’s real-life context, not only its formal description. Define a game situation as a game together with such beliefs; call the beliefs — and i’s resulting expectation — rational if there is common knowledge of rationality and a common prior. In two-person zero-sum games, i’s only rational expectation is the game’s value. In an arbitrary game G, we characterize i’s rational expectations in terms of the correlated equilibria of the doubled game 2G in which each of i’s strategies in G appears twice.

Sufficient conditions for Nash equilibrium in an n-person game are given in terms of what the players know and believe — about the game, and about each other’s rationality, actions, knowledge, and beliefs. Mixed strategies are treated not as conscious randomizations, but as conjectures, on the part of other players, as to what a player will do. Common knowledge plays a smaller role in characterizing Nash equilibrium than had been supposed. When n = 2, mutual knowledge of the payoff functions, of rationality, and of the conjectures implies that the conjectures form a Nash equilibrium. When n ≥ 3 and there is a common prior, mutual knowledge of the payoff functions and of rationality, and common knowledge of the conjectures, imply that the conjectures form a Nash equilibrium. Examples show the results to be tight.

The following sections are included:

• Introduction
• The Results
• Proofs
• Interpretation
• Discussion
• References

Call a perfect information (PI) game simple if each player moves just once. Call a player rational if he never takes an action while believing, with probability 1, that a different action would yield him a higher payoff. Using syntactic logic, we show that an outcome of a simple PI game is consistent with common strong belief of rationality iff it is a backward induction outcome. The result also applies to general PI games in which a player’s agents act independently, rendering forward inferences invalid.

In Rosenthal’s Centipede Game, if at the start of play it is commonly known that the players will choose rationally at vertices that are actually reached, then the backward induction outcome results; that is, the first player “goes out” at the first move.

The history of game theory has been evolutionary rather than revolutionary. Over the years, the fundamental concepts of the theory have been used in an ever-increasing circle of contexts; some of the most important developments consisted of innovative ways of recasting the theory so as to apply to problems that previously appeared not to fit in. A prime example is Harsanyi’s historic work (1967–68) on games of incomplete information. Before this work, it had been universally thought that for game theory to be applicable, the payoff matrix of the game must be commonly known. Harsanyi’s achievement consisted of formulating games of incomplete information so that they could be seen and analyzed as games of complete information; by this achievement, he opened the door to the development of the enormous fields of informational game theory and economics as we know them today. Similarly, the theory was extended from perfect information (Zermelo) to imperfect information (Borel and von Neumann); from strategic (normal) form to extensive; from two-person to n-person; from zero-sum to non-zero-sum; and from TU (transferable utility) to NTU (non-transferable utility)…

It now seems to be generally accepted that rational players would not necessarily use their backward-induction strategies if there were to be a deviation from the backward-induction path (Binmore, 1987). But Aumann (1995) has recently offered a formal defense of the proposition that prior common knowledge of rationality implies that play will nevertheless necessarily follow the backward-induction path. This brief note, extracted from a longer philosophical paper (Binmore, 1996), questions the definition of rationality that he employs…

Though we found it difficult to follow Binmore’s (1996) critique (henceforth [B]) of Aumann (1995) (henceforth [A]), we acknowledge that [A] is not transparent. Here we reply to [B], and also explain the analysis of [A] in verbal, conceptual terms, covering some points not covered in [A]…

The following sections are included:

• The Myth of Sisyphus
• Backward Induction
• Interpreting Counterfactuals
• Chain-Store Paradox
• Ultimatum Game
• Conclusion
• References

I heartily agree with many of the points made by Binmore and Samuelson. First, that the evolutionary approach to game theory is very important, though perhaps not to the exclusion of all other approaches. Second, that in perfect information (PI) games, backward induction (BI) may yield choices that are not only unwise and unreasonable, but quite simply irrational. Third, that interpretational issues are very important in these matters, and that in discussing them, one cannot rely exclusively on mathematics. Fourth, that in game theory and decision theory in general, and in the matter at hand in particular, one cannot restrict oneself to material implication, but must use what Binmore and Samuelson call ‘subjunctive conditionals’. Fifth, that deleting weakly dominated strategies is not ‘harmless’. Sixth, that in considering equilibria, one should not restrict attention to those that are ‘trembling hand’ perfect. Seventh, that the experimental results in the Ultimatum Game constitute an important phenomenon that cannot and should not be ignored or dismissed, and on which game theory has much of importance to say. And I could go on, listing many more points of agreement with their positions…

The following sections are included:

• Introduction
• Interactive Epistemology
• Knowledge at the Lowest Common Denominator
• The Boy-Scout Version of the Hangman’s Paradox
• Conclusion
• References

On the issue of ‘logical omniscience’ — the assumption that if one knows something, then one knows all its logical consequences — I am in complete agreement with Margalit and Yaari. There is no question that this is an important, far-reaching, and rather unreasonable assumption, and that it would be highly desirable to get rid of it. Unfortunately, I know of no coherent system of epistemic logic that does so, even in the one-agent case. One could take the position that this problem is so central that until it is solved, there is no point in bothering with the epistemic foundations of interactive decision theory at all. In the ‘Notes on Interactive Epistemology’ (Aumann, 1992) to which Margalit and Yaari refer, I chose not to take that position, but to set forth the epistemic foundations of game theory and rational economics as they appear today, i.e., with the assumption of logical omniscience…

In Aumann (1987), it is asserted that for those who adhere to the “… Bayesian view of the world, the notion of equilibrium is an unavoidable consequence…” I discuss two possible interpretations of the information model and show that neither interpretation supports this assertion. The hierarchy representation interpretation renders the prior stage meaningless and hence both the key assumption of Aumann’s theory and its conclusion become impossible to interpret. The prior interpretation, on the other hand, is distinctively non-Bayesian. Furthermore, both the common prior assumption and the notion of having beliefs over one’s own actions are problematic in the latter interpretation.

The following sections are included:

• Introduction
• Partition Structures and Hierarchies
• The Intuition for Common Priors
• Formal Treatment
• Discussion
• A Question About Axiom (2)
• Gul’s “Prior Interpretation”
• Gul’s “Hierarchy Interpretation”
• References

The following sections are included:

• Subject Index
• Name Index