離散最適化とその応用

第2回 アルゴリズムの高速化，投票力指数に関して
宇野 毅明
Il…州…ll……llI川tll……l………川＝…‖川＝……………ll州州………‖‖‖‖‖‖‖‖‖‖‖＝‖＝‖‖‖‖川…l…ltll………………l………………………＝＝‖＝‖‖‖‖＝‖……………＝＝‖‖‖＝＝＝＝＝＝‖‖‖‖＝＝＝‖‖‖＝‖川Ilが法案を通すためには，βの協力か，C，β，且のうち1． はじめに2党の協力が必要になった．つまり，Aは相変わらず

本連載では，ゲーム理論や分配問題への離散最適化第一党であり，かつ議席数も増えたにもかかわらず，の応用を解説しているが，今回は，ゲーム理論へのア法案を通す，という観点からは状況が悪くなっているルゴリズム的な研究という切り口で解説をしたいと思のである．

う．アルゴリズムは，およそ計算と名のつく事柄すべ

このような，各政党が自分の法案を通すにはどの程てに関わっている．特に複雑なシステムに関わる計算度苦労するか，という観点から指標をモデル化するには，単純な方法では多くの時間を必要とするため，アは，どのような政党の組合せ（提携と呼ぶ）が，ヴ以ルゴリズム的な研究の必要性が高い．ゲーム理論でも上の議席数を確保できるか，という組合せ的な要因を様々なアルゴリズム的研究が行われているが，今回は考慮して指数化するのが良い．そのような指数がいく

重み付き多数決ゲームの投票力指数計算アルゴリズム

つか研究されているが，ここでは代表的な3指数，バについて解説をする．

ンザフ（Banzhaf）指数，シャープレイ・シュービッ

ある議会を考えよう．この議会では乃党の政党がク（Shapley−Shubik）指数，ディーガン・バックルそれぞれ議席を以ル席持っている．この議会ではヴ人（Deegan−Packel）指数の紹介をしよう．以後プレイの賛成があれば法案が通るとする．このような状況で，ヤーかの各指数を励（動），Ss（か）ノわ（か）と表記する．

各政党をプレイヤーとみなし，その構造をモデル化しここでもう一度，用語の定義を行おう．ゲームのプたものが重み付き多数決ゲームである．投票力指数は，レイヤー集合をⅣ＝（れ…，♪乃）とし，プレイヤーれゲーム内でのプレイヤーの力の指標である．の重みを別々とする．プレイヤーの重みと定数す（法一般的に，政党の強さは議席数で測られることが多案を通すために必要な票数）が与えられると，重み付い．これは，政党の議席数の推移など，数自体を調べき多数決ゲームが一つ定義される．プレイヤーの集合

る目的には合っているが，法案を通すための力が大きを提携と呼び，提携5の重み紺（5）をSに属するプいか小さいかを測るには，少々モデルとして合わないレイヤーの重みの総和とする．空集合と全体集合も提部分がある．例えば，政党A，β，C，β，Eがあり，携と呼ぶ．重みがqと同じかそれより大きい提携をそれぞれ議席を40，24，12，12，12有するとする．

勝利提携と呼び，そうでない提携を敗北提携と呼ぶ．

法案成立に必要な票数ヴを51，つまり過半数とする

重み付き多数決ゲームは，投票システムと呼ばれる，（図1）．ここで，政党Aが法案を提案するとしよう．

より一般的なシステムの特殊ケースである．投票シス法案を成立させるためには，政党Aは政党β，C，β，テムとは，プレイヤー集合Ⅳと勝利提携集合Ⅳの互いずれか1党の協力を得ればよい．そうすれば，組（Ⅳ，Ⅳ）で定義される．重み付き多数決ゲームは，過半数である51票を確保できるからである．さてこ

勝利提携集合Ⅳが，重みが仔以上の提携の集合であこで選挙があり，Aは2，βは13，議席を増やし，るような投票システムである．

C，β，gはそれぞれ5議席失ったとしよう．議席数は1．1バンザフ指数

それぞれ42，37，7，7，7になる．この状況では，A

