Non-transferable Utility Games and Coalition Formation Mechanisms - Belief-based Stability in Coalition Formation with Uncertainty - page 23

Later, two related greedy algorithm-based heuristics (one determinis-
tic, one not) were proposed in [14]. However, stability was not handled,
and social utility was used instead. Then in [15] a round-based mecha-
nism was proposed for TU games, where the agents, arranged in some
random order, are allowed to make proposals to other agents, and
coalitions are formed when they are accepted by all agents. The au-
thors used social utility as the evaluation criterion in their experiments.
Kernel was later used in an enhanced version of their mechanism [16].
Other coalition formation mechanisms have been proposed for spe-
cific applications. For example, in a buyer coalition mechanism, an ap-
proach targeting TU-core-based solutions was proposed in [13]. Later,
in 2006, a centralized mechanism was proposed in [19], where the au-
thors used Pareto optimality as measurement of their solution qual-
ity. More recently, a distributed randomized mechanism approach has
been proposed, in which the evaluation criteria used was both Pareto
optimality and the NTU core [20].
A summary is given in Table 2.1.

Tab l e 2 . 1 Selected coalition formation mechanisms and their solution
concepts

Game
Type

Common
Knowledge

Mechanism Approach Solution Concept

[10] Auction TU Core Yes

[11] Propose-and-Evaluate TU Kernel Yes

[12] Propose-and-Evaluate TU Core Yes

[13] Greedy Algorithm TU Social utility and Core Yes

[14] Greedy Algorithm TU Social utility Yes

[15] Propose-and-Evaluate TU Social utility No

[16] Propose-and-Evaluate TU Social utility and Kernel No

[17] Propose-and-Evaluate TU Core Yes

[18] Auction TU Social utility Yes

[19] Centralised Search NTU Pareto Optimality Yes

[20] Propose-and-Evaluate NTU Pareto Optimality and Core Yes