『アルゴリズムデザイン』1章演習問題

正しくない。

反例は男女2人ずつで選好が以下の場合。

$ m1の選好 := w1 > w2

$ m2の選好 := w2 > w1

$ w1の選好 := m2 > m1

$ w2の選好 := m1 > m2

そもそも好意順リストで最高位同士であるペアが存在しない。

正しい。

含まないと仮定すると不安定なことが直ちに示せる。

正しくない（(b)が示せる）

$ S = [4, 2], T=[3, 1]

（ゲーム理論的に言えば、純粋戦略の範囲ではナッシュ均衡が存在しないことがある）

G-Sマッチング と同じアルゴリズムで、キープが1人でなく採用人数になるだけ。

東大の進振りなどでも使用されていて、受け入れ保留アルゴリズム、DAアルゴリズムという別名で有名。

(a) 強不安定性

存在する。同じ好感度は任意の順序でプロポーズするG-Sアルゴリズムでよい。証明は通常と同様。

(b) 弱不安定性

存在しない。以下が反例。

$ m1の選好 := w1 = w2

$ m2の選好 :=　any

$ w1の選好 := m1 > m2

$ w2の選好 := m1 > m2

(m1, w1)なら「w2はm2よりm1が好きで、かつ、mはw2がw1と同等に好き」を満たすし、(m1, w2)でも同様。

アルゴリズム

港視点で後ろから貪欲に打ち切る船を選ぶ。

この時、既に後ろで打ち切ることを決めた船は打ち切らない。

正当性

まず、2隻の船は同じ日に港に来ないし、同じ日に打ち切る船が重なることもない。

この貪欲で打ち切りは各港で高々1回起こり、また各船に対して高々1回起こることは明らか。

ここで、各港を全ての船が訪れることから各港で常に丁度1回起こることが言え、全部でN回の打ち切りが各船に高々1回起こることから、各船で丁度1回起こることも言える。

これで各船は条件を満たしたままそれぞれ別の港でメンテナンスされた状態で停止する。

アルゴリズム

実は「入力線はより上流で結合する出力線を好み、出力線はより下流で結合する入力線を好む」という選好でG-Sアルゴリズムを適用すればよい。

正当性

N:Nの二分グラフにG-Sアルゴリズムを使用しているので完全マッチングになっているのは明らか。

invalidなマッチングは「入力線mがまだスイッチされていないのに、出力線w'が(m, w')より上流でスイッチされている」ことで、これは「あるマッチングペア(m, w) (m', w')について、mの選好がw'>wかつ、wの選好がm> m'」に対応する。G-Sアルゴリズムではこういうペアの存在しない安全マッチングが得られるので示された。

実際のwの選好がm1>m2なのにm2>m1と申告して得があるか考えればよい。

m1, m2両方から告白された場合、wの好みでマッチング相手が決まるので、素直に言った方が得。

両方から告白される以外のケースでは関係ない。

ところで同様に男性側も同様に素直が一番。

マーケットデザインでよく出てくる有名問題で、こういう「耐戦略性」を満たしているのもG-Sアルゴリズムのいいところ。

受け入れ側のキープが許されなかったり、申し込み側に早い者勝ち（まず全員の第一希望でマッチングして、次に第二希望でマッチングするみたいな）要素があると虚偽の申告で有利になったり不利になったりする。