Symmetric strategy improvement
From MaRDI portal
Publication:3449491
Abstract: Symmetry is inherent in the definition of most of the two-player zero-sum games, including parity, mean-payoff, and discounted-payoff games. It is therefore quite surprising that no symmetric analysis techniques for these games exist. We develop a novel symmetric strategy improvement algorithm where, in each iteration, the strategies of both players are improved simultaneously. We show that symmetric strategy improvement defies Friedmann's traps, which shook the belief in the potential of classic strategy improvement to be polynomial.
Recommendations
Cites work
- scientific article; zbMATH DE number 1670778 (Why is no real title available?)
- scientific article; zbMATH DE number 1223729 (Why is no real title available?)
- scientific article; zbMATH DE number 549853 (Why is no real title available?)
- scientific article; zbMATH DE number 1500523 (Why is no real title available?)
- A Deterministic Subexponential Algorithm for Solving Parity Games
- A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games
- A subexponential lower bound for Zadeh's pivoting rule for solving linear programs and games
- A subexponential randomized algorithm for the simple stochastic game problem
- A superpolynomial lower bound for strategy iteration based on snare memorization
- Alternating tree automata, parity games, and modal \(\mu\)-calculus
- Alternating-time temporal logic
- An Optimal Strategy Improvement Algorithm for Solving Parity and Payoff Games
- An exponential lower bound for the latest deterministic strategy iteration algorithms
- An improved algorithm for the evaluation of fixpoint expressions
- DAG-Width and Parity Games
- Exponential lower bounds for policy iteration
- Fast mu-calculus model checking when tree-width is bounded.
- From Nondeterministic B\"uchi and Streett Automata to Deterministic Parity Automata
- Infinite games on finitely coloured graphs with applications to automata on infinite trees
- Infinite games played on finite graphs
- Non-oblivious strategy improvement
- Results on the propositional \(\mu\)-calculus
- Satisfiability and Finite Model Property for the Alternating-Time μ-Calculus
- Solving Parity Games in Big Steps
- Symmetric strategy improvement
- Synthesis of Asynchronous Systems
- The complexity of mean payoff games on graphs
Cited in
(10)- scientific article; zbMATH DE number 7533361 (Why is no real title available?)
- Synthesising strategy improvement and recursive algorithms for solving 2.5 player parity games
- Parity games with weights
- A delayed promotion policy for parity games
- A delayed promotion policy for parity games
- Priority promotion with Parysian flair
- Hyper temporal networks. A tractable generalization of simple temporal networks and its relation to mean payoff games
- Improvement in small progress measures
- Non-oblivious strategy improvement
- Symmetric strategy improvement
This page was built for publication: Symmetric strategy improvement
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3449491)
