Choosing social laws for multi-agent systems: Minimality and simplicity

The design of social laws for artificial agent societies is a basic approac h to coordinating multi-agent systems. It exposes the spectrum between full y-centralized and fully-decentralized coordination mechanisms. Useful socia l laws set constraints on the agents' activities which allow them to work i ndividually in a mutually compatible manner. The design of useful social la ws is a problem of considerable importance. In many cases, several useful s ocial laws might be considered, and we might wish to have some criteria in order to choose among them. In this paper, we present the notions of minima l and simple social laws, which capture two basic criteria for selecting am ong alternative (useful) social laws, and study these criteria in the frame work of basic settings, namely Automated Guided Vehicles and Distributed Co mputing. We also present results with regard to computational issues relate d to minimal and simple social laws, and to the relationship between these two concepts. Together, the new insights provided here can be used as a bas ic framework for the analysis of "good" social laws, and initiate research on the selection among alternative social laws. (C) 2000 Elsevier Science B .V. All rights reserved.