勝利提携5からプレイヤーかが抜けることによっうの たけあき
国立情報学研究所〒101−8430東京都千代田区一ツ橋2−1−2
丁88（36）てSが敗北提携になるとき，かはSのスウィングであるという．かが5のスウィングであれば，かはある種の発言力を持つと考えられるだろう．ここで，全© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズ・リサーチ

選挙前

＞

過半数になる組合せ

過半数になる組合せ

図1選挙後，A党の議席は増えたが，過半数を取れる組合せは減ったqll9I

図2 極小勝利提携．各プレイヤーの幅が重みに対応する．

l

どの70レイヤーが抜けても重みが〃を下回る

図3 れ…，♪6の順で提携に加わる．かが加わった時点で勝利提携になり，この順列のピボットは♪。になるての提携が一様に発生すると仮定すると，プレイヤーに変化する．このとき，プレイヤーかを順列打のピかがスウィングである確率はボットと呼ぶ（図3）．ピボットは，何らかの意味でl（S⊆州カf∈S，針≦紺（S）＜q＋軌 ／2乃となる．励（か）はこの確率により定義される［1］．
1．2 ティーガン・バックル指数

発言力を持つと考えられるので，全ての順列が一様に発生すると，かが発言力を持つ確率はl（汀l方は順列，かは打のピボット）l／乃！

提携Sに対し，Sから最小重みのプレイヤーを除いた提携をβ（5）とする．勝利提携Sから，どのプとなる．これがSs（♪ ）の定義である［7］．

パンザ7指数はBanzhafにより1965年［1］に，シビック指数はShapleyとShubik

レイヤーかが抜けても敗北提携になる，つまり，ャープレイ・シュー抑（β（5））＜〃であるとき，5は極小勝利提携であるとにより1953年［7］に，ティーガン・バックル指数はいう（図2）．プレイヤー達が勝利提携を組むとき，DeeganとPackelにより1978年【3］に提唱された．

大人数で合意を取るのは手間がかかるので，余分なプ

バンザフ指数，シャープレイ・シュービック指数に関レイヤーはメンバーになっていないだろうと考えられしては公理系からの指数の導出や，性質・構造の解析る．つまり，発生するのは極小勝利提携のみであるとなど，多種多様な研究が行われてきている．例えば，みなせる．極小勝利提携5に属するプレイヤーが発勅≦抑ノであれば必ずS5（♪f）≦駄（九），βz（か）≦βz（九）言力1／lSlを持つとし，極小勝利提携が等確率で発生が成り立つ，つまり議席数に対する指数の逆転は起きすると仮定すると，プレイヤーかの発言力の期待値ない，ということが知られている［8］．ティーガン・は，一方を極小勝利提携の集合とすると，バックル指数に関しても，前者ほどではないが，∑研究がある．この他にもいくつかの指数が提唱されている

1／】別耳♪∫∈5，￠≦川（5）．1〝（β（S））＜〃が，これら3指数ほどの深い研究は行われていないよとなる．これがβ夕（♪f）の定養である［3］．

うである．

1．3 シャープレイ・シュービック指数
勝利提携が形成されるとき，その勝利提携は一瞬に2．単純な指数計算アルゴリズムして発生するのではなく，徐々に大きくなっていくと考えられる．つまり，最初に空の提携Sがあり，ある順列方の順にプレイヤーが参加していくと考えられる．最初5は敗北提携であるが，順々に重みが増し，あるプレイヤーかが参加したところで勝利提携

2002年12月号

前節で定義した3つの指数を計算する最も単純な方法は，定義式通りに計算を行う方法である．シャープ
レイ・シュービック指数は，大きさ乃の全ての順列を発生させ，それらのピボットを見つけて以下のように計算できる．アルゴリズム実行前，任意のどについ© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（37）丁89

全ての勝利提携

Aを含みBを含まないAbを含む
勝利提携

勝利提携

図4 問題を分枝して勝利提携を列挙する．

勝利提携が含まれない子問題（×印）は探索しないて市】＝0であるとする．

が計算できる．

（55）全ての大きさ乃の順列のピボットかに対して（Ss2）全ての提携5とか∈5に対し，仔≦抑（S）＜〃十紬fならs［才］＝S［f］＋（15ト川（雅一151）！わ！

