The core is a quintessential solution concept in cooperative game theory and LP-duality theory has played a central role in its study, right from its early days to the present time. The classic 1971 paper of Shapley and Shubik showed the “right” way of exploiting this theory — in the context of characterizing the core of the assignment game.

The LP-relaxation of this game  has the following key property: the polytope defined by its constraints has integral vertices; in this case, they are matchings in the underlying graph. Similar characterizations for several basic combinatorial optimization games followed; throughout, this property was established by showing that the underlying linear system is totally unimodular (TUM). We will first exploit TUM further via a very general formulation due to Hoffman and Kruskal (1956). The way to take this methodology to its logical next step is to use total dual integrality (TDI). In the process, we address new classes of games which have their origins in two major theories within combinatorial optimization, namely perfect graphs and polymatroids.

Whereas the core of the assignment game is always non-empty, that of the general graph matching game can be empty.

We show how to salvage the situation — again using LP-duality in a fundamental way.