Algorithmic solutions for extensive games

MaRDI QIDQ4036943zbMATH OpenFDO

Authors Pierpaolo Battigalli

Publication date 18 May 1993

zbMATH Keywords

rationalizabilitystrategic manipulation of beliefs

Mathematics Subject Classification ID

Computational methods for problems pertaining to operations research and mathematical programming (90-08) 2-person games (91A05)

Review text

[For the entire collection see Zbl 0755.00017.] The paper defines four algorithms to solve extensive games using different sets of assumptions about players' updating processes. Two of them, IMP and \(*\)-IMP, do not necessarily solve an arbitrary game due to the possibility of strategic manipulation of beliefs; while the others. EFR and \(*\)-EFR, endow players with suitable hiearchies of beliefs ruling out strategic manipulation. This provides an alternative characterization of Pearce's extensive form rationalizability, which may be defended on the ground that there is a common belief in ``rationality at the beginning of the game, but not necessary at each information set. \(*\)-IMP and \(*\)-EFR rely on the assumption that a player facing an unexpected event updates her beliefs concerning different opponents independently of one another, which seems reasonable, since only non-correlated conjectures are allowed for. The relationships between these algorithms and with backward induction are discussed.

Recommendations

• On rationalizability in extensive games
• Algorithms for cautious reasoning in games
• Proper belief revision and rationalizability in dynamic games
• Computing Normal Form Perfect Equilibria for Extensive Two-Person Games
• Equilibrium computation for two-player games in strategic and extensive form

Cited in

(11)

• Conditional dominance, rationalizability, and game forms
• Admissibility and common belief.
• Algorithms for cautious reasoning in games
• Faster algorithms for extensive-form game solving via improved smoothing functions
• A computational method for solving \(n\)-person game
• Transparent restrictions on beliefs and forward-induction reasoning in games with asymmetric information
• Revisiting CFR^+ and alternating updates
• scientific article; zbMATH DE number 6520260 (Why is no real title available?)
• Playing Games with Approximation Algorithms
• Algorithms, games, and the internet (extended abstract)
• Exact algorithms for solving stochastic games

This page was built for publication: Algorithmic solutions for extensive games

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4036943)