Efficiently computing the Shapley value of connectivity games in low-treewidth graphs

Tom C. van der Zanden (), Hans L. Bodlaender () and Herbert J. M. Hamers ()
Additional contact information
Tom C. van der Zanden: Maastricht University
Hans L. Bodlaender: Utrecht University
Herbert J. M. Hamers: Tilburg University

Operational Research, 2023, vol. 23, issue 1, No 6, 23 pages

Abstract: Abstract The Shapley value is the solution concept in cooperative game theory that is most used in both theoretical and practical settings. Unfortunately, in general, computing the Shapley value is computationally intractable. This paper focuses on computing the Shapley value of (weighted) connectivity games. For these connectivity games, which are defined on an underlying (weighted) graph, computing the Shapley value is $$\#\textsf {P}$$ # P -hard, and thus (likely) intractable even for graphs with a moderate number of vertices. We present an algorithm that can efficiently compute the Shapley value if the underlying graph has bounded treewidth. Next, we apply our algorithm to several real-world (covert) networks. We show that our algorithm can quickly compute exact Shapley values for these networks, whereas in prior work these values could only be approximated using a heuristic method. Finally, it is demonstrated that our algorithm can also efficiently compute the Shapley value time for several larger (artificial) benchmark graphs from the PACE 2018 challenge.

Keywords: Centrality; Social network analysis; Treewidth; Graph theory; Game theory; 05C85; 91-04; 91-05; 91-08; 91A80 (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s12351-023-00742-4 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:operea:v:23:y:2023:i:1:d:10.1007_s12351-023-00742-4

Ordering information: This journal article can be ordered from
https://www.springer ... search/journal/12351

DOI: 10.1007/s12351-023-00742-4

Access Statistics for this article

Operational Research is currently edited by Nikolaos F. Matsatsinis, John Psarras and Constantin Zopounidis

More articles in Operational Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().