Normative system games

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Normative system games

Full text

Pdf (340 KB)

Source

International Conference on Autonomous Agents archive
Proceedings of the 6th international joint conference on Autonomous agents and multiagent systems table of contents

Honolulu, Hawaii

SESSION: Environments and implementation techniques: full papers table of contents

Article No. 129

Year of Publication: 2007

ISBN:978-81-904262-7-5

Authors

Thomas Ågotnes	Bergen University College, Bergen, Norway
Wiebe van der Hoek	University of Liverpool, Liverpool, UK
Michael Wooldridge	University of Liverpool, Liverpool, UK

Sponsor

: IFAAMAS

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 8, Downloads (12 Months): 38, Citation Count: 3

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1329125.1329284 What is a DOI?

ABSTRACT

We develop a model of normative systems in which agents are assumed to have multiple goals of increasing priority, and investigate the computational complexity and game theoretic properties of this model. In the underlying model of normative systems, we use Kripke structures to represent the possible transitions of a multiagent system. A normative system is then simply a subset of the Kripke structure, which contains the arcs that are forbidden by the normative system. We specify an agent's goals as a hierarchy of formulae of Computation Tree Logic (CTL), a widely used logic for representing the properties of Kripke structures: the intuition is that goals further up the hierarchy are preferred by the agent over those that appear further down the hierarchy. Using this scheme, we define a model of ordinal utility, which in turn allows us to interpret our Kripke-based normative systems as games, in which agents must determine whether to comply with the normative system or not. We then characterise the computational complexity of a number of decision problems associated with these Kripke-based normative system games; for example, we show that the complexity of checking whether there exists a normative system which has the property of being a Nash implementation is NP-complete.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	T. Agotnes, W. van der Hoek, J. A. Rodriguez-Aguilar, C. Sierra, and M. Wooldridge. On the logic of normative systems. In Proc. IJCAI-07, Hyderabad, India, 2007.
	2	Rajeev Alur , Thomas A. Henzinger , Orna Kupferman, Alternating-time temporal logic, Journal of the ACM (JACM), v.49 n.5, p.672-713, September 2002 [doi>10.1145/585265.585270]
	3	K. Binmore. Game Theory and the Social Contract Volume 1: Playing Fair. The MIT Press: Cambridge, MA, 1994.
	4	K. Binmore. Game Theory and the Social Contract Volume 2: Just Playing. The MIT Press: Cambridge, MA, 1998.
	5	V. Conitzer and T. Sandholm. Complexity of mechanism design. In Proc. UAI, Edmonton, Canada, 2002.
	6	V. Conitzer and T. Sandholm. Complexity results about nash equilibria. In Proc. IJCAI-03, pp. 765--771, Acapulco, Mexico, 2003.
	7	Constantinos Daskalakis , Paul W. Goldberg , Christos H. Papadimitriou, The complexity of computing a Nash equilibrium, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132527]
	8	E. Allen Emerson, Temporal and modal logic, Handbook of theoretical computer science (vol. B): formal models and semantics, MIT Press, Cambridge, MA, 1991
	9	E. Allen Emerson , Joseph Y. Halpern, “Sometimes” and “not never” revisited: on branching versus linear time temporal logic, Journal of the ACM (JACM), v.33 n.1, p.151-178, Jan. 1986 [doi>10.1145/4904.4999]
	10	David Fitoussi , Moshe Tennenholtz, Choosing social laws for multi-agent systems: minimality and simplicity, Artificial Intelligence, v.119 n.1-2, p.61-101, May 2000 [doi>10.1016/S0004-3702(00)00006-0]
	11	M. J. Osborne and A. Rubinstein. A Course in Game Theory. The MIT Press: Cambridge, MA, 1994.
	12	C. H. Papadimitriou. Computational Complexity. Addison-Wesley: Reading, MA, 1994.
	13	Y. Shoham and M. Tennenholtz. On the synthesis of useful social laws for artificial agent societies. In Proc. AAAI, San Diego, CA, 1992.
	14	Y. Shoham and M. Tennenholtz. On social laws for artificial agent societies: Off-line design. In Computational Theories of Interaction and Agency, pages 597--618. The MIT Press: Cambridge, MA, 1996.
	15	W. van der Hoek, M. Roberts, and M. Wooldridge. Social laws in alternating time: Effectiveness, feasibility, and synthesis. Synthese, 2007.
	16	M. Wooldridge and W. van der Hoek. On obligations and normative ability. Jnl. of Appl. Logic, 3:396--420, 2005.

CITED BY 3

	Thomas Ågotnes , Wiebe van der Hoek , Michael Wooldridge, Robust normative systems, Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems, May 12-16, 2008, Estoril, Portugal
	Michael Wooldridge , Thomas Agotnes , Paul E. Dunne , Wiebe Van der Hoek, Logic for automated mechanism design: a progress report, Proceedings of the 22nd national conference on Artificial intelligence, p.9-16, July 22-26, 2007, Vancouver, British Columbia, Canada
	Thomas Ågotnes , Wiebe van der Hoek , Moshe Tennenholtz , Michael Wooldridge, Power in normative systems, Proceedings of The 8th International Conference on Autonomous Agents and Multiagent Systems, May 10-15, 2009, Budapest, Hungary