Document Open Access Logo

Computing Shapley Values for Mean Width in 3-D

Author Shuhao Tan

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2021.67.pdf
  • Filesize: 0.78 MB
  • 17 pages

Document Identifiers

Author Details

Shuhao Tan
  • Department of Computer Science, University of Maryland, College Park, MD, USA

Acknowledgements

The author is very grateful to David Mount for discussions and advice for the paper. The author is also thankful to Geng Lin for proofreading and helping improving the readability.

Cite As Get BibTex

Shuhao Tan. Computing Shapley Values for Mean Width in 3-D. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 67:1-67:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.ISAAC.2021.67

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 convex-hull 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 3-dimensional 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 d-dimensional 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 n-element 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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
  • Theory of computation → Data structures design and analysis
Keywords
  • Shapley value
  • mean width
  • dynamic convolution

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Pankaj K. Agarwal, Sariel Har-Peled, Subhash Suri, Hakan Yıldız, and Wuzhou Zhang. Convex hulls under uncertainty. In Andreas S. Schulz and Dorothea Wagner, editors, Algorithms - ESA 2014, pages 37-48, Berlin, Heidelberg, 2014. Springer Berlin Heidelberg. URL: https://doi.org/10.1007/978-3-662-44777-2_4.
  2. Deepak Ajwani, Saurabh Ray, Raimund Seidel, and Hans Raj Tiwary. On computing the centroid of the vertices of an arrangement and related problems. In Frank Dehne, Jörg-Rüdiger Sack, and Norbert Zeh, editors, Algorithms and Data Structures, pages 519-528, Berlin, Heidelberg, 2007. Springer Berlin Heidelberg. URL: https://doi.org/10.1007/978-3-540-73951-7_45.
  3. David Alonso-Gutiérrez and Joscha Prochno. On the Gaussian behavior of marginals and the mean width of random polytopes. Proceedings of the American Mathematical Society, 143(2):821-832, 2015. URL: https://doi.org/10.1090/S0002-9939-2014-12401-4.
  4. Mauricio Alvarez-Manilla, Abbas Edalat, and Nasser Saheb-Djahromi. An extension result for continuous valuations. Journal of the London Mathematical Society, 61(2):629-640, 2000. URL: https://doi.org/10.1112/S0024610700008681.
  5. Boris Aronov and Matthew J. Katz. Batched point location in SINR diagrams via algebraic tools. ACM Trans. Algorithms, 14(4):41:1-41:29, August 2018. URL: https://doi.org/10.1145/3209678.
  6. Karoly J. Böröczky, Ferenc Fodor, Matthias Reitzner, and Viktor Vígh. Mean width of random polytopes in a reasonably smooth convex body. Journal of Multivariate Analysis, 100(10):2287-2295, 2009. URL: https://doi.org/10.1016/j.jmva.2009.07.003.
  7. Sergio Cabello and Timothy M. Chan. Computing Shapley Values in the Plane. In Gill Barequet and Yusu Wang, editors, 35th International Symposium on Computational Geometry (SoCG 2019), volume 129 of Leibniz International Proceedings in Informatics (LIPIcs), pages 20:1-20:19, Dagstuhl, Germany, 2019. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.SoCG.2019.20.
  8. Satya R. Chakravarty, Manipushpak Mitra, and Palash Sarkar. A Course on Cooperative Game Theory. Cambridge University Press, 2015. URL: https://doi.org/10.1017/CBO9781107415997.
  9. Timothy M. Chan. A (slightly) faster algorithm for Klee’s measure problem. Computational Geometry, 43(3):243-250, 2010. Special Issue on 24th Annual Symposium on Computational Geometry (SoCG'08). URL: https://doi.org/10.1016/j.comgeo.2009.01.007.
  10. Martin Fink, John Hershberger, Nirman Kumar, and Subhash Suri. Hyperplane Separability and Convexity of Probabilistic Point Sets. In Sándor Fekete and Anna Lubiw, editors, 32nd International Symposium on Computational Geometry (SoCG 2016), volume 51 of Leibniz International Proceedings in Informatics (LIPIcs), pages 38:1-38:16, Dagstuhl, Germany, 2016. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.SoCG.2016.38.
  11. Gudmund Skovbjerg Frandsen, Johan P. Hansen, and Peter Bro Miltersen. Lower bounds for dynamic algebraic problems. Information and Computation, 171(2):333-349, 2001. URL: https://doi.org/10.1006/inco.2001.3046.
  12. Alfred Gray. Steiner’s Formula, pages 209-229. Birkhäuser Basel, Basel, 2004. URL: https://doi.org/10.1007/978-3-0348-7966-8_10.
  13. Hugo Hadwiger. Vorlesungen über inhalt, Oberfläche und Isoperimetrie, volume 93. Springer-Verlag, 2013. URL: https://doi.org/10.1007/978-3-642-94702-5.
  14. Sergiu Hart. Shapley value. In John Eatwell, Murray Milgate, and Peter Newman, editors, Game Theory, pages 210-216. Palgrave Macmillan UK, London, 1989. URL: https://doi.org/10.1007/978-1-349-20181-5_25.
  15. Lingxiao Huang, Jian Li, Jeff M. Phillips, and Haitao Wang. epsilon-kernel coresets for stochastic points. In Piotr Sankowski and Christos Zaroliagis, editors, 24th Annual European Symposium on Algorithms (ESA 2016), volume 57 of Leibniz International Proceedings in Informatics (LIPIcs), pages 50:1-50:18, Dagstuhl, Germany, 2016. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.ESA.2016.50.
  16. Roland Huber. Continuous valuations. Mathematische Zeitschrift, 212(1):455-477, January 1993. URL: https://doi.org/10.1007/BF02571668.
  17. Daniel A. Klain. A short proof of Hadwiger’s characterization theorem. Mathematika, 42(2):329-339, 1995. URL: https://doi.org/10.1112/S0025579300014625.
  18. Stefan Langerman. On the complexity of halfspace area queries. Discrete & Computational Geometry, 30(4):639-648, October 2003. URL: https://doi.org/10.1007/s00454-003-2856-2.
  19. Maarten Löffler and Marc van Kreveld. Largest and smallest convex hulls for imprecise points. Algorithmica, 56(2):235, March 2008. URL: https://doi.org/10.1007/s00453-008-9174-2.
  20. Roger E. Miles. Poisson flats in Euclidean spaces. part I: A finite number of random uniform flats. Advances in Applied Probability, 1(2):211-237, 1969. URL: https://doi.org/10.2307/1426218.
  21. Josef S. Müller. On the mean width of random polytopes. Probability Theory and Related Fields, 82(1):33-37, June 1989. URL: https://doi.org/10.1007/BF00340011.
  22. Roger B. Myerson. Game Theory: Analysis of Conflict. Harvard University Press, 1991. URL: https://doi.org/10.2307/j.ctvjsf522.
  23. John H. Reif and Stephen R. Tate. On dynamic algorithms for algebraic problems. Journal of Algorithms, 22(2):347-371, 1997. URL: https://doi.org/10.1006/jagm.1995.0807.
  24. Alvin E. Roth, editor. The Shapley Value: Essays in Honor of Lloyd S. Shapley. Cambridge University Press, 1988. URL: https://doi.org/10.1017/CBO9780511528446.
  25. Rolf Schneider. Convex Bodies: The Brunn–Minkowski Theory. Encyclopedia of Mathematics and its Applications. Cambridge University Press, 2 edition, 2013. URL: https://doi.org/10.1017/CBO9781139003858.
  26. Subhash Suri, Kevin Verbeek, and Hakan Yıldız. On the most likely convex hull of uncertain points. In Hans L. Bodlaender and Giuseppe F. Italiano, editors, Algorithms - ESA 2013, pages 791-802, Berlin, Heidelberg, 2013. Springer Berlin Heidelberg. URL: https://doi.org/10.1007/978-3-642-40450-4_67.
  27. Eyal Winter. The Shapley value. In Handbook of Game Theory with Economic Applications, volume 3, chapter 53, pages 2025-2054. Elsevier, 2002. URL: https://doi.org/10.1016/S1574-0005(02)03016-3.
  28. Jie Xue, Yuan Li, and Ravi Janardan. On the expected diameter, width, and complexity of a stochastic convex-hull. In Faith Ellen, Antonina Kolokolova, and Jörg-Rüdiger Sack, editors, Algorithms and Data Structures, pages 581-592, Cham, 2017. Springer International Publishing. URL: https://doi.org/10.1007/978-3-319-62127-2_49.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact