Strategic Knowledge of the Past - Expressivity and Complexity | SpringerLink
Skip to main content
Springer Nature Link
Log in

Strategic Knowledge of the Past - Expressivity and Complexity

  • Conference paper
  • First Online:
Multi-Agent Systems and Agreement Technologies (EUMAS 2017, AT 2017)

Part of the book series: Lecture Notes in Computer Science ((LNAI,volume 10767))

Abstract

In this article we present theoretical results for an epistemic strategy logic with past operators, \(\text {PKSL}\). In \(\text {PKSL}\), agents are able to choose their strategies depending on past moves of other agents. This strictly extends the expressive power of some well-known epistemic strategy logics, which we illustrate by modelling forward induction: a rationality criterion, called admissibility, may be defined over agent’s strategies. Admissibility specifies coherence conditions between past and future actions, inducing new conditions for the availability of optimal strategies. We also give a resolution algorithm for \(\text {PKSL}\) model-checking. It runs in exponential time, while the satisfiability problem is undecidable, as is the case for similar logics for strategies such as Strategy Logic.

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

References

  1. Chatterjee, K., Henzinger, T.A., Piterman, N.: Strategy logic. Inf. Comp. 208(6), 677–693 (2010)

    Article  MathSciNet  Google Scholar 

  2. Mogavero, F., Murano, A., Perelli, G., Vardi, M.Y.: Reasoning about strategies: On the model-checking problem. ACM Trans. Comput. Log. 15(4), 1–47 (2014)

    Article  MathSciNet  Google Scholar 

  3. Ågotnes, T., Goranko, V., Jamroga, W., Wooldridge, M.: Knowledge and ability. Volume In: van Ditmarsch, H., Halpern, J.Y., van der Hoek, W., Kooi, B. (eds.) Handbook of Epistemic Logic, pp. 543–589. College Publications (2015)

    Google Scholar 

  4. Jamroga, W., Ågotnes, T.: Constructive knowledge: what agents can achieve under imperfect information. J. Appl. Non-Class. Log. 17, 423–475 (2007)

    Article  MathSciNet  Google Scholar 

  5. Belardinelli, F.: Reasoning about knowledge and strategies: epistemic strategy logic. In: Proceedings of 2nd International Workshop on Strategic Reasoning, SR, pp. 27–33 (2014)

    Article  MathSciNet  Google Scholar 

  6. Knight, S., Maubert, B.: Dealing with imperfect information in strategy logic. In: Proceedings of 3rd International Workshop on Strategic Reasoning, SR (2015)

    Google Scholar 

  7. Huang, X., van der Meyden, R.: An epistemic strategy logic. In: Proceedings of 2nd International Workshop on Strategic Reasoning, SR, pp. 35–41 (2014)

    Google Scholar 

  8. Van Ditmarsch, H., van Der Hoek, W., Kooi, B.: Dynamic Epistemic Logic, vol. 337. Springer Science & Business Media, Netherlands (2007). https://doi.org/10.1007/978-1-4020-5839-4

    Book  MATH  Google Scholar 

  9. Chareton, C., van Ditmarsch, H.: Strategic knowledge of the past in quantum cryptography. In: Baltag, A., Seligman, J., Yamada, T. (eds.) LORI 2017. LNCS, vol. 10455, pp. 347–361. Springer, Heidelberg (2017). https://doi.org/10.1007/978-3-662-55665-8_24

    Chapter  Google Scholar 

  10. Lichtenstein, O., Pnueli, A., Zuck, L.: The glory of the past. In: Parikh, R. (ed.) Logic of Programs 1985. LNCS, vol. 193, pp. 196–218. Springer, Heidelberg (1985). https://doi.org/10.1007/3-540-15648-8_16

    Chapter  MATH  Google Scholar 

  11. Vardi, M.Y.: Reasoning about the past with two-way automata. In: Larsen, K.G., Skyum, S., Winskel, G. (eds.) ICALP 1998. LNCS, vol. 1443, pp. 628–641. Springer, Heidelberg (1998). https://doi.org/10.1007/BFb0055090

    Chapter  MATH  Google Scholar 

  12. French, T., van der Meyden, R., Reynolds, M.: Axioms for logics of knowledge and past time: synchrony and unique initial states. In: Proceedings of AiML, vol. 5, pp. 53–72 (2004)

    Google Scholar 

  13. Sack, J.: Logic for update products and steps into the past. Ann. Pure Appl. Logic 161(12), 1431–1461 (2010)

    Article  MathSciNet  Google Scholar 

  14. Guelev, D.P., Dima, C.: Model-checking strategic ability and knowledge of the past of communicating coalitions. In: Baldoni, M., Son, T.C., van Riemsdijk, M.B., Winikoff, M. (eds.) DALT 2008. LNCS (LNAI), vol. 5397, pp. 75–90. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-540-93920-7_6

    Chapter  MATH  Google Scholar 

  15. Skyrms, B.: The Stag Hunt and the Evolution of Social Structure. Cambridge University Press, Cambridge (2004)

    Google Scholar 

  16. Brenguier, R., Pérez, G.A., Raskin, J.F., Sankur, O.: Admissibility in quantitative graph games. arXiv preprint arXiv:1611.08677 (2016)

  17. Berwanger, D.: Admissibility in infinite games. In: Thomas, W., Weil, P. (eds.) STACS 2007. LNCS, vol. 4393, pp. 188–199. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-70918-3_17

    Chapter  Google Scholar 

  18. Van Damme, E.: Stable equilibria and forward induction. J. Econ. Theory 48(2), 476–496 (1989)

    Article  MathSciNet  Google Scholar 

  19. Cooper, R., De Jong, D.V., Forsythe, R., Ross, T.W.: Forward induction in coordination games. Econ. Lett. 40(2), 167–172 (1992)

    Article  Google Scholar 

  20. Chareton, C., Brunel, J., Chemouil, D.: Towards an updatable strategy logic. In: Proceedings of 1st International Workshop on Strategic Reasoning, SR, pp. 91–98 (2013)

    Article  MathSciNet  Google Scholar 

  21. Chareton, C., Brunel, J., Chemouil, D.: A logic with revocable and refinable strategies. Inf. Comput. 242, 157–182 (2015)

    Article  MathSciNet  Google Scholar 

  22. De Giacomo, G., Vardi, M.Y.: Linear temporal logic and linear dynamic logic on finite traces. In: Proceedings of 22th IJCAI, pp. 854–860 (2013)

    Google Scholar 

  23. Baltag, A.: A logic for suspicious players: Epistemic actions and belief-updates in games. Technical report, Amsterdam, The Netherlands (2000)

    Google Scholar 

  24. Chandra, A.K., Stockmeyer, L.J.: Alternation. In: 17th Annual Symposium on Foundations of Computer Science, pp. 98–108. IEEE (1976)

    Google Scholar 

  25. Harel, D.: Recurring dominoes: making the highly undecidable highly understandable. North-Holl. Math. Stud. 102, 51–71 (1985)

    Article  MathSciNet  Google Scholar 

  26. Mogavero, F., Murano, A., Perelli, G., Vardi, M.Y.: Reasoning about strategies: on the satisfiability problem. Log. Methods Comput. Sci. 13(1), 1–37 (2017)

    MathSciNet  MATH  Google Scholar 

  27. Čermák, P., Lomuscio, A., Mogavero, F., Murano, A.: MCMAS-SLK: a model checker for the verification of strategy logic specifications. In: Biere, A., Bloem, R. (eds.) CAV 2014. LNCS, vol. 8559, pp. 525–532. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-08867-9_34

    Chapter  Google Scholar 

  28. Belardinelli, F., Lomuscio, A., Murano, A., Rubin, S.: Verification of broadcasting multi-agent systems against an epistemic strategy logic. In: Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI 2017, Melbourne, Australia, August 19–25, 2017, pp. 91–97 (2017)

    Google Scholar 

  29. Berthon, R., Maubert, B., Murano, A., Rubin, S., Vardi, M.Y.: Strategy logic with imperfect information. In: 32nd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2017, Reykjavik, Iceland, June 20–23, 2017, pp. 1–12 (2017)

    Google Scholar 

Download references

Acknowledgments

The author acknowledges financial support from ERC project EPS 313360 and thanks Hans van Ditmarsch for his useful comments on the presented research. He also gives thanks to the anonymous reviewers of conference SR 2017 for their comments on a previous version of this article.

Author information

Authors and Affiliations

  1. LORIA, CNRS, Université de Lorraine, Lorraine, France

    Christophe Chareton

Authors
  1. Christophe Chareton
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Christophe Chareton .

Editor information

Editors and Affiliations

  1. University of Évry Val d'Essonne, Paris Saclay, France

    Francesco Belardinelli

  2. Polytechnic University of Valencia, Valencia, Spain

    Estefanía Argente

Rights and permissions

Reprints and permissions

Copyright information

© 2018 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Chareton, C. (2018). Strategic Knowledge of the Past - Expressivity and Complexity. In: Belardinelli, F., Argente, E. (eds) Multi-Agent Systems and Agreement Technologies. EUMAS AT 2017 2017. Lecture Notes in Computer Science(), vol 10767. Springer, Cham. https://doi.org/10.1007/978-3-030-01713-2_9

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-01713-2_9

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-01712-5

  • Online ISBN: 978-3-030-01713-2

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation