A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games

DOI10.1016/J.DAM.2006.04.029zbMath1176.68087OpenAlexW2114657710MaRDI QIDQ867862

Sergei Vorobyov, Henrik Björklund

Publication date: 19 February 2007

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2006.04.029

zbMATH Keywords

cyclic gameergodic partitioniterative improvementcombinatorial linear programminglongest shortest pathmean payoff gameparity gamerandomized subexponential algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Noncooperative games (91A10) 2-person games (91A05) Games involving graphs (91A43) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (39)

TROPICAL POLYHEDRA ARE EQUIVALENT TO MEAN PAYOFF GAMES ⋮ Symmetric Strategy Improvement ⋮ Tropicalizing the Simplex Algorithm ⋮ The mu-calculus and Model Checking ⋮ USING STRATEGY IMPROVEMENT TO STAY ALIVE ⋮ From Parity and Payoff Games to Linear Programming ⋮ An average polynomial algorithm for solving antagonistic games on graphs ⋮ Solving parity games in big steps ⋮ The level set method for the two-sided max-plus eigenproblem ⋮ Tropical Fourier–Motzkin elimination, with an application to real-time verification ⋮ Incentive Stackelberg Mean-Payoff Games ⋮ The Complexity of Infinitely Repeated Alternating Move Games ⋮ Unnamed Item ⋮ Parameterized Algorithms for Parity Games ⋮ A pseudo-polynomial algorithm for mean payoff stochastic games with perfect information and few random positions ⋮ A convex programming-based algorithm for mean payoff stochastic games with perfect information ⋮ Abstract tropical linear programming ⋮ Tropical Linear Regression and Mean Payoff Games: Or, How to Measure the Distance to Equilibria ⋮ Improved complexity analysis of quasi-polynomial algorithms solving parity games ⋮ Synthesising Strategy Improvement and Recursive Algorithms for Solving 2.5 Player Parity Games ⋮ Solving mean-payoff games via quasi dominions ⋮ Tropical linear-fractional programming and parametric mean payoff games ⋮ Hyper temporal networks. A tractable generalization of simple temporal networks and its relation to mean payoff games ⋮ Unnamed Item ⋮ A superpolynomial lower bound for strategy iteration based on snare memorization ⋮ A note on the approximation of mean-payoff games ⋮ On short paths interdiction problems: Total and node-wise limited interdiction ⋮ Computation of weighted sums of rewards for concurrent MDPs ⋮ Polynomial-time algorithms for energy games with special weight structures ⋮ Cyclic games and linear programming ⋮ Pseudopolynomial iterative algorithm to solve total-payoff games and min-cost reachability games ⋮ Solving Mean-Payoff Games via Quasi Dominions ⋮ Faster algorithms for mean-payoff games ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On Solving Mean Payoff Games Using Pivoting Algorithms ⋮ Solving Parity Games in Big Steps ⋮ Parity Games: Zielonka's Algorithm in Quasi-Polynomial Time ⋮ Looking at mean-payoff and total-payoff through windows

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Combinatorial structure and randomized subexponential algorithms for infinite games
• Completely unimodal numberings of a simple polytope
• Positional strategies for mean payoff games
• The complexity of stochastic games
• Extensions of two person zero sum games
• The complexity of mean payoff games on graphs
• Memoryless determinacy of parity and mean payoff games: a simple proof
• A subexponential randomized algorithm for the simple stochastic game problem
• A subexponential bound for linear programming
• Mean Cost Cyclical Games
• Extending Dijkstra’s Algorithm to Maximize the Shortest Path by Node-Wise Limited Arc Interdiction
• Cyclic games and an algorithm to find minimax cycle means in directed graphs
• Linear Programming Polytope and Algorithm for Mean Payoff Games
• On Nonterminating Stochastic Games
• Perspectives of System Informatics
• On model checking for the \(\mu\)-calculus and its fragments

This page was built for publication: A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games