DIMACS TR: 96-34

Stable Effectivity Functions and Perfect Graphs

Authors: E. Boros, V. Gurvich


An effectivity function $\cE$ is called {\em stable} if the core $C(\cE,u)$ is not empty for any payoff $u$. The problem to characterize stable effectivity functions seems, in general, very difficult. In this paper we apply a graph theoretic approach to this problem. Using a graph based model we obtain some necessary and some sufficient conditions for stability in terms of perfect graphs. We also demonstrate that the conjecture by Berge and Duchet (1983) related to perfect graphs and kernels, in fact, is a special case of the considered problem of stability of effectivity functions.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1996/96-34.ps.gz
DIMACS Home Page