Social laws in alternating time: effectiveness, feasibility, and synthesis

Synthese 156 (1):1-19 (2007)


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" 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. 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

Download options


    Upload a copy of this work     Papers currently archived: 72,856

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library


Added to PP

26 (#444,385)

6 months
1 (#386,016)

Historical graph of downloads
How can I increase my downloads?

References found in this work

Autonomous Agents with Norms.Frank Dignum - 1999 - Artificial Intelligence and Law 7 (1):69-79.
Preface.Michael Wooldridge & Wiebe van der Hoek - 2003 - Studia Logica 75 (1):3-5.

Add more references

Similar books and articles

Davidson and Social Scientific Laws.Lee McIntyre - 1999 - Synthese 120 (3):375-394.
Editorial.Wiebe van der Hoek - 2004 - Synthese 139 (2):5-8.
Editorial.Wiebe van der Hoek - 2004 - Synthese 139 (2):133-134.
Davidson and Kim on Psychophysical Laws.Noa Latham - 1999 - Synthese 118 (2):121-143.
Laws and Development.David Resnik - 1997 - Synthese 112 (1):37-51.