順序の数量化と選好 - Rei Frontier Tech Blog

レイ・フロンティア株式会社のデータアナリストの齋藤です。
今回は最近興味を持ち始めた、選好関係と呼ばれる2項関係と、選好の順序を数値によって表現する方法についてご紹介します。

全順序に関する数量化定理
弱順序に関する数量化定理
参考文献

全順序に関する数量化定理

対象の集合$X$に2項関係$\precsim$が導入されているとします。この関係が好み、すなわち選好関係(preference relation)を表現すると考えます。
$x \precsim y$かつ$y \precsim x$のことを$x \sim y$と書き、$x \precsim y $だが$x \sim y$でないことを$x \prec y$と書きます。$x \precsim y$のことを$y \succsim x$とも書きます。$\prec$と同様に、$x \succsim y $だが$x \sim y$でないことを$x \succ y$と書きます。
全順序の定義から、次の3つが成り立ちます：

全順序の公理(1) 完備性：　$\forall x,y \in X, x \precsim y \vee y \precsim x$
(2) 反対称性：　$\forall x, y \in X, x \sim y \Rightarrow x = y$
(3) 推移性：　$\forall x, y, z \in X, x \precsim y \wedge y \precsim z \Rightarrow x \precsim z$

$X$は一般に数とは限らないいろいろな"もの"の集合ですが、$X$の元と数との間に選好関係を保つような対応があれば応用上有利です。ありがたいことに、$X$が高々可算であればそのような対応が存在することが知られています：

定理1.(全順序の数量化定理：有限集合の場合)有限集合$X$上の関係$\precsim$が全順序であるとき、$X$上の実数値関数$\phi:X \to \mathbb{R}$が存在して、$$\forall x,y \in X, \ x \succsim y \Leftrightarrow \phi(x) \geq \phi(y)$$

(証明) まず$\Rightarrow$を示す。$x \succsim y$を仮定する。推移性により、$y \succsim z$となるような任意の$z \in X$に対して$x \succsim z$が成立する。ゆえに、$\{ z \mid x \succsim z \} \supseteq \{ z \mid y \succsim z \}$である。ここで、有限集合$A$の要素の個数を$\sharp A$とし、関数$\phi \colon X \to \mathbb{R}$を$$\phi(x) := \sharp \{z \mid x \succsim z\}$$によって定める。この$\phi$について、$\forall x,y \in X, x \succsim y \Rightarrow \phi(x) \geq \phi(y)$が成り立つ。
つぎに$\Leftarrow$を示す。そのためには対偶を示せばよい。対偶は$$\forall x,y \in X,\ \lnot (x \succsim y) \Rightarrow \lnot (\phi(x) \geq \phi(y))$$であるが、完備性によりこの命題は$$\forall x,y \in X,\ y \succ x \Rightarrow \phi(x) < \phi(y)$$と同値である。ところが、$y \succ x $なるとき$\{ z \mid x \succsim z \} \subsetneqq \{ z \mid y \succsim z \}$であるため$\phi(x) < \phi(y)$である。以上で示された。■

この定理は$X$が可算無限集合の場合にも拡張できます：

定理2.(全順序の数量化定理：可算無限集合の場合)可算無限集合$X$上の関係$\precsim$が全順序であるとき、$X$上の実数値関数$\phi:X \to \mathbb{R}$が存在して、$$\forall x,y \in X, \ x \succsim y \Leftrightarrow \phi(x) \geq \phi(y)$$

(証明) まず$\Rightarrow$を示す。$\forall x,y \in X, x \succsim y$を仮定する。$X$の要素にてきとうな番号をふって$X = \{x_1,x_2,\dots,x_i,\dots\}$とし、二重数列$S_{ij}$を$x_i \succsim x_j$のとき$S_{ij}=1$、それ以外のとき$S_{ij} = 0$と定義する。そして、関数$\phi \colon X \to \mathbb{R}$を、$$\phi(x_i) := \sum_{j=1}^\infty \frac{1}{2^j}S_{ij}.$$無限級数が収束するのは明らかである。このように構成された関数$\phi$に対して、$\forall x,y \in X,\ x \succsim y \Rightarrow \phi(x) \geq \phi(y)$が成り立つ。
$\Leftarrow$の場合は定理1の証明と同様。■

