アローの不可能性定理における独立性の定義
はじめに
アローの不可能性定理というものを勉強しています。これは「いくつかの条件をみたす社会的厚生関数は存在しない」という定理なのですが、その条件の一つに「無関係な選択肢からの独立性（または単に独立性）」というものがあります。この条件のお気持ちはすんなり理解できたのですが、厳密な定義を理解するのに時間がかかってしまいました。この記事では、同じような方のために、定義を読み解いた過程を記録しておきます。
参考書
- Vohra, Mechanism Design: A Linear Programming Approach
想定知識
- 社会的厚生関数の定義
記法
参考書[1]から若干記法を変えています。
- $n \in \mathbb{N}$：エージェントの数
- $\mathcal{A} = \{ a_1, ..., a_n \}$：エージェントの集合
- $m \in \mathbb{N}$：選択肢の数
- $\Gamma = \{ \gamma_1, ..., \gamma_m \}$：選択肢の集合
- $\Sigma$：選好順序の集合（選択肢集合のすべての順列）
- $\Omega \subseteq \Sigma$：実行可能な選好順序の集合
- ${\prec}_i \in \Omega$：エージェント$i \in \mathcal{A}$の選好順序
- ${\prec} \in \Omega^n$：$n$人のエージェントの選好順序の集合（単に選好順序と呼ぶ）
- $x \prec_i y$：エージェント$i$は選択肢$x \in \Gamma$よりも選択肢$y \in \Gamma$の方が上位と評価
- $f: \Omega^n \rightarrow \Sigma$：社会的厚生関数
- $x \ f({\prec}) \ y$：社会的厚生関数$f$は選択肢$x \in \Gamma$よりも選択肢$y \in \Gamma$の方が上位と評価
独立性の定義
では、始めていきます。
参考書[1]では社会的厚生関数の独立性を以下で定義しています。
For any $x, y \in \Gamma$, suppose $\exists {\prec}, {\prec}' \in \Omega^n$, such that $x \prec_i y$ if and only if $x \prec'_i y$ for $i \in \mathcal{A}$. Then $x \ f({\prec}) \ y$ if and only if $x \ f({\prec}') \ y$.
直訳すると以下となります。
任意の$x, y \in \Gamma$に対して、次の条件を満たす${\prec}, {\prec}' \in \Omega^n$が存在すると仮定する：任意の$i \in \mathcal{A}$に対して、$x \prec_i y$のとき、かつ、そのときのみ、$x \prec'_i y$が成り立つ。このとき、$x \ f({\prec}) \ y$のとき、かつ、そのときのみ、$x \ f({\prec}') \ y$が成り立つ。
そして独立性のお気持ちとして以下が書かれていました。
The second axion states that the ranking of $x$ and $y$ by $f$ is not affected by how the agents rank the other alternatives.
"The second axion"とは独立性のことです。直訳すると以下となります。
二つ目の公理は、$f$による$x$と$y$の評価が、各エージェントが他の選択肢をどのように評価するかによって影響されない、ということを言っている。
私が躓いたポイントは二つあります。
(1) 「$x \prec_i y$のとき、かつ、そのときのみ、$x \prec'_i y$」の意味
（同様に「$x \ f({\prec}) \ y$のとき、かつ、そのときのみ、$x \ f({\prec}') \ y$」の意味）
(2) 定義に「他の選択肢」に関する記述が出てこないこと
以上を一つずつ読み解いていきます。
(1) 「$x \prec_i y$のとき、かつ、そのときのみ、$x \prec'_i y$」の意味
真偽表を書いてみると、「$x \prec_i y$のとき、かつ、そのときのみ、$x \prec'_i y$」は、「($x \prec_i y$かつ$x \prec'_i y$) または ($x \succ_i y$かつ$x \succ'_i y$)」と同値だと分かります。言い換えると「$\prec, \prec'$で$x, y$の評価が等しい」ということです。
| $x \prec'_i y$ | $x \succ'_i y$ | |
|---|---|---|
| $x \prec_i y$ | True | False |
| $x \succ_i y$ | False | True |
したがって、定義は以下のように書き換えられます。
任意の$x, y \in \Gamma$に対して、次の条件を満たす${\prec}, {\prec}' \in \Omega^n$が存在すると仮定する：任意の$i \in \mathcal{A}$に対して$x, y$の評価が等しい。このとき、$f({\prec}), f({\prec}')$で$x, y$の評価が等しい。
(2) 定義に「他の選択肢」に関する記述が出てこないこと
定義には「他の選択肢」に関する記述は明示的には出てきません。ただ、(1)解決後の定義によれば、${\prec}, {\prec}'$には$x, y$の評価が等しいことのみが求められるのですから、他の選択肢の評価が異なっていても良いことになります。したがって、定義は以下のように書き換えられます。
任意の$x, y \in \Gamma$と任意の${\prec} \in \Omega^n$に対して、$x, y$以外の評価が異なる${\prec}' \in \Omega^n$があったとしても、$f({\prec}), f({\prec}')$で$x, y$の評価は変わらない。
ここまで読み解けると、お気持ちの記載と同義になりますので、理解完了となりました。
おわりに
特に(1)で躓いていたのですが、論理演算の習熟度が低いからですね。。精進します。
