多対一マッチングにおける選好と優先順位

選好と優先順序

多対一マッチングにおける選好とは, 学生が学校をどのように好んでいるかを表すものです.
多対一マッチングにおける優先順序とは, 学校が学生をどのようにランク付けしているかを表すものです.
選好と優先順序は意味合いが異なります.
学校側が学生を一人だけ受け入れるなら誰を優先するかを表すのが優先順序といえます.
一方で, 学校側で選好を定義するには, 学生の部分集合に対して好みを持っている必要があります.
なぜなら考えている対象が多対一マッチングであり, 学校は複数の学生を受け入れるためです.
そのため, 学校が学生に対する選好を考えるのは複雑になりがちなので, 優先順位（一人だけの選好）に制限して考えることが多いです.

選好（優先順序）には弱選好と強選好の2種類があります.

数学的な定義

数学的な定義を以下で与える.

弱選好

定義弱選好

学生 $i\in I$ が学校に持つ選好 $R_i \subseteq (S\cup \{\emptyset\})\times (S\cup \{\emptyset\})$ が以下の条件を全て満たすとき, $R_i$ を弱選好という. 任意の $a,b,c\in S\cup \{\emptyset\}$ に対して,

（反射律） $(a,a)\in R_i.$
（推移律） $\{(a,b)\in R_i\ \text{かつ}\ (b,c)\in R_i\}\Rightarrow (a,c)\in R_i.$
（完備性） $(a,b)\in R_i\ \text{または}\ (b,a)\in R_i.$

強選好

定義強選好

学生 $i\in I$ が学校に持つ選好 $R_i \subseteq (S\cup \{\emptyset\})\times (S\cup \{\emptyset\})$ が以下の条件を全て満たすとき, $R_i$ を強選好という. 任意の $a,b,c\in S\cup \{\emptyset\}$ に対して,

（反射律） $(a,a)\in R_i.$
（推移律） $\{(a,b)\in R_i\ \text{かつ}\ (b,c)\in R_i\}\Rightarrow (a,c)\in R_i.$
（完備性） $(a,b)\in R_i\ \text{または}\ (b,a)\in R_i.$
（未割当に関する対称律）
$\{(a,\emptyset)\in R_i\ \text{かつ}\ (\emptyset,a)\in R_i\}\Rightarrow a=\emptyset.$
（未割当以上に関する対称律）

$\{(a,\emptyset)\in R_i\ \text{かつ}\ (b,\emptyset)\in R_i\ \text{かつ}\ (a,b)\in R_i\ \text{かつ}\ (b,a)\in R_i\}\Rightarrow a=b.$

弱優先順位

定義弱優先順位

学校 $s\in S$ に対して, $R_s \subseteq I\times I$ が弱優先順位であるとは, 反対称律の条件を除いた全順序の条件を満たすときである.

（強）優先順位

定義（強）優先順位

学校 $s\in S$ に対して, $R_s \subseteq I\times I$ が（強）優先順位であるとは, 全順序の条件を満たすときである.

（補足） $R_s$ が $I$ 上の全順序であるとき, と言い換えてもよい.

選好の記法（ $\succsim,\ \succ,\ \sim$ を用いた表現）

定義記法

学生 $i$ の弱選好 $R_i$ に対して, 以下の記法を用いる.

$a \succsim_i b$ $\Longleftrightarrow$ $(a,b)\in R_i$
$a \succ_i b$ $\Longleftrightarrow$ $(a,b)\in R_i\ \text{かつ}\ (b,a)\notin R_i$
$a \sim_i b$ $\Longleftrightarrow$ $(a,b)\in R_i\ \text{かつ}\ (b,a)\in R_i$

ここで,

$a \succ_i b$ は「 $i$ は $a$ を $b$ より厳密に好む」を表す.
$a \sim_i b$ は「 $i$ は $a$ と $b$ を無差別とみなす」を表す.

例：ハリーの選好

学校集合を $S=\{\text{グリフィンドール},\ \text{ハッフルパフ},\ \text{レイブンクロー},\ \text{スリザリン}\}$ とする.

