The b-Core: Belief-based Coalition Stability - Belief-based Stability in Coalition Formation with Uncertainty - page 74

be willing to provide any of such information at all. Thus, without any
publicly known preferences, agents often have to resort to their own
internal knowledge (or beliefs) during the coalition formation process.
Generally, there is no such things as common knowledge in the multi-
agent world.
Example 4.1 You are going to dine out with your new girlfriend
Mary. According to your observation, Mary seems to quite like French
cuisines. So you propose that you two would eat at the Bonheur
Restaurant . Unfortunately, your perception about your new girlfriend
is actually wrong. She actually prefers Chinese food, like you, and
share with you the same favourite restaurant Yung Kee .Henceyour
small coalition with your new girlfriend, formed under uncertainty (in
the form of unfortunate misbelief), does not achieve the optimal util-
ity by dining at Bonheur Restaurant . A better utility for both of you
could have been obtained by dining at Yung Kee . However, the better
option of dining at Yung Kee has not been achievable due to the mu-
tual lack of knowledge of other players' preference, a phenomenon that
is more commonly known as 'misunderstanding'. Interesting enough,
the formed coalition based on mutual misunderstanding can be stable.
For example, Mary might still be happy to accept your invitation if
she (mistakenly) believes that you also prefer French food.
Let us consider a typical propose-and-evaluate type of coalition
formation mechanism, such as the randomised distributed mechanism
proposed by Kraus, Shehory and Taase [1], where coalitions are formed
in steps. In each step, one or more agents are allowed to send proposal
messages to a subset of agents for forming new coalitions to accom-
plish a certain task. The agents receiving the proposal will have the
choice of either accepting or rejecting after evaluating the proposal,
and a coalition will be formed only if the proposal is accepted by all
parties invited. The coalition formation will then either end at this
point or continue (during which new coalition will be formed and old
ones may break to make way for the newer ones) until there are no