On the Synthesis of Useful Social Laws for Artificial Agent Societies (Preliminary Report)

Book One

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 10

Multi-Agent Coordination

We present a general model of social law in a computational system, and investigate some of its properties. The contribution of this paper is twofold. First, we argue that the notion of social law is not epiphenomenal, but rather should be built into the action representation; we then offer such a representation. Second, we investigate the complexity of automatically deriving useful social laws in this model, given descriptions of the agents’ capabilities, and the goals they might encounter. We show that in general the problem is NP-complete, and identify precise conditions under which it becomes polynomial.