ざ［才】＝ざ【オ】＋1／乃！とする

アルゴリズム実行後，各オに対してSs（か）＝5［オ］となる．計算時間は0（乃×乃！）である．バンザフ指数，デ計算時間は0（乃×2乃）に高速化される．
さらに，計算に実際に必要な提携は，デイーガン・イーガン・バックル指数も，以下のように全ての提携

バックル指数では極小勝利提携，バンザフ，シャープを発生させて計算できる．

レイ・■シュービック指数ではスウィングを持つ勝利提（Bz）全ての提携Sとか∈Sに対し，携だけであることから，以下の提携列挙アルゴリズム〃≦抄（5）＜ヴ＋勅ならs［才］＝5［オ］十1／2乃・を用いて計算時間の短縮ができる．ここでは，プレイヤーはその重みの降順でソートされている，つまり任（Dp）全ての提携5とか∈Sに対し，Sが極小勝利提携ならぶ［ブ】＝5【オ］＋川床l

意の才に対して彿≧軌．1であるとする．また，f≦ノ

これらの計算時間は0（乃×2りである．これらは，いに対して〃む＝（か，…，九）とする．初期入力をS＝￠，g

わゆるナイーブなアルゴリズムであり，利用している＝1とする．

指数の性質は，定義に用いられる集合族の大きさが有極小勝利提携列挙（提携5，添え字才）由である，というものだけである．「有限時間で計算できるかどうか」という開いに答えているにすぎない．
そこで次に，指数の性質をより深く利用したアルゴリ

1．紺（〃む）＋紬（5）≧〃となる最小のノを見つけ，5∪〃むを出力

2．紺（〃f乃）＋紺（5）一抑机1≧α，ゐ＋1≦ノなるゐについて，ゐ≦乃−2ならば極小勝利提携列挙（5∪ズムを解説しよう．

3．指数計算アルゴリズムの高速化
シャープレイ・シュービック指数の計算では，全ての順列を発生させている，という部分が計算上のボトルネックになっている．そこで，〃勅ゐ十2）を再帰呼び出し

スウィング勝利提携列挙（提携S，添え字才）
1．抑（〃む）＋∽（5）≦〃＋押上となる最大のノを見つける（如はSU〃ぴの最小添字プレイヤー）
2．針≦紺（凡人）＋∽（S），カ≦ノとなる各ゐについて，・かがピボットであり，かが加わる前の提携が5であるような順列はISl！（れ−15ト1）！個存在する（このとき♪fはSU（か）のスウィングである）．という性質に着目しよう．これは，かがピボットでSU凡人を出力3．抑（凡乃）十棚（S）一付目1≧q，ゐ＋1≦メなる各ゐについて，ゐ≦乃−2ならばスウィング勝利提携列挙（SU〃砺ゐ十2）を再帰呼び出し

あれば，かの前，および後ろのプレイヤー同士の順

これらのアルゴリズムは分割法と呼ばれる列挙法を番を入れ替えても，かはピボットになっているとい用いている．分割法は，図4で示すように，元の問題うことである．これより，全ての提携Sを発生させを二つの非空な問題に分割して再帰的に列挙する方法

れば，少fがピボットとなる順列の数がわかる．そこである．南アルゴリズムともに，出力する提携一つあで，スウィングがかである全ての提携Sについて，たりに必要な計算時間は0（乃）であるので，計算時間l到！（乃−1Sト1）！の総和をとる，という方法で鼠（か）は（必要な勝利提携数）×乃となる．スウィングを持丁90（38）© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズ・リサーチ．

○→○→○−○−→○→○．

．

図6 非ゼロな関数値のリスト．∬とエ一勘を指すポイン
タをずらし，どちらかのポインタが非ゼロ要素にぶ
つかると，′（f，エ）の次の非ゼロ関数値が見つかる．

．

図5 関数値を≠＝1，2，…の順番で計算．矢印は，／（i，6）
は′（オー1，6）と′（才一1，3），／（才＋1，6）は′（g，6）と∬）＞0となるので，0（仔乃）時間でβz（♪乃）が計算できる．才≠乃であるようなβz（か）を計算するには，かと♪乃の添え字を入れ替えればよい．シャープレイ・シ／（才，1）から計算されることを表すュービック指数に関しても，．

