  In allocation problems, a given set of goods are assigned to agents in such a
way that the social welfare is maximised, 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 $\#{\rm P}$-hard problem, so
that applying this good theoretical notion is often quite difficult in
real-world problems.
  We describe useful properties that allow us to greatly simplify the instances
of allocation problems, without affecting the Shapley value of any player.
Moreover, we propose 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 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 paper 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.
