Information Technology Reference
In-Depth Information
The second class of algorithms are oriented towards providing solutions rapidly,
however not guaranteeing optimality, nor worst-case bounds for the solution. This type
of algorithms is known to be scalable and more applicable to real scenarios. Amongst
them we mention several notable efforts employing, genetic algorithms [14], swarm op-
timization [17] or constraint satisfaction techniques [3]. However, the limitation of these
algorithms lies in that they represent a centralized, one-shot optimization procedure.
Thirdly, we identify the class of decentralized and dynamic methods. Here, quite the
opposite, considering a multi-agent environment, it is desirable that computing the solu-
tion could be achieved in a decentralized manner, based on the agents' local utility com-
putations, that seek to find feasible coalition structures through series of negotiations.
The suitability of decentralized scenarios, apart for advocating for the autonomy of the
agents in such setings, applies to manifold scenarios where coalitions have to adapt
their structure due to the dynamic nature of the environment. Along these lines, Klush
et al. introduced in [7] a distributed and completely decentralized process for coalition
formation, able of operating in open systems. Another relevant instances of such an al-
gorithm is the one proposed by Apt et al in [2], though limiting, in the sense of allowing
transformations only to make use of simple split and merge rules. A satisfying coali-
tion formation algorithms is proposed in [15]. Here, agents have an incomplete view
of the world, time and computational constraints, the coalition formation goal being
one of meeting minimum requirements rather than achieving maximum performance.
This allows for a more malleable framework of negotiation in contrast to the typical
techniques based on optimization of utility functions. Moreover, the dynamism of the
system does not allow the agents to rationalize optimally, but rather to engage in op-
portunistic negotiations and of high-risk, as the success of the formation of a coalition
cannot be guaranteed.
In this paper, we propose a mechanism that addresses the domain-dependent con-
straints posed by the electricity domain, which classifies our approach to the decentral-
ized and dynamic solutions.
3
Problem Representation
The coalition games we aim to address in our approach are the ones where the coalition
formation problem is projected on an underlying network topology, given that the cost
for cooperation also plays a major role. This class of games is primarily characterized
by non-superadditivity, in the sense that gains resultant from forming coalitions are lim-
ited by the actual cost of coalition formation
1
and coordination, thus the grand coalition
is seldom the optimal structure. Furthermore, the coalitional game is subject to the dy-
namism of the environment. The challenge is to develop mechanisms that permit large
number of autonomous agents to collectively achieve a desired functionality by perma-
nent adaptive dynamics. In contrast to static coalition formation, dynamic coalitional
games represent a more complex issue since the focus is not merely in analyzing the
coalitional structure, but the main aspect under investigation is how the formation of the
coalitional structure takes place through the players' interactions and its adaptability to
1
The cost of forming a coalition can be perceived through the negotiation process and informa-
tion exchange which incur costs.