つ勝利提携数，極小勝利提携数ともに，最悪の場合

ふ（ブ，々，エ）＝l（SIS⊆凡 ，lSl＝々，抑（S）＝∬）l㊥（2りとなるので計算量の意味での改善はないが，実と関数を定毒すると，際の計算時間の減少が期待できる．極小勝利提携の列

駄（轟）×乃！＝∑ ふ（乃−1，々，J）
q−比J汀≦∫く〃，々≦I7

挙に関しては松井・松井［5］に解説がある．となり，重みの整数性を仮定すると0（乃2仔）時間で計

さらに，両列挙アルゴリズムで，ノ，ぁの発見に2分探索を用いると，提携一つ当たりの計算時間を0（log乃）に減少できる．s［才］への数値の足しこみに，1反復で0（乃）かかっている部分を，区間木を用いた加算を用いることで0（logク2）に減少すれば，指数の計算時間を（必要な提携数）×0（lo占花）まで減少できる．

算できる．デイーガン・バックル指数についても同じような動的計画法が提案されているが［5］，ここでは割愛させていただく．

空間計算量，つまり上述の動的計画法アルゴリズムのメモリ使用量についても言及しておこう．アルゴリ
ズム実行中，全ての関数値をメモリに保持すると，それぞれ㊥（乃〃），㊥（乃2￠）のメモリを使用する．しかし，4．動的計画法とその高速化

よく観察すると，引数オ＝ノなる関数値を計算する際
投票力指数計算に対しては，上述のアルゴリズムとは異なる観点に着目して設計された，動的計画法も提案されている［2，4］．バンザフ指数計算を例にして解説しよう．まず，以下の関数を定義する．には，才＝ノー1なる関数値のみが参照されている．そこで，才＜ノー1なる関数値は破棄しても差し支えないことがわかる．これより，メモリ使用量はそれぞれ㊥（仔），㊥（乃々）ですむ．

ん（オ，∬）＝l（51S⊆州∫，紺（5）＝州上述の動的計画準では，全ての引数の組合せに対しこの関数を用いると，て関数値の計算を行うと，それぞれちょうど㊥（花々），βz（轟）×2乃＝ ∑ ん（乃−1，∬）㊥（乃2〃）時間を消費する．しかし，実際計算に必要な〃一肌，≦J＜￠

関数値は非ゼロなものだけである．そこで，引数ブ＝となる．ん（才，∬）はん（オ，エ）＝ん（才一1，J）＋ん（オー1，∬一肌）

ノー1である関数値の中で非ゼロのものだけを，引数という再帰式を満たすので，全ての0≦オ≦乃−1，0≦Jの大きさ順に連結リストを用いて保持しよう．する∬＜ヴに対するんの関数値をオ＝1，2，…，雅一1の順にと，図6のように二つのポインタでリストをなぞるこ

動的計画法を用いて計算できる（図5）．ん（才，J）＞0とにより，引数f＝ノである全ての関数値を，効率良となるようなオ，エの組合せは，最悪で2乃個存在する

く計算できる［9］．これにより，関数値がゼロであるので，この方法での計算量の減少は，そのままでは見ような引数に対しては計算を省略できる．

込めない．そこで，プレイヤー重みの整数性を仮定し次に，この数的計画法の高速化を考えよう．とはいよう．議会などの現実問題ではプレイヤーの重みはだえ，プレイヤー1人の指数を計算する動的計画法にはいたいが整数であるので，この仮定はさほど一般性を無駄な部分は少なく，根本的に新しいアイディアがな失わない．これより，エが整数であるときのみん（才，ければ計算量の改善は見込めない．現在のところ，そ2002年12月号© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（39）791のような新しいアイディアは発見されていない．そこ

2．引数オがノから（ノ＋ノ′）／2までの′の関数値を逐で少々視点を変え，全プレイヤーの指数計算を高速化

次計算し，指数計算分割統治（／（（ノ＋ノ′）／2，・）する，という方法を考えよう．上記動的計画法は，全の関数値，「（ノ＋ノ′）／2＋11，ノ′）を再帰呼び出しプレイヤーの指数計算をする際には，同じような問題

