重み付き投票ゲームにおける 投票力指数の計算の高速化

Presentation on theme: "重み付き投票ゲームにおける 投票力指数の計算の高速化"— Presentation transcript:

1 重み付き投票ゲームにおける 投票力指数の計算の高速化
国立情報学研究所 宇野 毅明

2 目的 計算方法を工夫して、無駄な計算を省き、計算量を小さくする 重み付き投票ゲームの、投票力指数を計算する
対象は、Banzhaf, Shapley-Shubik, Deegan-Packel 指数 すでに動的計画法アルゴリズムが提案されている ただし、全プレイヤーの指数を計算すると、同じような計算を繰り返すことになる そこで 計算方法を工夫して、無駄な計算を省き、計算量を小さくする

3 重み付き投票ゲーム 各政党の力を示す指数がほしい => 議席数？ ある議会に、政党（プレイヤー） A、B、C、D がある
票決のとき、同一政党内の議員は同一の投票をする 賛成票が q = 50人 以上で可決 政党A 45人 政党B 8人 政党D 30人 政党C 17人 各政党の力を示す指数がほしい　=>　議席数？

4 勝利提携 と 敗北提携 提携 ： 政党の集合 法案成立には、 q 人 か、それ以上の議員を含む提携を組む必要がある
政党A 45人 政党B 8人 政党D 30人 政党C 17人

5 議席数は良い指標ではない 勝利提携 （ 政党A（45人），政党D（30人） ） 政党B（8人） ： AB ， ABC ， ABD ， BCD
政党C（17人）　：　AC　，　ABC　，　ACD　，　BCD 　勝利提携の組合せは同じ！　指数は同じになるべき 提携の情報から指数を求めるモデルがよい

6 もう一度、用語の定義 プレイヤー p1,…,pn ： 政党 プレイヤーの重み w(pi) ： 政党の議席数 q ： 成立に必要な票数
提携 ： プレイヤーの集合 提携 S の重み w(S) ：提携に属するプレイヤーの重みの和 勝利提携 ： 重みが q か、それ以上の提携 敗北提携 ： 重みが q 以下の提携

7 バンザフ（Banzhaf）指数 「ある勝利提携 S から プレイヤー pi が抜けると敗北提携になるとする。このとき、 pi　は発言力を持つだろう」 このような提携の数を 2n で割ったものを指数とする pi のバンザフ指数 Bz(pi) 　　　 ＝ 　| { S | pi ∈S，w(S)≧q， w(S＼ pi)＜q } |　／ 2n pi q

8 バンザフ指数を計算する f(pi, y) ： プレイヤー集合 { p１,…, pi } に含まれる提携 S で、
　　　　　　w(S) =y となるものの数 プレイヤー pｎ に対して、 w(S) ≧ q， w(S＼ pn) ＜ q  q - w(pn) ≦ w(S＼ pn) ≦ q-１ 重みが q - w(pn) から q-１ の間で、 pn を含まない提携の数 　　　　　　　　q-１ 　　　　＝ 　　Σ 　　　f(pｎ-1, y) 　 　　　　　　　 y=q- w(pn) 　　　これを 2n で割るとバンザフ指数になる

9 動的計画法 s 再帰式： f(pi, y) = f( pi-1, y ) + f( pi-1, y- w(pi) )
　　　　　　　　　　pi を含まない提携数　　　　 pi を含む提携数 　　i=１,…,n-１ に対して、 f(pi, y) を順々に求める q q - w(pn) ・・・・・ s 　　p１　 p2 　 p3 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　pn-2 pn-1 このグラフで、 f(pi, y) は s から対応する頂点までのパスの数

10 計算量 ・ f(pi-１, y) から f(pi, y) を求める： Ｏ(q) 時間 ・ f(pn-1, y) を求める： Ｏ(nq) 時間
　　　　　pn と pi の添え字をつけなおして、同じ方法で計算 ・全員分の計算　　　　　　　　　　　　 Ｏ(n2q) 時間 変更がちょっとしかないので、ほとんど同じ計算を行う 　　　　なんとか無駄な計算を省けないでしょうか？

