Practical exact algorithm for trembling-hand equilibrium refinements in games
Nash equilibrium strategies have the known weakness that they do not prescribe rational play in situations that are reached with zero probability according to the strategies themselves, for example, if players have made mistakes. Trembling-hand refinements---such as extensive-form perfect equilibria and quasi-perfect equilibria---remedy this problem in sound ways. Despite their appeal, they have not received attention in practice since no known algorithm for computing them scales beyond toy instances. In this paper, we design an exact polynomial-time algorithm for finding trembling-hand equilibria in zero-sum extensive-form games. It is several orders of magnitude faster than the best prior ones, numerically stable, and quickly solves game instances with tens of thousands of nodes in the game tree. It enables, for the first time, the use of trembling-hand refinements in practice.
Code (0)
등록된 구현이 없습니다.
Tasks
FormSimilar Papers 제목 키워드 기반
Player-Compatible Learning and Player-Compatible Equilibrium
Player-Compatible Equilibrium (PCE) imposes cross-player restrictions on the magnitudes of the players' "trembles" onto different strategies. These restrictions capture the idea that trembles correspond to deliberate exp…
Reinforcement Learning for Mean Field Games with Strategic Complementarities
Mean Field Games (MFG) are the class of games with a very large number of agents and the standard equilibrium concept is a Mean Field Equilibrium (MFE). Algorithms for learning MFE in dynamic MFGs are unknown in general.…
reinforcement-learningReinforcement LearningReinforcement Learning (RL)Equilibrium Refinements for Multi-Agent Influence Diagrams: Theory and Practice
Multi-agent influence diagrams (MAIDs) are a popular form of graphical model that, for certain classes of games, have been shown to offer key complexity and explainability advantages over traditional extensive form game …
FormImplementations of Cooperative Games Under Non-Cooperative Solution Concepts
Cooperative games can be distinguished as non-cooperative games in which players can freely sign binding agreements to form coalitions. These coalitions inherit a joint strategy set and seek to maximize collective payoff…
AllFormObservable Perfect Equilibrium
While Nash equilibrium has emerged as the central game-theoretic solution concept, many important games contain several Nash equilibria and we must determine how to select between them in order to create real strategic a…