Extensive games with possibly unaware players

ABSTRACT

Standard game theory assumes that the structure of the game is common knowledge among players. We relax this assumption by considering extensive games where agents may be unaware of the complete structure of the game. In particular, they may not be aware of moves that they and other agents can make. We show how such games can be represented; the key idea is to describe the game from the point of view of every agent at every node of the game tree. We provide a generalization of Nash equilibrium and show that every game with awareness has a generalized Nash equilibrium. Finally, we extend these results to games with awareness of unawareness, where a player i may be aware that a player j can make moves that i is not aware of.

REFERENCES

• 1: R. Fagin , J. Y. Halpern, Belief, awareness, and limited reasoning, Artificial Intelligence, v.34 n.1, p.39-76, Dec. 1987 [doi>10.1016/0004-3702(87)90003-8]
• 2: Y. Feinberg. Subjective reasoning---games with unawareness. Technical Report Resarch Paper Series #1875, Stanford Graduate School of Business, 2004.
• 3: Y. Feinberg. Games with incomplete awareness. Technical Report Research Paper Series #1894, Stanford Graduate School of Business, 2005.
• 4: Y. Gal and A. Pfeffer. Reasoning about agents' beliefs and decision-making processes in games. Unpublished manuscript, 2005.
• 5: J. Y. Halpern. On ambiguities in the interpretation of game trees. Games and Economic Behavior, 20:66--96, 1997.
• 6: Joseph Y. Halpern , Yoram Moses, Knowledge and common knowledge in a distributed environment, Journal of the ACM (JACM), v.37 n.3, p.549-587, July 1990 [doi>10.1145/79147.79161]
• 7: J. Harsanyi. Games with incomplete information played by 'Bayesian' players, parts I--III. Management Science, 14:159--182, 320--334, 486--502, 1968.
• 8: M. J. Osborne and A. Rubinstein. A Course in Game Theory. MIT Press, Cambridge, Mass., 1994.
• 9: J. Weinstein and M. Yildiz. Impact of higher-order uncertainty. Unpublished manuscript., 2003.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Multiagent systems

General Terms:
Economics, Theory

Keywords:
awareness, foundations of game theory, solution concepts