11 不要な計算の省略 pi に対して, 提携 Sのプレイヤーを i 以下とi 以上に分けて考える
g(pi, y) ： プレイヤー集合 { pi,…, pn } に含まれる提携 S で、 　　　　　　w(S) =y となるものの数 重みが q - w(pi) から q-１ の間で、 pi を含まない提携  i 以下の重みが z ， i 以上がq - w(pi) - z から q-１-z の間 　　　　　　　　　　　　　　　　　　q-１　　　　　　　　　　　 q-１-z そのような提携の数　　＝ 　Σ 　　f(pi-1, z) 　Σ 　　g(pi+1, y) 　 　　　　　　　　　　　　　　　　　 　z=0 　　　　　　 y=q- w(pi)-z 　　　　　　 y　　　　　　　　　　 　 h(pi, y) = Σ g(pi, z) 　とすると　h(pi+1, q-１-z) - h(pi+1, q-w(pi)-z - 1) 　　　　　　z=0 　　　　

12 前後の計算を合わせる s q ・・・・・ ・・・・・ q p１ p2 p3 pi-１ pi pi+１ pn-１ pn
・・・・・ ・・・・・ q s 　　p１　 p2 　 p3 　　　　　　　　　　pi-１ pi pi+１ 　　　　　　　　　　　　　　　pn-１ pn f(pi, y) ，g(pi+2, y) から f(pi-1, y) ，g(pi+1, y) を計算：　Ｏ(q) g(pi+1, y) から h(pi+1, y) を計算 ：　　　　　　　　　　　　　Ｏ(q) 1プレイヤーの指数を計算 ：　　　　　　　　　　　　　　　　 Ｏ(q) 　　全員分の指数をＯ(nq) 時間で計算できる

13 シャープレイ・シュービック （Shapley-Shubik）指数
「空の提携にプレイヤーが順々に参加し、プレイヤー pi が参加して、はじめて S が勝利提携になるとき、 pi　は発言力を持つ」 このようなプレイヤーの参加順序（順列）の数を n! で割ったものを指数とする pi のシャープレイシュービック指数 Ss(pi) 　＝ | { 順列 (pj１ pj2,,…, pjn ) | 　　　　　　 q ≦ w({pj１ pj2,,…, pi }) < q+ w(pi) } | ／ n! pi q

14 Ss指数を計算する pi q S プレイヤー pi より前のプレイヤーの集合が S となるような順列の数は |S|!(|n-|S|-1)!
この場合、前に３プレイヤー、後ろに２プレイヤーいるので、 　　　　　 3!×2!　＝ 　3!（6-3-1）!　 ＝ 　|S|! (n-|S|-1)! pi　 を加えると勝利提携になる敗北提携について、この総和を取る Ss(pi)×2! 　　＝ 　　　　　　　Σ 　　　　　　　　　 |S|! (n-|S|-1)! 　　　 　　　　　　　　　　S | pi ∈S， q- w(pi) ≦ w(S)≦q-1 　 ／

15 Ss指数を計算する f(pi, k, y) ： プレイヤー集合 { p１,…, pi } に含まれる、大きさ k の提携 S で、w(S) =y となるものの数 重みが q - w(pn) から q-１ の間で、 pn を含まない提携 S に関して |S|!(n-|S|-1)! の和を取る 　 n-1 q-1 ＝ Σ 　Σ f(pn-1,k, y) × k!(n-k-1)! 　 　 k=0 y=q-w(pn) これを n! で割るとSs指数になる 終点が (pn-１, k, y) のパス重みを k!(n-k-1)! 　=> 　パスの重み和

16 Ss指数用の動的計画法 再帰式： f(pi, k, y) =　　 f( pi-1, k, y )　+　 f( pi-1, k-１, y- w(pi) ) 　　　　　　　　　　pi を含まない提携数　　　　 pi を含む提携数 ・ f(pi-１, k, y) から f(pi, k, y) を求める 　　　　　　　　　　　 Ｏ(nq) 　時間 ・ f(pn-1, k, y) を求める： 　　 　　　　　　 Ｏ(n2q) 時間 ・全員分の計算 　　　　　　　　 Ｏ(n3q) 時間 　 　k 　 … 　1 q 2 1 pi-１　　　 pi バンザフ指数と同じ方法で、高速化を行う

