Optimal Social Laws

Social laws have proved to be a powerful and theoretically elegantframework for coordination in multi-agent systems. Most existingmodels of social laws assume that a designer is attempting to produce a set of constraints on agent behaviour which will ensure thatsome single overall desirable objective is achieved. However, thisrepresents a gross simplification of the typical situation, where adesigner may have multiple (possibly conflicting) objectives, withdifferent priorities. Moreover, social laws, as well as bringing benefits, also have implementation costs: imposing a social law oftencannot be done at zero cost. We present a model of social lawsthat reflects this reality: it takes into account both the fact that thedesigner of a social law may have multiple differently valued objectives, and that the implementation of a social law is not cost-neutral. In this setting, designing a social law becomes an optimisation problem, in which a designer must take into account boththe benefits and costs of a social law. We investigate the issue ofrepresenting a designer's objectives, characterise the complexity ofthe optimal social law design problem, and consider possible constraints that lead to reductions in computational complexity. Wethen show how the problem of designing an optimal social law canbe formulated as an integer linear program.

Authors

• Thomas
• Aring; gotnes
• Michael Wooldridge University of Oxford

Keywords

• social laws
• normative systems
• logic
• optimisation
• complexity