Scholarlink

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 \(\textrm{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 \(\textrm{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.

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Computing Power Indices in Weighted Majority Games with Formal Power Series

  • 会议论文

  • 发表日期：

    2026年

查看全文
  • Naonori Kakimura,
  • Yoshihiko Terai

摘要

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 \(\textrm{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 \(\textrm{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.