アローの不可能性定理のお気持ち

はじめに

この記事は 数理最適化 Advent Calendar 2023 の7日目です。アローの不可能性定理のお気持ちについて書きます。 前の記事 でもこの定理を扱ったのですが、数式レベルで議論は追えても、理解した気になれませんでした。そこで、今一度この定理を勉強しなおし、この定理のお気持ちを少しは理解できるようになってきました。本記事ではそのお気持ちについて書きます。（ほぼ離散数学ですので数理最適化ということにしてください。。）

アローの不可能性定理

まずは、アローの不可能性定理を説明していきます。カジュアルに進めたいので、具体例で説明していきます。

候補者の順序を決める選挙を考えます。投票者の集合を$A = \{ a_1, a_2, a_3, a_4 \}$、候補者の集合を$B = \{ b_1, b_2, b_3, b_4 \}$とします。変数として、$i \in A$を投票者、$x, y \in B$を候補者とします。

各投票者は候補者の順序を決めます。本記事では順序をリストとして表し、先頭の方が高順位とします。投票者$i$の順序を${\succ}_i$、全員の順序の集合を${\succ}$とします。例えば以下です。

\begin{align} {\succ}_{a_1} : (b_1, b_2, b_3, b_4) \\ {\succ}_{a_2} : (b_2, b_3, b_1, b_4) \\ {\succ}_{a_3} : (b_4, b_1, b_2, b_3) \\ {\succ}_{a_4} : (b_2, b_4, b_3, b_1) \end{align}

順序$\succ_i$は二人の候補者の比較演算子としても使います。$x \succ_i y$は、順序$\succ_i$では候補者$x$が候補者$y$よりも高順位であることを意味します。

投票者の順序${\succ}$を入力として、集計関数$f$で全体としての順序$f({\succ})$を決めます。例えば以下です。

\begin{align} f({\succ}) : (b_2, b_1, b_3, b_4) \end{align}

ここで、集計関数$f$は以下の条件を満たしているとします。

1. 無制約性：集計関数$f$には任意の順序を入力できます。
2. 満場一致性：入力で全員が$x \succ_i y$であるなら、出力でも$x \; f(\succ) \; y$となります。
   例えば以下の入出力$({\succ}, f({\succ}))$では、（一例ですが、）入力で全員が$b_2 \succ_i b_3$であり、出力でも$b_2 \; f(\succ) \; b_3$ですので、満場一致性を満たしています。
   \begin{matrix} {\succ}_{a_1} : (b_1, b_2, b_3, b_4) & (b_2 \succ_{a_1} b_3) \\ {\succ}_{a_2} : (b_2, b_3, b_1, b_4) & (b_2 \succ_{a_2} b_3) \\ {\succ}_{a_3} : (b_4, b_1, b_2, b_3) & (b_2 \succ_{a_3} b_3) \\ {\succ}_{a_4} : (b_2, b_4, b_3, b_1) & (b_2 \succ_{a_4} b_3) \\ f({\succ}) : (b_2, b_1, b_3, b_4) & (b_2 \; f({\succ}) \; b_3) \end{matrix}
