Abstract
Matching games form a class of coalitional games
that attracted much attention in the literature. Indeed, several results are known about the complexity of computing over them solution concepts. In
particular, it is known that computing the Shapley
value is intractable in general, formally #P-hard,
and feasible in polynomial time over games defined
on trees. In fact, it was an open problem whether
or not this tractability result holds over classes of
graphs properly including acyclic ones. The main
contribution of the paper is to provide a positive
answer to this question, by showing that the Shapley value is tractable for matching games defined
over graphs having bounded treewidth. The proposed polynomial-time algorithm has been implemented and tested on classes of graphs having different sizes and treewidth up to three