Abstract
We consider the problem of characterizing the stability of effectivity functions (EFF), via a correspondence 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, for example, 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.