利用者:Theorist2/Archived

メカニズムデザイン

「メカニズムデザインの例」のセクション http://ja-two.iwiki.icu/w/index.php?title=メカニズムデザイン&oldid=41862390#.E3.83.A1.E3.82.AB.E3.83.8B.E3.82.BA.E3.83.A0.E3.81.AE.E4.BE.8B

協力ゲーム

「単純ゲームの性質」のセクション http://ja-two.iwiki.icu/w/index.php?title=協力ゲーム&oldid=41858190#.E5.8D.98.E7.B4.94.E3.82.B2.E3.83.BC.E3.83.A0.E3.81.AE.E6.80.A7.E8.B3.AA

「選好プロファイルにおける単純ゲームのコア」 http://ja-two.iwiki.icu/w/index.php?title=協力ゲーム&oldid=41858190#.E9.81.B8.E5.A5.BD.E3.83.97.E3.83.AD.E3.83.95.E3.82.A1.E3.82.A4.E3.83.AB.E3.81.AB.E3.81.8A.E3.81.91.E3.82.8B.E5.8D.98.E7.B4.94.E3.82.B2.E3.83.BC.E3.83.A0.E3.81.AE.E3.82.B3.E3.82.A2

中村ナンバー

協力ゲーム理論および社会選択理論において、中村ナンバー (なかむらナンバー、Nakamura 数、 Nakamura number) とは、(投票ルールに代表される) 集合的意思決定ルールの合理性の度合いをはかる指標 (整数) である。

• この数未満の選択肢 (候補、オプション) から選ぶ状況では、当該ルールはつねに問題なく「ベストな」ものを選び出せる (ただし「ベストな」ものがひとつだけとは限らない)。

その一方で、

• この数以上の選択肢から選ぶ状況では、ひとびとの投票の仕方 (「選好」の組合せ) によっては、当該ルールでは「ベストな」ものが定まらない場合がある (投票のパラドックスに見られるように、選択肢 a が b より、b が c より、c が a より集団的に好まれるといったサイクルの生じる場合)。

すなわち大きい中村ナンバーを持つルールほど、多くの選択肢を矛盾なくあつかえる。たとえば多数決の中村ナンバーは (投票者が4人のケースを除けば) ３であることから、２個までの選択肢なら (パラドックスなど起さずに) うまくあつかえることが分かる。「中村ナンバー」という名称は、選択の合理性が選択肢数とこの数の大小関係に左右される上記事実を、定理として証明した日本人ゲーム理論家である中村健二郎 (1947-1979) にちなむものである。

概要

中村ナンバーの正確な定義を与える前に、中村ナンバーを付与することのできる意思決定ルールの例を挙げる。 いま、1, 2, 3, 4, 5 からなる個人の集合を想定すると、たとえば「多数決ルール」の背後には、 過半数である３人以上をふくむ「提携」(個人の集合) のあつまり

$\{\{1,2,3\},\{1,2,4\},\{1,2,5\},\{1,3,4\},\{1,3,5\},\{1,4,5\},\{2,3,4\},\{2,3,5\},\{2,4,5\},\{3,4,5\},$

$\{1,2,3,4\},\{1,2,3,5\},\{1,2,4,5\},\{1,3,4,5\},\{2,3,4,5\},\{1,2,3,4,5\}\}$

が存在するはずである。意思決定ルールの背後にある、この種のあつまりが中村ナンバーを与えることのできる対象であり、こういう任意の提携のあつまりのことを 「シンプルゲーム」(単純ゲーム; 投票ゲーム) とよぶ。 そして、そういうあつまりに属する提携をそのシンプルゲームおける「勝利提携」とよび、それ以外の提携を「敗北提携」という。 勝利提携に属する個人 (上の例では最低3人) 全員が選択肢 x を選択肢 y より好ましいとするとき、 (上の例では5 人の) 社会全体としてもそれと同じ順序付け (「社会選好」) が実現する。

シンプルゲームの「中村ナンバー」とは、インターセクション (共通部分) が空集合となるような勝利提携のあつまりのうちもっとも提携数が少ないものの、その提携数のことである (この数だけ勝利提携を集めることでインターセクションを空集合にできることがあるが、これ未満の数を集めてもけっしてインターセクションを空にはできない)。 たとえば上の例におけるシンプルゲームの中村ナンバーは３である。なぜなら任意の２つの勝利提携のインターセクションは少なくともひとりの個人をふくみ、 その一方で次の３つの勝利提携のインターセクションは空になるためである: $\{1,2,3\}$, $\{4,5,1\}$, $\{2,3,4\}$.

