Automata and Compositional Strategies in Extensive Form Games | SpringerLink
Skip to main content
Springer Nature Link
Log in

Automata and Compositional Strategies in Extensive Form Games

  • Chapter
  • First Online:
Models of Strategic Reasoning

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 8972))

Abstract

We study automata as memory structure for “online” strategizing in extensive form games. By online strategizing we mean a model in which players start with potential (partial) strategies that are generic plans for (local) subgames and dynamically compose and switch between them. We consider such startegizing to be relevant for a theory of play. We suggest that for sufficiently large games and resource limited players, the game is better modelled as an infinite horizon game, and thus the study is carried out in games of infinite duration on finite game arenas. We show how strategy switching can be realised by finite state transducers and how they can be used to answer questions on stability of strategies.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    due originally to Émile Borel [11]; von Neumann was only developing the idea.

  2. 2.

    Indeed the considerations of online strategizing and compositional structure seem more relevant for such temporally large games. Arguably, for sufficiently small games, pre-game deliberation might suffice.

References

  1. Alur, R., Henzinger, T.A., Kupferman, O.: Alternating-time temporal logic. J. ACM 49(5), 672–713 (2002)

    Article  MathSciNet  Google Scholar 

  2. Arnold, T., Schwalbe, U.: Dynamic coalition formation and the core. J. Econ. Behav. Organ. 49, 363–380 (2002)

    Article  Google Scholar 

  3. Aumann, R.J., Dreze, J.H.: When all is said and done, how should you play and what should you expect? (2005). http://www.ma.huji.ac.il/raumann/pdf/dp_387.pdf

  4. van Benthem, J.: Games in dynamic epistemic logic. Bull. Econ. Res. 53(4), 219–248 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  5. van Benthem, J.: Extensive games as process models. J. Logic Lang. Inform. 11, 289–313 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  6. van Benthem, J.: In praise of strategies. In: van Eijck, J., Verbrugge, R. (eds.) Foundations of Social Software, Studies in Logic, pp. 283–317. College Publications (2007)

    Google Scholar 

  7. van Benthem, J.: Exploring a theory of play. In: Apt, K.R. (ed.) Proceedings of the 13th Conference on Theoretical Aspects of Rationality and Knowledge, pp. 12–16. ACM (2011)

    Google Scholar 

  8. van Benthem, J.: Logic in Games. MIT Press, Cambridge (2014)

    MATH  Google Scholar 

  9. van Benthem, J., Pacuit, E., Roy, O.: Toward a theory of play: a logical perspective on games and interaction. Games 2, 52–86 (2011)

    Article  MathSciNet  Google Scholar 

  10. Bonanno, G.: Modal logic and game theory: two alternative approaches. Risk Decis. Policy 7, 309–324 (2002)

    Article  Google Scholar 

  11. Borel, E.: La théorie du jeu et les equations intégrales à noyau symétrique gauche. C. R. Acad. Sci. 173, 1304–1308 (1921)

    MATH  Google Scholar 

  12. Büchi, J.R.: On a decision method in restricted second-order arithmetic. In: Proceedings of the 1960 International Congress for Logic, Methodology and Philosophy of Science, pp. 1–11. Stanford University Press (1962)

    Google Scholar 

  13. Büchi, J.R., Landweber, L.H.: Solving sequential conditions by finite-state strategies. Trans. Americal Math. Soc. 138, 295–311 (1969)

    Article  MATH  Google Scholar 

  14. Bulling, N., Goranko, V., Jamroga, W.: Logics for reasoning about strategic abilities in multi-player games. In: van Benthem, J., Ghosh, S., Verbrugge, R. (eds.) Models of Strategic Reasoning. LNCS, vol. 8972, pp. 93–136. Springer, Heidelberg (2015)

    Chapter  Google Scholar 

  15. Majumdar, R., Jurdziński, M., Chatterjee, K.: On nash equilibria in stochastic games. In: Tarlecki, A., Marcinkowski, J. (eds.) CSL 2004. LNCS, vol. 3210, pp. 26–40. Springer, Heidelberg (2004)

    Chapter  Google Scholar 

  16. Emerson, A., Jutla, C.: Tree automata, mu-calculus and determinacy. In: Proceedings of the 32nd IEEE Symposium on Foundations of Computer Science, pp. 368–377. IEEE Computer Society Press (1991)

    Google Scholar 

  17. Gale, D., Stewart, F.: Infinite games with perfect information. Ann. Math. Stud. 28, 245–266 (1953)

    MathSciNet  Google Scholar 

  18. Ghosh, S.: Strategies made explicit in dynamic game logic. In: Proceedings of the Workshop on Logic and Intelligent Interaction, ESSLLI 2008, pp. 74–81 (2008)

    Google Scholar 

  19. Ghosh, S., Simon, S., Ramanujam, R.: Playing extensive form games in parallel. In: Dix, J., Governatori, G., Leite, J., Jamroga, W. (eds.) CLIMA XI. LNCS, vol. 6245, pp. 153–170. Springer, Heidelberg (2010)

    Chapter  Google Scholar 

  20. Glazberg, Z., Moulin, M., Orni, A., Ruah, S., Zarpas, E.: PSL: Beyond hardware verification. In: Ramesh, S., Sampath, P. (eds.) Next Generation Design and Verification Methodologies for Distributed Embedded Control Systems, pp. 245–260. Springer, Netherlands (2007)

    Chapter  Google Scholar 

  21. Goranko, V.: The basic algebra of game equivalences. Stud. Logica 75(2), 221–238 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  22. Farwer, B.: \(\omega \)-automata. In: Grädel, E., Thomas, W., Wilke, T. (eds.) Automata, Logics, and Infinite Games. LNCS, vol. 2500, pp. 3–21. Springer, Heidelberg (2002)

    Chapter  Google Scholar 

  23. Grädel, E., Ummels, M.: Solution concepts and algorithms for infinite multiplayer games. In: New Perspectives on Games and Interaction. Texts in Logic and Games, vol. 4, pp. 151–178. Amsterdam University Press (2008)

    Google Scholar 

  24. Harel, D., Kozen, D., Parikh, R.: Process logic: expressiveness, decidability, completeness. J. Comput. Syst. Sci. 25(2), 144–170 (1982)

    Article  MATH  MathSciNet  Google Scholar 

  25. van den Herik, J., Schaeffer, J.: Games, computers, and artificial intelligence. Artif. Intell. 134, 1–7 (2001)

    Google Scholar 

  26. van der Hoek, W., Jamroga, W., Wooldridge, M.: A logic for strategic reasoning. In: Proceedings of the Fourth International Joint Conference on Autonomous Agents and Multi-Agent Systems, pp. 157–164 (2005)

    Google Scholar 

  27. van der Hoek, W., Wooldridge, M.: Cooperation, knowledge, and time: alternating-time temporal epistemic logic and its applications. Stud. Logica 75(1), 125–157 (2003)

    Article  MATH  Google Scholar 

  28. Lipman, B.L., Wang, R.: Switching costs in frequently repeated games. Working Papers 955, Queen’s University, Department of Economics, September 1997

    Google Scholar 

  29. Lipman, B.L., Wang, R.: Switching costs in infinitely repeated games. Games Econ. Behav. 66(1), 292–314 (2009)

    Article  MATH  MathSciNet  Google Scholar 

  30. Martin, D.A.: Borel determinacy. Ann. Math. 102, 363–371 (1975)

    Article  MATH  Google Scholar 

  31. Mostowski, A.W.: Games with forbidden positions. Technical Report 78, Instytut Matematyki, Uniwersytet Gdański, Poland (1991)

    Google Scholar 

  32. Moszkowski, B.C., Manna, Z.: Reasoning in interval temporal logic. In: Clarke, E.M., Kozen, D. (eds.) Logic of Programs. Lecture Notes in Computer Science, vol. 164, pp. 371–382. Springer, Heidelberg (1983)

    Chapter  Google Scholar 

  33. Muller, D.E.: Infinite sequences and finite machines. In: Proceedings of the 4th IEEE Symposium on Switching Circuit Theory and Logical Design, pp. 3–16 (1963)

    Google Scholar 

  34. Nisan, N., Roughgarden, T., Tardos, E., Vazirani, V.V.: Algorithmic Game Theory. Cambridge University Press, New York (2007)

    Book  MATH  Google Scholar 

  35. Osborne, M.J., Rubinstein, A.: A Course in Game Theory. MIT Press, Cambridge (1994)

    MATH  Google Scholar 

  36. Paul, S., Ramanujam, R., Simon, S.: Stability under strategy switching. In: Löwe, B., Merkle, W., Ambos-Spies, K. (eds.) CiE 2009. LNCS, vol. 5635, pp. 389–398. Springer, Heidelberg (2009)

    Chapter  Google Scholar 

  37. Paul, S., Simon, S.: Nash equilibrium in generalised Muller games. In: Proceedings of the Conference on Foundation of Software Technology and Theoretical Computer Science, FSTTCS, Leibniz International Proceedings in Informatics (LIPIcs), vol. 4, pp. 335–346. Schloss Dagstuhl-Leibniz-Zentrum für Informatik (2009)

    Google Scholar 

  38. Perea, A.: Epistemic Game Theory: Reasoning and Choice. Cambridge University Press, Cambridge (2012)

    Book  Google Scholar 

  39. Ramanujam, R., Simon, S.: Axioms for composite strategies. In: Proceedings of the 7th Conference on Logic and the Foundations of Game and Decision Theory (LOFT 2006) pp. 189–198 (2006)

    Google Scholar 

  40. Ramanujam, R., Simon, S.: Structured strategies in games on graphs. In: Flum, J., Grädel, E., Wilke, T. (eds.) Logic and Automata: History and Perspectives. Texts in Logic and Games, vol. 2, pp. 567–587. Amsterdam University Press (2007)

    Google Scholar 

  41. Ramanujam, R., Simon, S.: Dynamic logic on games with structured strategies. In: Proceedings of the 11th International Conference on Principles of Knowledge Representation and Reasoning (KR-2008), pp. 49–58. AAAI Press (2008)

    Google Scholar 

  42. Ramanujam, R., Simon, S.: A logical structure for strategies. In: Logic and the Foundations of Game and Decision Theory (LOFT 7), Texts in Logic and Games, vol. 3, pp. 183–208. Amsterdam University Press (2008)

    Google Scholar 

  43. Rubinstein, A.: Comments on the interpretation of game theory. Econometrica 59, 909–924 (1991)

    Article  Google Scholar 

  44. Selten, R.: Spieltheoretische Behandlung eines Oligopolmodells mit Nachfrageträgheit. Zeitschrift für die Gesamte Staatswissenschaft 121, 301–324 (1965)

    Google Scholar 

  45. von Neumann, J.: Zur Theorie der Gesellschaftsspiele. Math. Ann. 100, 295–328 (1928)

    Article  MATH  MathSciNet  Google Scholar 

  46. Weibull, J.W.: Evolutionary Game Theory. MIT Press, Cambridge, MA (1997)

    Google Scholar 

  47. Young, H.P.: The evolution of conventions. Econometrica 61, 57–84 (1993). Blackwell Publishing

    Article  MATH  MathSciNet  Google Scholar 

  48. Young, H.P.: The diffusion of innovations in social networks. Economics Working Paper Archive 437, The Johns Hopkins University, Department of Economics (2000)

    Google Scholar 

