Cyclic games and an algorithm to find minimax cycle means in directed graphs
From MaRDI portal
Publication:3471889
DOI10.1016/0041-5553(88)90012-2zbMath0695.90105OpenAlexW2008632553MaRDI QIDQ3471889
Alexander V. Karzanov, Leonid G. Khachiyan, Vladimir A. Gurvich
Publication date: 1988
Published in: USSR Computational Mathematics and Mathematical Physics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0041-5553(88)90012-2
cyclic gamevalueperfect informationdirected bipartite graphpure stationary strategiesTwo-person zero-sum stochastic gamesminimax mean cycle
Related Items (57)
TROPICAL POLYHEDRA ARE EQUIVALENT TO MEAN PAYOFF GAMES ⋮ Hyperplane separation technique for multidimensional mean-payoff games ⋮ The Theory of Universal Graphs for Infinite Duration Games ⋮ Memoryless determinacy of parity and mean payoff games: a simple proof ⋮ Deciding the winner in parity games is in \(\mathrm{UP}\cap\mathrm{co-UP}\) ⋮ Tropicalizing the Simplex Algorithm ⋮ The complexity of mean payoff games on graphs ⋮ USING STRATEGY IMPROVEMENT TO STAY ALIVE ⋮ Equilibria in nonantagonistic positional games on graphs and searching for them ⋮ From Parity and Payoff Games to Linear Programming ⋮ Exponential examples of solving parity games ⋮ An average polynomial algorithm for solving antagonistic games on graphs ⋮ Tropical Fourier–Motzkin elimination, with an application to real-time verification ⋮ A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games ⋮ On canonical forms for zero-sum stochastic mean payoff games ⋮ The Complexity of Infinitely Repeated Alternating Move Games ⋮ Robust worst cases for parity games algorithms ⋮ 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 ⋮ The complexity of mean payoff games ⋮ On Nash equilibria and improvement cycles in pure positional strategies for chess-like and backgammon-like \(n\)-person games ⋮ Continuous Positional Payoffs ⋮ On the Existence of Stationary Nash Equilibria for Mean Payoff Games on Graphs ⋮ Solving mean-payoff games via quasi dominions ⋮ Tropical linear-fractional programming and parametric mean payoff games ⋮ New algorithms for solving tropical linear systems ⋮ Unnamed Item ⋮ Nash-solvable two-person symmetric cycle game forms ⋮ On Nash-solvability in pure stationary strategies of the deterministic \(n\)-person games with perfect information and mean or total effective cost ⋮ Unnamed Item ⋮ Optimal paths in network games with \(p\) players ⋮ A note on the approximation of mean-payoff games ⋮ On discounted approximations of undiscounted stochastic games and Markov decision processes with limited randomness ⋮ On short paths interdiction problems: Total and node-wise limited interdiction ⋮ Polynomial-time algorithms for energy games with special weight structures ⋮ Cyclic games and linear programming ⋮ Scientific contributions of Leo Khachiyan (a short overview) ⋮ Solving parity games via priority promotion ⋮ Stochastic Mean Payoff Games: Smoothed Analysis and Approximation Schemes ⋮ A nested family of \(k\)-total effective rewards for positional games ⋮ Solving Mean-Payoff Games via Quasi Dominions ⋮ Improved pseudo-polynomial bound for the value problem and optimal strategy synthesis in mean payoff games ⋮ Approximation schemes for stochastic mean payoff games with perfect information and few random positions ⋮ Approximating the minimum cycle mean ⋮ Faster algorithms for mean-payoff games ⋮ A delayed promotion policy for parity games ⋮ Unnamed Item ⋮ On Solving Mean Payoff Games Using Pivoting Algorithms ⋮ On Memoryless Quantitative Objectives ⋮ Value Iteration Using Universal Graphs and the Complexity of Mean Payoff Games ⋮ Discrete control and algorithms for solving antagonistic dynamic games on networks ⋮ The GKK algorithm is the fastest over simple mean-payoff games ⋮ Qualitative analysis of concurrent mean-payoff games ⋮ Looking at mean-payoff and total-payoff through windows ⋮ Nash Equilibria Conditions for Cyclic Games with p Players ⋮ On Nash Equilibria in Stochastic Positional Games with Average Payoffs ⋮ Combinatorial structure and randomized subexponential algorithms for infinite games
This page was built for publication: Cyclic games and an algorithm to find minimax cycle means in directed graphs
