The complexity of two-person zero-sum games in extensive form

DOI10.1016/0899-8256(92)90035-QzbMath0758.90084OpenAlexW2023373582MaRDI QIDQ1195597

Nimrod Megiddo, Daphne Koller

Publication date: 12 January 1993

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

Full work available at URL: https://doi.org/10.1016/0899-8256(92)90035-q

zbMATH Keywords

extensive formcomplexity of finding max-min strategiesfinite two-person zero-sum games

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) 2-person games (91A05)

Related Items (25)

Computing equilibria: a computational complexity perspective ⋮ Successful Nash equilibrium agent for a three-player imperfect-information game ⋮ Computing human-understandable strategies: deducing fundamental rules of poker strategy ⋮ Parallel approximation of min-max problems ⋮ Team-maxmin equilibria ⋮ The independent choice logic for modelling multiple agents under uncertainty ⋮ Representations and solutions for game-theoretic problems ⋮ Complexity limitations on one-turn quantum refereed games ⋮ First-order algorithm with \({\mathcal{O}(\ln(1/\epsilon))}\) convergence for \({\epsilon}\)-equilibrium in two-person zero-sum games ⋮ On the complexity of iterated weak dominance in constant-sum games ⋮ Propositional logic of imperfect information: Foundations and applications ⋮ Approximating maxmin strategies in imperfect recall games using A-loss recall property ⋮ New complexity results about Nash equilibria ⋮ Good neighbors are hard to find: Computational complexity of network formation ⋮ A NEW SEQUENCE FORM APPROACH FOR THE ENUMERATION AND REFINEMENT OF ALL EXTREME NASH EQUILIBRIA FOR EXTENSIVE FORM GAMES ⋮ Limited lookahead in imperfect-information games ⋮ The complexity of computing a (quasi-)perfect equilibrium for an \(n\)-player extensive form game ⋮ Unnamed Item ⋮ Computer science and decision theory ⋮ On the computational consequences of independence in propositional logic ⋮ A Logic for Reasoning about Rational Agents ⋮ Finding mixed strategies with small supports in extensive form games ⋮ Reasoning about temporal properties of rational play ⋮ Computational complexity in additive hedonic games ⋮ Multi-agent reinforcement learning: a selective overview of theories and algorithms

Cites Work

• Complete inflation and perfect recall in extensive games
• Nash and correlated equilibria: Some complexity considerations
• Geometric algorithms and combinatorial optimization
• Finding mixed strategies with small supports in extensive form games
• An Overview of the Mathematical Theory of Games
• Computing Equilibria of Two-Person Games from the Extensive Form
• Extensive Games
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The complexity of two-person zero-sum games in extensive form