ギバードの定理

ギバードの定理は、メカニズム設計と社会的選択理論の分野において、哲学者アラン・ギバードによって1973年に証明された結果である。^[1]それは、集団的意思決定の決定論的プロセスでは、少なくとも次の3つの特性のうち1つが満たされなければならないことを述べている。

1. このプロセスは独裁的であり、つまり、投票者が一人いて、その投票によって結果が決まるのです。
2. このプロセスでは、可能な結果が 2 つのオプションのみに制限されます。
3. このプロセスは単純ではありません。有権者にとって最適な投票には「戦略的な投票が必要」であり、つまり、他の有権者の投票についての信念に依存します。

この定理の帰結として、投票ルールに関するギバード・サッタースウェイト定理が成立する。2つの定理の主な違いは、ギバード・サッタースウェイト定理は順位付け投票にのみ適用されることである。より広い適用範囲を持つため、ギバードの定理は、投票者が候補者の順位付けを逆転させる必要があるかどうかについては何も主張しておらず、最適な投票は他の投票者の投票に依存するということだけを主張している。^{[注 1]}

ギバードの定理はより一般的で、順序付けられない可能性のある集団的意思決定のプロセスを考慮します。たとえば、投票者が候補者に成績を付けたり、その他の方法で評価したりする投票システム (基数投票) などです。ギバードの定理は、アローの不可能性定理を使用して証明できます。^{[引用が必要]}

ギバードの定理自体は、ギバードの1978年の定理^[3]とヒルランドの定理^[4]によって一般化されており、これらの定理は、結果がエージェントの行動に依存するだけでなく偶然の要素も含む可能性がある非決定論的プロセスにこれらの結果を拡張します。

ギバードの定理は、集団的決定の結果、正確に 1 人の勝者が生まれることを前提としており、複数勝者投票には適用されません。複数勝者投票に関する同様の結果は、ダガン・シュワルツの定理です。

、およびの3 つの選択肢からオプションを選択したい有権者、 、 について考えます。 彼らが承認投票を使用すると仮定します。つまり、各有権者は各候補者にグレード 1 (承認) または 0 (承認保留) を割り当てます。 たとえば、は公認投票です。つまり、投票者は候補者 を承認し、候補者 を承認しないことを意味します。 投票が集められたら、最も高い合計グレードを持つ候補者が勝者と宣言されます。 候補者間の同点の場合はアルファベット順で決定されます。たとえば、候補者と が同点の場合は、 が勝ちます。 ${\displaystyle 1}$${\displaystyle 2}$${\displaystyle 3}$${\displaystyle a}$${\displaystyle b}$${\displaystyle c}$${\displaystyle (1,1,0)}$${\displaystyle a}$${\displaystyle b}$${\displaystyle c}$${\displaystyle a}$${\displaystyle b}$${\displaystyle a}$

有権者が代替案 を好むと仮定すると、 となります。どの投票が彼女の意見を最もよく支持するでしょうか? たとえば、次の 2 つの状況を考えてみましょう。 ${\displaystyle 1}$${\displaystyle a}$${\displaystyle b}$${\displaystyle c}$

• 他の 2 人の有権者がそれぞれ と に投票した場合、有権者は自分の好みの選択肢が選ばれる投票を 1 つだけ持つことになります 。${\displaystyle (0,1,1)}$${\displaystyle (1,1,1)}$${\displaystyle 1}$${\displaystyle a}$${\displaystyle (1,0,0)}$
• しかし、代わりに他の 2 人の投票者がそれぞれ と に投票したと仮定すると、は を勝利に導くため、は投票すべきではなく、 は を勝利に導く に投票すべきです。${\displaystyle (0,0,1)}$${\displaystyle (0,1,1)}$${\displaystyle 1}$${\displaystyle (1,0,0)}$${\displaystyle c}$${\displaystyle (1,1,0)}$${\displaystyle b}$

まとめると、有権者は戦略的な投票のジレンマに直面します。他の有権者が投じる票に依存するか、自分の意見を最もよく擁護する票になるかです。したがって、承認投票は戦略性がないと言えます。有権者が自分の好みを特定したら、あらゆる状況で自分の意見を最もよく擁護する投票用紙を自由に使えるわけではありません。他の有権者がどのように投票するつもりなのかを判断するために、他の有権者をスパイするなど、戦略的に行動する必要があります。 ${\displaystyle 1}$${\displaystyle (1,0,0)}$${\displaystyle (1,1,0)}$

ギバードの定理によれば、集団的意思決定の決定論的プロセスは、独裁的な権力を持つ著名なエージェントが存在する場合 (一方的)、またはプロセスによって結果が 2 つの選択肢のみに制限される場合 (二重) の 2 つの場合を除いて、戦略的証明にはなり得ません。

を選択肢の集合 とします。これは、投票の文脈では候補者とも呼ばれます。 をエージェントの集合 とします。これは、適用の文脈に応じてプレーヤーまたは投票者とも呼ばれます。各エージェント について、をエージェント が利用できる戦略を表す集合 とします。 は有限であると仮定します。を、戦略 の各 -組に選択肢をマップする関数 とします。 この関数はゲーム形式と呼ばれます。言い換えると、ゲーム形式は基本的にnプレーヤー ゲームのように定義されますが、可能な結果に関連付けられた効用はありません。つまり、ゲーム形式は手順のみを記述し、各エージェントが各結果から得る利益を 事前に指定しません。${\displaystyle {\mathcal {A}}}$${\displaystyle {\mathcal {N}}=\{1,\ldots ,n\}}$${\displaystyle i}$${\displaystyle {\mathcal {S}}_{i}}$${\displaystyle i}$${\displaystyle {\mathcal {S}}_{i}}$${\displaystyle g}$${\displaystyle n}$${\displaystyle (s_{1},\ldots ,s_{n})\in {\mathcal {S}}_{1}\times \cdots \times {\mathcal {S}}_{n}}$${\displaystyle g}$

