DIMACS TR: 96-34
Stable Effectivity Functions and Perfect Graphs
Authors: E. Boros, V. Gurvich
ABSTRACT
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