Robust normative systems

ABSTRACT

Although normative systems, or social laws, have proved to be a highly influential approach to coordination in multi-agent systems, the issue of compliance to such normative systems remains problematic. In all real systems, it is possible that some members of an agent population will not comply with the rules of a normative system, even if it is in their interests to do so. It is therefore important to consider the extent to which a normative system is robust, i.e., the extent to which it remains effective even if some agents do not comply with it. We formalise and investigate three different notions of robustness and related decision problems. We begin by considering sets of agents whose compliance is necessary and/or sufficient to guarantee the effectiveness of a normative system; we then consider quantitative approaches to robustness, where we try to identify the proportion of an agent population that must comply in order to ensure success, and finally, we consider a more general approach, where we characterise the compliance conditions required for success as a logical formula.

REFERENCES

• 1: T. Ågotnes, W. van der Hoek, J. A. Rodriguez-Aguilar, C. Sierra, and M. Wooldridge. On the logic of normative systems. In Proc. of the Twentieth Inter. Joint Conf. on Artificial Intelligence (IJCAI-07), Hyderabad, India, 2007.
• 2: Thomas Ågotnes , Wiebe van der Hoek , Michael Wooldridge, Normative system games, Proceedings of the 6th international joint conference on Autonomous agents and multiagent systems, May 14-18, 2007, Honolulu, Hawaii [doi>10.1145/1329125.1329284]
• 3: T. Ågotnes, W. van der Hoek, and M. Wooldridge. Quantified coalition logic. In Proc. of the Twentieth Intern. Joint Conf. on Artificial Intelligence (IJCAI-07), Hyderabad, India, 2007.
• 4: R. Axelrod. An evolutionary approach to norms. American Political Science Review, 80(4):1095--1110, 1986.
• 5: E. Allen Emerson, Temporal and modal logic, Handbook of theoretical computer science (vol. B): formal models and semantics, MIT Press, Cambridge, MA, 1991
• 6: 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]
• 7: Tim French , John C. Mc Cabe-Dansted , Mark Reynolds, A Temporal Logic of Robustness, Proceedings of the 6th international symposium on Frontiers of Combining Systems, September 10-12, 2007, Liverpool, UK [doi>10.1007/978-3-540-74621-8_13]
• 8: W. van der Hoek, M. Roberts, and M. Wooldridge. Social laws in alternating time: Effectiveness, feasibility, and synthesis. Synthese, 156(1):1--19, May 2007.
• 9: David S. Johnson, A catalog of complexity classes, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
• 10: M. J. Osborne and A. Rubinstein. A Course in Game Theory. The MIT Press: Cambridge, MA, 1994.
• 11: Y. Shoham and M. Tennenholtz. 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, 1992.
• 12: Y. Shoham and M. Tennenholtz. On social laws for artificial agent societies: Off-line design. In P. E. Agre and S. J. Rosenschein, editors, Computational Theories of Interaction and Agency, pages 597--618. The MIT Press, 1996.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.4 Knowledge Representation Formalisms and Methods

General Terms:
Theory

Keywords:
complexity, fault tolerance, normative systems, robustness