弱順序に関する数量化定理

次は、全順序の代わりに、条件を弱めた弱順序を考えます。弱順序とは、以下の2つの公理

弱順序の公理(1) 完備性：　$\forall x,y \in X, x \precsim y \vee y \precsim x$
(2) 推移性：　$\forall x, y, z \in X, x \precsim y \wedge y \precsim z \Rightarrow x \precsim z$

をみたすような関係のことです。ちょうど順序関係から反対称性を取り除いたものになっています。選好を考えるうえでは、異なる対象を同じくらい選好することがありうるために、このような関係を考えるケースがあります。

弱順序についても、$X$が高々可算であれば数量化定理が成立します。

定理3.(弱順序の数量化定理：有限集合の場合)有限集合$X$上の関係$\precsim$が弱順序であるとき、$X$上の実数値関数$\phi:X \to \mathbb{R}$が存在して、$$\forall x,y \in X, \ x \succsim y \Leftrightarrow \phi(x) \geq \phi(y)$$

(証明) $ \sim $は$X$上の関係とみなすとき同値関係である。したがって商集合$X/\sim$が定義できる。$X/\sim$上の関係$\succsim^\prime$を$$x \succsim y のとき [x] \succsim^\prime [y]$$であると定める（ただし、$x$を代表元とする同値類を$[x]$と書いている）とこれはwell-definedであり、かつ$\succsim^\prime$は$X/\sim$上の全順序である。したがって、定理1により実数値関数$\phi^\prime \colon X/\sim \to \mathbb{R}$が存在して$$\forall a,b \in X/\sim, \ a \succsim^\prime b \Leftrightarrow \phi^\prime (a) \geq \phi^\prime (b)$$となる。関数$\phi \colon X \to \mathbb{R}$を$x \in X,\ \phi(x) := \phi^\prime ([x])$によって定めれば、$$\forall x,y \in X, \ x \succsim y \Leftrightarrow \phi(x) \geq \phi(y)$$は成り立っている。■

定理4.(弱順序の数量化定理：可算無限集合の場合)可算無限集合$X$上の関係$\precsim$が弱順序であるとき、$X$上の実数値関数$\phi:X \to \mathbb{R}$が存在して、$$\forall x,y \in X, \ x \succsim y \Leftrightarrow \phi(x) \geq \phi(y)$$

(証明) 定理3の証明の「定理1により」を「定理2により」に置き換えればよい。■

これらの定理は$X$がたかだか可算の場合に限られており、$X$が非可算集合の場合には一般に成立しません。証明は割愛しますが、非可算無限集合については以下の定理が成り立ちます：

定理5.(弱順序の数量化定理：非可算集合の場合)非可算無限集合$X$上の関係$\precsim$が弱順序であり、かつ商集合$X/\sim$が$\succsim$順序稠密な可算部分集合をもつとき、$X$上の実数値関数$\phi:X \to \mathbb{R}$が存在して、$$\forall x,y \in X, \ x \succsim y \Leftrightarrow \phi(x) \geq \phi(y)$$

$X$の部分集合$Y$が$\leq$順序稠密であるとは、任意の要素$x,y\in X$について、$x \leq y$でありかつ$x,y \not\in Y$であるとき、ある$z \in Y$が存在して$x \leq z$かつ$z \leq y$となることをいいます。順序稠密は順序関係のある種の"連続性"を示すものであり、たとえば$\mathbb{Q}$は$\mathbb{R}$に$\leq$順序稠密です。

参考文献

[1] 竹村和久, 藤井聡 (2015), "意思決定の処方", 朝倉書店