Tan, Shuhao
Computing Shapley Values for Mean Width in 3D
Abstract
The Shapley value is a classical concept from game theory, which is used to evaluate the importance of a player in a cooperative setting. Assuming that players are inserted in a uniformly random order, the Shapley value of a player p is the expected increase in the value of the characteristic function when p is inserted. Cabello and Chan (SoCG 2019) recently showed how to adapt this to a geometric context on planar point sets. For example, when the characteristic function is the area of the convex hull, the Shapley value of a point is the average amount by which the convexhull area increases when this point is added to the set. Shapley values can be viewed as an indication of the relative importance/impact of a point on the function of interest.
In this paper, we present an efficient algorithm for computing Shapley values in 3dimensional space, where the function of interest is the mean width of the point set. Our algorithm runs in O(n³log²n) time and O(n) space. This result can be generalized to any point set in ddimensional space (d ≥ 3) to compute the Shapley values for the mean volume of the convex hull projected onto a uniformly random (d  2)subspace in O(n^d log²n) time and O(n) space. These results are based on a new data structure for a dynamic variant of the convolution problem, which is of independent interest. Our data structure supports incremental modifications to nelement vectors (including cyclical rotation by one position). We show that n operations can be executed in O(n log²n) time and O(n) space.
BibTeX  Entry
@InProceedings{tan:LIPIcs.ISAAC.2021.67,
author = {Tan, Shuhao},
title = {{Computing Shapley Values for Mean Width in 3D}},
booktitle = {32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
pages = {67:167:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772143},
ISSN = {18688969},
year = {2021},
volume = {212},
editor = {Ahn, HeeKap and Sadakane, Kunihiko},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/15500},
URN = {urn:nbn:de:0030drops155008},
doi = {10.4230/LIPIcs.ISAAC.2021.67},
annote = {Keywords: Shapley value, mean width, dynamic convolution}
}
30.11.2021
Keywords: 

Shapley value, mean width, dynamic convolution 
Seminar: 

32nd International Symposium on Algorithms and Computation (ISAAC 2021)

Issue date: 

2021 
Date of publication: 

30.11.2021 