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

この記事ではギバードサタースウェイトの定理の証明を紹介します。

証明は有名な証明であるReny(2001)に従いますが、この記事の特徴として、自分がつまずいた箇所を丁寧に説明するとともに全体像を適宜確認することで独学でも読破できることを目指しています。前提知識は中級レベルのミクロ経済学です。また、先にこちらの記事を読んでいると理解しやすいです：アローの不可能性定理の証明（前提知識あり）。

ギバード・サタースウェイトの定理は、「耐戦略性を満たす（誰にも嘘をつくインセンティブを持たせない）社会的選択関数は必ず独裁的になってしまう」と主張する定理です。

ーーーーーーー
定理の主張

まずはギバード・サタースウェイト（Gibbard-Satterthwaite）の主張を見ていきます。これより先はGS定理と呼ぶことにします。

$A$ を選択肢の集合とします( $3 ≤\ |A| \lt \infty$ )。 $N=\{1,2,\cdots,n\}$ を個人の集合とします( $2 ≤ n \lt \infty$ )。選択肢の集合 $A$ 上のStrict Preference Ordering全体からなる集合を $L$ で表します。個人 $i\in N$ は $A$ 上にstrict preference $\succ_i \in L$ を持っています。各個人の選好を組にした $(\succ_1,\cdots,\succ_n)$ は選好プロファイルと呼ばれ、選好プロファイル全体からなる集合を $L^n$ とします。

ここで社会的選択関数を定義します。

社会的選択関数とは、各選好プロファイルに選択肢を $1$ つ対応させる関数 $f:\ L^n\rightarrow A$ のことである。アローの定理で注目した社会的厚生関数が各選好プロファイルに対して「社会さんの選好」を作るものだったのに対して、社会的選択関数は各選好プロファイルに対して「社会が選ぶ選択肢」を対応させるものであることに注意してください。

なお表記として下付き文字を取った $\succ$ は選好プロファイルを表すのに使います（アローの時とは違うので注意してください）。

$f$ の性質として「耐戦略性」（Strategy-Proofness)を定義します。

定義（耐戦略性）
社会的選択関数 $f:\ L^n\rightarrow A$ が耐戦略性を満たすとは、
任意の $i\in N$ 、任意の $\succ \in L^n$ 、任意の $\succ'_i \in L$ について以下が成り立つことである。

$f(\succ'_i,\succ_{-i})\ne f(\succ)$ ならば $f(\succ) \succ_i f(\succ'_i,\succ_{-i})$ 。

