On Computing the Shapley Value in Bankruptcy Games -llustrated by Rectified Linear Function Game-
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909976601034752 |
|---|---|
| author | Yamazaki, Shunta Matsui, Tomomi |
| author_facet | Yamazaki, Shunta Matsui, Tomomi |
| contents | In this research, we discuss a problem of calculating the Shapley value in bankruptcy games. We show that the decision problem of computing the Shapley value in bankruptcy games is NP-complete. We also investigate the relationship between the Shapley value of bankruptcy games and the Shapley-Shubik index in weighted voting games. The relation naturally implies a dynamic programming technique for calculating the Shapley value. We also present two recursive algorithms for computing the Shapley value: the first is the recursive completion method originally proposed by O'Neill, and the second is our novel contribution based on the dual game formulation. These recursive approaches offer conceptual clarity and computational efficiency, especially when combined with memoisation technique. Finally, we propose a Fully Polynomial-Time Randomized Approximation Scheme (FPRAS) based on Monte Carlo sampling, providing an efficient approximation method for large-scale instances. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_22208 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On Computing the Shapley Value in Bankruptcy Games -llustrated by Rectified Linear Function Game- Yamazaki, Shunta Matsui, Tomomi Computer Science and Game Theory 91A68, 68W20, 91A12 In this research, we discuss a problem of calculating the Shapley value in bankruptcy games. We show that the decision problem of computing the Shapley value in bankruptcy games is NP-complete. We also investigate the relationship between the Shapley value of bankruptcy games and the Shapley-Shubik index in weighted voting games. The relation naturally implies a dynamic programming technique for calculating the Shapley value. We also present two recursive algorithms for computing the Shapley value: the first is the recursive completion method originally proposed by O'Neill, and the second is our novel contribution based on the dual game formulation. These recursive approaches offer conceptual clarity and computational efficiency, especially when combined with memoisation technique. Finally, we propose a Fully Polynomial-Time Randomized Approximation Scheme (FPRAS) based on Monte Carlo sampling, providing an efficient approximation method for large-scale instances. |
| title | On Computing the Shapley Value in Bankruptcy Games -llustrated by Rectified Linear Function Game- |
| topic | Computer Science and Game Theory 91A68, 68W20, 91A12 |
| url | https://arxiv.org/abs/2511.22208 |