中村の定理 (Nakamura, 1979) は、 シンプルゲームがすべての選好プロファイル (各個人の選好の列) にたいして非空の「コア」を持つ (つまり「ベストな」選択肢の集合が空集合にならない) ための必要条件として以下を挙げている (選択肢集合が有限のばあいは十分条件でもある): 選択肢の数がそのシンプルゲームの中村ナンバーよりも小さいこと。 ここで「与えられた選好プロファイルについてのシンプルゲームのコア」とは、 ある勝利提携に属する個人すべてが $x$ より好むような選択肢 $y$ が存在しないような 選択肢 $x$ の集合 (すなわち社会選好の極大要素の集合) のことである。 上記の過半数シンプルゲームの例でいえば、選択肢が３個以上あるばあい、選好プロファイルの選び方によっては コアに属する選択肢がなくなる (「ベスト」といえるものが存在しない) ことをこの定理は意味する。

中村の定理にはいくつかの変種があり、たとえば以下の各条件をみたすようなすべての選好プロファイルにたいしてコアが非空になるための条件を挙げている: (i) 「非循環性」をみたす選好; (ii) 「推移性」をみたす選好; (iii) 「線形順序」となる選好。 また、これらとは異なる変種として、合理性にかんする弱い要件である「非循環性」さえ取り除いた定理 (Kumabe and Mihara, 2010) があり、 その定理は極大要素を持つような個人選好からなるすべてのプロファイルにたいしてコアが非空になるための条件を挙げている。

選択肢を「順序づけること」にかんしては、社会選択理論における「アローの不可能性定理」という有名な定理が存在し、 個人の集まりが３つ以上の選択肢に順序を与えることの困難さを指摘している。 与えられた選択肢集合からなんらかの選択肢を「選ぶこと」にかんしては、 (順序を持つとは限らない社会選好の極大要素の集合である「コア」に注目した) 中村の定理がより直接的な関連性を持っている。 この定理の主張を考えると、「中村ナンバーはどれだけ大きくなりうるか？」という疑問が興味深いものであることが分かる。 この疑問については、以下の結果を挙げることができる: 「拒否権を持つプレーヤー (すべての勝利提携に属する個人) が存在しないような、(有限あるいは) 計算可能なシンプルゲームが ３より大きな中村ナンバーをもつためには、そのシンプルゲームが「強い」ものであってはならない。」 これは、ある敗北提携で、その補集合も敗北提携になっているようものが存在することを意味する。 このことは、３つ以上の選択肢を持つ集合でコアがつねに非空になるためには、 コアのなかに互いに比較できない複数の選択肢をふくまざるをえないことを意味する。

フレームワーク

$N$ を (有限または無限の) 非空な「個人」の集合とする。 集合 $N$ の部分集合を「提携」とよぶ。 シンプルゲーム (投票ゲーム) とは、提携のあつまり $W$ のことである。 (それぞれの提携に 1 または 0 の値を与える提携ゲームと考えることもできる。) ここでは $W$ は非空で空集合をふくまないと仮定する。 $W$ に属する提携は「勝利」提携、属さない提携は「敗北」提携という。 シンプルゲーム $W$ が「単調である」とは、任意の $S\in W$ と $S\subseteq T$ について、$T\in W$ がなりたつことをいう。 $W$ が「プロパーである」とは、任意の $S\in W$ について、$N\setminus S\notin W$ となることをいう。 $W$ が「強い」とは、任意の $S\notin W$ について、$N\setminus S\in W$ となることをいう。 「拒否権プレーヤー」とは、すべての勝利提携に属する個人のことである。 シンプルゲームが「弱い」とは、それが拒否権プレーヤーをもつことを意味する。 $W$ が「有限である」とは、ある有限集合 (キャリアとよばれる) $T\subseteq N$ が存在して、 任意の提携 $S$ について、$S\in W$ と $S\cap T\in W$ が同値になることをいう。

$X$ を (有限または無限の)「選択肢」の集合とし、その濃度 (要素数) $\#X$ は最小でも２とする。 ここで (強い; 狭義の) 選好とは、$X$ 上の「非対称的な」関係 $\succ$ を指す: すなわち $x\succ y$ (「$x$ は $y$ より好まれる」の意) ならば、 $y\not \succ x$ となる。 選好 $\succ$ が「非循環的である」(「サイクル」をふくまない) とは、任意の有限個の選択肢 $x_{1},\ldots ,x_{m}$ について、もし $x_{1}\succ x_{2}$, $x_{2}\succ x_{3}$,…, $x_{m-1}\succ x_{m}$ ならば、 $x_{m}\not \succ x_{1}$ となることをいう。非循環的な関係は非対称的であるため、選好に該当することに注意。