これは感覚を掴むのが難しいです。まず $f(\succ'_i,\succ_{-i})$ と $f(\succ)$ がどちらも選択肢であることを抑えるのが大切です。後者は選好プロファイル $\succ$ を $f$ で飛ばした先の選択肢です（ $f(\succ_i,\succ_{-i})$ と書くこともでき、そちらの方が色々理解しやすくなるかもしれません）。前者は選好プロファイル $(\succ'_i,\succ_{-i})$ を $f$ で飛ばした先の選択肢です（ただし $(\succ'_i,\succ_{-i})$ は、選好プロファイル $\succ$ の $i$ さんの選好だけ $\succ'_i$ に変えた選好プロファイルです）。

定義を少し書き換えてみます。

定義（意味をとりやすく）
社会的選択関数 $f:\ L^n\rightarrow A$ が耐戦略性を満たすとは、
任意の $i\in N$ 、任意の $\succ_i \in L$ 、任意の $\succ_{-i}\in L^{n-1}$ 、任意の $\succ'_i \in L$ について以下が成り立つことである。

$f(\succ'_i,\succ_{-i})\ne f(\succ_i,\succ_{-i})$ ならば $f(\succ_i,\succ_{-i})\succ_i f(\succ'_i,\succ_{-i})$ 。

これで意味が取りやすくなったはずです。その意味は、「すべての個人 $i$ にとって自分の選好 $\succ_i$ がどのようなものであっても、他の個人がどう申告するか（どの $\succ_{-i}$ を申告するか）に関わらず他の選好 $\succ'_i$ を自身の選好として申告するよりも本当の選好を申告した方が得である（仮に嘘をつくことで本当に申告した場合と違う選択肢が選ばれるならばその選択肢よりも本当の申告をしたときに選ばれる選択肢の方が $\succ_i$ において望ましい）」です。

つまり、どの個人も相手がどう申告してくるかに関わらず自分の選好をそのまま申告するのが損にならないという意味です。

社会的選択関数が耐戦略性を満たすときは、特に工夫することなく、「みなさん自身の選好を教えてくださいね。皆さんの申告を信じて $f$ が示す選択肢を選ぶので。」と言ってしまっても各個人は正直に申告してくれると想定できるわけです。耐戦略性が満たされていれば、ナイーブに上のようにすればいいのでとても楽です。非常に強い条件ではありますが満たされていたらとても嬉しい条件です。

次に独裁性を定義します。

定義（独裁性）
社会的選択関数 $f:\ L^n\rightarrow A$ が独裁的であるとは、
ある個人 $i\in N$ が存在して、任意の $a\in A$ に対して、「 $f(\succ)=a$ if and only if $i$ が $a$ をTopに位置付けている」が成り立つことである。このような $i$ さんを独裁者と呼び、独裁者が存在しないとき $f$ は非独裁性を満たすという。

もう少し丁寧に書きます。

定義（丁寧に）
社会的選択関数 $f:\ L^n\rightarrow A$ が独裁的であるとは、
ある個人 $i\in N$ が存在して、任意の $a\in A$ と任意の $\succ \in L^n$ に対して、 $f(\succ)=a$ if and only if $\forall b\in A\setminus\{a\}$ $a\succ_i b$ が成り立つことである。

ではGS定理を見てみます。

GS定理
社会的選択関数 $f$ が耐戦略性を満たし全射であるとする。このとき $f$ は独裁的になる。

全射の定義は一般的な全射の定義そのままで、すべての $a\in A$ に対してある $\succ \in L^n$ が存在して $f(\succ)=a$ が成り立つことです。あまり気にしなくても良い条件です。ただ一応、「全射」を外すとGS定理が成り立たないことを確認しておきましょう。 $A=\{x,y,z\}$ として $N=\{1,2\}$ とします。このとき $f$ としてどんな選好プロファイルに対しても $x$ を対応させる社会的選択関数を考えましょう（当然この $f$ は全射ではない）。この $f$ は耐戦略性を満たしますが（嘘をつくインセンティブが起きようがない）独裁的ではないです。

いまからGS定理を証明したいのですが、ダイレクトに証明するのではなく、 $2$ つの性質を経由して証明することになります。これから使うことになる $２$ つの性質を定義します。最初の条件は「全会一致性」で非常に分かりやすいです。もう $1$ つは「単調性」で少しややこしいのです。

定義（全会一致性）
社会的選択関数 $f:\ L^n\rightarrow A$ が全会一致性を満たすとは、任意の $a\in A$ と任意の選好プロファイル $\succ$ について、すべての個人 $i\in N$ が $\succ_i$ において $a$ を一番上に位置づけているならば $f(\succ)=a$ 。

意味はそのままで、全員にとって $a$ が一番望ましい選好プロファイルを飛ばした先においては $a$ が選ばれることを要請します。

次の単調性には注意が必要です。イメージとしては、 $a$ がある選好プロファイル $\succ$ のもとで選ばれているとして、そこからすべての個人について $a$ が $\succ$ においてよりも上位にくるような $\succ'$ についても $a$ が選ばれるという条件です。ただいまの表現では正確ではないので表記を導入します。 $B(\succ_i,a)$ で $\succ_i$ において $a$ よりも下に位置する選択肢全体からなる集合を表します。例えば、 $A=\{a,b,c,d\}$ で $\succ_i$ が $b\succ_i a \succ_i c \succ_i d$ のとき、 $B(\succ_i,a)=\{c,d\}$ 、 $B(\succ_i,c)=\{d\}$ です。

定義（単調性）
社会的選択関数 $f:\ L^n\rightarrow A$ が単調性を満たすとは、任意の選好プロファイル $\succ,\succ'$ と任意の $a\in A$ 対して、

$f(\succ)=a$ かつ任意の $i\in N$ について $B(\succ_i,a)$ $\subset$ $B(\succ'_i,a)$ ならば $f(\succ')=a$

が成り立つことである。

注意点として $\subset$ は $=$ になることも許容している。

もう少しイメージを掴もうとしてみる。

下図の左の選好プロファイルにおいて $a$ が選ばれるとする。このときに右の選好プロファイルにおいても $a$ が選ばれるというのが単調性の主張である。左を $\succ$ 、右を $\succ'$ としたときに、各個人の選好について $B(\succ_i,a)$ $\subset$ $B(\succ'_i,a)$ を確認してみてください（確認の仕方としてはまず、 $\succ_1$ においては $a$ より下に $b,d$ があるな、そして $b,d$ はちゃんと $\succ'_1$ においても $a$ より下にあるな。次に $\succ_2$ においては、、、のように確認する）。

