Document Open Access Logo

Observation and Distinction. Representing Information in Infinite Games

Authors Dietmar Berwanger, Laurent Doyen

PDF
Thumbnail PDF

File

LIPIcs.STACS.2020.48.pdf
  • Filesize: 0.51 MB
  • 17 pages

Document Identifiers

Author Details

Dietmar Berwanger
  • LSV, CNRS & ENS Paris-Saclay, France
Laurent Doyen
  • LSV, CNRS & ENS Paris-Saclay, France

Cite As Get BibTex

Dietmar Berwanger and Laurent Doyen. Observation and Distinction. Representing Information in Infinite Games. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 48:1-48:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.STACS.2020.48

Abstract

We compare two approaches for modelling imperfect information in infinite games by using finite-state automata. The first, more standard approach views information as the result of an observation process driven by a sequential Mealy machine. In contrast, the second approach features indistinguishability relations described by synchronous two-tape automata.
The indistinguishability-relation model turns out to be strictly more expressive than the one based on observations. We present a characterisation of the indistinguishability relations that admit a representation as a finite-state observation function. We show that the characterisation is decidable, and give a procedure to construct a corresponding Mealy machine whenever one exists.

Subject Classification

ACM Subject Classification
  • Theory of computation → Automata over infinite objects
  • Theory of computation → Representations of games and their complexity
  • Computing methodologies → Reasoning about belief and knowledge
  • Computing methodologies → Planning under uncertainty
Keywords
  • Infinite Games on Finite Graphs
  • Imperfect Information
  • Automatic Structures

Metrics

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

Related Versions

