An Impossibility Theorem on Beliefs in Games
by
Adam Brandenburger
Harvard Business School, Boston MA 02163
Coauthors: H. Jerome Keisler (Department of Mathematics, University of Wisconsin-Madison)

The epistemic program in game theory operates with a description of a game that includes, in addition to the customary strategies and payoffs, the players' beliefs or knowledge about these objects, the players' beliefs or knowledge about each other's beliefs or knowledge about these objects, and so on.

Such talk of beliefs about beliefs about . . . might suggest that some kind of self-reference could arise in the analysis, similar to the well-known examples of self-reference in logic, such as Russell's Paradox ("The set of all sets which are not members of themselves"). This is indeed the case. Take player a's belief about player b's beliefs. Now, player b's beliefs are, in part, about player a's belief. (They also concern player a's strategy and payoffs, as well as the strategies, payoffs, and beliefs of players other than a.) Thus, player a's belief refers to itself, in some sense.

Russell's Paradox can be viewed as an intuitive analog to a formal impossibility theorem in mathematical logic, viz. a weak form of Tarski's Theorem. Similarly, this talk will present an informal, verbal 'paradox' of self-reference concerning beliefs, which is then formalized as a game-theoretic impossibility theorem.

The impossibility argument operates in a "possibility structure." Fix a two-person strategic-form game, and let S^a and S^b be the strategy sets of the two players. (Other interpretations of S^a and S^b are possible.) To this description, a possibility structure appends sets T^a and T^b, called the "type sets" of the two players. Each element of T^a, i.e. each type of player a, is associated with a nonempty subset of S^b×T^b, to be interpreted as the collection of strategy-type pairs of player b considered possible by player a. (Call this the "possibility set" of the given type of player a.) Likewise, each element of T^b is associated with a nonempty subset of S^a×T^a, i.e. the possibility set of that type of player b.

Given a particular possibility structure, there is a naturally associated first-order predicate logic within which certain subsets of S^b×T^b and of S^a×T^a are definable. A possibility structure will be called "definably complete" if: (i) each nonempty definable subset of S^b×T^b is the possibility set of some type of player a; and (ii) each nonempty definable subset of S^a×T^a is the possibility set of some type of player b. The impossibility theorem states that a definably complete structure does not exist. (To be precise, this is true provided at least one of the sets S^a and S^b is non-singleton.)

The question of the existence of a complete possibility structure is a natural foundational one. But it is also a more 'practical' one in the context of current epistemic investigations into the backward-induction algorithm and iterated admissibility (iterated weak dominance). The talk will spell out this connection.

Date received: June 13, 2000

Copyright © 2000 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # cafi-73.