Document Open Access Logo

Admissibility in Quantitative Graph Games

Authors Romain Brenguier, Guillermo A. Pérez, Jean-Francois Raskin, Ocan Sankur

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2016.42.pdf
  • Filesize: 0.5 MB
  • 14 pages

Document Identifiers

Author Details

Romain Brenguier
Guillermo A. Pérez
Jean-Francois Raskin
Ocan Sankur

Cite As Get BibTex

Romain Brenguier, Guillermo A. Pérez, Jean-Francois Raskin, and Ocan Sankur. Admissibility in Quantitative Graph Games. In 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 65, pp. 42:1-42:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.FSTTCS.2016.42

Abstract

Admissibility has been studied  for games of infinite duration with Boolean objectives. We extend here this study to games of infinite duration with quantitative objectives. First, we show that, under the assumption that optimal worst-case and cooperative strategies exist, admissible strategies are guaranteed to exist. Second, we give a characterization of admissible strategies using the notion of adversarial and cooperative values of a history, and we characterize the set of outcomes that are compatible with admissible strategies. Finally, we show how these characterizations can be used to design algorithms to decide relevant verification and synthesis problems.

Subject Classification

Keywords
  • Quantitative games
  • Verification
  • Reactive synthesis
  • Admissibility

Metrics

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

References

  1. Brandenburger Adam, Friedenberg Amanda, H Jerome, et al. Admissibility in games. Econometrica, 2008. Google Scholar
  2. Dietmar Berwanger. Admissibility in infinite games. In STACS, volume 4393 of LNCS, pages 188-199. Springer, February 2007. Google Scholar
  3. Udi Boker, Krishnendu Chatterjee, Thomas A. Henzinger, and Orna Kupferman. Temporal specifications with accumulative values. ACM Trans. Comput. Logic, 15(4):27:1-27:25, July 2014. URL: http://dx.doi.org/10.1145/2629686.
  4. Romain Brenguier, Jean-François Raskin, and Ocan Sankur. Assume-admissible synthesis. In Luca Aceto and David de Frutos-Escrig, editors, CONCUR, volume 42 of LIPIcs, pages 100-113. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2015. URL: http://dx.doi.org/10.4230/LIPIcs.CONCUR.2015.100.
  5. Romain Brenguier, Jean-François Raskin, and Mathieu Sassolas. The complexity of admissibility in omega-regular games. In CSL-LICS'14, 2014. ACM, 2014. URL: http://dx.doi.org/10.1145/2603088.2603143.
  6. Krishnendu Chatterjee, Laurent Doyen, Emmanuel Filiot, and Jean-François Raskin. Doomsday equilibria for omega-regular games. In VMCAI'14, volume 8318, pages 78-97. Springer, 2014. Google Scholar
  7. Krishnendu Chatterjee, Laurent Doyen, and Thomas A. Henzinger. Quantitative languages. ACM Transactions on Computational Logic, 11(4), 2010. URL: http://dx.doi.org/10.1145/1805950.1805953.
  8. Krishnendu Chatterjee, Thomas A. Henzinger, and Marcin Jurdziński. Mean-payoff parity games. In LICS, pages 178-187. IEEE Computer Society, 2005. URL: http://dx.doi.org/10.1109/LICS.2005.26.
  9. Krishnendu Chatterjee, Thomas A Henzinger, and Marcin Jurdziński. Games with secure equilibria. Theoretical Computer Science, 365(1):67-82, 2006. Google Scholar
  10. Krishnendu Chatterjee, Mickael Randour, and Jean-François Raskin. Strategy synthesis for multi-dimensional quantitative objectives. Acta Inf., 51(3-4):129-163, 2014. URL: http://dx.doi.org/10.1007/s00236-013-0182-6.
  11. Marco Faella. Admissible strategies in infinite games over graphs. In MFCS 2009, volume 5734 of Lecture Notes in Computer Science, pages 307-318. Springer, 2009. Google Scholar
  12. Dana Fisman, Orna Kupferman, and Yoad Lustig. Rational synthesis. In TACAS'10, volume 6015 of LNCS, pages 190-204. Springer, 2010. Google Scholar
  13. R. J. Gretlein. Dominance elimination procedures on finite alternative games. International Journal of Game Theory, 12(2):107-113, 1983. URL: http://dx.doi.org/10.1007/BF01774300.
  14. O. Kupferman, G. Perelli, and M.Y. Vardi. Synthesis with rational environments. In Proc. 12th European Conference on Multi-Agent Systems, LNCS. Springer, 2014. Google Scholar
  15. Amir Pnueli and Roni Rosner. On the synthesis of a reactive module. In POPL, pages 179-190, 1989. URL: http://dx.doi.org/10.1145/75277.75293.
  16. Wolfgang Thomas. On the synthesis of strategies in infinite games. In STACS, pages 1-13, 1995. URL: http://dx.doi.org/10.1007/3-540-59042-0_57.
  17. Yaron Velner. Robust multidimensional mean-payoff games are undecidable. In Andrew M. Pitts, editor, FoSSaCS, volume 9034 of LNCS, pages 312-327. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-662-46678-0_20.
  18. Uri Zwick and Mike Paterson. The complexity of mean payoff games on graphs. TCS, 158(1):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