Document Open Access Logo

Computing Shapley Values in the Plane

Authors Sergio Cabello , Timothy M. Chan

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2019.20.pdf
  • Filesize: 1.08 MB
  • 19 pages

Document Identifiers

Author Details

Sergio Cabello
  • Department of Mathematics, FMF, University of Ljubljana, Slovenia
  • Department of Mathematics, IMFM, Ljubljana, Slovenia
Timothy M. Chan
  • Department of Computer Science, University of Illinois at Urbana-Champaign, USA

Funding

  • Cabello, Sergio: Supported by the Slovenian Research Agency (P1-0297, J1-8130, J1-8155).
  • Chan, Timothy M.: Supported in part by NSF Grant CCF-1814026.

Acknowledgements

The authors are very grateful to Sariel Har-Peled for fruitful discussions.

Cite AsGet BibTex

Sergio Cabello and Timothy M. Chan. Computing Shapley Values in the Plane. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 20:1-20:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.SoCG.2019.20

Abstract

We consider the problem of computing Shapley values for points in the plane, where each point is interpreted as a player, and the value of a coalition is defined by the area of usual geometric objects, such as the convex hull or the minimum axis-parallel bounding box. For sets of n points in the plane, we show how to compute in roughly O(n^{3/2}) time the Shapley values for the area of the minimum axis-parallel bounding box and the area of the union of the rectangles spanned by the origin and the input points. When the points form an increasing or decreasing chain, the running time can be improved to near-linear. In all these cases, we use linearity of the Shapley values and algebraic methods. We also show that Shapley values for the area of the convex hull or the minimum enclosing disk can be computed in O(n^2) and O(n^3) time, respectively. These problems are closely related to the model of stochastic point sets considered in computational geometry, but here we have to consider random insertion orders of the points instead of a probabilistic existence of points.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
Keywords
  • Shapley values
  • stochastic computational geometry
  • convex hull
  • minimum enclosing disk
  • bounding box
  • arrangements
  • convolutions
  • airport problem

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 Yildiz, and Wuzhou Zhang. Convex Hulls Under Uncertainty. Algorithmica, 79(2):340-367, 2017. URL: http://dx.doi.org/10.1007/s00453-016-0195-y.
  2. Pankaj K. Agarwal, Nirman Kumar, Stavros Sintos, and Subhash Suri. Range-max queries on uncertain data. J. Comput. Syst. Sci., 94:118-134, 2018. URL: http://dx.doi.org/10.1016/j.jcss.2017.09.006.
  3. 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 K. H. A. Dehne, Jörg-Rüdiger Sack, and Norbert Zeh, editors, 10th International Workshop Algorithms and Data Structures, WADS 2007, volume 4619 of Lecture Notes in Computer Science, pages 519-528. Springer, 2007. URL: http://dx.doi.org/10.1007/978-3-540-73951-7_45.
  4. Boris Aronov and Matthew J. Katz. Batched Point Location in SINR Diagrams via Algebraic Tools. ACM Trans. Algorithms, 14(4):41:1-41:29, 2018. URL: http://dx.doi.org/10.1145/3209678.
  5. Sergio Cabello and Timothy M. Chan. Computing Shapley values in the plane. CoRR, abs/1804.03894, 2018. URL: http://arxiv.org/abs/1804.03894.
  6. Georgios Chalkiadakis, Edith Elkind, and Michael Wooldridge. Computational Aspects of Cooperative Game Theory. Synthesis Lectures on Artificial Intelligence and Machine Learning. Morgan & Claypool Publishers, 2011. URL: http://dx.doi.org/10.2200/S00355ED1V01Y201107AIM016.
  7. Mark de Berg, Otfried Cheong, Marc J. van Kreveld, and Mark H. Overmars. Computational Geometry: Algorithms and Applications. Springer, 3rd edition, 2008. Google Scholar
  8. Xiaotie Deng and Qizhi Fang. Algorithmic Cooperative Game Theory. In Altannar Chinchuluun, Panos M. Pardalos, Athanasios Migdalas, and Leonidas Pitsoulis, editors, Pareto Optimality, Game Theory And Equilibria, pages 159-185. Springer New York, 2008. URL: http://dx.doi.org/10.1007/978-0-387-77247-9_7.
  9. Xiaotie Deng and Christos H. Papadimitriou. On the Complexity of Cooperative Solution Concepts. Mathematics of Operations Research, 19(2):257-266, 1994. URL: http://dx.doi.org/10.1287/moor.19.2.257.
  10. Ulrich Faigle, Sándor P. Fekete, Winfried Hochstättler, and Walter Kern. On approximately fair cost allocation in Euclidean TSP games. Operations-Research-Spektrum, 20(1):29-37, 1998. URL: http://dx.doi.org/10.1007/BF01545526.
  11. Thomas S. Ferguson. Game Theory, 2nd edition, 2014. Electronic text available at URL: https://www.math.ucla.edu/~tom/Game_Theory/Contents.html.
  12. Martin Fink, John Hershberger, Nirman Kumar, and Subhash Suri. Hyperplane separability and convexity of probabilistic point sets. JoCG, 8(2):32-57, 2017. URL: http://jocg.org/index.php/jocg/article/view/321.
  13. Pegah Kamousi, Timothy M. Chan, and Subhash Suri. Stochastic minimum spanning trees in Euclidean spaces. In Ferran Hurtado and Marc J. van Kreveld, editors, Proceedings of the 27th ACM Symposium on Computational Geometry, SoCG'11, pages 65-74. ACM, 2011. URL: http://dx.doi.org/10.1145/1998196.1998206.
  14. Pegah Kamousi, Timothy M. Chan, and Subhash Suri. Closest pair and the post office problem for stochastic points. Comput. Geom., 47(2):214-223, 2014. URL: http://dx.doi.org/10.1016/j.comgeo.2012.10.010.
  15. Stefan Langerman. On the Complexity of Halfspace Area Queries. Discrete & Computational Geometry, 30(4):639-648, 2003. URL: http://dx.doi.org/10.1007/s00454-003-2856-2.
  16. Stephen C. Littlechild and Guillermo Owen. A Simple Expression for the Shapely Value in A Special Case. Management Science, 20(3):370-372, 1973. URL: http://dx.doi.org/10.1287/mnsc.20.3.370.
  17. Nimrod Megiddo. Computational Complexity of the Game Theory Approach to Cost Allocation for a Tree. Mathematics of Operations Research, 3(3):189-196, 1978. URL: http://dx.doi.org/10.1287/moor.3.3.189.
  18. Guillaume Moroz and Boris Aronov. Computing the Distance between Piecewise-Linear Bivariate Functions. ACM Trans. Algorithms, 12(1):3:1-3:13, 2016. URL: http://dx.doi.org/10.1145/2847257.
  19. Roger B. Myerson. Game theory - Analysis of Conflict. Harvard University Press, 1997. Google Scholar
  20. Noam Nisan, Tim Roughgarden, Éva Tardos, and Vijay V. Vazirani. Algorithmic Game Theory. Cambridge University Press, 2007. Google Scholar
  21. Martin J. Osborne and Ariel Rubinstein. A Course in Game Theory. The MIT Press, 1994. Google Scholar
  22. Mark H. Overmars and Chee-Keng Yap. New Upper Bounds in Klee’s Measure Problem. SIAM J. Comput., 20(6):1034-1045, 1991. URL: http://dx.doi.org/10.1137/0220065.
  23. Pablo Pérez-Lantero. Area and Perimeter of the Convex Hull of Stochastic Points. Comput. J., 59(8):1144-1154, 2016. URL: http://dx.doi.org/10.1093/comjnl/bxv124.
  24. Justo Puerto, Arie Tamir, and Federico Perea. A cooperative location game based on the 1-center location problem. European Journal of Operational Research, 214(2):317-330, 2011. URL: http://dx.doi.org/10.1016/j.ejor.2011.04.020.
  25. Justo Puerto, Arie Tamir, and Federico Perea. Cooperative location games based on the minimum diameter spanning Steiner subgraph problem. Discrete Applied Mathematics, 160(7-8):970-979, 2012. URL: http://dx.doi.org/10.1016/j.dam.2011.07.020.
  26. Alvin E. Roth, editor. The Shapley Value: Essays in Honor of Lloyd S. Shapley. Cambridge University Press, 1988. Google Scholar
  27. William Thomson. Cost allocation and airport problems, 2013. Rochester Center for Economic Research Working Paper. Version of 2014 available at URL: http://www.iser.osaka-u.ac.jp/collabo/20140524/Airport_Problems.pdf.
  28. Dan E. Willard. New Data Structures for Orthogonal Range Queries. SIAM J. Comput., 14:232-253, 1985. URL: http://dx.doi.org/10.1137/0214019.
  29. Eyal Winter. The Shapley value. In R.J. Aumann and S. Hart, editors, Handbook of Game Theory with Economic Applications, volume 3, chapter 53, pages 2025-2054. Elsevier, 1 edition, 2002. URL: http://dx.doi.org/10.1016/S1574-0005(02)03016-3.
  30. Jie Xue, Yuan Li, and Ravi Janardan. On the separability of stochastic geometric objects, with applications. Comput. Geom., 74:1-20, 2018. URL: http://dx.doi.org/10.1016/j.comgeo.2018.06.001.
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 Imprint Privacy Contact