Fast algorithms for finding randomized strategies in game trees

DOI10.1145/195058.195451MaRDI QIDQ2817671zbMATH OpenOpenAlexFDO

Authors Daphne Koller, Nimrod Megiddo, Bernhard von Stengel

Publication date 1 September 2016

Published in Proceedings of the twenty-sixth annual ACM symposium on Theory of computing - STOC '94 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/195058.195451

Mathematics Subject Classification ID

Agent technology and artificial intelligence (68T42) Linear programming (90C05) 2-person games (91A05) Applications of game theory (91A80)

Recommendations

• Finding Equilibria in Games of No Chance
• Finding mixed strategies with small supports in extensive form games
• Efficient computation of behavior strategies
• Computing a quasi-perfect equilibrium of a two-player game
• Computing Normal Form Perfect Equilibria for Extensive Two-Person Games

Cited in

(30)

• Extending the alternating-offers protocol in the presence of competition: Models and theoretical analysis
• Game tree searching by min/max approximation
• On sparse approximations to randomized strategies and convex combinations
• Searching minimax game trees under memory space constraint
• Representations and solutions for game-theoretic problems
• Multi-agent influence diagrams for representing and solving games.
• Simulating cardinal preferences in Boolean games: a proof technique
• Computing human-understandable strategies: deducing fundamental rules of poker strategy
• Approximating maxmin strategies in imperfect recall games using A-loss recall property
• Finding mixed strategies with small supports in extensive form games
• A sublinear-time randomized approximation algorithm for matrix games
• Multi-agent reinforcement learning: a selective overview of theories and algorithms
• Game theoretic resource allocation model for designing effective traffic safety solution against drunk driving
• Automated construction of bounded-loss imperfect-recall abstractions in extensive-form games
• Alternating-offers bargaining with one-sided uncertain deadlines: an efficient algorithm
• Algorithms for computing strategies in two-player simultaneous move games
• A Dynamic Algorithm for Reachability Games Played on Trees
• Parallel approximation of min-max problems
• The Variance of Two Game Tree Algorithms
• Randomized sampling for large zero-sum games
• From duels to battlefields: computing equilibria of Blotto and other games
• COMPACT REPRESENTATIONS OF SEARCH IN COMPLEX DOMAINS
• COMPACT REPRESENTATIONS OF SEARCH IN COMPLEX DOMAINS
• A choice of strategy in nondeterministic antagonistic games
• A new lower bound for the list update problem in the partial cost model
• Equilibrium semantics of languages of imperfect information
• HSVI can solve zero-sum partially observable stochastic games
• On the complexity of computing sparse equilibria and lower bounds for no-regret learning in games
• Quadratic programming approach for Nash equilibrium computation in multiplayer imperfect-information games
• Computing a quasi-perfect equilibrium of a two-player game

This page was built for publication: Fast algorithms for finding randomized strategies in game trees

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