Document Open Access Logo

To Reach or not to Reach? Efficient Algorithms for Total-Payoff Games

Authors Thomas Brihaye, Gilles Geeraerts, Axel Haddad, Benjamin Monmege

PDF
Thumbnail PDF

File

LIPIcs.CONCUR.2015.297.pdf
  • Filesize: 0.57 MB
  • 14 pages

Document Identifiers

Author Details

Thomas Brihaye
Gilles Geeraerts
Axel Haddad
Benjamin Monmege

Cite As Get BibTex

Thomas Brihaye, Gilles Geeraerts, Axel Haddad, and Benjamin Monmege. To Reach or not to Reach? Efficient Algorithms for Total-Payoff Games. In 26th International Conference on Concurrency Theory (CONCUR 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 42, pp. 297-310, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015) https://doi.org/10.4230/LIPIcs.CONCUR.2015.297

Abstract

Quantitative games are two-player zero-sum games played on directed weighted graphs. Total-payoff games - that can be seen as a refinement of the well-studied mean-payoff games - are the variant where the payoff of a play is computed as the sum of the weights. Our aim is to describe the first pseudo-polynomial time algorithm for total-payoff games in the presence of arbitrary weights. It consists of a non-trivial application of the value iteration paradigm. Indeed, it requires to study, as a milestone, a refinement of these games, called min-cost reachability games, where we add a reachability objective to one of the players. For these games, we give an efficient value iteration algorithm to compute the values and optimal strategies (when they exist), that runs in pseudo-polynomial time. We also propose heuristics to speed up the computations.

Subject Classification

Keywords
  • Games on graphs
  • reachability
  • quantitative games
  • value iteration

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Henrik Björklund and Sergei Vorobyov. A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games. Discrete Applied Mathematics, 155:210-229, 2007. Google Scholar
  2. Thomas Brihaye, Gilles Geeraerts, Axel Haddad, and Benjamin Monmege. To reach or not to reach? Efficient algorithms for total-payoff games. Research Report 1407.5030, arXiv, July 2014. Google Scholar
  3. Thomas Brihaye, Gilles Geeraerts, Shankara Narayanan Krishna, Lakshmi Manasa, Benjamin Monmege, and Ashutosh Trivedi. Adding negative prices to priced timed games. In Proceedings of the 25th International Conference on Concurrency Theory (CONCUR'14), volume 8704 of Lecture Notes in Computer Science, pages 560-575. Springer, 2014. Google Scholar
  4. Luboš Brim, Jakub Chaloupka, Laurent Doyen, Rafaella Gentilini, and Jean-François Raskin. Faster algorithms for mean-payoff games. Formal Methods for System Design, 38(2):97-118, 2011. Google Scholar
  5. Taolue Chen, Vojtěch Forejt, Marta Kwiatkowska, David Parker, and Aistis Simaitis. Automatic verification of competitive stochastic systems. Formal Methods in System Design, 43(1):61-92, 2013. Google Scholar
  6. Carlo Comin and Romeo Rizzi. An improved pseudo-polynomial upper bound for the value problem and optimal strategy synthesis in mean payoff games. Technical Report 1503.04426, arXiv, 2015. Google Scholar
  7. Andrzej Ehrenfeucht and Jan Mycielski. Positional strategies for mean payoff games. International Journal of Game Theory, 8(2):109-113, 1979. Google Scholar
  8. Emmanuel Filiot, Rafaella Gentilini, and Jean-François Raskin. Quantitative languages defined by functional automata. In Proceedings of the 23rd International Conference on Concurrency theory (CONCUR'12), volume 7454 of Lecture Notes in Computer Science, pages 132-146. Springer, 2012. Google Scholar
  9. Thomas Martin Gawlitza and Helmut Seidl. Games through nested fixpoints. In Proceedings of the 21st International Conference on Computer Aided Verification (CAV'09), volume 5643 of Lecture Notes in Computer Science, pages 291-305. Springer, 2009. Google Scholar
  10. Hugo Gimbert and Wiesław Zielonka. When can you play positionally? In Proceedings of the 29th International Conference on Mathematical Foundations of Computer Science (MFCS'04), volume 3153 of Lecture Notes in Computer Science, pages 686-698. Springer, 2004. Google Scholar
  11. Leonid Khachiyan, Endre Boros, Konrad Borys, Khaled Elbassioni, Vladimir Gurvich, Gabor Rudolf, and Jihui Zhao. On short paths interdiction problems: Total and node-wise limited interdiction. Theory of Computing Systems, 43:204-233, 2008. Google Scholar
  12. Donald A. Martin. Borel determinacy. Annals of Mathematics, 102(2):363-371, 1975. Google Scholar
  13. Martin L. Puterman. Markov Decision Processes. John Wiley & Sons, Inc., New York, NY, 1994. Google Scholar
  14. Ralph E. Strauch. Negative dynamic programming. The Annals of Mathematical Statistics, 37:871-890, 1966. Google Scholar
  15. Robert E. Tarjan. Depth first search and linear graph algorithms. SIAM Journal on Computing, 1(2):146-160, 1972. Google Scholar
  16. Wolfgang Thomas. On the synthesis of strategies in infinite games. In Symposium on Theoretical Aspects of Computer Science (STACS'95), volume 900 of Lecture Notes in Computer Science, pages 1-13. Springer, 1995. Google Scholar
  17. Uri Zwick and Michael S. Paterson. The complexity of mean payoff games. Theoretical Computer Science, 158:343-359, 1996. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact