The complexity of mean payoff games on graphs

From MaRDI portal

Publication:1351468

Jump to:navigation, search

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 reduction pseudo-polynomial time algorithm

Mathematics Subject Classification ID

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

Related Items

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, Mean-payoff games with \(\omega\)-regular specifications, Average-energy games, Robust worst cases for parity games algorithms, Reachability games with relaxed energy constraints, 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, Cooperative concurrent games, Randomness for free, A survey of stochastic \(\omega \)-regular games, Solving parity games by a reduction to SAT, Unique end of potential line, The complexity of stochastic Müller games, Automated competitive analysis of real-time scheduling with graph games, On strategy improvement algorithms for simple stochastic games, Tropical linear-fractional programming and parametric mean payoff games, Checking dynamic consistency of conditional hyper temporal networks via mean payoff games. Hardness and (pseudo) singly-exponential time algorithm, Hyper temporal networks. A tractable generalization of simple temporal networks and its relation to mean payoff games, Computing branching distances with quantitative games, Synthesis of opaque systems with static and dynamic masks, Equilibria, fixed points, and complexity classes, A superpolynomial lower bound for strategy iteration based on snare memorization, 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, The quantitative linear-time-branching-time spectrum, The per-character cost of repairing word languages, Interface simulation distances, Stochastic limit-average games are in EXPTIME, Polynomial-time algorithms for energy games with special weight structures, Cyclic games and linear programming, Concurrent reachability games, Solving parity games via priority promotion, Minimal sensor activation and minimal communication in discrete-event systems, An exponential lower bound for Cunningham's rule, Determining the optimal strategies for zero-sum average stochastic positional games, The tropical analogue of the Helton-Nie conjecture is true, Reactive synthesis without regret, Pseudopolynomial iterative algorithm to solve total-payoff games and min-cost reachability games, A nested family of \(k\)-total effective rewards for positional games, Optimal infinite scheduling for multi-priced timed automata, Strategy synthesis for multi-dimensional quantitative objectives, Synthesizing robust systems, 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, Quantitative fair simulation games, First-cycle games, Meet your expectations with guarantees: beyond worst-case synthesis in quantitative games, Approximating the minimum cycle mean, Energy parity games, Reduction of stochastic parity to stochastic mean-payoff games, Faster algorithms for mean-payoff games, Planning and acting in partially observable stochastic domains, Tropical polar cones, hypergraph transversals, and mean payoff games, Mean-payoff games and propositional proofs, A delayed promotion policy for parity games, A general approach for optimizing dynamic sensor activation for discrete event systems, Quantitative reductions and vertex-ranked infinite games, Recursive Markov Decision Processes and Recursive Stochastic Games, Quantitative simulations by matrices, Estimation of the complexity of the potential transformation algorithm for solving cyclic games on graphs, A constructive algorithm for max-min paths problems on energy networks, On satisficing in quantitative games, Deciding probabilistic bisimilarity distance one for probabilistic automata, What's decidable about weighted automata?, Simulation distances, Model checking discounted temporal properties, The GKK algorithm is the fastest over simple mean-payoff games, The complexity of multi-mean-payoff and multi-energy games, Qualitative analysis of concurrent mean-payoff games, Looking at mean-payoff and total-payoff through windows, Comparison of algorithms for simple stochastic games, Contingent planning under uncertainty via stochastic satisfiability, An efficient algorithm for a class of constraint satisfaction problems, Combinatorial structure and randomized subexponential algorithms for infinite games, 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

Cites Work

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Publication:1351468&oldid=13488313"