Dipartimento di Ingegneria informatica, automatica e gestionale

In allocation problems, a given set of goods are assigned to agents in such a way that the social welfare is maximized, that is, the largest possible global worth is achieved. When goods are indivisible, it is possible to use money compensation to perform a fair allocation taking into account the actual contribution of all agents to the social welfare. Coalitional games provide a formal mathematical framework to model such problems, in particular the Shapley value is a solution concept widely used for assigning worths to agents in a fair way. Unfortunately, computing this value is a #P-hard problem, so that applying this good theoretical notion is often quite difficult in real-world problems. In this paper, we first review the application of the Shapley value to an allocation problem that models the evaluation of the Italian research structures with a procedure known as VQR. For large universities, the problem involves thousands of agents and goods (here, researchers and their research products). We then describe some useful properties that allow us to greatly simplify many such large instances. Moreover, we propose new algorithms for computing lower bounds and upper bounds of the Shapley value, which in some cases provide the exact result and that can be combined with approximation algorithms. The proposed techniques have been tested on large real-world instances of the VQR research evaluation problem.