{"ID":2839302,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.14995","arxiv_id":"2511.14995","title":"Computing Power Indices in Weighted Majority Games with Formal Power Series","abstract":"In this paper, we propose fast pseudo-polynomial-time algorithms for computing power indices in weighted majority games. We show that we can compute the Banzhaf index for all players in $O(n+q\\log (q))$ time, where $n$ is the number of players and $q$ is a given quota. Moreover, we prove that the Shapley--Shubik index for all players can be computed in $O(nq\\log (q))$ time. Our algorithms are faster than existing algorithms when $q=2^{o(n)}$. Our algorithms exploit efficient computation techniques for formal power series.","short_abstract":"In this paper, we propose fast pseudo-polynomial-time algorithms for computing power indices in weighted majority games. We show that we can compute the Banzhaf index for all players in $O(n+q\\log (q))$ time, where $n$ is the number of players and $q$ is a given quota. Moreover, we prove that the Shapley--Shubik index...","url_abs":"https://arxiv.org/abs/2511.14995","url_pdf":"https://arxiv.org/pdf/2511.14995v1","authors":"[\"Naonori Kakimura\",\"Yoshihiko Terai\"]","published":"2025-11-19T00:29:33Z","proceeding":"cs.GT","tasks":"[\"cs.GT\",\"cs.DS\"]","methods":"[]","has_code":false}