f:id:KoHarada:20220313092942p:plain
ここまでをまとめると、我々は社会的選択関数について、耐戦略性、独裁性、全会一致性、単調性を定義しました（なお、アローの定理においては社会的厚生関数について全会一致性や独裁性を定義しました。「何についての概念か」が異なるので注意してください）。

これからGS定理の証明に入っていきます。この証明は $2$ つの定理（前半と後半）に分かれています。まずは社会的選択関数が単調性と全会一致性を満たすならば独裁的になることを証明します。次に社会的選択関数が耐戦略性を満たし全射であるならば単調性と全会一致性を満たすことを証明します。この２つが証明できればGS定理は証明されます。

証明（前半のパート）

定理
社会的選択関数 $f$ が全会一致性と単調性を満たすとする。このとき $f$ は独裁的である。

証明
全会一致性と単調性を満たす $f$ について考える。これから $f$ が独裁的であることを示すがアローの定理の証明と同じように、まずは「独裁者っぽい人」が存在することを示す。そしてその人が独裁者であることを示す。

まず任意に $a\in A$ を固定する。これからやるのは $a$ についての独裁者になっている人（その個人が $a$ を一番上に位置づけている任意の選好プロファイルにおいて $a$ が選ばれる）が存在することを示す。実はこれが示されれば証明は終わる。

$４$ つのステップによって、いま任意に固定した $a$ についての独裁者が存在することを示していく。

STEP1
任意に $a$ ではない選択肢 $b$ を固定する。そして、 $b$ が全員において一番下で $a$ が全員において一番上にくる選好プロファイルを $1$ つ固定する。この選好ファイルにおいては $a$ が選ばれることになる（全会一致性より）。

ここで $1$ さんの選好から順に変更を加えていく。まずは $1$ さんの選好において $b$ の位置を $1$ つずつ上にあげていく。

f:id:KoHarada:20220313095144p:plain
なお、 $1$ さんの選好において $b$ が $a$ の真下にきた時点までは（つまり図の最後の矢印の時点では） $a$ が確実に選ばれ続ける。これは全会一致性からもいえるし単調性からもいえる。しかし、もう $1$ つ $b$ の位置をあげて $a$ の真上までくると場合によってはその選好プロファイルにおいて $b$ が選ばれるかもしれない（厳密な話をするとここで第三の選択肢が選ばれることはない）。 $1$ さんの選好において $b$ が $a$ の真上にきた時点で $b$ が選ばれる場合はそこでプロセスが終わるが $a$ が選ばれ続ける場合には $2$ さんの選好に移り同じことを繰り返していく。

ここで注意が必要なのは、 $2$ さんの選好においても $b$ が $a$ の真上にくるまでは $a$ が選ばれることである。 $1$ さんの選好で $b$ が一番上にきた時点の選好プロファイルと、 $b$ を $2$ さんの選好において少し上げた（ $a$ の上にはこない）選好プロファイルを比べると、単調性より後者においても $a$ が選ばれることが分かる。つまり $2$ さんの選好の修正中に $a$ から $b$ に選ばれるものが切り替わるのであれば、それは $b$ を $a$ の真下から真上に持ってきたときである。また細かい点ではあるが $b$ を $a$ の真下から真上に持ってきたときに $a$ から $b$ にではなく第三の選択肢 $d$ に切り替わることがないについてであるが、これはあり得ない（そのようなことがあるとすると単調性に反する）。*1