3. 独立性：出力での各二人の順序は、入力でのその二人の順序のみで決まります。
   例えば以下の二つの入出力$({\succ}, f({\succ})), ({\succ}', f({\succ}'))$では、入力で各投票者の候補者$b_1, b_3$に対する順序が同じであるにもかかわらず、出力での候補者$b_1, b_3$に対する順序が異なっています。したがって、独立性を満たしていないです。独立性を満たすためには、出力での候補者$b_1, b_3$に対する順序が同じである必要があります。
   \begin{matrix} {\succ}_{a_1} : (b_1, b_2, b_3, b_4) & (b_1 \succ_{a_1} b_3) \\ {\succ}_{a_2} : (b_2, b_3, b_1, b_4) & (b_3 \succ_{a_2} b_1) \\ {\succ}_{a_3} : (b_4, b_1, b_2, b_3) & (b_1 \succ_{a_3} b_3) \\ {\succ}_{a_4} : (b_2, b_4, b_3, b_1) & (b_3 \succ_{a_4} b_1) \\ f({\succ}) : (b_2, b_1, b_3, b_4) & (b_1 \; f({\succ}) \; b_3) \end{matrix}
   \begin{matrix} {\succ}'_{a_1} : (b_1, b_2, b_4, b_3) & (b_1 \succ'_{a_1} b_3) \\ {\succ}'_{a_2} : (b_3, b_2, b_1, b_4) & (b_3 \succ'_{a_2} b_1) \\ {\succ}'_{a_3} : (b_4, b_2, b_1, b_3) & (b_1 \succ'_{a_3} b_3) \\ {\succ}'_{a_4} : (b_2, b_3, b_4, b_1) & (b_3 \succ'_{a_4} b_1) \\ f({\succ}') : (b_2, b_3, b_1, b_4) & (b_3 \; f({\succ}') \; b_1) \end{matrix}

そして、アローの不可能性定理では、上記の条件を満たす集計関数は"独裁"となってしまうことを示しています。独裁とは、特定の投票者の入力が出力と同じになる状態のことを言います。例えば以下の入出力$({\succ}, f({\succ}))$では、（一例ですが、）投票者$a_1$の入力が出力と同じになっていますので、独裁となっています。

\begin{align} {\succ}_{a_1} : (b_1, b_2, b_3, b_4) \\ {\succ}_{a_2} : (b_2, b_3, b_1, b_4) \\ {\succ}_{a_3} : (b_4, b_1, b_2, b_3) \\ {\succ}_{a_4} : (b_2, b_4, b_3, b_1) \\ f({\succ}) : (b_1, b_2, b_3, b_4) \end{align}

お気持ち

アローの不可能性定理は、定理の意味自体は分かりやすいものの、条件がどれも当たり前のように感じますので、そこから独裁というかなり強い状態になっていることが直感では結びつきません。では、一つずつお気持ちを理解していきます。

独立性のお気持ち

まずは独立性のお気持ちです。当たり前のように感じる条件ですが、保証しようとするとかなり強い条件です。（例えば、多数決ルールでは独立性を保証できません。）というのは、すでに分かっている入出力によって、別の入力に対する出力が決まってしまうからです。

以下の例を見てみます。仮に、入力${\succ}$に対する出力$f({\succ})$の一部が分かっているとします。（$*$はまだ順序が確定していない候補者です。）入力${\succ}$では、投票者$a_1, a_2, a_3$の候補者$b_1, b_2$に対する順位が出力と同じであり、投票者$a_1, a_2, a_3$が独裁者の候補となります。

\begin{matrix} {\succ}_{a_1} : (b_1, b_2, b_3, b_4) & (b_1 \succ_{a_1} b_2) \\ {\succ}_{a_2} : (b_1, b_3, b_2, b_4) & (b_1 \succ_{a_2} b_2) \\ {\succ}_{a_3} : (b_4, b_1, b_2, b_3) & (b_1 \succ_{a_3} b_2) \\ {\succ}_{a_4} : (b_2, b_4, b_3, b_1) & (b_2 \succ_{a_4} b_1) \\ f({\succ}) : (b_1, b_2, *, *) & (b_1 \; f({\succ}) \; b_2) \end{matrix}

そして、さらに以下の入力${\succ}'$を考えます。入力${\succ}'$では、候補者$b_1, b_2$の順序が入力${\succ}$と同じですので、独立性から、出力でも同じ順序$x \; f({\succ}') \; y$になります。

\begin{matrix} {\succ}'_{a_1} : (b_1, b_2, b_3, b_4) & (b_1 \succ'_{a_1} b_2) \\ {\succ}'_{a_2} : (b_1, b_4, b_2, b_3) & (b_1 \succ'_{a_2} b_2) \\ {\succ}'_{a_3} : (b_4, b_3, b_1, b_2) & (b_1 \succ'_{a_1} b_2) \\ {\succ}'_{a_4} : (b_2, b_3, b_4, b_1) & (b_2 \succ'_{a_4} b_1) \\ f({\succ}) : (b_1, b_2, *, *) & (b_1 \; f({\succ}) \; b_2) \end{matrix}

