ギバード・サタースウェイトの定理

ギバード・サッタースウェイト定理は、投票理論における定理である。この定理は、1961年に哲学者マイケル・ダメットと数学者ロビン・ファーカーソンによって最初に推測され^[1]、その後、1973年に哲学者アラン・ギバード^[2]と1975年に経済学者マーク・サッタースウェイトによって独立に証明された^[3]。この定理は、単一の勝者を選ぶ決定論的順序選挙システムを扱っており、この形式のすべての投票ルールについて、次の3つのうち少なくとも1つが成立する必要があることを示しています。

1. ルールは独裁的である、つまり勝者を選ぶことができる著名な投票者が存在する、または
2. このルールは、起こり得る結果を2つの選択肢のみに制限します。
3. このルールは単純ではありません。つまり、常に最善の戦略（他の投票者の好みや行動に依存しない戦略）は存在しません。

ギバードの定理の証明はより一般的であり、基数投票などの順序付けられない可能性のある集団決定のプロセスをカバーしています。^{[注 1]}ギバードの 1978 年の定理とヒルランドの定理はさらに一般的であり、結果が部分的に偶然に依存する可能性のある非決定論的プロセスにこれらの結果を拡張します。ダガン-シュワルツの定理は、これらの結果を複数勝者選挙システムに拡張します。

アリス、ボブ、キャロルという 3 人の有権者が、、、およびという4 人の候補者の中から勝者を選びたいとします。彼らはボルダ カウントを使用しているものとします。つまり、各有権者は候補者に対する自分の優先順位を伝えます。各投票では、最上位の候補者に 3 ポイント、2 位の候補者に 2 ポイント、3 位の候補者に 1 ポイント、最後の候補者に 0 ポイントが割り当てられます。すべての投票が集計されると、最も多くのポイントを獲得した候補者が勝者と宣言されます。 ${\displaystyle a}$${\displaystyle b}$${\displaystyle c}$${\displaystyle d}$

彼らの好みは次の通りであると仮定します。

有権者が誠実に投票した場合、得点は次のようになります。したがって、候補者は7 ポイントで当選します。 ${\displaystyle (a:3,b:6,c:7,d:2)}$${\displaystyle c}$

しかし、アリスは戦略的に投票して結果を変えることができます。彼女が投票用紙を修正して、次の状況を作り出すと仮定します。

アリスは、戦略的に候補者 をアップグレードし、候補者 をダウングレードしました。これで、スコアは次のようになります。したがって、が選出されます。アリスは、 よりもの結果を望んでいるため、投票用紙の修正に満足しています。これは、アリスが誠実に投票した場合に得られる結果です。 ${\displaystyle b}$${\displaystyle c}$${\displaystyle (a:2,b:7,c:6,d:3)}$${\displaystyle b}$${\displaystyle b}$${\displaystyle c}$

ボルダカウントは操作可能であると言われています。つまり、誠実な投票が有権者の好みを最大限に守らない状況が存在するのです。

ギバード・サッタースウェイト定理によれば、すべての優先順位投票は、独裁的な権力を持つ著名な投票者がいる場合、または規則によって可能な結果が 2 つの選択肢のみに制限されている場合の 2 つのケースを除いて、操作可能であるとされています。

を選択肢の集合（有限であると仮定）とし、候補者 とも呼ばれます。候補者は必ずしも人物である必要はありません。特定の問題に関する複数の可能な決定である可能性もあります。を投票者の集合で表します。を 上の厳密な弱順序の集合とします。この集合の要素は投票者の選好を表すことができ、投票者はいくつかの選択肢の順序付けについては無関心である可能性があります。投票ルールは関数 です。その入力は選好のプロファイルであり、勝利した候補者のアイデンティティーを生成します。 ${\displaystyle {\mathcal {A}}}$${\displaystyle {\mathcal {N}}=\{1,\ldots ,n\}}$${\displaystyle {\mathcal {P}}}$${\displaystyle {\mathcal {A}}}$${\displaystyle f:{\mathcal {P}}^{n}\to {\mathcal {A}}}$${\displaystyle (P_{1},\ldots ,P_{n})\in {\mathcal {P}}^{n}}$

