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.

Computing the shapley value in allocation problems: Approximations and bounds, with an application to the Italian VQR research assessment program / Lupia, Francesco; Mendicelli, Angelo; Ribichini, Andrea; Scarcello, Francesco; Schaerf, Marco. - STAMPA. - 1745:(2016), pp. 27-43. (Intervento presentato al convegno 23rd RCRA International Workshop on Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion, RCRA 2016 tenutosi a Genova, Italy nel 28 November 2016).

Computing the shapley value in allocation problems: Approximations and bounds, with an application to the Italian VQR research assessment program

RIBICHINI, ANDREA;SCHAERF, Marco
2016

Abstract

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.
2016
23rd RCRA International Workshop on Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion, RCRA 2016
Computer Science (all)
04 Pubblicazione in atti di convegno::04b Atto di convegno in volume
Computing the shapley value in allocation problems: Approximations and bounds, with an application to the Italian VQR research assessment program / Lupia, Francesco; Mendicelli, Angelo; Ribichini, Andrea; Scarcello, Francesco; Schaerf, Marco. - STAMPA. - 1745:(2016), pp. 27-43. (Intervento presentato al convegno 23rd RCRA International Workshop on Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion, RCRA 2016 tenutosi a Genova, Italy nel 28 November 2016).
File allegati a questo prodotto
File Dimensione Formato  
Lupia_Computin-the-shapley_2016.pdf

accesso aperto

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 1.38 MB
Formato Adobe PDF
1.38 MB Adobe PDF
Schaerf_RCRA-frontespizio-indice_2016.pdf

accesso aperto

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 117.35 kB
Formato Adobe PDF
117.35 kB Adobe PDF

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/951636
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? ND
social impact