3．ノからノ′までの添え字を逆順に付け直すを何回も解くことになり，ここには大いなる無駄があ

4．引数オがノから（ノ＋ノ′）／2までの′の関数値を逐るので，そこを省略する方法を考える．

次計算し，指数計算分割統治（′（（ノ＋ノ′）／2，りまず簡単に思いつく方法が，図7のような分割統治の関数値，L（ノ＋ノり／2＋1」，ノ′）を再帰呼び出し法的なアプローチである．以下では，プレイヤーの添

このアルゴリズムは，最初に全ての／（0，りの値，ノえ字の小数部分は切り捨ててあるとする．上述の垂加勺＝1，ノ＝刀を引数として呼び出す．バンザフ指数，シ計画法は，プレイヤー♪乃′2＋1，…，♪〃の指数計算を行う

ャ∵プレイ・シュービック指数どちらにも適用できる．

とき，アルゴリズム中のループの前半，オ＝乃／2とな1回再帰を行うと，着目するプレイヤー琴は半分になるまではまったく同じ計算を行う．つまり，計算したるので，再帰の深さはたかだかlog2乃となる．再帰関数値（′と書く）は再利用できるのである．プレイの各レベルでの計算時間の総和は，もとのアルゴリズ

ヤーれ…，少乃／2に関しては，プレイヤーの添え字を逆ムのループ乃回り分に相当する．よって，全プレイ順に付け直したとみなして動的計画法を通用すると，ヤーの指数計算は，バンザフ指数では0（￠乃2）からやはりループの前半でまったく同じ計算を行うので，0（〃乃logク官），シャープレイ・シュービック指数では計算した関数値を再利用できる．

0（す乃3）から0（す紹2logク2）に減少される．

この方法を再帰的に適用して，関数値の計算を省略

分割統治法的なアイディアに基づかない改良も提案する方法を考えよう．今，引数オ＝乃／2である′の関されている［9］．最初に説明した動的計画法は，プレ数値が求まっていて，プレイヤー♪刀′2．1，…，カ乃の指数

イヤーかの指数計算では，プレイヤーかとプレイヤ計算を行うとしよう．このとき，プレイヤー勿醐＋1，ー♪乃を入れ替えて再計算する．その結果，か＋1から…，み−の指数計算は，g＝乃／2十1，‥・，3乃ノ4までまった♪乃＿1の部分の関数値をすべて計算しなおすことになく同じ計算を行うので，関数値の再利用ができる．プる．この計算を他の何らかの方法で共通化できれば，レイヤーカ乃／2．1，・・・，♪3月′。に関しても，プレイヤー高速化が行えるだろう．この発想に基づいた改良を，

轟／2＋1，…，♪乃の添え字のみ逆順にすれば，同じく前半

まずはバンザフ指数の場合について説明する．

部分の計算結果を再利用できる．このようにして再帰プレイヤーか以外のプレイヤーを才より添え字が的にプレイヤーを分割し，添え字を入れ替えながら計小さいプレイヤーと，そうでないプレイヤーに分けて算を行えば，計算のかなりの部分を再利用できる．こ考え，関数馳〜（オ，ご）をの方法でアルゴリズムを記述すると，以下のようになl（Sl♪i∈S，彿（Sn凡（ト1））＝エ，ヴ≦紺（S）＜q＋勘）lる．

で定義する．この関数は，「添え字が才より小さいプ

指数計算分割統治（′（ノー1，・）の関数値，ノ，′）

レイヤーの重み和がエである勝利提携で，♪iがスウ

1．ifノ＝ノ′thenれの指数を計算し終了

ィングになっているものの数」である．この関数を用

12345678＼＼＼▲／＼

図7 分割統治の様子．各反複で太線で囲まれたところのみ計算する．灰色の部分は上位の反復で計算済み
丁92（40）© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズ・リサーチ

．

q ＝105．補遺
本稿で取り上げた投票力指数に関する詳しい解説が文献［5，6］にある．特に文献［6］には，各指数について，公理系からの導出から実際問題への適用例まで詳しい解吉見がある．バンザフ，シャープレイ・シュービ
ック指数計算を行う動的計画法は，文献［2，4］で解説されている．また，ティーガン・バックル指数計算を行う動的計画法も含めた解説が文献［5］にある．全プ．

