Abstract
Since it was first proposed by Moses, Shoham, and Tennenholtz, the social laws paradigm has proved to be one of the most compelling approaches to the offline coordination of multiagent systems. In this paper, we make four key contributions to the theory and practice of social laws in multiagent systems. First, we show that the Alternating-time Temporal Logic (atl) of Alur, Henzinger, and Kupferman provides an elegant and powerful framework within which to express and understand social laws for multiagent systems. Second, we show that the effectiveness, feasibility, and synthesis problems for social laws may naturally be framed as atl model checking problems, and that as a consequence, existing atl model checkers may be applied to these problems. Third, we show that the complexity of the feasibility problem in our framework is no more complex in the general case than that of the corresponding problem in the Shoham–Tennenholtz framework (it is np-complete). Finally, we show how our basic framework can easily be extended to permit social laws in which constraints on the legality or otherwise of some action may be explicitly required. We illustrate the concepts and techniques developed by means of a running example.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Alur R., Henzinger T.A., Kupferman O. (2002). Alternating-time temporal logic. Journal of the ACM, 49(5): 672–713
Alur, R., Henzinger, T. A., Mang, F. Y. C., Qadeer, S., Rajamani, S. K., & Taşiran, S. (1998). Mocha: Modularity in model checking. In CAV 1998: Tenth International Conference on Computer-aided Verification (LNCS Volume 1427) (pp. 521–525). Berlin, Germany: Springer-Verlag.
Blackburn P., de Rijke M., Venema Y. (2001). Modal Logic. Cambidge University Press, Cambridge, England
Clarke E.M., Grumberg O., Peled D.A. (2000). Model Checking. The MIT Press, Cambridge, MA
Dignum F. (1999). Autonomous agents with norms. Artificial Intelligence and Law, 7, 69–79
van Drimmelen, G. (2003). Satisfiability in alternating-time temporal logic. In Eighteenth Annual IEEE Symposium on Logic in Computer Science (LICS 2003) (pp. 208–217). Ottawa, Canada.
Durfee E.H. (1999). Distributed problem solving and planning. In: Weiß G. (Eds). Multiagent systems. The MIT Press, Cambridge, MA, pp. 121–164
Emerson E.A. (1990). Temporal and modal logic. In: van Leeuwen J. (Eds). Handbook of theoretical computer science volume B: Formal models and semantics. Elsevier Science Publishers B.V., Amsterdam, The Netherlands, pp. 996–1072
Fitoussi D., Tennenholtz M. (2000). Choosing social laws for multi-agent systems: Minimality and simplicity. Artificial Intelligence, 119(1–2): 61–101
van der Hoek, W., & Wooldridge, M. (2002). Tractable multiagent planning for epistemic goals. In Proceedings of the First International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS-2002) (pp. 1167–1174). Bologna, Italy.
van der Hoek W., Wooldridge M. (2003a). Model checking cooperation, knowledge, and time—a case study. Research in Economics, 57(3): 235–265
van der Hoek W., Wooldridge M. (2003b). Time, knowledge, and cooperation: Alternating-time temporal epistemic logic and its applications. Studia Logica, 75(1): 125–157
Moses Y., Tennenholtz M. (1995). Artificial social systems. Computers and AI, 14(6): 533–562
Papadimitriou C.H. (1994). Computational complexity. Addison-Wesley, Reading, MA
Pauly, M. (2001). Logic for Social Software PhD thesis, University of Amsterdam, ILLC Dissertation Series 2001–10.
Pauly M. (2002). A modal logic for coalitional power in games. Journal of Logic and Computation, 12(1): 149–166
Shoham, Y., & Tennenholtz, M. (1992). On the synthesis of useful social laws for artificial agent societies. In Proceedings of the Tenth National Conference on Artificial Intelligence (AAAI-92), San Diego, CA.
Shoham Y., Tennenholtz M. (1996). On social laws for artificial agent societies: Off-line design. In: Agre P.E., Rosenschein S.J. (Eds). Computational theories of interaction and agency. The MIT Press, Cambridge, MA, pp. 597–618
Shoham Y., Tennenholtz M. (1997). On the emergence of social conventions: Modelling, analysis, and simulations. Artificial Intelligence, 94(1–2): 139–166
Wooldridge, M. (2002). An introduction to multiagent systems JohnWiley & Sons.
Author information
Authors and Affiliations
Corresponding author
Additional information
This paper was presented at the Social Software conference in May 2004, Copenhagen, organised by PHILOG. We thank the organisers for providing the opportunity, and the participants for their useful feedback.
Rights and permissions
About this article
Cite this article
van der Hoek, W., Roberts, M. & Wooldridge, M. Social laws in alternating time: effectiveness, feasibility, and synthesis. Synthese 156, 1–19 (2007). https://doi.org/10.1007/s11229-006-9072-6
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11229-006-9072-6