Solving mean-payoff games via quasi dominions

DOI10.1016/j.ic.2024.105151arXiv1907.06264OpenAlexW4391252080WikidataQ129283761 ScholiaQ129283761MaRDI QIDQ6204169

Daniele Dell'Erba, Fabio Mogavero, Massimo Benerecetti

Publication date: 27 March 2024

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1907.06264

Mathematics Subject Classification ID

2-person games (91A05) Games involving graphs (91A43) Algorithmic game theory and complexity (91A68)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Deciding the winner in parity games is in \(\mathrm{UP}\cap\mathrm{co-UP}\)
• Improved pseudo-polynomial bound for the value problem and optimal strategy synthesis in mean payoff games
• Faster algorithms for mean-payoff games
• A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games
• Positional strategies for mean payoff games
• The complexity of stochastic games
• The complexity of mean payoff games on graphs
• Hyper temporal networks. A tractable generalization of simple temporal networks and its relation to mean payoff games
• Solving parity games via priority promotion
• PRIMES is in P
• A delayed promotion policy for parity games
• Sur le théorème de Zorn
• Mean Cost Cyclical Games
• USING STRATEGY IMPROVEMENT TO STAY ALIVE
• Non-oblivious Strategy Improvement
• Beyond the flow decomposition barrier
• Tropicalizing the Simplex Algorithm
• Cyclic games and an algorithm to find minimax cycle means in directed graphs
• An Optimal Strategy Improvement Algorithm for Solving Parity and Payoff Games
• Infinite Runs in Weighted Timed Automata with Energy Constraints
• Better Quality in Synthesis through Quantitative Objectives
• Solving Parity Games in Practice
• Faster scaling algorithms for general graph matching problems
• Solving Parity Games via Priority Promotion
• Scaling Algorithms for the Shortest Paths Problem
• Solving Mean-Payoff Games via Quasi Dominions
• The Tropical Shadow-Vertex Algorithm Solves Mean Payoff Games in Polynomial Time on Average
• Combinatorial Simplex Algorithms Can Solve Mean Payoff Games
• Mathematical Foundations of Computer Science 2004
• Synthesis from LTL Specifications with Mean-Payoff Objectives
• Beweisstudien zum Satz von M. Zorn. Herrn Erhard. Schmidt zum 75. Geburtstag gewidmet
• Liminf progress measures

This page was built for publication: Solving mean-payoff games via quasi dominions