Multi-agent Cooperation and Stability - Belief-based Stability in Coalition Formation with Uncertainty - page 9

any solutions satisfying those criteria are indeed stable even if the
agents are self-interested, which make them useful concepts in many
applications. For example, many works in coalition formation perform
experiments to measure the percentage of their solutions that are sta-
ble according to the core (or other stability concepts) as indicators of
the quality of their proposed mechanisms.
However, one problem still remains: these classical game theoreti-
cal concepts (no matters the utilities are transferable or not) rely on
one important assumption: that all information are assumed to be
common knowledge — an assumption that is often not valid in semi-
competitive agent cooperation problems.
1.3 Problem with the Common Knowledge
Assumption
There is an important assumption in the traditional cooperative games
theories approaches, namely that all agent's utility functions or pref-
erences are assumed to be common knowledge . That is, each agent is
assumed to know, accurately and without any uncertainty, not only
his own preferences regarding various outcomes, but also the prefer-
ences of all other agents, and that each agent also knows that everyone
knows his preferences, and this fact is also known by everyone, etc.
However, such an assumption violates the standard multi-agent
assumption that the agents are not omniscient, meaning that each
agent knows nothing more than its beliefs, and yet these beliefs are
fallible, and there may be uncertainties in the beliefs.
Firstly, regarding fallible beliefs, consider a simple case with three
agents, Peter, Mary and John. The three agents are negotiating the
important question of where they are going for lunch. Both Peter and
Mary's most preferred choice are actually to go, just two of them, to
a local steak house, with the second choice being a nearby canteen in