The core is a quintessential solution concept in cooperative game theory — it contains all ways of distributing the total profit of a game among individual agents in such a way that the grand coalition remains intact, i.e., a sub-coalition will not be able to generate more profit by itself and therefore has no incentive to secede. The classic 1971 paper of Shapley and Shubik characterized the core of the assignment game using ideas from matching theory and LP-duality theory and their highly non-trivial interplay.
We pose and resolve two basic questions:
1). Do core imputations spread the profit more-or-less evenly or do they restrict them to certain chosen agents? If the latter, what characterizes these “chosen” agents?
2). Whereas the core of the assignment game is always non-empty, that of the general graph matching game can be empty. Is there a way of salvaging the situation via the notion of an approximate core?
This talk is completely self-contained. It is based on: