The complexity of mean payoff games on graphs

DOI10.1016/0304-3975(95)00188-3zbMath0871.68138OpenAlexW2026128612MaRDI QIDQ1351468

Uri Zwick, Mike S. Paterson

Publication date: 27 February 1997

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(95)00188-3

zbMATH Keywords

polynomial reductionpseudo-polynomial time algorithm

Mathematics Subject Classification ID

Game theory (91A99) Graph theory (including graph drawing) in computer science (68R10)

Related Items (only showing first 100 items - show all)

The Theory of Universal Graphs for Infinite Duration Games ⋮ Symmetric Strategy Improvement ⋮ Permissive strategies: from parity games to safety games ⋮ Minimum Attention Controller Synthesis for Omega-Regular Objectives ⋮ Tropicalizing the Simplex Algorithm ⋮ Graph Games and Reactive Synthesis ⋮ From Parity and Payoff Games to Linear Programming ⋮ Measuring Permissivity in Finite Games ⋮ Optimal strategy synthesis for request-response games ⋮ 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 ⋮ Unnamed Item ⋮ Parameterized Algorithms for Parity Games ⋮ Temporal Specifications with Accumulative Values ⋮ Approximating Min-Mean-Cycle for Low-Diameter Graphs in Near-Optimal Time and Memory ⋮ The Tropical Nullstellensatz and Positivstellensatz for Sparse Polynomial Systems ⋮ Parity Games and Propositional Proofs ⋮ On the comparison of discounted-sum automata with multiple discount factors ⋮ Tropical Linear Regression and Mean Payoff Games: Or, How to Measure the Distance to Equilibria ⋮ Reasoning about Quality and Fuzziness of Strategic Behaviors ⋮ A Simple P-Matrix Linear Complementarity Problem for Discounted Games ⋮ On the complexity of rational verification ⋮ Continuous Positional Payoffs ⋮ On the Existence of Stationary Nash Equilibria for Mean Payoff Games on Graphs ⋮ Optimal repair for omega-regular properties ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The stochastic arrival problem ⋮ Value Iteration ⋮ Token Games and History-Deterministic Quantitative-Automata ⋮ Solving mean-payoff games via quasi dominions ⋮ Unnamed Item ⋮ New algorithms for solving tropical linear systems ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Bounding Average-Energy Games ⋮ Constraint Satisfaction Problems over Numeric Domains ⋮ QUASY: Quantitative Synthesis Tool ⋮ Stochastic Mean Payoff Games: Smoothed Analysis and Approximation Schemes ⋮ The Cost of Traveling between Languages ⋮ Solving Mean-Payoff Games via Quasi Dominions ⋮ A survey of computational complexity results in systems and control ⋮ Max-Closed Semilinear Constraint Satisfaction ⋮ On Values of Games ⋮ Quantitative Simulation Games ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The Robot Routing Problem for Collecting Aggregate Stochastic Rewards ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On Solving Mean Payoff Games Using Pivoting Algorithms ⋮ Optimizing Winning Strategies in Regular Infinite Games ⋮ On Omega-Languages Defined by Mean-Payoff Conditions ⋮ Stochastic Müller Games are PSPACE-Complete ⋮ Solving Parity Games in Big Steps ⋮ Finite-range topical functions and uniformly topical functions ⋮ Deterministic Graphical Games Revisited ⋮ On Memoryless Quantitative Objectives ⋮ The Complexity of Nash Equilibria in Limit-Average Games ⋮ Time-Optimal Winning Strategies for Poset Games ⋮ Value Iteration Using Universal Graphs and the Complexity of Mean Payoff Games ⋮ Discrete control and algorithms for solving antagonistic dynamic games on networks ⋮ Parity Games: Zielonka's Algorithm in Quasi-Polynomial Time ⋮ Dynamic Observers for the Synthesis of Opaque Systems ⋮ Energy Games in Multiweighted Automata ⋮ Nash Equilibria Conditions for Cyclic Games with p Players ⋮ TROPICAL POLYHEDRA ARE EQUIVALENT TO MEAN PAYOFF GAMES ⋮ Hyperplane separation technique for multidimensional mean-payoff games ⋮ Equilibria for games with combined qualitative and quantitative objectives ⋮ Expected reachability-time games ⋮ Synthesizing Efficient Controllers ⋮ 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}\) ⋮ Looking at mean payoff through foggy windows ⋮ Tropically convex constraint satisfaction ⋮ USING STRATEGY IMPROVEMENT TO STAY ALIVE ⋮ A potential reduction algorithm for two-person zero-sum mean payoff stochastic games ⋮ Mean-payoff games with partial observation ⋮ An average polynomial algorithm for solving antagonistic games on graphs ⋮ Solving parity games in big steps ⋮ The fixed initial credit problem for partial-observation energy games is \textsc{Ack}-complete ⋮ The level set method for the two-sided max-plus eigenproblem ⋮ Strategy improvement for concurrent reachability and turn-based stochastic safety games ⋮ A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games ⋮ On canonical forms for zero-sum stochastic mean payoff games ⋮ Instantaneous reaction-time in dynamic consistency checking of conditional simple temporal networks ⋮ Optimal supervisory control with mean payoff objectives and under partial observation ⋮ Bidding mechanisms in graph games ⋮ Generic uniqueness of the bias vector of finite zero-sum stochastic games with perfect information ⋮ Safraless LTL synthesis considering maximal realizability ⋮ Solving generic nonarchimedean semidefinite programs using stochastic game algorithms

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Cyclical games with prohibitions
• Selection and sorting with limited storage
• Positional strategies for mean payoff games
• Cycles in extensive form perfect information games
• An \(O(n^ 2)\) algorithm for the maximum cycle mean of an \(n\times n\) bivalent matrix
• The complexity of stochastic games
• New scaling algorithms for the assignment and minimum mean cycle problems
• Undirected edge geography
• Geography
• Complexity of path-forming games
• A characterization of the minimum cycle mean in a digraph
• Strongly polynomial algorithms for finding minimax paths in networks and solution of cyclic games
• A subexponential randomized algorithm for the simple stochastic game problem
• Cyclic games and an algorithm to find minimax cycle means in directed graphs
• Every Prime Has a Succinct Certificate
• An optimal on-line algorithm for metrical task system
• Tighter Lower Bounds on the Exact Complexity of String Matching
• Faster parametric shortest path and minimum‐balance algorithms
• Stochastic Games

This page was built for publication: The complexity of mean payoff games on graphs