中村数

協力ゲーム理論と社会的選択理論において、中村数は投票ルールなどの選好集約ルール（集団決定ルール）の合理性の度合いを測定する。これは集約ルールが明確に定義された選択をどの程度生み出せるかを示す指標である。

• 選択できる代替案（候補、オプション）の数がこの数より少ない場合、問題のルールは問題なく「最良」の代替案を識別します。

対照的に、

• 選択肢の数がこの数以上である場合、投票パラドックス（社会的に好まれる選択肢 が選択肢 、 、 など、生成されるサイクル）が発生するため、ルールは、何らかの投票パターン（つまり、個人の好みの何らかのプロファイル（タプル） ）に対して「最善の」選択肢を特定できません。${\displaystyle a}$${\displaystyle b}$${\displaystyle b}$${\displaystyle c}$${\displaystyle c}$${\displaystyle a}$

ルールの中村数が大きいほど、そのルールが合理的に扱える選択肢の数が多くなります。例えば、多数決ルールの中村数は 3 なので (投票者が 4 人いる場合を除く)、そのルールは 2 つまでの選択肢を合理的に扱えます (パラドックスは発生しません)。この数は、集団選択の合理性は選択肢の数に大きく依存するという上記の事実を証明した日本のゲーム理論家、中村健次郎 (1947–1979) にちなんで名付けられました。 [ ^1]

ナカムラ数の正確な定義を紹介するために、ナカムラ数が割り当てられる「ゲーム」（問題のルールの基盤となる）の例を示します。個体の集合が個体 1、2、3、4、5 で構成されているとします。多数決の背後には、少なくとも 3 人のメンバーを持つ次の（「決定的な」）連合（個体のサブセット）の集合があります。

