Output details
11 - Computer Science and Informatics
University of Southampton
A linear approximation method for the Shapley value
Significance of output:
<22>Develops new approximation algorithm for computing the Shapley value.
Shapley value is key solution concept for coalitional games (he was awarded Nobel prize in 2012 in part for this work). However, computing it is computationally complex. Thus developing an algorithm with time complexity linear in number of players and with an approximation error lower than the previous state of the art is important step forward. Work has been built upon by authors at Microsoft Research, Princeton and University of Singapore.
Algorithm's worst-case bound proved analytically, average case analysis empirically by benchmarking against only previous algorithm for this task.