Structural Tractability of Shapley and Banzhaf Values in Allocation Games

Abstract

Allocation games are coalitional games defined in the literature as a way to analyze fair division problems of indivisible goods. The prototypical solution concepts for them are the Shapley value and the Banzhaf value. Unfortunately, their computation is intractable, formally #P-hard. Motivated by this bad news, structural requirements are investigated which can be used to identify islands of tractability. The main result is that, over the class of allocation games, the Shapley value and the Banzhaf value can be computed in polynomial time when interactions among agents can be formalized as graphs of bounded treewidth. This is shown by means of technical tools that are of interest in their own and that can be used for analyzing different kinds of coalitional games. Tractability is also shown for games where each good can be assigned to at most two agents, independently of their interactions.