Document Open Access Logo

Admissibility in Games with Imperfect Information (Invited Talk)

Authors Romain Brenguier, Arno Pauly, Jean-François Raskin, Ocan Sankur

PDF
Thumbnail PDF

File

LIPIcs.CONCUR.2017.2.pdf
  • Filesize: 0.55 MB
  • 23 pages

Document Identifiers

Author Details

Romain Brenguier
Arno Pauly
Jean-François Raskin
Ocan Sankur

Cite As Get BibTex

Romain Brenguier, Arno Pauly, Jean-François Raskin, and Ocan Sankur. Admissibility in Games with Imperfect Information (Invited Talk). In 28th International Conference on Concurrency Theory (CONCUR 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 85, pp. 2:1-2:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.CONCUR.2017.2

Abstract

In this invited paper, we study the concept of admissible strategies for two player win/lose infinite sequential games with imperfect information. We show that in stark contrast with the perfect information variant, admissible strategies are only guaranteed to exist when players have objectives that are closed sets. As a consequence, we also study decision problems related to the existence of admissible strategies for regular games as well as finite duration games.

Subject Classification

Keywords
  • Admissibility
  • non-zero sum games
  • reactive synthesis
  • imperfect infor- mation

Metrics

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

References

  1. Martín Abadi, Leslie Lamport, and Pierre Wolper. Realizable and unrealizable specifications of reactive systems. In ICALP'89, volume 372 of LNCS. Springer, 1989. Google Scholar
  2. Brandenburger Adam, Friedenberg Amanda, H Jerome, et al. Admissibility in games. Econometrica, 2008. Google Scholar
  3. Christel Baier and Joost-Pieter Katoen. Principles of model checking. MIT Press, 2008. Google Scholar
  4. Nicolas Basset, Gilles Geeraerts, Jean-François Raskin, and Ocan Sankur. Admissibility in concurrent games. CoRR, abs/1702.06439, 2017. URL: http://arxiv.org/abs/1702.06439.
  5. Raphael Berthon, Bastien Maubert, Aniello Murano, Sasha Rubin, and Moshe Vardi. Strategy logic with imperfect information. In LICS'14. IEEE, 2014. Google Scholar
  6. Dietmar Berwanger. Admissibility in infinite games. In STACS 2007, 24th Annual Symposium on Theoretical Aspects of Computer Science, Aachen, Germany, February 22-24, 2007, Proceedings, volume 4393 of Lecture Notes in Computer Science, pages 188-199. Springer, 2007. Google Scholar
  7. Dietmar Berwanger, Anup Basil Mathew, and Marie van den Bogaard. Hierarchical information patterns and distributed strategy synthesis. In Automated Technology for Verification and Analysis - 13th International Symposium, ATVA 2015, Shanghai, China, October 12-15, 2015, Proceedings, volume 9364 of Lecture Notes in Computer Science, pages 378-393. Springer, 2015. Google Scholar
  8. Felix Brandt, Markus Brill, Felix Fischer, and Paul Harrenstein. On the complexity of iterated weak dominance in constant-sum games. Theory of Computing Systems, 49(1):162-181, 2011. URL: http://dx.doi.org/10.1007/s00224-010-9282-7.
  9. Romain Brenguier, Lorenzo Clemente, Paul Hunter, Guillermo A. Pérez, Mickael Randour, Jean-François Raskin, Ocan Sankur, and Mathieu Sassolas. Non-zero sum games for reactive synthesis. In Language and Automata Theory and Applications - 10th International Conference, LATA 2016, Prague, Czech Republic, March 14-18, 2016, Proceedings, volume 9618 of Lecture Notes in Computer Science, pages 3-23. Springer, 2016. Google Scholar
  10. Romain Brenguier, Guillermo A. Pérez, Jean-François 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, December 13-15, 2016, Chennai, India, volume 65 of LIPIcs, pages 42:1-42:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. Google Scholar
  11. Romain Brenguier, Jean-François Raskin, and Ocan Sankur. Assume-admissible synthesis. Acta Inf., 54(1):41-83, 2017. URL: http://dx.doi.org/10.1007/s00236-016-0273-2.
  12. 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.
  13. Krishnendu Chatterjee, Laurent Doyen, Thomas A. Henzinger, and Jean-François Raskin. Algorithms for omega-regular games with imperfect information. Logical Methods in Computer Science, 3(4), 2007. Google Scholar
  14. Krishnendu Chatterjee, Thomas A. Henzinger, and Nir Piterman. Strategy logic. Inf. Comput., 208(6):677-693, 2010. Google Scholar
  15. Vincent Conitzer and Tuomas Sandholm. Complexity of (iterated) dominance. In EC '05: Proceedings of the 6th ACM conference on Electronic commerce, pages 88-97, New York, NY, USA, 2005. ACM. URL: http://dx.doi.org/10.1145/1064009.1064019.
  16. Werner Damm and Bernd Finkbeiner. Automatic compositional synthesis of distributed systems. In FM 2014, volume 8442 of LNCS, pages 179-193. Springer, 2014. Google Scholar
  17. Luca de Alfaro, Thomas A. Henzinger, and Orna Kupferman. Concurrent reachability games. In 39th Annual Symposium on Foundations of Computer Science, FOCS '98, November 8-11, 1998, Palo Alto, California, USA, pages 564-575. IEEE Computer Society, 1998. Google Scholar
  18. 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
  19. Daniel Kirsten. Alternating tree automata and parity games. In Automata, Logics, and Infinite Games: A Guide to Current Research [outcome of a Dagstuhl seminar, February 2001], volume 2500 of Lecture Notes in Computer Science, pages 153-167. Springer, 2001. Google Scholar
  20. Donald Knuth, Christos Papadimitriou, and John Tsitsiklis. A note on strategy elimination in bimatrix games. Operations Research Letters, 7(3):103-107, 1988. URL: http://dx.doi.org/10.1016/0167-6377(88)90075-2.
  21. Orna Kupferman and Moshe Y. Vardi. Synthesis with incomplete informatio. In Howard Barringer, Michael Fisher, Dov Gabbay, and Graham Gough, editors, Advances in Temporal Logic, pages 109-127, Dordrecht, 2000. Springer Netherlands. URL: http://dx.doi.org/10.1007/978-94-015-9586-5_6.
  22. Fabio Mogavero, Aniello Murano, and Moshe Y. Vardi. Reasoning about strategies. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2010, December 15-18, 2010, Chennai, India, volume 8 of LIPIcs, pages 133-144. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2010. Google Scholar
  23. Arno Pauly. The computational complexity of iterated elimination of dominated strategies. Theory of Computing Systems, pages 52-75, 2016. URL: http://dx.doi.org/10.1007/s00224-015-9637-1.
  24. Amir Pnueli and Roni Rosner. On the synthesis of a reactive module. In POPL, pages 179-190, 1989. Google Scholar
  25. John H. Reif. The complexity of two-player games of incomplete information. J. Comput. Syst. Sci., 29(2):274-301, 1984. URL: http://dx.doi.org/10.1016/0022-0000(84)90034-5.
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