{ {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 人) が選択肢 y よりも選択肢 x を好む場合、社会 (上記の例では 5 人の個人) は同じ順位 (社会的選好) を採用します。

単純ゲームのナカムラ数は、交差が空である勝利連合の最小数として定義されます。(この数の勝利連合を交差させることで、空集合を得られる場合があります。しかし、この数より少ない数の交差では、空集合を得ることはできません。) たとえば、上記の単純ゲームの中村数は 3 です。これは、任意の 2 つの勝利連合の交差には少なくとも 1 つの個体が含まれますが、次の 3 つの勝利連合の交差は空であるためです: 、、。${\displaystyle \{1,2,3\}}$${\displaystyle \{4,5,1\}}$${\displaystyle \{2,3,4\}}$

中村の定理(1979 ^[2] ) は、すべての個人選好プロファイルに対して、単純ゲームが空でない「コア」(社会的に「最良」な選択肢の集合) を持つための次の必要条件 (選択肢の集合が有限で ある場合も十分条件) を示しています。選択肢の数は、単純ゲームの中村数より少ないです。ここで、選好プロファイルに関する単純ゲームのコアは 、勝利連合内のすべての個人が好む選択肢が存在しないすべての選択肢の集合、つまり社会的選好の最大要素の集合です。上記の多数決ゲームの例では、定理は、3 つ以上の選択肢がある場合、あるプロファイルに対してコアが空になる (どの選択肢も「最良」とは見なされない) ことを意味します。 ${\displaystyle x}$${\displaystyle y}$${\displaystyle x}$

中村の定理には、(i) 非巡回選好のすべてのプロファイル、(ii)推移的選好のすべてのプロファイル、 (iii)線形順序のすべてのプロファイルについて、コアが空でないための条件を与える変種が存在する。合理性の弱い要件である非巡回性を排除する異なる種類の変種 (Kumabe and Mihara, 2011 ^[3] )もある。この変種は、最大要素を持つ選好のすべてのプロファイルについて、コアが空でないための条件を与える。

選択肢の順位付けについては、社会選択理論において「アローの不可能性定理」と呼ばれる非常によく知られた結果があり、これは、個人のグループが3つ以上の選択肢を順位付けすることの難しさを指摘している。選択肢の集合から選択する場合（順位付けするのではなく）、中村の定理の方がより適切である。^[5] 中村数はどのくらいの大きさになり得るかは興味深い問題である。（有限または）アルゴリズム的に計算可能な単純なゲームで、拒否権を持つプレイヤー（すべての勝利連合に属する個人）がいないゲームが中村数を3より大きくするには、そのゲームは非強でなければならないことが示されている。^{[6]これは、}負けている（つまり、勝っていない）連合 があり、その補完も負けていることを意味する。これは、3つ以上の選択肢の集合について、コアが厳密に順位付けできない選択肢をいくつか含むことができる場合にのみ、コアが空でないことが保証されることを意味する。^[8]

を（有限または無限の）空でない個体の集合とします。 のサブセットは連合と呼ばれます。単純ゲーム（投票ゲーム）は連合の集まりです。 （同様に、これは各連合に 1 または 0 を割り当てる連合ゲームです。） は空でなく、空集合を含まないものとします。 に属する連合はに勝ち、その他はに負けます。 およびが 意味する場合、単純ゲームは単調です。 が意味する場合、単純ゲームは適切です。 が意味する場合、単純ゲームは強いです。拒否権プレイヤー（拒否者）は、すべての勝利連合 に属する個体です。単純ゲームに拒否権プレイヤーがいない場合、単純ゲームは弱くありません。 が有限集合（キャリアと呼ばれる）があり、すべての連合 について の場合に限り、 が成り立つ場合、単純ゲームは有限です。 ${\displaystyle N}$${\displaystyle N}$${\displaystyle W}$${\displaystyle W}$${\displaystyle W}$${\displaystyle W}$${\displaystyle S\in W}$${\displaystyle S\subseteq T}$${\displaystyle T\in W}$${\displaystyle S\in W}$${\displaystyle N\setminus S\notin W}$${\displaystyle S\notin W}$${\displaystyle N\setminus S\in W}$${\displaystyle T\subseteq N}$${\displaystyle S}$${\displaystyle S\in W}$${\displaystyle S\cap T\in W}$

を（有限または無限の）選択肢の集合とし、その基数（要素の数） は少なくとも 2 であるとします。（厳密な）選好は上の非対称関係です。（「が よりも好まれる」と読みます）場合、 となります。任意の有限個の選択肢 について、、、…、のときはいつでもが成り立つ場合、選好は非巡回（循環 を含まない）であるといいます。非巡回関係は非対称であるため、選好であることに注意してください。 ${\displaystyle X}$${\displaystyle \#X}$${\displaystyle \succ }$${\displaystyle X}$${\displaystyle x\succ y}$${\displaystyle x}$${\displaystyle y}$${\displaystyle y\not \succ x}$${\displaystyle \succ }$${\displaystyle x_{1},\ldots ,x_{m}}$${\displaystyle x_{1}\succ x_{2}}$${\displaystyle x_{2}\succ x_{3}}$${\displaystyle x_{m-1}\succ x_{m}}$${\displaystyle x_{m}\not \succ x_{1}}$

プロファイルは個人の好みのリストです。ここでは、個人がプロファイル の代替案を好むことを意味します。 ${\displaystyle p=(\succ _{i}^{p})_{i\in N}}$${\displaystyle \succ _{i}^{p}}$${\displaystyle x\succ _{i}^{p}y}$${\displaystyle i}$${\displaystyle x}$${\displaystyle y}$${\displaystyle p}$

順序選好を持つ単純ゲームは、単純ゲームとプロファイルからなるペアです。 が与えられた場合、に対する優位性（社会的選好）関係は、すべて を 満たす勝利連合が存在する場合に限り、によって定義されます。の核は、 によって優位にされない選択肢の集合（に関する の最大要素の集合）です。 ${\displaystyle (W,p)}$${\displaystyle W}$${\displaystyle p}$${\displaystyle (W,p)}$${\displaystyle \succ _{W}^{p}}$${\displaystyle X}$${\displaystyle x\succ _{W}^{p}y}$${\displaystyle S\in W}$${\displaystyle x\succ _{i}^{p}y}$${\displaystyle i\in S}$ ${\displaystyle C(W,p)}$${\displaystyle (W,p)}$${\displaystyle \succ _{W}^{p}}$${\displaystyle X}$${\displaystyle \succ _{W}^{p}}$

${\displaystyle x\in C(W,p)}$が存在しない場合に限ります。${\displaystyle y\in X}$${\displaystyle y\succ _{W}^{p}x}$

単純ゲームにおける中村数は 、空の交差点を持つ勝利連合の最小集合の大きさ（基数）である。^[9]${\displaystyle \nu (W)}$${\displaystyle W}$

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

（拒否権を持つプレイヤーがいない）の場合； ^[2] それ以外の場合（どの基数よりも大きい）。 ${\displaystyle \cap W=\cap _{S\in W}S=\emptyset }$${\displaystyle \nu (W)=+\infty }$

が拒否権を持つプレイヤーのいない単純なゲームである場合、 であることは簡単に証明できます。 ${\displaystyle W}$${\displaystyle 2\leq \nu (W)\leq \#N}$

有限個の個体（）の例（Austen-SmithとBanks（1999）、補題3.2 ^[4]を参照）。を単調かつ適切な単純なゲームとします。 ${\displaystyle N=\{1,\ldots ,n\}}$${\displaystyle W}$

• が強く、拒否権を持つプレイヤーがいない場合は、 となります。${\displaystyle W}$${\displaystyle \nu (W)=3}$
• が多数決ゲームである場合（つまり、連合が勝利するのは、その連合が半数以上の個人で構成されている場合のみ）、 の場合、の場合。${\displaystyle W}$${\displaystyle \nu (W)=3}$${\displaystyle n\neq 4}$${\displaystyle \nu (W)=4}$${\displaystyle n=4}$
• が-ルール（つまり、連合が勝利するのは、少なくとも個人から構成されている場合のみ）で である場合、 となり、 は以上の最小の整数になります。${\displaystyle W}$${\displaystyle q}$${\displaystyle q}$${\displaystyle n/2<q<n}$${\displaystyle \nu (W)=[n/(n-q)]}$${\displaystyle [x]}$${\displaystyle x}$

最大で可算個数の個体 ( ) の場合の例。Kumabe と Mihara (2008) は、単純なゲームのさまざまな特性 (単調性、適切性、強さ、非弱さ、有限性) がナカムラ数に課す制約を包括的に研究しています (以下の表「可能なナカムラ数」に結果をまとめています)。特に、彼らは、拒否権を持つプレイヤーがいないアルゴリズム的に計算可能な単純なゲーム^[10] が、適切かつ非強い場合にのみ、ナカムラ数が 3 より大きいことを示しています。^[6]${\displaystyle N=\{1,2,\ldots \}}$

中村の定理（中村、1979、定理2.3および2.5 ^[2]）。を単純なゲームとします。が有限であり、 である場合に限り、コアは非巡回選好のすべてのプロファイルに対して空でなくなります。 ${\displaystyle W}$${\displaystyle C(W,p)}$${\displaystyle p}$${\displaystyle X}$${\displaystyle \#X<\nu (W)}$

備考

• 中村の定理は、核心部分を参照せずに、次のような形で引用されることが多い（例えば、Austen-Smith and Banks, 1999、定理3.2 ^[4]）。優越関係が非循環的選好のすべてのプロファイルに対して非循環的であるためには、すべての有限に対してである必要がある（中村 1979、定理3.1 ^[2]）。${\displaystyle \succ _{W}^{p}}$${\displaystyle p}$${\displaystyle \#B<\nu (W)}$${\displaystyle B\subseteq X}$
• この定理の記述は、「非循環的選好のすべてのプロファイルについて」を「負の推移的選好のすべてのプロファイルについて」または「線形順序付けされた（すなわち推移的かつ総和的な）選好のすべてのプロファイルについて」に置き換えても有効である。^[12]${\displaystyle p}$${\displaystyle p}$${\displaystyle p}$

• この定理は -単純ゲームに拡張できる。ここで、連合のコレクションは、ルベーグ可測集合の -代数のような、の部分集合の任意のブール代数である。 -単純ゲームは の部分コレクションである。プロファイルは適切に可測なものに制限される。プロファイルが可測であるとは、すべての に対してが成り立つ場合である。^[3]${\displaystyle {\mathcal {B}}}$${\displaystyle {\mathcal {B}}}$${\displaystyle N}$${\displaystyle \sigma }$${\displaystyle {\mathcal {B}}}$${\displaystyle {\mathcal {B}}}$${\displaystyle p}$${\displaystyle x,y\in X}$${\displaystyle \{i:x\succ _{i}^{p}y\}\in {\mathcal {B}}}$

このセクションでは、非循環的な選好という通常の仮定を捨てます。代わりに、選好を、ある基本的な選択肢の集合のサブセットである、与えられたアジェンダ（個人のグループが直面する機会の集合）上で最大要素を持つものに制限します。（選好に対するこの弱い制限は、行動経済学の観点からは興味深いかもしれません。）したがって、ここでは をアジェンダとして考えるのが良いでしょう。選択肢がに関して最大​​要素である （つまり、最大要素を持つ）のは、となるような が存在しないときです。選好が基本的な選択肢の集合上で非循環的である場合、それはすべての有限のサブセット上で最大要素を持ちます。 ${\displaystyle X}$${\displaystyle x\in X}$${\displaystyle \succ _{i}^{p}}$${\displaystyle \succ _{i}^{p}}$${\displaystyle x}$${\displaystyle y\in X}$${\displaystyle y\succ _{i}^{p}x}$${\displaystyle X}$

中村の定理の変形を述べる前に、コアの強化を導入する。 に「満足していない」 （つまり、それぞれがよりもを好む）個人の勝利連合があったとしても、代替案がコアに存在する可能性がある。次の解は、そのような を排除する：^[3]${\displaystyle x}$${\displaystyle C(W,p)}$${\displaystyle i}$${\displaystyle x}$${\displaystyle i}$${\displaystyle y_{i}}$${\displaystyle x}$${\displaystyle x}$

すべての に対して が最大でない（何らかの満足する が存在する）ような勝利連合が存在しない場合には、多数派の不満なしに代替案がコアに存在します。${\displaystyle x\in X}$ ${\displaystyle C^{+}(W,p)}$ ${\displaystyle S\in W}$${\displaystyle i\in S}$${\displaystyle x}$${\displaystyle y_{i}\in X}$${\displaystyle y_{i}\succ _{i}^{p}x}$

が各個体の最大要素の集合にのみ依存し、そのような集合の和集合に含まれることは簡単に証明できます。さらに、各プロファイル に対して、 が成り立ちます。 ${\displaystyle C^{+}(W,p)}$${\displaystyle p}$${\displaystyle C^{+}(W,p)\subseteq C(W,p)}$

中村の定理（隈部・三原、2011、定理2 ^[3]）の変形。を単純なゲームとする。このとき、次の3つのステートメントは同等である。 ${\displaystyle W}$

1. ${\displaystyle \#X<\nu (W)}$;
2. 最大要素を持つすべての選好プロファイルに対して、多数派の不満のないコアは空ではない。${\displaystyle C^{+}(W,p)}$${\displaystyle p}$
3. 最大要素を持つすべての選好プロファイルのコアは空ではありません。${\displaystyle C(W,p)}$${\displaystyle p}$

備考

• 中村の元の定理とは異なり、有限であることは、すべてのプロファイルにとって空でないことの必要条件ではありません。アジェンダに無限の選択肢がある場合でも、不等式が満たされている限り、適切なプロファイルのコアに要素が存在します。${\displaystyle X}$${\displaystyle C^{+}(W,p)}$${\displaystyle C(W,p)}$${\displaystyle p}$${\displaystyle X}$${\displaystyle \#X<\nu (W)}$
• 定理の記述は、記述 2 と 3 の「最大要素を持つすべての選好プロファイルについて」を「正確に 1 つの最大要素を持つすべての選好プロファイルについて」または「最大要素を持つ線形順序付けされたすべての選好プロファイルについて」に置き換えても有効です (Kumabe and Mihara、2011、命題 1)。${\displaystyle p}$${\displaystyle p}$${\displaystyle p}$
• 中村の非巡回選好定理と同様に、この定理は -単純ゲームに拡張できる。この定理は、中村数の概念を拡張することで、勝利集合の集合にさらに拡張できる（1と2は同値であり、3を意味する）。^[13]${\displaystyle {\mathcal {B}}}$ ${\displaystyle W'\subseteq {\mathcal {B}}'}$

• ギバード・サタースウェイトの定理
• メイの定理
• 投票のパラドックス