Coalitional games induced by matching problems: Complexity and islands of tractability for the Shapley value

摘要

The paper focuses on cooperative games where the worth of any coalition of agents is determined by the optimal value of a matching problem on (possibly weighted) graphs. These games come in different forms that can be grouped in two broad classes, namely of matching and allocation games, and they have a wide spectrum of applications, ranging from two-sided markets where buyers and sellers are encoded as vertices in a graph, to allocation problems where indivisible goods have to be assigned (matched) to agents in a fair way, possibly using monetary compensations.