Efficiently computing the Shapley value of connectivity games in low-treewidth graphs
| Autor: | van der Zanden, Tom C., Bodlaender, Hans L., Hamers, Herbert J.M., Sub Algorithms and Complexity, Algorithms and Complexity |
|---|---|
| Přispěvatelé: | RS: GSBE other - not theme-related research, Data Analytics and Digitalisation, RS: FSE DACS Mathematics Centre Maastricht, Sub Algorithms and Complexity, Algorithms and Complexity |
| Rok vydání: | 2023 |
| Předmět: |
FOS: Computer and information sciences
Numerical Analysis NETWORK ANALYSIS Treewidth Strategy and Management Statistics Management Science and Operations Research Graph theory Social network analysis Computational Theory and Mathematics Computer Science - Computer Science and Game Theory Modelling and Simulation Management of Technology and Innovation Modeling and Simulation Computer Science - Data Structures and Algorithms Centrality Data Structures and Algorithms (cs.DS) Probability and Uncertainty Statistics Probability and Uncertainty Game theory Computer Science and Game Theory (cs.GT) |
| Zdroj: | Operational Research, 23(1):6. Springer Verlag Operational Research, 23(1). Springer Verlag |
| ISSN: | 1866-1505 1109-2858 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink