Monte Carlo Methods for the Shapley–Shubik Power Index
This paper deals with the problem of calculating the Shapley–Shubik power index in weighted majority games. We propose an efficient Monte Carlo algorithm based on an implicit hierarchical structure of permutations of players. Our algorithm outputs a vector of power indices preserving the monotonicit...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2022-06-01
|
| Series: | Games |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2073-4336/13/3/44 |
| _version_ | 1797487264554549248 |
|---|---|
| author | Yuto Ushioda Masato Tanaka Tomomi Matsui |
| author_facet | Yuto Ushioda Masato Tanaka Tomomi Matsui |
| author_sort | Yuto Ushioda |
| collection | DOAJ |
| description | This paper deals with the problem of calculating the Shapley–Shubik power index in weighted majority games. We propose an efficient Monte Carlo algorithm based on an implicit hierarchical structure of permutations of players. Our algorithm outputs a vector of power indices preserving the monotonicity, with respect to the voting weights. We show that our algorithm reduces the required number of samples, compared with the naive algorithm. |
| first_indexed | 2024-03-09T23:46:08Z |
| format | Article |
| id | doaj.art-cb6ff67149134f2497c222552d71b176 |
| institution | Directory Open Access Journal |
| issn | 2073-4336 |
| language | English |
| last_indexed | 2024-03-09T23:46:08Z |
| publishDate | 2022-06-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Games |
| spelling | doaj.art-cb6ff67149134f2497c222552d71b1762023-11-23T16:44:27ZengMDPI AGGames2073-43362022-06-011334410.3390/g13030044Monte Carlo Methods for the Shapley–Shubik Power IndexYuto Ushioda0Masato Tanaka1Tomomi Matsui2Graduate School of Engineering, Tokyo Institute of Technology, Ookayama, Meguro-ku, Tokyo 152-8552, JapanGraduate School of Engineering, Tokyo Institute of Technology, Ookayama, Meguro-ku, Tokyo 152-8552, JapanGraduate School of Engineering, Tokyo Institute of Technology, Ookayama, Meguro-ku, Tokyo 152-8552, JapanThis paper deals with the problem of calculating the Shapley–Shubik power index in weighted majority games. We propose an efficient Monte Carlo algorithm based on an implicit hierarchical structure of permutations of players. Our algorithm outputs a vector of power indices preserving the monotonicity, with respect to the voting weights. We show that our algorithm reduces the required number of samples, compared with the naive algorithm.https://www.mdpi.com/2073-4336/13/3/44voting gameweighted majority gamepower indexMonte Carlo algorithm |
| spellingShingle | Yuto Ushioda Masato Tanaka Tomomi Matsui Monte Carlo Methods for the Shapley–Shubik Power Index Games voting game weighted majority game power index Monte Carlo algorithm |
| title | Monte Carlo Methods for the Shapley–Shubik Power Index |
| title_full | Monte Carlo Methods for the Shapley–Shubik Power Index |
| title_fullStr | Monte Carlo Methods for the Shapley–Shubik Power Index |
| title_full_unstemmed | Monte Carlo Methods for the Shapley–Shubik Power Index |
| title_short | Monte Carlo Methods for the Shapley–Shubik Power Index |
| title_sort | monte carlo methods for the shapley shubik power index |
| topic | voting game weighted majority game power index Monte Carlo algorithm |
| url | https://www.mdpi.com/2073-4336/13/3/44 |
| work_keys_str_mv | AT yutoushioda montecarlomethodsfortheshapleyshubikpowerindex AT masatotanaka montecarlomethodsfortheshapleyshubikpowerindex AT tomomimatsui montecarlomethodsfortheshapleyshubikpowerindex |