Two Algorithms for Computing Power Indices of All Players Efficiently(APOR(2))

スポンサーリンク

概要

• 論文の詳細を見る

• For a weighted majority game with n players, several power indices have been proposed. Two in particular, the Banzhaf index and the Shapley-Shubik index are well studied. Two dynamic programming algorithms had been proposed for computing the exact values of these indices of a player in O(nq) time, and O(n^2q) time. Here n is the number of players, and q is the quote. In this paper, we propose two algorithms for efficiently computing these indices for all players simultaneously. Oiir algorithms are obtained by modifying those dynamic programming algorithm. Our algorithms run in O(nq) time, and O(n^2qlogn) time,thus our algorithms are faster than existing algorithms.

• 社団法人日本オペレーションズ・リサーチ学会の論文
• 1999-09-20

著者

• Uno Takeaki

  Department Of Industial Engineering And Management Tokyo Institute Of Technology

関連論文

• Two Algorithms for Computing Power Indices of All Players Efficiently(APOR(2))

スポンサーリンク