COALITIONS AMONG INTELLIGENT AGENTS: A TRACTABLE CASE

Authors: Belmonte, M. V.; Conejo, R.; Pérez-de-la-Cruz, J. L.; Triguero, F.

Source: Computational Intelligence, Volume 22, Number 1, February 2006 , pp. 52-68(17)

Buy & download fulltext article:

Price: $48.00 plus tax (Refund Policy)

Abstract:

Coalition formation is an important mechanism for cooperation in multiagent systems. In this paper we address the problem of coalition formation among self-interested agents in superadditive task-oriented domains. We assume that each agent has some “structure,” i.e., that it can be described by the values taken by a set of m nonnegative attributes that represent the resources w each agent is endowed with. By defining the coalitional value as a function V of w, we prove a sufficient condition for the existence of a stable payment configuration—in the sense of the core—in terms of certain properties of V. We apply these ideas to a simple case that can be described by a linear program and show that it is possible to compute for it—in polynomial time—an optimal task allocation and a stable payment configuration.

Keywords: agents; coalition; core

Document Type: Research article

DOI: http://dx.doi.org/10.1111/j.1467-8640.2006.00273.x

Affiliations: 1: Escuela Técnica Superior de Ingeniería Informática, Universidad de Málaga, Bulevar Luis Pasteur s/n, Málaga 29071, Spain

Publication date: 2006-02-01