このプロセスを繰り返していくとどこかのタイミングで $b$ が選ばれる選好プロファイルに行きつく（誰かしらの個人において $b$ を $a$ の真下から真上に持ってきたタイミングで $a$ から $b$ に社会的に選ばれる選択肢が切り替えることになる）。そのような個人を $m$ で表す。

この $m$ さんが $a$ についての独裁者になっていること示していくことになる。

$m$ さんの選好において $b$ が $a$ の真下にきた時点と $a$ の真上にきた時点の選好プロファイルをそれぞれ選好プロファイル $P$ , $Q$ と呼ぶことにする。

f:id:KoHarada:20220313100649p:plain

f:id:KoHarada:20220313100703p:plain

これでSTEP1終了である。やったことは $b$ を $1$ つずつ上にあげていって、 $a$ から $b$ に切り替わる $m$ さんを見つけ、その切り替わる直前と直後の選好プロファイルに $P$ 、 $Q$ と名前をつけた。

これからSTEP2〜STEP4でややこしいことをしていくが、STEP4では次図の選好プロファイルにおいて $a$ が選ばれることを示す。このような選好プロファイルにおいて $a$ が選ばれることが示されれば実は単調性より $m$ さんは $a$ についての独裁者になっているといえることになる（これとても重要！）
f:id:KoHarada:20220313101622p:plain

注目すべきは各個人における $a$ の位置だけで $b$ とか $c$ については無視して良い。上図における $a$ の位置に注目しよう。そしてなぜこの選好プロファイルにおいて $a$ が選ばれるならば $m$ さんが $a$ についての独裁者になっているといえるかを考える。これは実は背理法で一発で、仮にある選好プロファイルが存在して、 $m$ さんが一番上に $a$ を位置づけているにも関わらず他の選択肢が選ばれるとしてみる。そのような選好プロファイルと上図の選好プロファイルを比べると単調性に満たされなくなっていることが分かる。

我々が目指すべきは上図である。これを意識しておくと迷子になりづらい。

STEP2
選好プロファイルPとQにおいて、 $m$ さんより小さい番号の人については $a$ を一番下まで下げ、 $m$ さんより大きい番号の人については $a$ を下から $2$ 番まで下げる。このようにして選好プロファイル $P'$ と $Q'$ を作る。

f:id:KoHarada:20220313100742p:plain

f:id:KoHarada:20220313100806p:plain
ここで示したいのは $P'$ において $a$ が選ばれることである。まず単調性より $Q'$ においては $b$ が選ばれることになる（ $Q$ において $b$ が選ばれていたことを思い出す）。次に $P'$ において $a,b$ 以外の選択肢が選ばれることはない（仮に選ばれるとするとPでも選ばれないと単調性に反するから）。では $P'$ で $b$ が選ばれるかであるが、もし選ばれるとするとこれは $P$ でも $b$ が選ばれる必要が出てくるが $P$ では $a$ が選ばれるのでこれはおかしい。したがって、 $P'$ においては $a$ が選ばれることになる。

STEP1の段階では $P$ で $a$ が選ばれることが分かっていたが、STEP2の段階では $P'$ で $a$ が選ばれることが分かった。 $2$ つを見比べるとSTEP4で示したい図へと着実に近づいていることが分かる。

STEP3
ここで $a$ とも $b$ とも違う任意の選択肢 $c$ を取ってくる。そして新しい選好プロファイルとして次のようなものを考える（ $\cdot$ になっている部分は何でも良い）。この選好プロファイルを $R$ とする。単調性よりこの $R$ においても $a$ が選ばれることが分かる（ $P'$ と比べると分かる）。

f:id:KoHarada:20220313101401p:plain

STEP4
選好プロファイル $R$ から $m$ より大きい番号の人について $a$ と $b$ を入れ替える。これを $R'$ とする。このとき $a,b$ 以外の選択肢が選ばれることはない（もし選ばれるならば $R$ でも選ばれないとおかしいから）。

f:id:KoHarada:20220313101338p:plain
あとは $b$ が選ばれないことを言えればいいが、そのために $c$ が選ばれないことを使う。注目すべきは $R'$ において $c$ が全員の選好において $b$ よりも上にきていることである。仮に $R'$ において $b$ が選ばれるとしよう。そのときに $c$ を全員の選好において一番上まで上げてみる。そのようにして $R'$ から作った選好プロファイルにおいても単調性より $b$ が選ばれる必要が出てくるが、それは全会一致性に反する。よって、 $R'$ において $a$ が選ばれることが分かった。

