David Fitoussi, Moshe Tennenholtz
Research on social laws in computational environments has proved the usefulness of the law-based approach for the coordination of multi-agent systems. Though researchers have noted that the imposition of a specification could be attained by a variety of different laws, there has been no attempt to identify a criterion for selection among alternative useful social laws. We propose such a criterion which is based on the notion of minimality. A useful social law puts constraints on the agents’ actions in such away that as a result of these constraints, they are able to achieve their goals. A minimal social law is a useful social law that minimizes the amount of constraints the agents shall obey. Minimal social laws give an agent maximal exibility inchoosing a new behavior as a function of various local changes either in his capabilities or in his objectives, without interfering with the other agents. We show that this concept can be usefully applied to a problem in robotics and present a computational study of minimal social laws.