DIMACS TR: 99-01

Stable Effectivity Functions and Perfect Graphs

Authors: Endre Boros and Vladimir Gurvich


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