ECAI 2004 Conference Paper

[full paper]

Equilibrium Strategies for Task Allocation in Dynamic Multi-Agent System

David Sarne, Meirav Hadad, Sarit Kraus

In this paper we address a model of self interested agents competing over performing tasks. The agents are situated in an uncertain environment while different types of tasks are dynamically arriving from a central manager. The agents differ in their skills to perform a task under different world states. In such environments, previous models concerning cooperative agents aiming for a joint goal are not applicable, as self interested agents has a motivation to deviate from the joint allocation strategy in order to increase their private benefits. A stable solution, is a set of strategies, derived from equilibrium where no agent can benefit from changing its strategy given the other agents' strategies and the allocation protocol set by the central manager. Specifically we focus on a protocol in which upon arrival of a new task, the central manager starts a reverse auction among the agents, and the agent who bids the lowest payment wins. We introduce the model, formulate its equations and suggest equilibrium strategy for the agents. Identifying some specific characteristics of the equilibria, we manage to suggest an efficient algorithm for enhancing the agents' equilibrium strategies calculation. Comparison to the central allocation mechanism, and the effect of environmental settings over the perceived equilibrium are given through simulation.

Keywords: Multi-Agent Systems, Autonomous Agents, Distributed AI

Citation: David Sarne, Meirav Hadad, Sarit Kraus: Equilibrium Strategies for Task Allocation in Dynamic Multi-Agent System. In R.López de Mántaras and L.Saitta (eds.): ECAI2004, Proceedings of the 16th European Conference on Artificial Intelligence, IOS Press, Amsterdam, 2004, pp.1083-1084.