Séminaire de Mathématiques Discrètes,
Optimisation et Décision

# Gleb Koshevoy (Central Economics and Mathematics Institute of the Russian Academy of Sciences)

# Solution concepts for games with general coalitional structure

We introduce a theory on marginal values and their core stability for cooperative games with arbitrary coalition structure. The theory
is based on the notion of nested sets and the complex of nested sets associated to an arbitrary set system and the M-extension of a
game for this set system. For a set-system being a building set, the corresponding
complex is a polyhedral complex, and the vertices of this complex correspond to maximal strictly nested sets. To each
maximal strictly nested set is associated a rooted tree. For a given characteristic function on a building set and a maximal
strictly nested set, we define a marginal value associated to the corresponding tree as in \cite{demange}. We show that the same marginal
value is obtained by using the M-extension for every permutation that is associated to the rooted tree. The GC-solution is defined as the
average of the marginal values over all maximal strictly nested sets. The solution can be viewed as the gravity center of the
image of the vertices of the polyhedral complex. The GC-solution differs from the Myerson-kind value defined in \cite{ab} for union
stable structures. The HS-solution is defined as the average of marginal values over the subclass of so-called half-space nested sets.
The NT-solution is another solution and is defined as the average of marginal values over the subclass of NT-nested sets. For graphical
buildings the collection of NT-nested sets corresponds to the set of spanning normal trees on the underlying graph and the NT-solution coincides
with the average tree solution. We also study core stability of the solutions and show that both the HS-solution and NT-solution belong to the
core under half-space supermodularity, which is a weaker condition than convexity of the game.
For an arbitrary set system we show that there exists a unique minimal building set containing the set system.
As solutions we take the solutions for this building covering by extending in a natural way the characteristic function to it
by using its Möbius inversion.