投票者が自分の投票用紙を別の投票用紙に置き換えることで、（ の意味で） 自分が好む結果を得ることができるプロファイルが存在する場合にのみ、は操作可能であると言えます。${\displaystyle f}$${\displaystyle (P_{1},\ldots ,P_{n})\in {\mathcal {P}}^{n}}$${\displaystyle i}$${\displaystyle P_{i}}$${\displaystyle P_{i}'}$${\displaystyle P_{i}}$

を のイメージ、つまり選挙の可能な結果の集合で表します。たとえば、の濃度が 3 以上である 場合に限り、 には少なくとも 3 つの可能な結果があると言えます。${\displaystyle f({\mathcal {P}}^{n})}$${\displaystyle f}$${\displaystyle f}$${\displaystyle f({\mathcal {P}}^{n})}$

独裁的であるとは、他の有権者の好みに関係なく、可能な結果の中で常にその有権者が最も好む選択肢が勝利するという意味において、独裁者である有権者が存在する場合に限ります。独裁者が可能な結果の中で同様に最も好まれる選択肢をいくつか持っている場合、勝利する選択肢は単にそれらのうちの 1 つになります。 ${\displaystyle f}$${\displaystyle i}$

ギバード・サッタースウェイトの定理の条件が適用されない場合、この定理に対するさまざまな「反例」が存在します。

スコア投票によって実施される 3 人の候補者による選挙について考えてみましょう。投票者にとって、最も優れた候補者に可能な限り最高のスコアを与え、最も劣る候補者に可能な限り最低のスコアを与えることが常に最適です。すると、投票者が中間の候補者にどのスコアを割り当てたとしても、それは常に (厳密には) 最初のスコアと最後のスコアの間になります。これは、投票者のスコア投票がその投票者の正直な順位付けと弱く一致することを意味します。ただし、ギバードの定理で示されるように、実際の最適スコアは他の投票によって左右される可能性があります。

連続独裁制は次のように定義されます。投票者 1 に唯一最も好かれている候補者がいる場合、この候補者が選出されます。そうでない場合、可能な結果は最も好かれている候補者に限定され、他の候補者は排除されます。次に、投票者 2 の投票が検討されます。排除されていない候補者の中に唯一最も好かれている候補者がいる場合、この候補者が選出されます。そうでない場合、可能な結果のリストが再び縮小されます。すべての投票が検討された後も、排除されていない候補者がまだ複数いる場合は、任意の同点決着ルールが使用されます。

この投票ルールは操作不可能です。投票者は常に自分の誠実な好みを伝える方が得策です。また、このルールは独裁的で、その独裁者は投票者 1 です。つまり、勝利する選択肢は常にその投票者にとって最も好まれる選択肢であり、最も好まれる選択肢が複数ある場合はその中から選ばれます。

結果が 2 つしかない場合、投票ルールは独裁的ではなくとも操作不可能である可能性があります。たとえば、単純多数決の場合です。各投票者は、最有力候補に 1 ポイント、もう 1 つに 0 ポイントを割り当て、ポイントが最も多い候補が勝者と宣言されます。(両方の候補が同じポイント数に達した場合、結果が 勝つなど、恣意的だが決定的な方法で同点が決定されます。) この投票ルールは、投票者は常に自分の誠実な好みを伝える方が有利であるため、操作不可能であり、明らかに独裁的ではありません。他の多くのルールは、操作可能でも独裁的でもありません。たとえば、選択肢が3 分の 2 の票を獲得した場合は勝ち、そうでない場合は勝つと仮定します。 ${\displaystyle a}$${\displaystyle a}$${\displaystyle b}$

ここで、仮定により、投票者が 2 人の候補者の間で無関心ではいられない場合について考えます。を 上の厳密な全順序の集合で表し、厳密な投票規則を関数 として定義します。可能な結果、操作可能、独裁的の定義は、このフレームワークに自然に適応します。 ${\displaystyle {\mathcal {L}}}$${\displaystyle {\mathcal {A}}}$${\displaystyle f:{\mathcal {L}}^{n}\to {\mathcal {A}}}$

厳格な投票ルールの場合、ギバード・サッタースウェイト定理の逆が成り立ちます。実際、厳格な投票ルールが独裁的であるのは、常に独裁者が最も好む候補者を可能な結果の中から選択する場合のみです。特に、他の投票者の投票には依存しません。結果として、操作できません。独裁者は誠実な投票によって完全に守られ、他の投票者は結果に影響を与えないため、誠実な投票から逸脱する動機がありません。したがって、次の同値が得られます。

定理でも系でも、どの選択肢も選出されると仮定する必要はない。少なくとも 3 つの選択肢が勝つ可能性がある、つまり が投票規則の可能な結果であると仮定するだけである。他の選択肢がいかなる状況でも選出される可能性がある場合もあり、その場合も定理と系は適用される。しかし、系はより一般的でない形式で提示されることもある。^[4]規則に少なくとも 3 つの可能な結果があると仮定する代わりに、 には少なくとも 3 つの要素が含まれており、投票規則は全射、つまりすべての選択肢が可能な結果であると仮定されることがある。^{[5]が全射であるという仮定は、規則が}全員一致 であるという仮定に置き換えられることもある。つまり、すべての投票者が同じ候補者を好めば、その候補者が選出されるに違いないという意味である。^{[6] [7]}${\displaystyle {\mathcal {A}}}$

ギバード・サッタースウェイト定理は、社会ランキング関数に対するアローの不可能性定理を使って証明できます。ある投票ルールがパレート効率的であると仮定した単純化されたケースで証明の概要を示します。 ${\displaystyle f}$

次のようにして、社会的ランキング関数 を構築することができます。 かどうかを判断するために、関数は、 と がすべての投票者の選好のトップに移動する新しい選好を作成します。 ^{[説明が必要]}次に、 がまたは を選択するかどうかを調べます。 ${\displaystyle \operatorname {Rank} }$${\displaystyle a\prec b}$${\displaystyle \operatorname {Rank} }$${\displaystyle a}$${\displaystyle b}$${\displaystyle \operatorname {Rank} }$${\displaystyle f}$${\displaystyle a}$${\displaystyle b}$

が操作不可能かつ独裁的でない場合、無関係な選択肢の独立性を満たすことを証明することは可能である。アローの不可能性定理によれば、3つ以上の選択肢がある場合、そのような関数は独裁制でなければならない。したがって、そのような投票ルールも独裁制でなければならない。^{[8] : 214–215}${\displaystyle f}$${\displaystyle \operatorname {Rank} }$${\displaystyle \operatorname {Rank} }$${\displaystyle f}$

その後の著者らは証明の別の変種を開発した。^{[5] [6] [7] [9] [10] [11] [12] [13] [14] [過剰な引用]}

投票の戦略的側面は、社会選択理論の先駆者であるルイス・キャロルとしても知られるチャールズ・ドジソンによって1876年にすでに指摘されていました。彼の（特定の投票システムに関する）引用は、ダンカン・ブラックによって有名になりました：^[15]

この投票の原則により、選挙は選挙民の希望を真に試すものというよりは、むしろ技能を競うゲームのようなものになります。

1950年代、ロビン・ファーカーソンは投票理論に関する影響力のある論文を発表しました。^[16]マイケル・ダメットとの共著論文^[17]で、彼は少なくとも3つの結果を伴う決定論的な投票ルールは決して単純な戦略的投票ではないと推測しています。^{[18]この推測は後に}アラン・ギバードとマーク・サッタースウェイトによって独立に証明されました。1973年の論文で、ギバードは1951年のアローの不可能性定理を利用して、現在ギバードの定理として知られている結果を証明しました。^[2]サッタースウェイトは独立して1973年の博士論文で同じ結果を証明し、1975年の論文でそれを発表しました。^[3]この証明もアローの不可能性定理に基づいていますが、ギバードの定理によって与えられたより一般的なバージョンは含まれていません。

ギバードの定理は、順序的ではない可能性のある集団選択のプロセス、つまり、投票者の行動が候補者に対する優先順位を伝えることではない可能性のあるプロセスを扱います。ギバードの 1978 年の定理とヒルランドの定理は、これらの結果を非決定論的なメカニズムに拡張します。つまり、結果は投票に依存するだけでなく、偶然の要素も含まれる可能性があります。

ダガン・シュワルツの定理は、複数の勝者を選ぶ決定論的な投票ルールを扱うことで、この結果を別の方向に拡張します。^[19]

ギバード・サッタースウェイト定理は、一般的には投票システムに関する結果として提示されるが、より広範な意思決定ルールを扱うメカニズムデザイン の重要な結果としても見ることができる。ノアム・ニサンはこの関係を次のように説明している。^{[8] : 215}

GS 定理は、インセンティブに適合した社会的選択関数を設計するあらゆる希望を打ち砕くように思われます。メカニズム設計の全分野は、モデルにさまざまな修正を加えることで、この不可能な結果から逃れようと試みています。

これらの「脱出ルート」の主なアイデアは、アローの不可能定理からの脱出ルートと同様に、順位付け投票よりも幅広いメカニズムのクラスを可能にすることです。

• アローの不可能性定理
• コンドルセサイクル
• ダガン・シュワルツの定理
• ギバードの定理
• 順位投票
• 戦略的投票