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

DOI10.1016/J.GEB.2019.03.006zbMATH Open1458.91030OpenAlexW3081265119MaRDI QIDQ1995464FDOQ1995464

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

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

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)

Cites Work

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

Cited In (8)

• Computational complexity of computing a quasi-proper equilibrium
• A variant of Harsanyi's tracing procedures to select a perfect equilibrium in normal form games
• Polynomial-time computation of exact correlated equilibrium in compact games
• Risk-free bidding in complement-free combinatorial auctions
• Computing lexicographically safe Nash equilibria in finite two-person games with tight game forms given by oracles
• On the Hardness and Existence of Quasi-Strict Equilibria
• The real computational complexity of minmax value and equilibrium refinements in multi-player games
• The Effective Computation of Equilibrium Point for N-Person Games Cyclic to the Next Person

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)