  Mechanism design is addressed in the context of fair allocations of
indivisible goods with monetary compensation. Motivated by a real-world social
choice problem, mechanisms with verification are considered in a setting where
(i) agents' declarations on allocated goods can be fully verified before
payments are performed, and where (ii) verification is not used to punish
agents whose declarations resulted in incorrect ones. Within this setting, a
mechanism is designed that is shown to be truthful, efficient, and
budget-balanced, and where agents' utilities are fairly determined by the
Shapley value of suitable coalitional games. The proposed mechanism is however
shown to be #P-complete. Thus, to deal with applications with many agents
involved, two polynomial-time randomized variants are also proposed: one that
is still truthful and efficient, and which is approximately budget-balanced
with high probability, and another one that is truthful in expectation, while
still budget-balanced and efficient.
