96-33: Stable Families of Coalitions and Normal Hypergraphs

DIMACS TR: 96-33

Stable Families of Coalitions and Normal Hypergraphs

Authors: E. Boros, V. Gurvich, A. Vasin

ABSTRACT
The core of a game is defined as the set of outcomes acceptable for {\em all} coalitions. This is probably the simplest and most natural concept of cooperative game theory. However, the core can be empty because there are too many coalitions. Yet, some players may not like or know each other, so they cannot form a coalition. Let $\cK$ be a fixed family of coalitions. The $\cK$-core is defined as the set of outcomes acceptable for all the coalitions from $\cK$. The family $\cK$ is called {\em stable} if the $\cK$-core is not empty for any normal form game (or equivalently, for any game in generalized characteristic function form). \\*[\parskip] \hspace*{1.5em}{\em Normal hypergraphs} can be characterized by several equivalent properties, e.g. they are {\em dual} to the {\em clique hypergraphs} of {\em perfect graphs}. We prove that a family $\cK$ of coalitions is stable iff $\cK$ as a hypergraph is normal.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1996/96-33.ps.gz

DIMACS Home Page