ÍâÍøÌìÌÃ

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. Interestingly, our definition of anÌýimputation for these games is quite unusual and is inspired by a notion from quantum computing.Ìý

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.

Note: This talk is self-contained. It is based on:

ÌýÌý