Fast algorithms for finding randomized strategies in game trees

By Daphne Koller, N. Megiddo, Bernhard von Stengel. 1994

Subfields: Game & Decision Theory, Algorithms & Complexity

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Game & Decision Theory

In Algorithms & Complexity

Citations in the corpus

Frank-Wolfe Algorithms for Saddle Point Problems (2016, background): “When a strategy space involves a polynomial number of constraints, the equilibria of such games can be solved efficiently (Koller et al., 1994).”
OpenSpiel: A Framework for Reinforcement Learning in Games (2019, background): “extensive-form games ([31] and [63, Section 5]), and an algorithm to check whether an action is dominated by a mixture of other strategies in a normal-form [63, Sec 4.”
A Unified Game-Theoretic Approach to Multiagent Reinforcement Learning (2017, methodology): “To compute this number, the exact Nash equilibrium was obtained using sequence-form linear programming [51]; see also [90, Section 5.”
Fictitious Self-Play in Extensive-Form Games (2015, background): “The sequence-form (Koller et al., 1994; Von Stengel, 1996) of a game decomposes players’ strategies into sequences of actions and probabilities of realizing these sequences.”
Dynamic Programming for Partially Observable Stochastic Games (2004, background): “A notable exception is reported in [14, 15], in which the authors take advantage of the sequence form representation of two-player games to find mixed strategy Nash equilibria efficiently.”
Decentralized POMDPs (2012, methodology): “In order to address this problem Boularias and Chaib-draa (2008) represent these values more compactly by making use of a sequence form (Koller et al, 1994) representation.”
Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms (2019, background): “Furthermore, when it comes to zero-sum games with imperfect information, [245, 246, 247, 248] have proposed to transform extensive-form games into normal-form games using the sequence form representation, which enables equilibrium finding via linear programming.”
Monte Carlo Sampling for Regret Minimization in Extensive Games (2009, methodology): “Multiple techniques [1, 2] now exist for solving games with up to 1012 game states, which is about four orders of magnitude larger than the previous state-of-the-art of using sequence-form linear programs [ 3 ].”
Provable Self-Play Algorithms for Competitive Reinforcement Learning (2020, background): “…( φ, ψ ) ∈ ∆ A × ∆ B for zero-sum game, which satisﬁes This problem can by solved efﬁciently (in polynomial time) by many existing algorithms designed for convex-concave optimization (see, e.g. (Koller, 1994)), and does not suffer from the PPAD-completeness that N ASH G ENERAL S UM does.”
Computing Approximate Equilibria in Sequential Adversarial Games by Exploitability Descent (2019, methodology): “There have two main techniques used to solve adversarial games in this case: the ﬁrst is to rely on the sequence-form representation of policies which makes the optimization problem convex [ Koller et al. , 1994; Hoda et al. , 2007].”
Playing large games using simple strategies (2003, unknown): “We also show that the payo.s to all players in any (exact) Nash equilibrium can be E-approximated by the payo.s to the players in some such logarithmic support E-Nash equilibrium.”
Playing games for security: an efficient exact algorithm for solving Bayesian Stackelberg games (2008, background): “Furthermore, [8, 9] have not focused on computing optimal response in stackelberg games, but rather in only finding equilibria.”
Algorithms for Sequential Decision Making (1996, methodology): “Koller, Megiddo, and von Stengel [82, 84, 83] looked closely at games of partial information.”