Thomas Ågotnes
Michael Wooldridge
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.
- 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. Google Scholar
Digital Library
- R. Alur, T. A. Henzinger, and O. Kupferman. Alternating-time temporal logic. Jnl. of the ACM, 49(5):672--713, 2002. Google ScholarDigital Library
- K. Binmore. Game Theory and the Social Contract Volume 1: Playing Fair. The MIT Press: Cambridge, MA, 1994.Google Scholar
- K. Binmore. Game Theory and the Social Contract Volume 2: Just Playing. The MIT Press: Cambridge, MA, 1998.Google Scholar
- V. Conitzer and T. Sandholm. Complexity of mechanism design. In Proc. UAI, Edmonton, Canada, 2002. Google ScholarDigital Library
- V. Conitzer and T. Sandholm. Complexity results about nash equilibria. In Proc. IJCAI-03, pp. 765--771, Acapulco, Mexico, 2003. Google ScholarDigital Library
- C. Daskalakis, P. W. Goldberg, and C. H. Papadimitriou. The complexity of computing a Nash equilibrium. In Proc. STOC, Seattle, WA, 2006. Google ScholarDigital Library
- E. A. Emerson. Temporal and modal logic. In Handbook of Theor. Comp. Sci. Vol. B, pages 996--1072. Elsevier, 1990. Google ScholarDigital Library
- E. A. Emerson and J. Y. Halpern. 'Sometimes' and 'not never' revisited: on branching time versus linear time temporal logic. Jnl. of the ACM, 33(1):151--178, 1986. Google ScholarDigital Library
- D. Fitoussi and M. Tennenholtz. Choosing social laws for multiagent systems: Minimality and simplicity. Artificial Intelligence, 119(1--2):61--101, 2000. Google ScholarDigital Library
- M. J. Osborne and A. Rubinstein. A Course in Game Theory. The MIT Press: Cambridge, MA, 1994.Google Scholar
- C. H. Papadimitriou. Computational Complexity. Addison-Wesley: Reading, MA, 1994.Google Scholar
- Y. Shoham and M. Tennenholtz. On the synthesis of useful social laws for artificial agent societies. In Proc. AAAI, San Diego, CA, 1992.Google Scholar
- 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.Google Scholar
- W. van der Hoek, M. Roberts, and M. Wooldridge. Social laws in alternating time: Effectiveness, feasibility, and synthesis. Synthese, 2007.Google ScholarCross Ref
- M. Wooldridge and W. van der Hoek. On obligations and normative ability. Jnl. of Appl. Logic, 3:396--420, 2005.Google ScholarCross Ref
Index Terms
- Normative system games
Recommendations
Reasoning under compliance assumptions in normative multiagent systems
AAMAS '12: Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems - Volume 1The use of norms in multiagent systems has proven to be a successful approach in order to coordinate and regulate the behaviour of participating agents. In such normative systems it is generally assumed that agents can obey or disobey norms. In this ...
A Role Based Model for the Normative Specification of Organized Collective Agency and Agents Interaction
In this article we propose a role based model for the specification of organized collective agency, based on the legal concept of artificial person and on the normative perspective of organizational systems. We focus on the analysis of groups of agents (...
On the multimodal logic of normative systems
COIN'07: Proceedings of the 2007 international conference on Coordination, organizations, institutions, and norms in agent systems IIIWe introduce Multimodal Logics of Normative Systems as a contribution to the development of a general logical framework for reasoning about normative systems over logics for Multi-Agent Systems. Given a multimodal logic L, for every modality □i and ...
Comments