(選好) プロファイルとは、個人の選好 $\succ _{i}^{p}$ の列 (リスト) $p=(\succ _{i}^{p})_{i\in N}$ のことである。 ここで、$x\succ _{i}^{p}y$ は個人 $i$ がプロファイル $p$ において、選択肢 $x$ を選択肢 $y$ より好むことを表している。

「譲渡可能な効用を前提としない投票ゲーム」(選好つきシンプルゲーム) とは、シンプルゲーム $W$ とプロファイル $p$ のペア $(W,p)$ のことである。 いま $(W,p)$ が与えられたとき、 $X$ 上の「支配関係」(社会選好) $\succ _{W}^{p}$ を次のように定義する: $x\succ _{W}^{p}y$ とは、ある勝利提携 $S\in W$ が存在して、すべての $i\in S$ にたいして $x\succ _{i}^{p}y$ となること。 $(W,p)$ のコア $C(W,p)$ とは、$\succ _{W}^{p}$ によって支配されない選択肢の集合 ($\succ _{W}^{p}$ にかんして $X$ 上で極大要素となる選択肢の集合) である:

$x\in C(W,p)$ とは、$y\succ _{W}^{p}x$ となる $y\in X$ が存在しないこと。

中村ナンバー: 定義と例

シンプルゲーム $W$ の中村ナンバー (Nakamura 数) $\nu (W)$ とは、インターセクションが空集合となるような勝利提携のあつまりのうちもっとも小さなものの濃度 (提携数) のことである: $\cap W=\cap _{S\in W}S=\emptyset$ (拒否権プレーヤーが存在しない) となるとき、

