Skip to main content
Article
Structure Theorems for Game Trees
Proceedings of the National Academy of Sciences (2002)
  • Srihari Govindan, University of Iowa
  • Robert B Wilson, Stanford University
Abstract

Kohlberg and Mertens proved that the graph of the Nash equilibrium correspondence is homeomorphic to its domain when the domain is the space of payoffs in normal-form games. A counterexample disproves the analog for the equilibrium outcome correspondence over the space of payoffs in extensive-form games, but we prove an analog when the space of behavior strategies is perturbed so that every path in the game tree has nonzero probability. Without such perturbations, the graph is the closure of the union of a finite collection of its subsets, each diffeomorphic to a corresponding path-connected open subset of the space of payoffs. As an application we construct an algorithm for computing equilibria of an extensive-form game with a perturbed strategy space, and thus, approximate equilibria of the unperturbed game.

Keywords
  • game theory,
  • extensive form,
  • structure theorem,
  • computation
Disciplines
Publication Date
2002
Citation Information
Srihari Govindan and Robert B Wilson. "Structure Theorems for Game Trees" Proceedings of the National Academy of Sciences Vol. 99 Iss. 13 (2002)
Available at: http://works.bepress.com/wilson_robert/12/