Optimal Social Laws

Social laws have proved to be a powerful and theoretically elegant framework for coordination in multi-agent systems. Most existing models of social laws assume that a designer is attempting to pro- duce a set of constraints on agent behaviour which will ensure that some single overall desirable objective is achieved. However, this represents a gross simplification of the typical situation, where a designer may have multiple (possibly conflicting) objectives, with different priorities. Moreover, social laws, as well as bringing ben- efits, also have implementation costs: imposing a social law often cannot be done at zero cost. We present a model of social laws that reflects this reality: it takes into account both the fact that the designer of a social law may have multiple differently valued ob- jectives, and that the implementation of a social law is not cost- neutral. In this setting, designing a social law becomes an optimi- sation problem, in which a designer must take into account both the benefits and costs of a social law. We investigate the issue of representing a designer's objectives, characterise the complexity of the optimal social law design problem, and consider possible con- straints that lead to reductions in computational complexity. We then show how the problem of designing an optimal social law can be formulated as an integer linear program.