$\nu (W)=\min\{\#W':W'\subseteq W;\cap W'=\emptyset \}$;

それ以外のケースでは $\nu (W)=+\infty$ (任意の濃度より大きい) とする。

$W$ が拒否権プレーヤーなしのシンプルゲームであれば、$2\leq \nu (W)\leq \#N$ となることは簡単にしめせる。

有限人のばあいの例 ($N=\{1,\ldots ,n\}$) (Austen-Smith and Banks (1999), Lemma 3.2 を参照). 以下で $W$ は単調でプロパーとする．

• $W$ が拒否権プレーヤーなしの強いシンプルゲームなら、$\nu (W)=3$ である。
• $W$ が過半数ゲーム (半分を超える個人をふくむ提携を勝利提携とするシンプルゲーム) なら、$n\neq 4$ のケースでは $\nu (W)=3$ となり、$n=4$ のケースでは $\nu (W)=4$ となる。
• $W$ が $q$-ルール (すなわち $q$ 人以上の個人をふくむ提携を勝利提携とするシンプルゲーム) で、 $n/2<q<n$ のとき、$\nu (W)=[n/(n-q)]$ となる。ただし $[x]$ は $x$ 以上の最小の整数。

たかだか加算個の個人がいるばあいの例 ($N=\{1,2,\ldots \}$). シンプルゲームにかかわる代表的な性質 (単調かどうか、プロパーかどうか、強いかどうか、拒否権プレーヤーなしかどうか、有限かどうか) がその中村ナンバーにあたえる制限については、Kumabe and Mihara (2008) が徹底的に調べ上げている (その結果は以下の表「可能な中村ナンバー」に要約されている)。 特に、アルゴリズムによって「計算可能」で かつ拒否権プレーヤーをもたないシンプルゲームが３より大きい中村ナンバーをもつとき、 そのシンプルゲームはプロパーで強いことが分かっている。

可能な中村ナンバー

タイプ	有限ゲーム	無限ゲーム
1111	3	3
1110	+∞	none
1101	≥3	≥3
1100	+∞	+∞
1011	2	2
1010	none	none
1001	2	2
1000	none	none
0111	2	2
0110	none	none
0101	≥2	≥2
0100	+∞	+∞
0011	2	2
0010	none	none
0001	2	2
0000	none	none

非循環的な選好にたいする中村の定理

中村の定理 (Nakamura, 1979, Theorems 2.3 and 2.5). $W$ をシンプルゲームとする。非循環的な選好からなる任意のプロファイル $p$ にたいしてコア $C(W,p)$ が非空となることは、$X$ が有限かつ $\#X<\nu (W)$ となることと同値である。

リマーク

• 中村の定理は、以下に近い形で (コアへの言及なく) 参照されることも多い (e.g., Austen-Smith and Banks, 1999, Theorem 3.2): 非循環的な選好からなる任意のプロファイル $p$ にたいして支配関係 $\succ _{W}^{p}$ が非循環的になることは、任意の有限な $B\subseteq X$ にたいして $\#B<\nu (W)$ となることと同値である (Nakamura 1979, Theorem 3.1)。

• 定理中で「非循環的な選好からなる任意のプロファイル $p$ にたいして」を「否定推移的な (negatively transitive) 選好からなる任意のプロファイル $p$ にたいして」あるいは「線形順序である (すなわち推移的で total) 選好からなる任意のプロファイル $p$ にたいして」と言い換えても、得られたステートメントは正しい。

• 上記定理は ${\mathcal {B}}$-シンプルゲームに拡張できる。 ここで ${\mathcal {B}}$ は、$N$ の部分集合からなる任意のブール代数であり、それに属する要素を「提携」とみなす。${\mathcal {B}}$ の例としては、ルベーグ可測集合の$\sigma$-代数などがある。「${\mathcal {B}}$-シンプルゲーム」とは、${\mathcal {B}}$ の部分族である。選好プロファイルは以下の意味で可測なものに限定するのが適切である: プロファイル $p$ が「可測である」とは、任意の $x,y\in X$ について、$\{i:x\succ _{i}^{p}y\}\in {\mathcal {B}}$ となることである。

サイクルをふくみ得る選好にたいする中村定理の変種

このセクションでは「非循環的な選好」という通常の仮定を捨てることにする。 そのかわり与えられた「アジェンダ」(agenda, 個人のグループが当面直面している「機会集合」) 上で極大要素を持つような選好をここでは考える。 (選好にかんするこの弱い制限は、行動経済学の観点からみても興味深いかもしれない。) ノーテーションを節約するため、ここでは集合 $X$ 自体をアジェンダとみなすことにする。 選択肢 $x\in X$ が選好 $\succ _{i}^{p}$ にかんして「極大 (要素) である」 (あるいは $\succ _{i}^{p}$ が「極大要素 $x$ を持つ」) とは、 $y\succ _{i}^{p}x$ となるような $y\in X$が存在しないことである。 もし選好が選択肢全体の集合上で非循環的であれば、その選好は任意の「有限」部分集合 $X$ 上で極大値を持つ。

中村の定理の変種 (variant) を述べる前に、「コア」を強めた解概念を導入しておく。 たとえある提携が存在してそれに属するすべての個人 $i$ が選択肢 $x$ に「不満を持っている」 (各 $i$ がなんらかのべつの選択肢 $y_{i}$ を $x$ より好むの意) としても、 選択肢 $x$ がコア $C(W,p)$ には属してしまうことがある。 次の解概念はそのような選択肢 $x$ を除外するものである:

選択肢 $x\in X$ が「多数不満なきコア」(core without majority dissatisfaction) $C^{+}(W,p)$ に属するとは、任意の $i\in S$ にとって $x$ が極大でない ($y_{i}\in X$ が存在して $y_{i}\succ _{i}^{p}x$ となる) ような勝利提携 $S\in W$ が存在しないことである。

以下の結果は容易にしめせる: $C^{+}(W,p)$ は各人の選好の極大要素集合だけに依存し、それらの集合のユニオンにふくまれる。 また、任意の選好プロファイル $p$ について、$C^{+}(W,p)\subseteq C(W,p)$ となる。

中村定理の変種 (Kumabe and Mihara, Theorem 2). $W$ をシンプルゲームとする。以下の３つのステートメントは同値である:

1. $\#X<\nu (W)$;
2. 極大要素を持つ選好からなる任意のプロファイル $p$ にたいして多数不満なきコア $C^{+}(W,p)$ が非空となる;
3. 極大要素を持つ選好からなる任意のプロファイル $p$ にたいしてコア $C(W,p)$ が非空となる。

リマーク

• もとの中村の定理と異なり、この変種定理において $X$ が有限であることは、任意のプロファイル $p$ にたいして $C^{+}(W,p)$ あるいは $C(W,p)$ が非空となるための必要条件ではないことに注意。すなわち無限個の選択肢を持つアジェンダ $X$ 上でも、不等式 $\#X<\nu (W)$ さえみたせば、それらコアに属する要素が存在する。

• 定理の 2, 3 中で「極大要素を持つ選好からなる任意のプロファイル $p$ にたいして」を「極大要素をひとつだけ持つ選好からなる任意のプロファイル $p$ にたいして」あるいは「極大要素を持ち線形順序である選好からなる任意のプロファイル $p$ にたいして」と言い換えても、得られたステートメントは正しい (Kumabe and Mihara, Proposition 1)。

• もとの中村の定理と同様、この変種定理は ${\mathcal {B}}$-シンプルゲームに拡張できる。さらにこの定理は「中村ナンバー」の概念を拡張することにより「勝利提携の族」$W'\subseteq {\mathcal {B}}'$ にも拡張できる (ステートメント 1, 2 が同値で、それらから 3 が導ける)。

関連項目

• アローの不可能性定理
• 多数決
• 投票の逆理