レイヤーの指数計算を高速化する方法は文献［9］で提図8 βz（か）の指数計算を′と∂を使って行う．軌＝3より，g（オ，1）は縦線区間の和と／（ト1，1）の積になる案されている．スウィングを持つ勝利提携の列挙アルゴリズム，および勝利提携列挙を一つ当たり0（log乃）時間で列挙する方法，区間木を用いて足しこみを0（logク7）時間で行う方法，分割統治法による動的計

いると，画法の改良は，本稿のために新しく考案したものであβ之（か）×2乃＝ ∑ 如ヱ（オ，エ）0≦J＜マと表される．関数紬の効率の良い計算のために占お（才，∬）＝l（S15−⊆〃叫紺（S）＝エ）lり，文献はない．しかし証明自体は簡単であるので試していただきたい．

ぁぉ（オ，エ）＝ ∑ 占お（才，y）

参考文献

0≦y≦Jと定義する．∂彪（オ，∬）は，「添え字が才以上のプレイ

ヤーの提携で，重みがJになるものの数」である．
関数んと∂βzは対称なので，∂此の関数値はんと同じ方法で計算できる．ぁぉはぁおより簡単に計算でき［1］J．F．BanzhafIII， WeightedVotingdoesn t work ，RutgersLawReview19，Pp．317−343，1965・［2］S．）．Brams and P．J．Affuso， Power and size：anewparadox ，TheoryandDecision7，pp．29−56，1975・［3］J．Deegan and E．W．Packel，る．これらの関数を用いると，
紬（才，∬）＝ん（才一1，エ）× ∑ ∂＆（オ十1，y）グー肌−∫≦y＜q−エ＝ん（オー1，エ）×（ゐ＆（才＋1，￠−1−エ）−ゐ＆（オ十1，α−1−∬一肌））PowerforSimplen−PerSOnGamesA NewIndex of，InternatinalJour−nalofGame Theory7，pp，113−123，1978．

［4］W．F．Lucas， MeasuringPowerinWeightedVoting
Systems ，in S．J．Brams，W．F．Lucas and P・D・と表現される．よって，馳の全ての関数値は0（α乃）Stra爪n Eds．，Politicaland r・elated models，Springer

時間で計算でき，全プレイヤーのパンザフ指数はVerlag，Pp．183−238，1983．

0（す乃）時間で計算できる．

シャープレイ・シュー

ビック指数，デイーガン・バGames

ックル指数に関しても，∂∫ぶ（ブ，々，∬）＝ ∑ （々＋lSl）！（乃＋1一々−151）！
5⊆〃れ！〃（5）＝J∂。♪（オ，々，J）＝［5］T．MatsuiandY．Matsui， ASurveyofAlgorithms
forCalculatingPowerIndices ofWeighted Majority∑

1／（lS廿々）〃−J≦；礼（S）＜〃−J＋ヱ（5），Journalofthe Operations Research Society

OfJapan43，pp．71−86，2000．

［6］武藤滋夫，小野理恵，「投票システムのゲーム分析」，日科技連，1998．

［7］L．S．Shapley and M．Shubik， A Method for
EvaluatingtheDistributionofPowerinaCommitteeと定義すると，5∫（か），上わ（か）はそれぞれ∑ （ふ（オー1，た，エ）System0≦J≦グーl，0≦鳥≦〃，American PoliticalScience Review48，pp・787−792，1954．
×∑占ss（ブ十1，々，y））

ロー紺i−エ≦〝≦〃−1−∫∑ （ふ（才一1，々，エ）×∂。♪（才，々，エ））0≦∫≦q−1，0≦斤≦打を用いて，0（乃2q）時間で計算できる．

［8］P．D．Stra抗n， Powerindicesinpolitics ，Politicaland Related Models，Springer−Verlag，pp．256−321，
1983．

［9］宇野毅明，「重み付き投票ゲームにおける投票力指数の計算の高速化」，情報処理学会アルゴリズム研究会80，2001．

2002年12月号© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（41）Tg3