17 Ss指数の高速化 g(pi, k, y) ： (pi, k, y) から (pn, k’, ＊) へのパスの重み和
　　　（重みは k’!(|n-k’-1)! ） 重みが q - w(pi) から q-１の間で、 pi を含まない提携 S に 　　関する|S|!(|n-|S|-1)! の和 　　　　　　 n-１ 　　q-１　　　　　　　　　　　　　　　　 q-１ - z 　　　　＝ Σ 　　Σ 　　　f(pi-1, k, z) × Σ g(pi-1, k, y) 　 　　　　　　 k=0　 z=q-w(pi)　　　　　　　　　　　　 y=q- w(pi) - z k １プレイヤー 　　　　Ｏ(nq) 全プレイヤー 　　　 　Ｏ(n2q) ・・・ 　　p１ p2 　 　　　　　pi-１ pi pi+１ 　　　　　　　　　　　　　pn-１ pn

18 ディーガン・パックル指数 （Deegan-Packel）指数
極小勝利提携 ： どのプレイヤーが抜けても敗北になる勝利提携 「 pi が極小勝利提携 S に所属すれば，発言力1/|S| を持つ」 pi が所属する極小勝利提携すべてに対して発言力の和を取って、極小勝利提携の数 W で割ったものを指数とする q

19 ディーガン・パックル指数２ q プレイヤーは、重みの大きい順にソートされているとする d(S) ： 提携 S から最小重みのプレイヤー
　　　　（　＝　添え字最大のプレイヤー　）　　を除いた提携 pi のディーガン・パックル指数 Dp(pi) 　　　 ＝ 　| { S | pi ∈S，w(S)≧q， w(d(S))＜q } |　／ W q

20 ディーガンパックル指数を計算 s Ss 指数計算で用いた、動的計画法のグラフを考える
終点が (pi, k, y) （q-w(pi) ≦ y ≦ q-１） のパスの重みを 1/k とする pi 上Dp指数の計算： pi を使い、 S から上の条件を満たす点へのパスの重み和　　（重みは １/k’ ） q ・・・ ・・・ s 　　p１　 p2 　 p3 　　　　　pi-1　 pi 　 pi+1 　　　　　　　　　　　　　pn-１ pn 1プレイヤー Ｏ(n2q)　　：　　全プレイヤー　Ｏ(n3q)

21 Dp指数の動的計画法（高速版） g(pi, k, y) ： pi を使い、(pi, k, y) から （q-w(pj) ≦ z ≦ q-１） を 満たす点 (pj, k’, z) へのパスの重み和　　（重みは １/k’ ） pi を使うパスの重み和： ［ S から (pi-1, k, y) までのパス数 × g(pi, k, y) 　］　の総和 　　　　　　n-1 　　 q-1 　　　　＝ Σ 　　Σ 　　　f(pi-1, y) × g(pi, k+１, y+w(pi)) 　　　　　　 k=0　 y=q- w(pi) 　　　　　　　　（　f(pi, k, y) は Ss 指数での定義と同じ　） ・すべての f(pi, k, y) , g(pi, k, y) を求める： Ｏ(n2q) 時間 ・１プレイヤーの計算：　　　　　　　　　　　　　 Ｏ(nq)　時間 ・全員分の計算　　　　　　　　　　　　 　　 Ｏ(n2q) 時間

22 まとめ 重み付き投票ゲームの投票力指数を計算する動的計画法に対して、全員分の計算を1人分の計算と同じ計算量で行うアルゴリズムを提案した バンザフ指数は　　　　　　　　　　　 Ｏ(n2q)　＝＞　Ｏ(nq) 　 シャープレイ・シュービック指数は　Ｏ(n3q)　＝＞　Ｏ(n2q) 　 ディーガン・パックル指数は　　　　 Ｏ(n4q)　 ＝＞　Ｏ(n2q) 　 と、計算量は減少した 今後の課題： 　　同じテクニックが使える問題はどの程度あるか？