Shoham and Tennenholtz have written a most interesting paper, one that may well prove to be seminal. The question they consider is one of distributed artificial intelligence, although the specific application treated is robotics. The question is “How can we make artificial agents cooperate?” Prior work took two approaches, both, Shoham and  Tennenholtz  successfully argue, too extreme. The first is to plan the agents’ behavior fully off-line with a central coordinator making all decisions: in that case, we do not have true agents. The second alternative is to allow agents to behave freely, dealing with all conflicts online as they arise by negotiation between the agents. In the case of robots, typical conflicts include the intersection of “the planned space-time paths of robots,” the removal of “an object needed by one robot…by another,” and bottlenecks.

This contribution adopts a middle-of-the-road strategy: “why not adopt a convention, or, as we’d like to think of it, a social law, according to which each” agent follows procedures that prevent conflicts?

The first part of the paper presents a case study involving mobile robots that follow traffic laws; the paradigmatic situation involves eight conditions (their Traffic Law 2). In addition to elaborating these laws and proving that they succeed in avoiding conflicts, the authors present a comprehensive analysis of their complexity.

The second part of the paper presents “a more general treatment of social laws in a computational setting,” treating the question of how to derive useful social laws for a given (abstract) social system. The authors prove that, in general, finding such a law in a multi-agent system where each agent has n states is NP-complete, but that if the number of transitions that might change a particular state is bounded by O ( log n ) and several additional restrictions apply, the problem becomes polynomial in n.

The paper is not cluttered with excessive mathematical detail, is not too long, and is well written, three desiderata that other papers in the journal often do not meet. More important, the work itself is well done and should prove important--it may be a starting point for much future research.