任意のエージェント について、および選択肢上の任意の厳密な弱い順序について、エージェントが好み を持つときにエージェントにとって優位な戦略が存在する場合、は戦略証明性がある（元々は単純明快 と呼ばれていた）と言います。つまり、 とは異なる別の戦略 が（ の意味で）厳密により良い結果につながるような、他のエージェントの戦略のプロファイルは存在しません。この特性は民主的な意思決定プロセスにとって望ましいものです。つまり、エージェントが自分の好み を特定したら、他のエージェントが選択した戦略を知ったり推測したりする必要なく、自分の好みを最もよく守る戦略を選択できるということです。 ${\displaystyle g}$${\displaystyle i}$ ${\displaystyle P_{i}}$${\displaystyle s_{i}^{*}(P_{i})}$${\displaystyle i}$${\displaystyle P_{i}}$${\displaystyle s_{i}}$${\displaystyle s_{i}^{*}(P_{i})}$${\displaystyle P_{i}}$${\displaystyle i}$${\displaystyle P_{i}}$${\displaystyle s_{i}^{*}(P_{i})}$

および を の値域、つまりゲーム形式の可能な結果の集合で表します。たとえば、の濃度が3 以上である場合に限り、 には少なくとも 3 つの可能な結果があると言えます。戦略集合は有限であるため、も有限です。したがって、選択肢の集合が有限であると仮定されない場合でも、可能な結果のサブセットは必然的に有限になります。 ${\displaystyle {\mathcal {S}}={\mathcal {S}}_{1}\times \cdots \times {\mathcal {S}}_{n}}$${\displaystyle g({\mathcal {S}})}$${\displaystyle g}$${\displaystyle g}$${\displaystyle g({\mathcal {S}})}$${\displaystyle g({\mathcal {S}})}$${\displaystyle {\mathcal {A}}}$${\displaystyle g({\mathcal {S}})}$

独裁者であるエージェントが存在する場合、 は独裁的であるといいます。独裁的であるとは、あらゆる可能な結果 に対して、エージェントは、他のエージェントがどのような戦略を選択しても、結果 となることを保証する戦略を自由に使用できるという意味です。 ${\displaystyle g}$${\displaystyle i}$${\displaystyle a\in g({\mathcal {S}})}$${\displaystyle i}$${\displaystyle a}$

各投票者は候補者に対して厳密な弱い順序を伝えるものと仮定します。連続独裁制は次のように定義されます。投票者 1 が最も好む候補者を 1 人だけ持つ場合、その候補者が選出されます。そうでない場合、可能な結果は投票者 1 の同様に好む候補者に限定され、他の候補者は排除されます。次に投票者 2 の投票が調べられます。排除されなかった候補者の中で投票者 2 が最も好む候補者を 1 人だけ持つ場合、その候補者が選出されます。そうでない場合、可能な結果のリストが再び縮小されます。すべての投票が調べられた後も、排除されなかった候補者がまだ複数いる場合は、任意の同点決着ルールが使用されます。

このゲーム形式は戦略に依存しません。つまり、投票者の好みが何であれ、投票者は自分の誠実な優先順位を宣言するという支配的な戦略を持っています。また、このゲーム形式は独裁的でもあり、その独裁者は投票者 1 です。投票者が候補者の当選を望む場合、投票者は優先順位を伝えればよく、その優先順位は唯一最も好まれる候補者です。 ${\displaystyle a}$${\displaystyle a}$

可能な結果が 2 つしかない場合、ゲーム形式は独裁的ではなく戦略不可能である可能性があります。たとえば、単純多数決の場合です。各投票者は、2 つの可能な結果のうち、最も好ましい選択肢に投票し、最も多くの票を獲得した選択肢が勝者と宣言されます。このゲーム形式は、最も好ましい選択肢に投票することが常に最適であるため、戦略不可能です (2 つの選択肢に無関心でない限り)。ただし、明らかに独裁的ではありません。他の多くのゲーム形式は、独裁的ではなく戦略不可能です。たとえば、選択肢が3 分の 2 の票を獲得した場合はその選択肢が勝ち、そうでない場合はその選択肢が勝つと仮定します。 ${\displaystyle a}$${\displaystyle b}$

次のゲーム形式を考えてみましょう。投票者 1 は、自分が選んだ候補者に投票することも、棄権することもできます。前者の場合、指定された候補者は自動的に選出されます。それ以外の場合、他の投票者は、ボルダ カウントなどの古典的な投票ルールを使用します。このゲーム形式は、投票者 1 が結果を強制できるため、明らかに独裁的です。ただし、これは戦略不可能ではありません。他の投票者は、通常のボルダ カウントの場合と同じように、戦略的投票の問題に直面します。したがって、ギバードの定理は含意であり、同値ではありません。

ギバードの 1978 年の定理によれば、非決定論的投票法は、片側ルールと二重ルールの混合である場合にのみ戦略不可能である。たとえば、コインを投げて表が出たら独裁者をランダムに選ぶルール、裏が出たら 2 人の候補者の中から 1 組の勝者を選ぶルールは戦略不可能である。非決定論的方法は、決定論的方法の結果を近似しながら戦略不可能であるように考案されている。^{[5] [6]}

• アローの不可能性定理
• ギバード・サタースウェイトの定理