DIMACS TR: 99-01
Stable Effectivity Functions and Perfect Graphs
Authors: Endre Boros and Vladimir Gurvich
ABSTRACT
We consider the problem of characterizing the stability of
effectivity functions (EFF), via a combinatorial
correspondance between game theoretic and well-known combinatorial concepts.
To every EFF we assign a pair of hypergraphs, representing clique covers
of two associated graphs,
and obtain some necessary and some sufficient conditions
for the stability of EFFs in terms of graph-properties.
These conditions imply e.g. that
to check the stability of an EFF is an NP-complete problem.
We also translate some well known conjectures
of graph theory into game theoretic language
and vice versa.
Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1999/99-01.ps.gz
DIMACS Home Page