Stable effectivity functions and perfect graphs

We consider the problem of characterizing the stability of effectivity func tions (EFF), via a correspondence between game theoretic and well-known com binatorial concepts. To every EFF we assign a pair of hypergraphs, represen ting clique covers of two associated graphs, and obtain some necessary and some sufficient conditions for the stability of EFFs in terms of graph-prop erties. These conditions imply, for example, that to check the stability of an EFF is an NP-complete problem. We also translate some well-known conjec tures of graph theory into game theoretic language and vice versa. (C) 2000 Elsevier Science B.V. All rights reserved.