Algorithmic aspects of the core of combinatorial optimization games

We discuss an integer programming formulation for a class of cooperative ga mes. We focus on algorithmic aspects of the core, one of the most important solution concepts in cooperative game theory. Central to our study is a si mple (but very useful) observation that the core for this class is nonempty if and only if an associated linear program has an integer optimal solutio n. Based on this, we study the computational complexity and algorithms to a nswer important questions about the cores of various games on graphs, such as maximum flow, connectivity, maximum matching, minimum vertex cover, mini mum edge cover, maximum independent set, and minimum coloring.