The complexity of computing a (quasi-)perfect equilibrium for an \(n\)-player extensive form game

DOI10.1016/j.geb.2019.03.006zbMath1458.91030OpenAlexW3081265119MaRDI QIDQ1995464

Kousha Etessami

Publication date: 23 February 2021

Published in: Games and Economic Behavior (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.geb.2019.03.006

zbMATH Keywords

algorithmscomputational complexityextensive form gameperfect equilibriumquasi-perfect equilibrium

Mathematics Subject Classification ID

(n)-person games, (n>2) (91A06) Games in extensive form (91A18) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Algorithmic game theory and complexity (91A68) Equilibrium refinements (91A11)

Related Items (4)

Computational complexity of computing a quasi-proper equilibrium ⋮ A variant of Harsanyi's tracing procedures to select a perfect equilibrium in normal form games ⋮ The real computational complexity of minmax value and equilibrium refinements in multi-player games ⋮ Risk-free bidding in complement-free combinatorial auctions

Uses Software

• Gambit

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A path-following procedure to find a proper equilibrium of finite games
• A relation between perfect equilibria in extensive form games and proper equilibria in normal form games
• Computing a quasi-perfect equilibrium of a two-player game
• On the computational complexity and geometry of the first-order theory of the reals. III: Quantifier elimination
• Nash and correlated equilibria: Some complexity considerations
• The complexity of two-person zero-sum games in extensive form
• Reexamination of the perfectness concept for equilibrium points in extensive games
• On the complexity of the parity argument and other inefficient proofs of existence
• Two examples of strategic equilibrium
• Efficient computation of behavior strategies
• Efficient computation of equilibria for extensive two-person games
• On the equivalence between (quasi-)perfect and sequential equilibria
• Non-cooperative games
• The Complexity of Approximating a Trembling Hand Perfect Equilibrium of a Multi-player Game in Strategic Form
• On the Complexity of Nash Equilibria and Other Fixed Points
• The Computational Complexity of Trembling Hand Perfection and Other Equilibrium Refinements
• Computing sequential equilibria for two-player games
• The Game World Is Flat: The Complexity of Nash Equilibria in Succinct Games
• "Almost" Implies "Near"
• Sequential Equilibria
• The Algebraic Geometry of Perfect and Sequential Equilibrium
• The Complexity of Computing a Nash Equilibrium
• Computational Complexity
• Game Theory
• Algorithmic Game Theory
• Computing Normal Form Perfect Equilibria for Extensive Two-Person Games
• The Approximation of Fixed Points of a Continuous Mapping
• SIMPLICIAL APPROXIMATION OF FIXED POINTS
• Computing Equilibria of Two-Person Games from the Extensive Form
• Twenty Lectures on Algorithmic Game Theory
• Refinements of the Nash equilibrium concept

This page was built for publication: The complexity of computing a (quasi-)perfect equilibrium for an \(n\)-player extensive form game