Coalition Formation for Large-Scale Electronic Markets
K. Lerman* and O. Shehory**
* Information Sciences Institute
Univ. of Southern California
Marina del Rey, CA 90292-6695
** IBM Research Lab in Haifa, the Tel-Aviv site,
Tel-Aviv, 61336 Israel
November 15, 1999
Abstract
Coalition formation is a desirable behavior in a multi-agent system, when
a group
of agents can perform a task more effciently than any single agent
can. Computa-
tional and communications complexity of traditional approaches to coalition
forma-
tion, e.g., through negotiation, make them impractical for large systems.
We propose
an alternative, physics-motivated mechanism for coalition formation
that treats agents
as randomly moving, locally interacting entities. A new coalition may
form when two
agents encounter one another, and it may grow when a single agent encounters
it. Such
agent-level behavior leads to a macroscopic model that describes how
the number and
distribution of coalitions change with time. We increase the generality
and complexity
of the model by letting the agents leave coalitions with some probability.
The model
is expressed mathematically as a series of di erential equations. These
equations have
steady state solutions that describe the equilibrium distribution of
coalitions. Within
a context of a speci c multi-agent application, we analyze and discuss
the connection
between the global system utility and the parameters of the model.
(Full text)