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

DOI10.1016/J.GEB.2019.03.006MaRDI QIDQ1995464zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• The computational complexity of trembling hand perfection and other equilibrium refinements
• The complexity of approximating a trembling hand perfect equilibrium of a multi-player game in strategic form
• The real computational complexity of minmax value and equilibrium refinements in multi-player games
• Computing a quasi-perfect equilibrium of a two-player game
• The real computational complexity of minmax value and equilibrium refinements in multi-player games

Cites work

• scientific article; zbMATH DE number 51788 (Why is no real title available?)
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 3487169 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 1099369 (Why is no real title available?)
• scientific article; zbMATH DE number 3215746 (Why is no real title available?)
• scientific article; zbMATH DE number 3078991 (Why is no real title available?)
• "Almost" Implies "Near"
• A course in game theory.
• 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
• Algorithmic Game Theory
• Computational Complexity
• Computing Equilibria of Two-Person Games from the Extensive Form
• Computing Normal Form Perfect Equilibria for Extensive Two-Person Games
• Computing a quasi-perfect equilibrium of a two-player game
• Computing sequential equilibria for two-player games
• Efficient computation of behavior strategies
• Efficient computation of equilibria for extensive two-person games
• Game theory. Translated from the Hebrew by Ziv Hellman and edited by Mike Borns
• Nash and correlated equilibria: Some complexity considerations
• Non-cooperative games
• On the Complexity of Nash Equilibria and Other Fixed Points
• On the complexity of the parity argument and other inefficient proofs of existence
• On the computational complexity and geometry of the first-order theory of the reals. III: Quantifier elimination
• On the equivalence between (quasi-)perfect and sequential equilibria
• Reexamination of the perfectness concept for equilibrium points in extensive games
• Refinements of the Nash equilibrium concept
• SIMPLICIAL APPROXIMATION OF FIXED POINTS
• Sequential Equilibria
• The Algebraic Geometry of Perfect and Sequential Equilibrium
• The Approximation of Fixed Points of a Continuous Mapping
• The Game World Is Flat: The Complexity of Nash Equilibria in Succinct Games
• The complexity of approximating a trembling hand perfect equilibrium of a multi-player game in strategic form
• The complexity of computing a Nash equilibrium
• The complexity of two-person zero-sum games in extensive form
• The computational complexity of trembling hand perfection and other equilibrium refinements
• Twenty lectures on algorithmic game theory
• Two examples of strategic equilibrium

Cited in

(11)

• Polynomial-time computation of exact correlated equilibrium in compact games
• Computational complexity of computing a quasi-proper equilibrium
• The complexity of approximating a trembling hand perfect equilibrium of a multi-player game in strategic form
• On the Hardness and Existence of Quasi-Strict Equilibria
• Computing lexicographically safe Nash equilibria in finite two-person games with tight game forms given by oracles
• 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
• The computational complexity of trembling hand perfection and other equilibrium refinements
• Computing a quasi-perfect equilibrium of a two-player game
• The Effective Computation of Equilibrium Point for N-Person Games Cyclic to the Next Person
• The real computational complexity of minmax value and equilibrium refinements in multi-player games

Describes a project that uses

Uses Software

• Gambit

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

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