Document Open Access Logo

Quantitative Games under Failures

Authors Thomas Brihaye, Gilles Geeraerts, Axel Haddad, Benjamin Monmege, Guillermo A. Pérez, Gabriel Renault

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2015.293.pdf
  • Filesize: 0.59 MB
  • 14 pages

Document Identifiers

Author Details

Thomas Brihaye
Gilles Geeraerts
Axel Haddad
Benjamin Monmege
Guillermo A. Pérez
Gabriel Renault

Cite As Get BibTex

Thomas Brihaye, Gilles Geeraerts, Axel Haddad, Benjamin Monmege, Guillermo A. Pérez, and Gabriel Renault. Quantitative Games under Failures. In 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 45, pp. 293-306, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015) https://doi.org/10.4230/LIPIcs.FSTTCS.2015.293

Abstract

We study a generalisation of sabotage games, a model of dynamic network games introduced by van Benthem. The original definition of the game is inherently finite and therefore does not allow one to model infinite processes. We propose an extension of the sabotage games in which the first player (Runner) traverses an arena with dynamic weights determined by the second player (Saboteur). In our model of quantitative sabotage games, Saboteur is now given a budget that he can distribute amongst the edges of the graph, whilst Runner attempts to minimise the quantity of budget witnessed while completing his task. We show that, on the one hand, for most of the classical cost functions considered in the literature, the problem of determining if Runner has a strategy to ensure a cost below some threshold is EXPTIME-complete. On the other hand, if the budget of Saboteur is fixed a priori, then the problem is in PTIME for most cost functions. Finally, we show that restricting the dynamics of the game also leads to better complexity.

Subject Classification

Keywords
  • Quantitative games
  • verification
  • synthesis
  • game theory

Metrics

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

References

  1. Krzysztof R. Apt and Erich Grädel. Lectures in game theory for computer scientists. Cambridge University Press, 2011. Google Scholar
  2. Thomas Brihaye, Gilles Geeraerts, Axel Haddad, Benjamin Monmege, Guillermo A. Pérez, and Gabriel Renault. Quantitative games under failures. Research Report 1504.06744, arXiv, April 2015. Google Scholar
  3. Krishnendu Chatterjee, Laurent Doyen, and Thomas A. Henzinger. Quantitative languages. ACM Trans. Comput. Log., 11(4), 2010. Google Scholar
  4. Krishnendu Chatterjee, Thomas A. Henzinger, and Marcin Jurdzinski. Mean-payoff parity games. In LICS, pages 178-187. IEEE, 2005. Google Scholar
  5. A. Ehrenfeucht and J. Mycielski. Positional strategies for mean payoff games. International Journal of Game Theory, 8:109-113, 1979. Google Scholar
  6. Arthur S. Goldstein and Edward M. Reingold. The complexity of pursuit on a graph. Theor. Comput. Sci., 143(1):93 - 112, 1995. Google Scholar
  7. Sten Grüner, Frank G. Radmacher, and Wolfgang Thomas. Connectivity games over dynamic networks. Theor. Comput. Sci., 493:46-65, 2013. Google Scholar
  8. Marcin Jurdziński. Deciding the winner in parity games is in \UP ∩ \coUP. Information Processing Letters, 68(3):119-124, 1998. Google Scholar
  9. Richard M. Karp. Reducibility among combinatorial problems. In Proceedings of a Symposium on the Complexity of Computer Computations, pages 85-103, 1972. Google Scholar
  10. Dominik Klein, Frank G. Radmacher, and Wolfgang Thomas. Moving in a network under random failures: A complexity analysis. Science of Comp. Prog., 77(7-8):940-954, 2012. Google Scholar
  11. Lena Maria Kurzen. Complexity in interaction. PhD thesis, Institute for Logic, Language and Computation, 2011. Google Scholar
  12. Christof Löding and Philipp Rohde. Solving the sabotage game is PSPACE-hard. In MFCS, volume 2747 of LNCS, pages 531-540. Springer, 2003. Google Scholar
  13. Donald A Martin. Borel determinacy. Annals of Mathematics, 102(2):363-371, 1975. Google Scholar
  14. Merlijn Sevenster. Branches of imperfect information: logic, games, and computation. PhD thesis, Institute for Logic, Language and Computation, 2006. Google Scholar
  15. Larry J. Stockmeyer and Ashok K. Chandra. Provably difficult combinatorial games. SIAM J. Comput., 8(2):151-174, 1979. Google Scholar
  16. Johan van Benthem. An essay on sabotage and obstruction. In Mechanizing Mathematical Reasoning, volume 2605 of LNAI, pages 268-276. Springer, 2005. Google Scholar
  17. Masafumi Yamashita and Ichiro Suzuki. Characterizing geometric patterns formable by oblivious anonymous mobile robots. Theor. Comput. Sci., 411(26-28):2433-2453, 2010. Google Scholar
  18. Uri Zwick and Michael S. Paterson. The complexity of mean payoff games. Theor. Comput. Sci., 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