ということで、STEP1の後ろで説明した通り、ここから $m$ さんは $a$ についての独裁者になっているといえる（繰り返すがその意味は任意の選好プロファイルについて $m$ さんが一番上に $a$ を位置づけているならば $a$ が選ばれるという意味である）。

いま我々は最初に $a$ を任意にとってきて、それについての独裁者が存在することを示した。このことから、各選択肢についてその選択肢ごとの独裁者がいるといえる。ここまでの議論では選択肢ごとに独裁者は異なりうるが、実はそのような人は同一人物になることが分かる。（背理法で示せる。ある選択肢 $c,d$ が存在してその選択肢についての独裁者が異なるとする、として示す）。*2

以上よりSTEP1で見つけた $m$ さんは全ての選択肢についての独裁者になっていることが分かった。よって $f$ は独裁的である。これで証明終了である。*3

定理（再掲）
社会的選択関数 $f$ が全会一致性と単調性を満たすとする。このとき $f$ は独裁的である。

証明（後半のパート）

定理
社会的選択関数が耐戦略性を満たし全射だとする。このとき $f$ は全会一致性と単調性を満たす。

なおこの定理は $|A|$ が $2$ でも成り立ちます（先ほどの定理は $|A|$ が $2$ では成り立たちません）。一度ここで耐戦略性の定義を確認しておきます。

定義（再掲）
社会的選択関数 $f:\ L^n\rightarrow A$ が耐戦略性を満たすとは、
すべての $i\in N$ 、すべての $\succ_i \in L$ 、すべての $\succ_{-i}\in L^{n-1}$ 、すべての $\succ'_i \in L$ について以下が成り立つことである。

$f(\succ'_i,\succ_{-i})\ne f(\succ_i)$ ならば $f(\succ) \succ_i f(\succ'_i,\succ_{-i})$ 。

証明の方針としては、背理法ではなく普通に示していきます。つまり $f$ が耐戦略性を満たし全射であるとして、その $f$ が単調性と全会一致性が満たすことを示していきます（まずは単調性を示し、次に全会一致性を示す）。

ただし難しさとして、単調性の定義を思い出すと単調性は２つの選好プロファイルを比べています。その際に比べる選好プロファイルにおいて各人の選好は異なりえます（選好が異なる人数は $1$ 人かもしれないし $2$ 人かもしれないし $n$ 人かもしれないし特に決まっていません）。選好が異なる人数が何人でも良いのは少し扱いづらいので、まずは選好が異なる人数が $1$ 人であるような場合のみに注目したLemmaを $1$ つ用意してから証明に入ります。

Lemma
社会的選択関数 $f$ が耐戦略性を満たすとする。このとき、すべての $a\in A$ と、すべての $\succ \in L^n$ ただし　 $f(\succ)=a$ 、任意の $i\in N$ と、任意の $\succ'_i \in L$ ただし $B(\succ_i,a)\ \subset \ B(\succ'_i,a)$ について、

$f(\succ)=f(\succ'_i,\succ_{-i})$ が成り立つ。

これを繰り返し適応すれば単調性は示そうな雰囲気があります。そしてこれは $1$ 人の選好を変えるだけなので耐戦略性から言うのが簡単そうです。

Lemmaの証明
背理法で示す。仮にある $a,\succ, i, \succ'_i$ が存在して（ただし上の細かい条件は満たす）、 $f(\succ)\ne f(\succ'_i,\succ_{-i})$ だとする。

