Efficient computation of equilibria for extensive two-person games

DOI10.1006/GAME.1996.0051zbMATH Open0859.90127OpenAlexW2086386133MaRDI QIDQ1815001FDOQ1815001

Daphne Koller, Nimrod Megiddo, Bernhard von Stengel

Publication date: 10 April 1997

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

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.9.4639

zbMATH Keywords

Nash equilibriaLemke's algorithmlinear complementarity

Mathematics Subject Classification ID

2-person games (91A05) Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) (90C33)

Cited In (34)

• Limited lookahead in imperfect-information games
• Approximating maxmin strategies in imperfect recall games using A-loss recall property
• Nondominated equilibrium solutions of a multiobjective two-person nonzero-sum game in extensive form and corresponding mathematical programming problem
• The complexity of computing a (quasi-)perfect equilibrium for an \(n\)-player extensive form game
• Polytope-form games and index/degree theories for extensive-form games
• Algorithms for computing strategies in two-player simultaneous move games
• New complexity results about Nash equilibria
• Exploiting extensive-form structure in empirical game-theoretic analysis
• Good neighbors are hard to find: Computational complexity of network formation
• Representations and solutions for game-theoretic problems
• Computing sequential equilibria using agent quantal response equilibria
• The Computational Complexity of Trembling Hand Perfection and Other Equilibrium Refinements
• Conditional dominance, rationalizability, and game forms
• Computational complexity of computing a quasi-proper equilibrium
• On taxed matrix games and changes in the expected transfer
• The give and take game: analysis of a resource sharing game
• Homotopy methods to compute equilibria in game theory
• Computing a quasi-perfect equilibrium of a two-player game
• Solving for Best Responses and Equilibria in Extensive-Form Games with Reinforcement Learning Methods
• Computational complexity in additive hedonic games
• A Complementary Pivot Algorithm for Market Equilibrium under Separable, Piecewise-Linear Concave Utilities
• Patrolling security games: definition and algorithms for solving large instances with single patroller and single intruder
• Polynomial-time computation of exact correlated equilibrium in compact games
• Faster algorithms for extensive-form game solving via improved smoothing functions
• Computing lexicographically safe Nash equilibria in finite two-person games with tight game forms given by oracles
• Solving zero-sum one-sided partially observable stochastic games
• Multi-agent reinforcement learning: a selective overview of theories and algorithms
• Online learning in sequential Bayesian persuasion: handling unknown priors
• The complexity of two-person zero-sum games in extensive form
• The Effective Computation of Equilibrium Point for N-Person Games Cyclic to the Next Person
• The value of large extensive form games
• Simple uncoupled no-regret learning dynamics for extensive-form correlated equilibrium
• Bargaining with limited computation: Deliberation equilibrium
• A theoretical and empirical investigation of search in imperfect information games

   Recommendations

• Equilibrium computation for two-player games in strategic and extensive form 👍 👎
• Computing Normal Form Perfect Equilibria for Extensive Two-Person Games 👍 👎
• Computing a quasi-perfect equilibrium of a two-player game 👍 👎
• Efficient computation of behavior strategies 👍 👎

This page was built for publication: Efficient computation of equilibria for extensive two-person games

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