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.
DIMACS Home Page