Dealing with the Shapley Value: islands of tractability and useful tools

VCLA and WPI hosted a talk by Francesco Scarcello

ABSTRACT

Coalitional games provide a formal mathematical framework to model problems where the values of agents are defined in terms of the coalitions they may form. The total available worth is the value of the coalition with all players, called the grand-coalition, and a crucial problem in these games is finding a suitable distribution of this total worth to the agents that is “fair” for all of them.

The Shapley value is a solution concept widely used for this purpose. Unfortunately, computing this value is a #P-hard problem, so that applying this good theoretical notion is often quite difficult in real-world problems.

The talk focuses on two well-known kinds of coalitional games, namely, the allocation games and the matching games, looking for islands of tractability, that is, for classes of these games where the Shapley value can be computed efficiently. Positive results were known only for very trivial cases, and it was open whether such results could be extended to bounded treewidth instances. The talk shows that this is actually the case, by providing polynomial-time algorithms that, among other ingredients, use recent results on counting problems in databases and constraint satisfaction.

The proposed techniques have been implemented and tested on a real-world application of allocation problems, namely, the Italian research assessment program, known as VQR. For the large university considered in the experiments, the problem involves thousands of agents and goods (here, researchers and their research products). The algorithms described in the talk are able to compute the Shapley value for most of those agents, and to get a good approximation of the Shapley value for all of them.

Francesco Scarcello, University of Calabria