- 投票ゲームってなに？
- 投票力指数ってなに？
- シャープレイ・シュービック指数ってなに？
こんにちは！しゅんです！
今回の記事では投票ゲームとシャープレイ・シュービック指数について解説します！
それではやっていきましょう！
普段は組合せ最適化の記事を書いてたりします。
ぜひ他の記事も読んでみてください！
このブログの簡単な紹介はこちらに書いてあります。
興味があったら見てみてください。
このブログでは経営工学を勉強している現役理系大学生が、経営工学に関することを色々話していきます！
ぼくが経営工学を勉強している中で感じたことや、興味深かったことを皆さんと共有出来たら良いなと思っています。
そもそも経営工学とは何なのでしょうか。Wikipediaによると
経営工学（けいえいこうがく、英: engineering management）は、人・材料・装置・情報・エネルギーを総合したシステムの設計・改善・確立に関する活動である。そのシステムから得られる結果を明示し、予測し、評価するために、工学的な分析・設計の原理・方法とともに、数学、物理および社会科学の専門知識と経験を利用する。
引用元 : 経営工学 – Wikipedia
長々と書いてありますが、要は経営、経済の課題を理系的な観点から解決する学問です。
投票ゲームってなに？
まず初めに具体例を使って投票ゲームについて説明したいと思います。
総理大臣を投票によって決定する
3つの政党があり、今から総理大臣を決める投票を行うとします。総理大臣になるためには過半数の投票が必要になると仮定します。上図の例だと合計300議席なので、151議席以上の投票が必要になります。
同じ政党に所属する人は同じ人に投票すると仮定します。
ここで政党が協力する場合を考えます。例えば政党Aと政党Bが協力する場合、投票数は
\(150 + 120 = 270\)
となり過半数の151議席を超します。従って政党Aと政党Bが協力すれば彼らが投票した人が総理大臣となります。一方で政党Bと政党Cが協力する場合の投票数は
\(120 + 30 = 150\)
となり過半数の151議席を超しません。従って政党Bと政党Cが協力しても彼らが投票した人は総理大臣にはなりません。投票ゲームではこのような状況を考えます。
ゲーム理論の分野では「協力」という言葉ではなく、「提携」という言葉を使います。この記事でもこれ以降「提携」という言葉を使って説明したいと思います。
投票ゲームを数式で定式化する
それではここまで話してきた投票ゲームを数式を使ってモデル化してみましょう。
\(N\)：プレイヤーの集合
\(w_i\)：プレイヤー \(i\) の持つ票数
\(q\)：投票に勝つための必要票数
上の3つについて1つずつ説明していきます。\(N\) はプレイヤーの集合を表しています。今回の例であれば
\(N = \{A,B,C\}\)
となります。\(w_i\) はプレイヤー \(i\) が持つ票数を表しています。今回の例であれば
\(w_A = 150, w_B = 120, w_C = 30\)
となります。\(q\) は投票に勝つために必要な票数を表しています。今回の例であれば
\(q = 151\)
となります。
特性関数：
\(v(S) = \begin{equation}\begin{cases}1 \;\; (\sum_{i \in S}w_i \geq q) \\ 0 \;\; (\sum_{i \in S}w_i < q)\end{cases}\end{equation} \;\; (S \subseteq N)\)
上の特性関数は「提携\(S\)による投票によって総理大臣を決められるかどうか」を表しています。例えば\(S = \{A,B\}\) のとき
\(\sum\limits_{i \in S}w_i = w_A + w_B = 150+120 = 270 \geq 151 = q\)
となるので
\(v(S) = v(\{A,B\})=1\)
となります。これは政党Aと政党Bの提携によって総理大臣を擁立することができるということを表しています。
一方で\(S = \{B,C\}\) のとき
\(\sum\limits_{i \in S}w_i = w_B + w_C = 120+30 = 150 < 151 = q\)
となるので
\(v(S) = v(\{B,C\})=0\)
となります。これは政党Bと政党Cの提携によっては総理大臣を擁立することができないということを表しています。
ということで投票ゲームを数式で表すことができました。
今回の例であれば、\(v(S)=1\) となる提携は \(\{A,B\},\{A,C\},\{A,B,C\}\) の3つです。このように総理大臣を擁立できるような提携を勝利提携と言います。
投票力指数ってなに？
それでは次に投票力指数というものについて解説したいと思います。
各プレイヤーはどれくらいの影響力を持っているの？
投票ゲームで重要なことの1つが
各プレイヤーがどれくらい投票に対して影響力を持っているのか
ということです。直観的に考えると
各プレイヤーが持つ議席数がそのまま投票への影響力になるんじゃないの？
と思うかもしれません。ただ本当にそうでしょうか？
例えば政党Bと政党Cについて考えてみましょう。政党Bは120議席、政党Cは30議席を保有しているので、直観的に考えると政党Bは政党Cの4倍も影響力があることになります。
でも先ほどの議論から、総理大臣を擁立できる提携（\(v(S)=1\) となる提携\(S\)）は
\(\{A,B\},\{A,C\},\{A,B,C\}\)
の3つであり、政党Bと政党Cが対称的であることが分かります。ということで政党Bは政党Cの4倍の影響力を持つという考えには疑問が残ります。
投票力指数は投票への影響力を表す
ということで登場するのが投票力指数です。
投票力指数（power index）：
各プレイヤーの投票力（投票への影響力）を表す指数
・シャープレイ・シュービック指数（S-S指数）
・バンザフ指数（Bz指数） etc.
投票力指数は「各プレイヤーがどれくらい投票に影響を与えるか」を数値化する指数です。票数だけからでは見えない影響力を測ることができます。
投票力指数はこれまでにいくつか提案されており、
・シャープレイ・シュービック指数（Shapley-Shubik index）
・バンザフ指数（Banzhaf index）
などがしばしば用いられています。
この記事ではシャープレイ・シュービック指数について解説したいと思います！
シャープレイ・シュービック指数の計算方法
ということでここでは投票力指数の1つである、シャープレイ・シュービック指数について解説したいと思います。
ある順番で政党が提携に参加するシチュエーションを考える
まず最初に以下のシチュエーションを考えます。
政党A → 政党B → 政党Cの順番で提携に参加する
1. 政党Aだけの提携
政党Aだけの提携の場合、この提携の投票数は150票です。従ってこの時点では過半数を超えていません。
2. 政党Aと政党Bの提携
つづいて政党Aだけの提携に政党Bが加わった場合を考えます。この提携の投票数の合計は270票です。従ってこの時点で過半数を超えました。
3. 政党Aと政党Bと政党Cの提携
政党Aと政党Bの提携の時点で過半数を超えているので、この提携に政党Ｃが加わっても投票数の合計は過半数を超えています。
ピボットプレイヤーを考える
政党Bに着目してみましょう。自身が提携に参加するまでは過半数を超えていませんでしたが、自分が提携に参加したら過半数を超えました。このようなプレイヤーのことをピボットプレイヤー（pivot player）と言います。
イメージとしてはピボットプレイヤーは自分の力によって過半数の成立を左右できる存在のことです。
上の例では政党A→政党B→政党Cの順番で提携に参加するシチュエーションを考えたのでピボットプレイヤーは政党Bでしたが、順番が変わればピボットプレイヤーも変わります。
例えば政党B→政党C→政党Aの順番で提携に参加する場合を考えます。このときは政党Aが提携に参加して初めて過半数を超えるので、ピボットプレイヤーは政党Aとなります。
全ての順列に対してピボットプレイヤーを考える
シャープレイ・シュービック指数を計算するためには全ての順列に対してピボットプレイヤーを考える必要があります。今回の例だとプレイヤーの数は3つなので、\(3!=6\)通りの順列を考える必要があります。
ということで全ての順列に対してピボットプレイヤーを考えることができました。ここまで出来たらシャープレイ・シュービック指数を計算することができます。シャープレイ・シュービック指数の計算式は下記の通りです。
\(\text{プレイヤー}i\text{のS-S指数} = \frac{\text{プレイヤー}i\text{がピボットプレイヤーになった回数}}{\text{順列の総数}}\)
（S-S指数はシャープレイ・シュービック指数の略）
3人のプレイヤーの場合、分母は6になりますね。この式に従って各政党のシャープレイ・シュービック指数を計算してみましょう。
政党A：\(\frac{4}{6}=0.6666…\)
政党B：\(\frac{1}{6}=0.1666…\)
政党C：\(\frac{1}{6}=0.1666…\)
ということで各政党のシャープレイ・シュービック指数を計算することができました。これを見ると政党Cは政党Bと同じくらいの影響力を持っていて、政党Aは政党Bの4倍の影響力を持っていることが分かります。
実はシャープレイ・シュービック指数は投票ゲームにおけるシャープレイ値なんです。シャープレイ値は提携型ゲームにおける配分の1つで、各プレイヤーの限界貢献度をもとに計算されます。投票ゲームにおいては各プレイヤーがピボットプレイヤーのときに限界貢献度が1、それ以外の場合は限界貢献度は0となります。（機会があったら今度シャープレイ値の記事も書こうと思います。）
おわりに
いかがでしたか。
今回の記事では投票ゲームとシャープレイ・シュービック指数について解説してみました。
今後もこのようなゲーム理論に関する記事を書いていきます！
最後までこの記事を読んでくれてありがとうございました。
