Information Technology Reference
In-Depth Information
Fig. 1.
The coalition formation model
2.2
Coalition Formation Model
Coalition formation is an important mechanism for cooperation in Multi-Agent Sys-
tems (MAS). In order to be used by autonomous agents, a coalition formation mecha-
nism must solve the following issues: i) maximise the agents' profit or utility. For every
coalition
S
, coalitional value
V
(
S
)
must be computed, i.e., the total utility obtained by
S
as a whole ii) divide the total utility among agents in a fair and stable way, so that
the agents in the coalition are not motivated to abandon it. For every coalition
S
and
every agent
i
S
, payment configuration
x
(
i
)
must be computed, i.e., the share of
V
(
S
)
that is assigned to the agent
i
. iii) do this within a reasonable amount of time and
using a reasonable amount of computational efforts. Our coalition formation model al-
lows cooperation to take place between autonomous, rational and self-interested agents
in a class of superadditive task oriented domains [15]. Each agent has the necessary
resources to carry out its own task, however it is possible to form a coalition between
agents with a new re-distribution of the task that may allow them to obtain benefits. The
proposed model guarantees an optimum task allocation and a stable payoff division.
Furthermore, computational complexity problems are solved.
In this section the coalition formation scheme is applied with the goal of improving
the performance of P2P file exchange systems. In this case, the central idea is based on
sharing the task of downloading a file among a set of peers forming a coalition. From
the point of view of the peer that wants to download the file there is a clear advantage,
since the total download time is reduced. From the point of view of uploading peers,
for each one the task of transferring the file is alleviated, since it is divided between the
members of the coalition.
Let us consider the simplified situation illustrated in figure 1. In this scenario, peer
p
b
,asks
p
a
for a file
Z
. This peer
p
a
forms a coalition
S
with three other peers
p
h
,
p
l
and
p
m
to transfer that file. In P2P file sharing systems, every node
p
m
has an upload
b
i
i
and download
b
ou
i
bandwidth dedicated to file sharing. Usually these bandwidths are
user defined and indicate maximum values, and
b
i
i
is much lower than
b
ou
i
.Thissim-
plified scenario can be generalised, we can consider that the downloader peer splits its
bandwidth in order to perform simultaneous downloads, determining the
b
out
i
∈
dedicated
for each download. The model is valid for both scenarios.
