Output details
11 - Computer Science and Informatics
University of Southampton
Return to search
Output 0 of 0 in the submission
Article title
A linear approximation method for the Shapley value
Type
D - Journal article
Title of journal
Artificial Intelligence
Article number
-
Volume number
172
Issue number
14
First page of article
1673
ISSN of journal
0004-3702
Year of publication
2008
Number of additional authors
2
Additional information
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.
Interdisciplinary
-
Cross-referral requested
-
Research group
None
Citation count
20
Proposed double-weighted
No
Double-weighted statement
-
Reserve for a double-weighted output
No
Non-English
No
English abstract
-
