Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Reasoning about temporal properties of rational play

  • Published:
Annals of Mathematics and Artificial Intelligence Aims and scope Submit manuscript

Abstract

This article is about defining a suitable logic for expressing classical game theoretical notions. We define an extension of alternating-time temporal logic (ATL) that enables us to express various rationality assumptions of intelligent agents. Our proposal, the logic ATLP (ATL with plausibility) allows us to specify sets of rational strategy profiles in the object language, and reason about agents’ play if only these strategy profiles were allowed. For example, we may assume the agents to play only Nash equilibria, Pareto-optimal profiles or undominated strategies, and ask about the resulting behaviour (and outcomes) under such an assumption. The logic also gives rise to generalized versions of classical solution concepts through characterizing patterns of payoffs by suitably parameterized formulae of ATLP. We investigate the complexity of model checking ATLP for several classes of formulae: It ranges from \(\Delta_{\mathbf{3}}^{\mathbf{P}}\) to PSPACE in the general case and from \(\Delta_{\mathbf{3}}^{\mathbf{P}}\) to \(\Delta_{\mathbf{4}}^{\mathbf{P}}\) for the most interesting subclasses, and roughly corresponds to solving extensive games with imperfect information.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  1. Ågotnes, T., Goranko, V., Jamroga, W.: Alternating-time temporal logics with irrevocable strategies. In: Samet, D. (ed.) Proceedings of TARK XI, pp. 15–24 (2007)

  2. Alur, R., Henzinger, T.A., Kupferman, O.: Alternating-time temporal logic. In: Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS), pp. 100–109. IEEE Computer Society Press, Silver Spring (1997)

    Chapter  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

  4. Bacharach, M.: A theory of rational decision in games. Erkenntnis 27, 17–55 (1987)

    Article  Google Scholar 

  5. Baltag, A.: A logic for suspicious players. Bull. Econ. Res. 54(1), 1–46 (2002)

    Article  MathSciNet  Google Scholar 

  6. Bonanno, G.: The logic of rational play in games of perfect information. Econ. Philos. 7, 37–65 (1991)

    Article  Google Scholar 

  7. Brihaye, T., Da Costa, A., Laroussinie, F., Markey, N.: ATL with strategy contexts and bounded memory. Technical report LSV-08-14, ENS Cachan (2008)

  8. Bulling, N.: Modal logics for games, time, and beliefs. Master thesis, Clausthal University of Technology (2006)

  9. Bulling, N., Jamroga, W.: Agents, beliefs and plausible behaviour in a temporal setting. Technical report IfI-06-05, Clausthal University of Technology (2006)

  10. Bulling, N., Jamroga, W.: Agents, beliefs and plausible behaviour in a temporal setting. In: Proceedings of AAMAS’07, pp. 570–577 (2007)

  11. Bulling, N., Jamroga, W.: A logic for reasoning about rational agents: yet another attempt. In: Czaja, L. (ed.) Proceedings of CS&P, pp. 87–99 (2007)

  12. Chu, F., Halpern, J.: On the NP-completeness of finding an optimal strategy in games with common payoffs. Int. J. Game Theory. 30(1), 99–106 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  13. Clarke, E.M., Emerson, E.A.: Design and synthesis of synchronization skeletons using branching time temporal logic. In: Proceedings of Logics of Programs Workshop. Lecture Notes in Computer Science, vol. 131, pp. 52–71 (1981)

  14. Clarke, E.M., Emerson, E.A., Sistla, A.P.: Automatic verification of finite-state concurrent systems using temporal logic specifications. ACM Trans. Program. Lang. Syst. 8(2), 244–263 (1986)

    Article  MATH  Google Scholar 

  15. Conitzer, V., Sandholm, T.: Complexity results about Nash equilibria. Technical report CMU-CS-02-135, School of Computer Science, Carnegie-Mellon University (2002)

  16. Friedman, N., Halpern, J.Y.: A knowledge-based framework for belief change, Part I: foundations. In: Proceedings of TARK, pp. 44–64 (1994)

  17. Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-completeness. Freeman, W.H., San Francisco (1979)

    MATH  Google Scholar 

  18. Gilboa, I., Zemel, E.: Nash and correlated equilibria: some complexity considerations. Games Econom. Behav. 1, 80–93 (1989)

    Article  MATH  MathSciNet  Google Scholar 

  19. Goranko, V., Jamroga, W.: Comparing semantics of logics for multi-agent systems. Synthese 139(2), 241–280 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  20. Harrenstein, B.P., van der Hoek, W., Meyer, J.-J., Witteveen, C.: A modal characterization of Nash equilibrium. Fundam. Inform. 57(2–4), 281–321 (2003)

    MATH  Google Scholar 

  21. Harrenstein, P., van der Hoek, W., Meijer, J-J., Witteveen, C.: Subgame-perfect Nash equilibria in dynamic logic. In: Pauly, M., Baltag, A. (eds.) Proceedings of the ILLC Workshop on Logic and Games, pp. 29–30. University of Amsterdam (2002) Tech. Report PP-1999-25.

  22. Herzig, A., Troquard, N.: Knowing how to play: uniform choices in logics of agency. In: Proceedings of AAMAS’06, pp. 209–216 (2006)

  23. Jamroga, W.: Reducing knowledge operators in the context of model checking. Technical report IfI-07-09, Clausthal University of Technology (2007)

  24. Jamroga, W., Ågotnes, T.: What agents can achieve under incomplete information. In: Proceedings of AAMAS’06, pp. 232–234. ACM, New York (2006)

    Google Scholar 

  25. Jamroga, W., Bulling, N.: A framework for reasoning about rational agents. In: Proceedings of AAMAS’07, pp. 592–594 (2007)

  26. Jamroga, W., Bulling, N.: A logic for reasoning about rational agents. In: Sadri, F., Satoh, K. (eds.) Computational Logic in Multi-Agent Systems, 8th InternationalWorkshop, CLIMA VIII, Revised Selected and Invited Papers. Lecture Notes, Porto, Portugal, September. pp. 42–61. Springer (2007)

  27. Jamroga, W., Dix, J.: Model checking ATL ir is indeed \(\Delta_2^P\)-complete. In: Proceedings of EUMAS’06 (2006)

  28. Jamroga, W., Dix, J.: Model checking abilities of agents: a closer look. Theory of Computing Systems, 42(3):366–410, (2008)

    Article  MATH  MathSciNet  Google Scholar 

  29. Jamroga, W., van der Hoek W.: Agents that know how to play. Fundam. Inform. 63(2–3):185–219 (2004)

    MATH  Google Scholar 

  30. Jamroga, W., van der Hoek, W., Wooldridge, M.: Intentions and strategies in game-like scenarios. In: Bento, C., Cardoso, A., Dias, G. (eds.) Progress in Artificial Intelligence: Proceedings of EPIA 2005. Lecture Notes in Artificial Intelligence, vol. 3808, pp. 512–523. Springer, New York (2005)

    Chapter  Google Scholar 

  31. Koller, D., Megiddo, N.: The complexity of twoperson zero-sum games in extensive form. Games Econom. Behav. 4, 528–552 (1992)

    Article  MATH  MathSciNet  Google Scholar 

  32. Laroussinie, F., Markey, N., Schnoebelen Ph.: Model checking CTL+ and FCTL is hard. In: Proceedings of FoSSaCS’01. Lecture Notes in Computer Science, vol. 2030, pp. 318–331. Springer, New York (2001)

    Google Scholar 

  33. Andreu Mas-Colell, Michael Whinston, D., Jerry Green, R.: Microeconomic Theory. Oxford (1995)

  34. Moses, Y., Tennenholz, M.: Artificial social systems. Comput. Artif. Intell. 14(6), 533–562 (1995)

    Google Scholar 

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

    Google Scholar 

  36. Papadimitriou, C.H.: Computational Complexity. Addison Wesley, Reading (1994)

    MATH  Google Scholar 

  37. Tuomas Sandholm, W.: Distributed rational decision making. In: Gerhard Weiss (ed.) Multiagent Systems: A Modern Approach to Distributed Artificial Intelligence, pp. 201–258. MIT, Cambridge, MA, USA (1999)

    Google Scholar 

  38. Schobbens, P.Y.: Alternating-time logic with imperfect recall. Electronic Notes in Theoretical Computer Science, 85(2), 82–93 (2004)

    Article  MathSciNet  Google Scholar 

  39. Shoham, Y., Tennenholz, M.: On the synthesis of useful social laws for artificial agent societies. In: Proceedings of AAAI-92 (1992)

  40. Ståhl, I.: Bargaining Theory. Stockholm School of Economics, Stockholm (1972)

    Google Scholar 

  41. Stalnaker, R.: On the evaluation of solution concepts. Theory Decis. 37(1), 49–73 (1994)

    Article  MATH  MathSciNet  Google Scholar 

  42. Stalnaker, R.: Knowledge, belief and counterfactual reasoning in games. Econ. Philos. 12, 133–163 (1996)

    Google Scholar 

  43. Su, K., Sattar, A., Governatori, G., Chen, Q.: A computationally grounded logic of knowledge, belief and certainty. In: Proceedings of AAMAS’05, pp. 149–156. ACM, New York (2005)

    Google Scholar 

  44. van Benthem, J.: Rational dynamics and epistemic logic in games. In: Vannucci, S. (ed.) Logic, Game Theory and Social Choice III, pp. 19–23 (2003)

  45. van der Hoek, W., Jamroga, W., Wooldridge, M.: A logic for strategic reasoning. In: Proceedings of AAMAS’05, pp. 157–164 (2005)

  46. van der Hoek, W., Roberts, M., Wooldridge, M.: Social laws in alternating time: Effectiveness, feasibility and synthesis. Synthese 156(1), 1–19 (2005)

    Article  Google Scholar 

  47. van der Hoek, W., Wooldridge, M.: Tractable multiagent planning for epistemic goals. In: Castelfranchi, C., Johnson, W.L. (eds.) Proceedings of the First International Joint Conference on Autonomous Agents and Multi-Agent Systems (AAMAS-02), pp. 1167–1174. ACM, New York (2002)

    Chapter  Google Scholar 

  48. van Otterloo, S., Jonker, G.: On epistemic temporal strategic logic. In: Proceedings of LCMAS’04. Electronic Notes in Theoretical Computer Science, vol. XX, pp. 35–45 (2004)

  49. van Otterloo, S., Roy, O.: Verification of voting protocols. Working paper, University of Amsterdam (2005)

  50. van Otterloo, S., van der Hoek, W., Wooldridge, M.: Preferences in game logics. Preliminary version, unpublished manuscript (2004)

  51. van Otterloo, S., van der Hoek, W., Wooldridge, M.: Preferences in game logics. In: Proceedings of AAMAS-04, pp. 152–159 (2004)

Download references

Author information

Authors and Affiliations

  1. Standort Clausthal, Institut für Informatik, Niedersächsische Technische Hochschule (NTH), Julius-Albert-Straße 4, 38678, Clausthal-Zellerfeld, Germany

    Nils Bulling, Wojciech Jamroga & Jürgen Dix

Authors
  1. Nils Bulling
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Wojciech Jamroga
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Jürgen Dix
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Nils Bulling.

Additional information

This article is dedicated to Victor W. Marek on the occasion of his 65th birthday. The third author very gratefully acknowledges Victor’s help and support in the past.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Bulling, N., Jamroga, W. & Dix, J. Reasoning about temporal properties of rational play. Ann Math Artif Intell 53, 51–114 (2008). https://doi.org/10.1007/s10472-009-9110-4

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10472-009-9110-4

Keywords

Mathematics Subject Classifications (2000)

Search

Navigation