ここから、各候補者について、独裁者の候補となる順序が一つでもあるなら、それと似ている順序でも独裁者の候補となれる（候補者となりやすい）ことが分かります。

無制約性のお気持ち

次に無制約性のお気持ちです。無制約性により、すでに独裁者の候補が分かっている入力をベースに、独裁者の候補がより少ない入力を作れます。これは、無制約性により任意の順位を入力できることから、独裁者の候補の中で意見が割れるような入力を作れるからです。

実は先ほどの入力${\succ}'$がそのように設計された入力の例となります。（以下に再掲します。）候補者$b_1, b_2$と候補者$b_3$の順序を考えてみると、入力${\succ}$とは順序が異なるので、独立性による出力の制限には引っ掛かりません。出力でありうる順序をすべて挙げると、独立性で候補者$x, y$の順序は決まっているので、$x \; f({\succ}') \; y \; f({\succ}') \; z$、$x \; f({\succ}') \; z \; f({\succ}') \; y$、$z \; f({\succ}') \; x \; f({\succ}') \; y$の三つだけとなります。ここで、説明は省略しますが、二つ目の$x \; f({\succ}') \; z \; f({\succ}') \; y$の順序にはなりえないで除外します。そして、入力を巧妙に設計したことにより、残った二つのどちらになったとしても、投票者$a_1, a_2$か候補者$a_3$のどちらかが独裁者候補として残ります。（また、投票者$a_4$が独裁者候補に入らないようにも設計されています。）

\begin{matrix} {\succ}'_{a_1} : (b_1, b_2, b_3, b_4) & (b_1 \succ'_{a_1} b_2 \succ'_{a_1} b_3) \\ {\succ}'_{a_2} : (b_1, b_4, b_2, b_3) & (b_1 \succ'_{a_2} b_2 \succ'_{a_1} b_3) \\ {\succ}'_{a_3} : (b_4, b_3, b_1, b_2) & (b_3 \succ'_{a_3} b_1 \succ'_{a_1} b_2) \\ {\succ}'_{a_4} : (b_2, b_3, b_4, b_1) & (b_2 \succ'_{a_4} b_3 \succ'_{a_1} b_1) \\ \end{matrix}
パターン①
\begin{matrix} f({\succ}') : (b_1, b_2, b_3, *) & (b_1 \; f({\succ}') \; b_2 \; f({\succ}') \; b_3) \end{matrix}
パターン②
\begin{matrix} f({\succ}') : (b_1, b_3, b_2, *) & (b_1 \; f({\succ}') \; b_3 \; f({\succ}') \; b_2) \end{matrix}
パターン③
\begin{matrix} f({\succ}') : (b_3, b_1, b_2, *) & (b_3 \; f({\succ}') \; b_1 \; f({\succ}') \; b_2) \end{matrix}

このように、元の入力${\succ}$での独裁者候補よりも少ない数の独裁者候補を持つ入力${\succ}'$を作れます。これを繰り返し適用していくと、独裁者候補はただ一人となり、独裁状態を示せます。（正確には、任意の入力と候補者ペアで独裁となっていることを示す必要があります（※）。）

満場一致性のお気持ち

最後に満場一致性のお気持ちですが、これは省略します。先ほどの※の証明で効いてきます。

まとめ

以上をまとめると、アローの不可能性定理のお気持ちは以下だと私は理解しました。

おわりに

前よりはアローの不可能性定理を理解できたような気がしてきましたが、まだまだしっくり来ていないところがたくさんあります。さらにじっくり理解していきたいと思います。