Negotiation and Task Sharing Among Autonomous Agents in Cooperative Domains

Abstract

Research in Distributed Ar~tificial Intelligence is concerned with how automated agents can be designed to interact effectively. One important capability that could aid inter-agent cooperation would be that of negotiation : agents could be built that are able to communicate their respective desires and compromise to reach mutually beneficial agreements. This work uses the language of game theory to analyze negotiation among automated agents in cooperative domains. However, while game theory generally deals with negotiation in continuous domains and among agents with full information, this research considers discrete domains and the case where agents have only partial information, assumptions of greater interest for artificial intelligence. A novel, stable, negotiation protocol is introduced for the case of agents who are able to share a discrete set of tasks with one another. The case of agents who may lie to one another during the negotiation, either by hiding some of their tasks or by creating fictitious tasks, is analyzed; it is shown that under some conditions lies are beneficial and "safe," i.e., undiscoverable, while under other circumstances, lies can never be safe.