重み付き投票ゲームにおける 投票力指数の計算の高速化 国立情報学研究所 宇野 毅明 [email protected] 目的 • • • • 重み付き投票ゲームの、投票力指数を計算する 対象は、Banzhaf, Shapley-Shubik, Deegan-Packel 指数 すでに動的計画法アルゴリズムが提案されている ただし、全プレイヤーの指数を計算すると、同じような計 算を繰り返すことになる そこで 計算方法を工夫して、無駄な計算を省き、 計算量を小さくする 重み付き投票ゲーム • ある議会に、政党（プレイヤー） A、B、C、D がある • 票決のとき、同一政党内の議員は同一の投票をする • 賛成票が q = 50人 以上で可決 政党A 45人 政党B 8人 政党C 17人 政党D 30人 各政党の力を示す指数がほしい => 議席 数？ 勝利提携 と 敗北提携 提携 ： 政党の集合 法案成立には、 q 人 か、それ以上の議員を含む提携を 組む必要がある 勝利提携 ： 提携に属する議員が q 人か、それ以上の提携 敗北提携 ： 提携に属する議員が q 人以下の提携 政党A 45人 政党B 8人 政党C 17人 政党D 30人 議席数は良い指標ではない • 勝利提携 人） ） （ 政党A（45人），政党D（30 政党B（8人） ： AB ， ABC ， ABD ， BCD 政党C（17人） ： AC ， ABC ， ACD ， BCD 勝利提携の組合せは同じ！ 指数は同じになるべき 提携の情報から指数を求めるモデルがよい もう一度、用語の定義 プレイヤー p1,…,pn ： 政党 プレイヤーの重み w(pi) ： 政党の議席数 q ： 成立に必要な票数 提携 ： プレイヤーの集合 提携 S の重み w(S) ：提携に属するプレイヤーの重みの和 勝利提携 ： 重みが q か、それ以上の提携 敗北提携 ： 重みが q 以下の提携 バンザフ（Banzhaf）指数 「ある勝利提携 S から プレイヤー pi が抜けると敗北提携に なるとする。このとき、 pi は発言力を持つだろう」 このような提携の数を 2n で割ったものを指数とする pi のバンザフ指数 Bz(pi) ＝ | { S | pi ∈S，w(S)≧q， w(S＼ pi)＜q } | ／ 2n pi q バンザフ指数を計算する 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 で割るとバンザフ指数になる 動的計画法 再帰式： f(pi, y) = f( pi-1, y ) + pi を含まない提携数 f( pi-1, y- w(pi) ) pi を含む提携数 i=１,…,n-１ に対して、 f(pi, y) を順々に求める q q - w(pn) ・・・・・ s p１ p2 p3 pn-2 pn-1 このグラフで、 f(pi, y) は s から対応する頂点までのパスの数 計算量 ・ f(pi-１, y) から f(pi, y) を求める： ・ f(pn-1, y) を求める： Ｏ(q) 時間 Ｏ(nq) 時間 pn 以外のプレイヤーに対しての計算： pn と pi の添え字をつけなおして、同じ方法で計算 ・全員分の計算 Ｏ(n2q) 時間 変更がちょっとしかないので、ほとんど同じ計算を行う なんとか無駄な計算を省けないでしょうか？ 不要な計算の省略 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-１ そのような提携の数 ＝ Σ z=0 y q-１-z f(pi-1, z) Σ g(pi+1, y) y=q- w(pi)-z h(pi, y) = Σ g(pi, z) とすると h(pi+1, q-１-z) - h(pi+1, q-w(pi)-z - 1) z=0 前後の計算を合わせる q 0 ・・・・・ 0 s ・・・・・ q 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) 時間で計算できる シャープレイ・シュービック （Shapley-Shubik）指数 「空の提携にプレイヤーが順々に参加し、プレイヤー pi が参加して、 はじめて S が勝利提携になるとき、 pi は発言力を持つ」 このようなプレイヤーの参加順序（順列）の数を n! で割ったものを 指数とする pi のシャープレイシュービック指数 Ss(pi) ＝ | { 順列 (pj１ pj2,,…, pjn ) | q ≦ w({pj１ pj2,,…, pi }) < q+ w(pi) } | ／ n! pi q Ss指数を計算する プレイヤー pi より前のプレイヤーの集合が S となるような順列 の数は |S|!(|n-|S|-1)! pi q S この場合、前に３プレイヤー、後ろに２プレイヤーいるので、 3!×2! ＝ 3!（6-3-1）! ＝ |S|! (n-|S|-1)! pi を加えると勝利提携になる敗北提携について、この総和を取る Ss(pi)×2! ＝ Σ S | ／ pi ∈S， q- w(pi) ≦ w(S)≦q-1 |S|! (n-|S|-1)! 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)! => パスの重み和 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) 時間 0 q k … 1 2 1 0 pi-１ バンザフ指数と同じ方法で、高速化を行う pi 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 ・・・ p１ p2 pi-１ pi pi+１ pn-１ pn １プレイヤー Ｏ(nq) 全プレイヤー Ｏ(n2q) ディーガン・パックル指数 （Deegan-Packel）指数 極小勝利提携 ： どのプレイヤーが抜けても敗北になる勝利提携 「 pi が極小勝利提携 S に所属すれば，発言力1/|S| を持つ」 pi が所属する極小勝利提携すべてに対して発言力の和を取って、 極小勝利提携の数 W で割ったものを指数とする q ディーガン・パックル指数２ プレイヤーは、重みの大きい順にソートされているとする d(S) ： 提携 S から最小重みのプレイヤー （ ＝ 添え字最大のプレイヤー ） を除いた提携 pi のディーガン・パックル指数 Dp(pi) ＝ | { S | pi ∈S，w(S)≧q， w(d(S))＜q } | ／ W q ディーガンパックル指数を計算 Ss 指数計算で用いた、動的計画法のグラフを考える 終点が (pi, k, y) （q-w(pi) ≦ y ≦ q-１） のパスの重みを 1/k とする pi 上Dp指数の計算： pi を使い、 S から上の条件を満たす点への パスの重み和 （重みは １/k’ ） q ・・・ ・・・ s p１ p2 p3 1プレイヤー Ｏ(n2q) pi-1 pi pi+1 ： pn-１ pn 全プレイヤー Ｏ(n3q) 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 ＝ Σ Σ k=0 f(pi-1, y) × g(pi, k+１, y+w(pi)) y=q- w(pi) （ f(pi, k, y) は Ss 指数での定義と同じ ） ・すべての f(pi, k, y) , g(pi, k, y) を求める： ・１プレイヤーの計算： ・全員分の計算 Ｏ(n2q) 時間 Ｏ(nq) 時間 Ｏ(n2q) 時間 まとめ • 重み付き投票ゲームの投票力指数を計算する動的計画法 に対して、全員分の計算を1人分の計算と同じ計算量で行う アルゴリズムを提案した • バンザフ指数は Ｏ(n2q) ＝＞ Ｏ(nq) シャープレイ・シュービック指数は Ｏ(n3q) ＝＞ Ｏ(n2q) ディーガン・パックル指数は Ｏ(n4q) ＝＞ Ｏ(n2q) と、計算量は減少した 今後の課題： 同じテクニックが使える問題はどの程度あるか？
© Copyright 2024 ExpyDoc
![[1510] 岩盤力学応用 釧路コールマインにおける排水量は](http://s1.expydoc.com/store/data/005761823_1-a0b9fb93a0c6920ee567690e52c9b2c7-250x500.png)