このとき、ある $b\in A\setminus \{a\}$ が存在して $b=f(\succ'_i,\succ_{-i})$ 。

ここで次の $2$ つのことを並べてみる。

$f(\succ_i,\succ_{-i})=a$
$f(\succ'_i,\succ_{-i})=b$

すると耐戦略性より、 $a\succ_i b$ と $b\succ'_i a$ がいえる。

しかし $\succ'_i$ は $B(\succ_i,a)\ \subset \ B(\succ'_i,a)$ を満たしており、これと $a\succ_i b$ より $a\succ'_i b$ となっていないとおかしい。よって矛盾。

これでLemmaが証明できた。このLemmaが単調性の $1$ 人の選好だけ動かしたバージョンになっていることに気づけばこれを繰り替し適応すれば良いと分かる。

証明
社会的選択関数 $f$ が耐戦略性を満たし全射であるとする。

以下の条件を満たす、任意の選好プロファイル $\succ,\succ'$ と任意の選択肢 $a\in A$ を固定する。 $f(\succ)=a$ かつ任意の $i\in N$ について $B(\succ_i,a)$ $\subset$ $B(\succ'_i,a)$ 。

示したいのは $f(\succ')=a$ である。

$\succ$ と $\succ'$ で何人の選好が異なっているかが問題だが $0$ 人であればそれは同じ選好プロファイルなので問題なくいえる。 $1$ 人であればこれはLemmaからすぐにいえる。 $2$ 人の選好が異なる場合でも、まずは一回Lemmaを適応して、次にもう一回Lemmaを適応すれば $f(\succ')=a$ をいえる。それ以上の場合でも同じように繰り返し適応すればいい。

どのように繰り返し適応するかというと、 $\succ$ と $\succ'$ で選好が異なる個人の中で $1$ 番若い番号の個人を選んでその人だけが $\succ'$ の選好で他の人は $\succ$ の選好である選好プロファイルを考える。そしてその選好プロファイルにLemmaを適応する。次にこの選好プロファイルを起点にして、 $\succ$ と $\succ'$ で選好が異なる個人で $2$ 番目に若い番号の個人についてその人は $\succ'$ の選好で他の人はいま起点にしている選好プロファイルの選好であるような選好プロファイルを持ってきてそれにLemmaを適応する、、、、、のようにやっていく。

これで $f(\succ')=a$ が示せた（単にLemmaを繰り返し使っただけ）。

次に全会一致性を示す。

任意の選択肢 $a$ を固定する。任意の選好プロファイル $\succ$ ただし $f(\succ)=a$ を固定する。示したいのは $f(\succ)=a$ である。

$f$ が全射であることからある選好プロファイル $\succ'' \in L^n$ が存在して $f(\succ'')=a$ となる。その選好プロファイル $\succ''$ から $a$ を全員において一番上に持ってきた選好プロファイルを考える。すると単調性よりその新しい選好プロファイルにおいては $a$ が選ばれることになる。

つまり、ある選好プロファイルただし $a$ が全員において一番上にきている、において $a$ が選ばれることが分かった。ということは単調性から先ほど固定した $\succ$ においても $a$ が選ばれると分かる。

以上より $f$ は単調性と全会一致性を満たす。

これで後半の定理も証明終了であり、前半の定理と合わせればGS定理の証明終了である。お疲れ様でした！

参考文献：
Reny, P. J. (2001). Arrow’s theorem and the Gibbard-Satterthwaite theorem: a unified approach. Economics letters, 70(1), 99-105.

Fin.

*1:簡単に示す。 $2$ さんの選好において $b$ を $a$ の真下に持ってきた時点までは $a$ が選ばれているわけだが、 $b$ を一番上に持ってきた瞬間に $d$ に切り替わるとする。このときに $b$ が $a$ の真下にある選好プロファイルと真上にある選好プロファイルを比較すると、後者では $d$ が選ばれているのに前者では $a$ が選ばれており、後者の選好プロファイルを単調性の定義の $\succ$ の方を選好プロファイルだと思うと単調性に反していることが分かる。

*2:念のため示しておく。 $c$ についての独裁者を $C$ として $d$ についての独裁者を $D$ とする。このとき、 $C$ さんが $c$ を一番上におき、 $D$ さんが $d$ を一番上におく選好プロファイルを $1$ つ考える。このとき $C$ さんが $c$ についての独裁者であることから社会は $c$ を選ぶことになるが、これは $D$ さんが $d$ についての独裁者であることに反する。

*3:ある個人がすべての選択肢について独裁者であることと、その個人が独裁者であることは本当に同値であるかについては確認する必要があるが、一旦ここではそれは認めておく。独裁の定義のところにif and only if が出てくるところが面倒だが割と簡単に示せる。