例例1. 強選好の例

ハリーはスリザリンはいやだという. これはスリザリンに行くぐらいだったら寮に入らない方がいいと思っていることを意味する.
またハリーはレイブンクローに入るぐらいだったら, 寮に入らないほうがましだと考えているとする.
またハリーはハッフルパフよりもグリフィンドールの方が入りたいと思っているとする.
このときのハリーに関する選好 $\succsim_{\text{ハリー}}$ は次で定義できる.

$\text{グリフィンドール} \succ_{\text{ハリー}} \text{ハッフルパフ} \succ_{\text{ハリー}} \emptyset \succ_{\text{ハリー}} \text{レイブンクロー} \sim_{\text{ハリー}} \text{スリザリン}$

このとき,

未割当 $\emptyset$ より上（グリフィンドール, ハッフルパフ）では無差別が存在しない.
したがって, 未割当より上で強い選好を持つ.

よってこの選好は強選好である.

例例2. 弱選好の例

一方, ハリーが次のように考えているとする.

$\text{グリフィンドール} \sim_{\text{ハリー}} \text{ハッフルパフ} \succ_{\text{ハリー}} \emptyset \succ_{\text{ハリー}} \text{レイブンクロー} \sim_{\text{ハリー}} \text{スリザリン}$

このとき,

未割当 $\emptyset$ より上に位置するグリフィンドールとハッフルパフが無差別である.

したがって, 未割当より上で無差別が存在するため, この選好は弱選好である.

例例3. ロンの選好

ロンが次のように考えているとする.

$\text{グリフィンドール} \succ_{\text{ロン}} \emptyset \succ_{\text{ロン}} \text{ハッフルパフ} \sim_{\text{ロン}} \text{レイブンクロー} \sim_{\text{ロン}} \text{スリザリン}$

このとき,

未割当 $\emptyset$ より上はグリフィンドールのみである.
その部分では無差別が存在しない.

したがって, ロンの選好は未割当より上で強い選好である.

例例4. ハーマイオニーの選好

ハーマイオニーが次のように考えているとする.

$\text{グリフィンドール} \succ_{\text{ハーマイオニー}} \text{レイブンクロー} \sim_{\text{ハーマイオニー}} \text{ハッフルパフ} \succ_{\text{ハーマイオニー}} \emptyset \succ_{\text{ハーマイオニー}} \text{スリザリン}$

このとき,

未割当 $\emptyset$ より上にレイブンクローとハッフルパフの無差別が存在する.

したがって, この選好は弱選好である.

グリフィンドールの優先順位の例

学生集合を $I=\{\text{ハリー},\ \text{ロン},\ \text{ハーマイオニー}\}$ とする.

例例5. 強優先順位の例

グリフィンドールが次のように順位付けしており, 無差別が存在しないとする.

$\text{ハーマイオニー} \succ_{\text{グリフィンドール}} \text{ハリー} \succ_{\text{グリフィンドール}} \text{ロン}$

このとき, グリフィンドールの優先順位は強優先順位（学生集合上の全順序）である.

例例6. 弱優先順位の例

一方, グリフィンドールが次のように考えているとする.

$\text{ハリー} \sim_{\text{グリフィンドール}} \text{ロン} \succ_{\text{グリフィンドール}} \text{ハーマイオニー}$

この場合, ハリーとロンの間に無差別が存在するため, これは弱優先順位である.

未割当より下は省略してよい

一般に未割当 $\emptyset$ より下に位置付けられているものは省略して書くことが多いです.
例えばハリーの選好が

であった場合は,

$\text{グリフィンドール}\succ_{\text{ハリー}}\text{ハッフルパフ}$

のように書きます.
未割当より下の順位はマッチングにほとんど影響しないため, この省略が許されていることに注意しましょう. （ただし制約による.）

りきのblog

理学部数学科→経営工学修士（理論経済学；多対一マッチング）　もし間違いあればおしえてください！ハリーポッター（魔法の覚醒）が好き

多対一マッチングにおける選好と優先順位