References

  1. Michael Bacharach. Some extensions of a claim of Aumann in an axiomatic model of knowledge. Journal of Economic Theory, 37(1):167-190, 1985. URL: https://doi.org/10.1016/0022-0531(85)90035-3.
  2. Dietmar Berwanger and Laurent Doyen. Observation and distinction. Representing information in infinite games. CoRR, abs/1809.05978, 2018. URL: http://arxiv.org/abs/1809.05978.
  3. Dietmar Berwanger, Lukasz Kaiser, and Bernd Puchala. A perfect-information construction for coordination in games. In Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011), volume 13 of LIPIcs, pages 387-398. Leibniz-Zentrum fuer Informatik, 2011. URL: https://doi.org/10.4230/LIPIcs.FSTTCS.2011.387.
  4. Achim Blumensath and Erich Grädel. Automatic structures. In Logic in Computer Science (LICS 2000), pages 51-62. IEEE Comput. Soc, 2000. URL: https://doi.org/10.1109/LICS.2000.855755.
  5. Laura Bozzelli, Bastien Maubert, and Sophie Pinchinat. Uniform strategies, rational relations and jumping automata. Information and Computation, 242:80-107, June 2015. URL: https://doi.org/10.1016/j.ic.2015.03.012.
  6. Julius R. Büchi and Lawrence H. Landweber. Solving sequential conditions by finite-state strategies. Transactions of the American Mathematical Society, 138:295-311, 1969. URL: https://doi.org/10.2307/1994916.
  7. Krishnendu Chatterjee, Laurent Doyen, Thomas A. Henzinger, and Jean-Francois Raskin. Algorithms for omega-regular games with imperfect information. Logical Methods in Computer Science, Volume 3, Issue 3, 2007. URL: https://doi.org/10.2168/LMCS-3(3:4)2007.
  8. Catalin Dima, Bastien Maubert, and Sophie Pinchinat. Relating Paths in Transition Systems: The Fall of the Modal Mu-Calculus. ACM Transactions on Computational Logic (TOCL), 19(3):23:1-23:33, September 2018. URL: https://doi.org/10.1145/3231596.
  9. Ronald Fagin, Joseph Y. Halpern, Yoram Moses, and Moshe Y. Vardi. Reasoning about knowledge. MIT Press, Cambridge, Mass., 2003. Google Scholar
  10. Paulin Fournier and Nathan Lhote. Equivalence kernels of sequential functions and sequential observation synthesis. CoRR, abs/1910.06019, 2019. URL: http://arxiv.org/abs/1910.06019.
  11. John Geanakoplos. Common Knowledge. Journal of Economic Perspectives, 6(4):53-82, 1992. URL: https://doi.org/10.1257/jep.6.4.53.
  12. Olivier Gossner and Tristan Tomala. Repeated games with complete information. In Robert A. Meyers, editor, Encyclopedia of Complexity and Systems Science, pages 7616-7630. Springer New York, New York, NY, 2009. URL: https://doi.org/10.1007/978-0-387-30440-3_451.
  13. Erich Grädel, Wolfgang Thomas, and Thomas Wilke, editors. Automata, logics, and infinite games. Number 2500 in Lecture notes in computer science. Springer, 2002. Google Scholar
  14. Bakhadyr Khoussainov and Anil Nerode. Automatic presentations of structures. In Gerhard Goos, Juris Hartmanis, Jan Leeuwen, and Daniel Leivant, editors, Logic and Computational Complexity, volume 960, pages 367-392. Springer Berlin Heidelberg, Berlin, Heidelberg, 1995. URL: https://doi.org/10.1007/3-540-60178-3_93.
  15. Harold W. Kuhn. Extensive games and the problem of information, Contributions to the theory of games II. Annals of Mathematics Studies, 28:193-216, 1953. Google Scholar
  16. 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, Applied Logic Series, pages 109-127. Springer Netherlands, Dordrecht, 2000. URL: https://doi.org/10.1007/978-94-015-9586-5_6.
  17. Dietrich Kuske and Markus Lohrey. Automatic structures of bounded degree revisited. The Journal of Symbolic Logic, 76(04):1352-1380, 2011. URL: https://doi.org/10.2178/jsl/1318338854.
  18. F. Lin and W. M. Wonham. On observability of discrete-event systems. Information Sciences, 44(3):173-198, April 1988. URL: https://doi.org/10.1016/0020-0255(88)90001-1.
  19. Anatoly I. Mal’cev. Algebraic Systems. Springer Berlin Heidelberg, Berlin, Heidelberg, 1973. URL: https://doi.org/10.1007/978-3-642-65374-2.
  20. Bastien Maubert. Logical foundations of games with imperfect information : uniform strategies. (Fondations logiques des jeux à information imparfaite : stratégies uniformes). PhD thesis, University of Rennes 1, France, 2014. URL: https://tel.archives-ouvertes.fr/tel-00980490.
  21. Bastien Maubert and Sophie Pinchinat. A General Notion of Uniform Strategies. International Game Theory Review, 16(01):1440004, March 2014. URL: https://doi.org/10.1142/S0219198914400040.
  22. Boleslaw Mikolajczak. Algebraic and structural automata theory. Annals of Discrete Mathematics. North-Holland, Amsterdam, 1991. Google Scholar
  23. Michael Oser Rabin. Automata on Infinite Objects and Church’s Problem. American Mathematical Society, Boston, MA, USA, 1972. Google Scholar
  24. Frank P. Ramsey. On a problem in formal logic. Proc. London Math. Soc., 30:264-286, 1930. Google Scholar
  25. John H. Reif. The complexity of two-player games of incomplete information. Journal of Computer and System Sciences, 29(2):274-301, 1984. URL: https://doi.org/10.1016/0022-0000(84)90034-5.
  26. Wolfgang Thomas. On the synthesis of strategies in infinite games. In Symposium on Theoretical Aspects of Computer Science (STACS 1995), volume 900, pages 1-13. Springer, 1995. URL: https://doi.org/10.1007/3-540-59042-0_57.
  27. Ron van der Meyden and Thomas Wilke. Synthesis of Distributed Systems from Knowledge-Based Specifications. In Martín Abadi and Luca de Alfaro, editors, CONCUR 2005 – Concurrency Theory, volume 3653, pages 562-576, Berlin, Heidelberg, 2005. Springer Berlin Heidelberg. URL: https://doi.org/10.1007/11539452_42.
  28. John von Neumann and Oskar Morgenstern. Theory of games and economic behavior. Princeton University Press, 1944. Google Scholar
  29. Andreas Weber. On the valuedness of finite transducers. Acta Inf., 27(8):749-780, 1990. URL: https://doi.org/10.1007/BF00264285.
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