Download references

Acknowledgments

The authors would like to thank Dietmar Berwanger and Sujata Ghosh for many interesting discussions on this theme and the editors of the volume for their patience and encouragement.

Author information

Authors and Affiliations

  1. IRIT, Université Paul Sabatier, Toulouse, France

    Soumya Paul

  2. Institute of Mathematical Sciences, Chennai, India

    R. Ramanujam

  3. Indian Institute of Technology, Kanpur, India

    Sunil Simon

Authors
  1. Soumya Paul
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. R. Ramanujam
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Sunil Simon
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to R. Ramanujam .

Editor information

Editors and Affiliations

  1. Inst for Logic Language & Computation, University of Amsterdam, Amsterdam, Noord-Holland, The Netherlands

    Johan van Benthem

  2. Indian Statistical Institute, Chennai, Tamil Nadu, India

    Sujata Ghosh

  3. Faculty of Math & Natural Sci, University of Groningen, Groningen, Groningen, The Netherlands

    Rineke Verbrugge

Rights and permissions

Reprints and permissions

Copyright information

© 2015 Springer-Verlag Berlin Heidelberg

About this chapter

Cite this chapter

Paul, S., Ramanujam, R., Simon, S. (2015). Automata and Compositional Strategies in Extensive Form Games. In: van Benthem, J., Ghosh, S., Verbrugge, R. (eds) Models of Strategic Reasoning. Lecture Notes in Computer Science(), vol 8972. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-48540-8_6

Download citation

  • DOI: https://doi.org/10.1007/978-3-662-48540-8_6

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-662-48539-2

  • Online ISBN: 978-3-662-48540-8

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics