安定マッチング

毎年数千人の新米医師が合衆国中の病院のインターンとなります。 二十世紀の最初の 50 年の間に良い医師を求める病院同士の競争は激しさを増していき、医学学校にいる生徒へのインターンシップの勧誘はどんどん早くなっていきました。時には二年生の生徒にまで締め切りの短い勧誘が来ることがあったといいます。このような状況を受けて、1940 年代に全国の医学校は生徒が 4 年生の特定の日になるまではインターンの情報を解禁しないということで合意しました。

しかしこの結果として、病院側は勧誘に対する返答の締め切りを早めるようになりました。1950 年ごろまでは病院が新米の医師を呼び付け、インターンの勧誘を行い、即時の返答を要求することも稀ではありませんでした。選択肢として三番目の病院から連絡を受けた場合、インターンは後から来るもっと良い病院からのオファーが無駄になるリスクを取ってそれを受け入れるか、それともどこにも受け入れてもらえなくなるリスクを取って拒否するかというギャンブルを迫られることになります1。

1950 年代の初頭になってついに National Resident Matching Program (NRMP) が設立され、インターンの割り当てに関する情報はこの機関が管理するようになりました。毎年、医師はインターンに行きたいと思っている病院をランク付けしたものを提出し、病院はインターンとして受け入れたいと思っている医師をランク付けしたものを提出します。 NRMP は提出された情報を使って病院と医師のマッチングを計算しますが、このとき次の安定性 (stability) に関する条件が満たされるようにします。

マッチングが安定でない (unstable) とは、そのマッチングではマッチしていないある医師 \(\alpha\) とある病院 \(B\) があって、両者をマッチさせた方が両者とも現在よりも幸せになる、つまり:

という状況が生じていることを言います。このような場合、\((\alpha, B)\) を不安定ペア (unstable pair) と言います。 NRMP の目標は不安定ペアの無い安定マッチング (stable matching) を見つけることです。

問題を単純にするために、病院の数と医師の数は等しく、全ての病院はちょうど一つのインターンを募集し、全ての医師/病院は全ての病院/医師をランク付けし、病院と医師の作るランク付けに同着は無いものとします2。

上手く行かない例いくつか

一目見ただけでは、安定マッチングが必ず存在するかさえ分かりません！ ただ、不安定な病院と医師のマッチングが存在することは確かです。例えば Dr. Quincy, Dr. Rotwang, Dr. Shephard という三人の医師 (小文字で表す) と Arkham Asylum, Bethlem Royal Hospital, County General Hospital という三つの病院 (大文字で表す) があり、それぞれを次のようにランク付けしたとします: \[ \begin{array}{cccc} q & r & s \\ \hline A & C & A \\ C & A & B \\ B & B & C \end{array} \quad \begin{array}{cccc} A & B & C \\ \hline r & s & q \\ q & q & r \\ s & r & s \end{array} \]

このときマッチング \(\lbrace Aq, Br, Cs \rbrace\) は不安定です。なぜなら Arkham は Dr.Quincy よりも Dr.Rotwang を受け入れたがっていて、 Dr. Rotwang は Bedlam よりも Arkham で働きたがっているからです。つまりこのマッチングでは \((A, r)\) が不安定ペアです。

適当なマッチングから初めて、不安定ペアを貪欲に解消していって少しずつ解に近づくというアルゴリズムを考えるかもしれません。しかし残念ながら、不安定ペアを取り除くと新しく不安定ペアができてしまうことがあります。さらに、この段階的な "改善" が無限ループを起こす場合があります。例えば先ほどの不安定なマッチング \(\lbrace Aq, Br, Cs \rbrace\) から始めて次のように (矢印の上に示した) 不安定ペアを交換して解消していくと、最初のマッチングに戻ってきます3: \[ \lbrace Aq, Br, Cs \rbrace \overset{Ar}{\rightarrow} \lbrace Ar, Bq, Cs \rbrace \overset{Cr}{\rightarrow} \lbrace As, Bq, Cr \rbrace \overset{Cq}{\rightarrow} \lbrace As, Br, Cq \rbrace \overset{Aq}{\rightarrow} \lbrace Aq, Br, Cs \rbrace \]

あるいは、次に示す多段階の貪欲アルゴリズムを考えるかもしれません: 各反復でまずマッチしていない病院がマッチしていない中で一番ランクの高い医師を獲得し、次にマッチしていない医師がマッチしていない中で一番ランクの高い病院からの勧誘を承諾するというものです。反復ごとに最低でも一人の新しい病院と医師のペアが作られることを示すのは難しくないので、このアルゴリズムはマッチングを計算します。先ほどの例を入力すると、最初の反復で安定マッチング \(\lbrace Ar, Bs, Cq \rbrace\) が得られます！しかし、次の入力を考えてみてください: \[ \begin{array}{cccc} q & r & s \\ \hline C & A & A \\ B & C & B \\ A & B & C \end{array} \quad \begin{array}{cccc} A & B & C \\ \hline q & q & s \\ s & r & r \\ r & s & q \end{array} \]

最初の反復で Dr.Shephard は Country からのオファーを受け入れ、 Fr.Quincy は (Arkham からのオファーを断って) Bedlam からのオファーを受け入れます。この結果 Dr.Rotwang と Arkham がマッチせずに残ります。よって二回目の反復でこの両者がマッチされ、マッチング \(\lbrace Ar, Bq, Cs \rbrace\) が出力されます。残念ながらこのマッチングでは Arkham と Dr. Shephard がお互いを現在のマッチ相手よりも好んでいるので、このマッチングは不安定です。

Boston Pool と Gale-Shapley のアルゴリズム

1952年、NRMP はインターンの割り当てにおいて「Boston Pool (ボストンプール)」アルゴリズムを利用することを決定しました。この名前は以前に同じアルゴリズムが Boston のとある地域手形交換所で使われていたことに由来します。それから 10 年後、David Gale (デイヴィッド・ゲール) と Lloyd Shapley (ロイド・シャープレー) は Boston Pool のアルゴリズムを一般化したものを提案し、詳細な解析を行いました。その結果として、このアルゴリズムが常に安定マッチングを計算することを証明しています。このとき Gale と Shapley は大学入試の比喩を使いました。

本質的に同じアルゴリズムは 1972 年に Elliott Peranson (エリオット・ペランソン) によって医学校の入試のために開発されています。また同様のアルゴリズムは様々なマッチング市場で利用されており、例えばフランスにおける学部教員の雇用、合衆国における経済学 Ph.D. の雇用、ドイツにおける大学入試、ニューヨークとボストンにおける公立校の入試、米海軍の船員に対する宿舎割り当て、そして腎臓のマッチングプログラムに使われています。

Shapley は 2012 年に安定マッチングに関する研究でノーベル賞を受賞しました。共同受賞者は Shapley の研究を大きく拡張し、現実世界への応用を示した Albin Roth (アルヴィン・ロス) です (Gale は 2008 年に亡くなっていたので、一緒に賞を受賞することはできませんでした)。

Gale-Shapley のアルゴリズムは、最後に示した上手く行かない貪欲アルゴリズムと同じように、反復ごとに少しずつマッチングを作成していきます。各反復は二つのステージからなります:

この処理を反復すると全ての医師はランク付けに従って一番良い病院からのオファーを受けることになります4。このアルゴリズムを簡単に言うと、病院は貪欲にオファーを出し、医師はオファーを貪欲に受け入れるということです。双方が貪欲になるこの戦術が上手く行く鍵は、医師がより良いオファーを受け取った場合に現在持っているオファーを断れる点です。

例えば、四人の医師 (Dr. Quincy, Dr. Rotwang, Dr. Shephard, and Dr. Tam) と四つの病院 (Arkham Asylum, Bethlem Royal Hospital, County General Hospital, and The Dharma Initiative) が双方を次のようにランク付けしたとします: \[ \begin{array}{cccc} q & r & s & t \\ \hline A & A & B & D \\ B & D & A & B \\ C & C & C & C \\ D & B & D & A \end{array} \quad \begin{array}{cccc} A & B & C & D \\ \hline t & r & t & s \\ s & t & r & r \\ r & q & s & q \\ q & s & q & t \\ \end{array} \] この入力に対する Gale-Shapley のアルゴリズムの実行例は次のようになります:

  1. Arkham が Dr. Tam にオファーを出す。Dr. Tam はこのオファーを受け入れる。
  2. Bedlam が Dr. Rotwang にオファーを出す。Dr. Rotwang はこのオファーを受け入れる。
  3. County が Dr. Tam にオファーを出す。 Dr. Tam は Arkham からのオファーを断って、このオファーを受け入れる。
  4. Dharma が Dr. Shephard にオファーを出す。Dr. Shephard はこのオファーを受け入れる (ここから先マッチしていない医師と病院の組が一つだけになるので、処理に恣意性がなくなる)。
  5. Arkham が Dr. Shephard にオファーを出す。Dr. Shephard は Dharma からのオファーを断って、このオファーを受け入れる。
  6. Dharma が Dr. Rotwang にオファーを出す。Dr. Rotwang は Bedlam からのオファーを断って、このオファーを受け入れる。
  7. Bedlam が Dr. Tam にオファーを出す。Dr. Tam は County からのオファーを断って、このオファーを受け入れる。
  8. County が Dr. Rotwang にオファーを出す。Dr. Rotwang はこのオファーを断る。
  9. County が Dr. Shephard にオファーを出す。Dr. Shephard はこのオファーを断る。
  10. County が Dr. Quincy にオファーを出す。Dr. Quincy はこのオファーを受け入れる。

10 回目の反復が終わると暫定的な全てのオファーが受け入れられ、アルゴリズムはマッチング \(\lbrace As, Bt, Cq, Dr \rbrace\) を出力します。このマッチングが安定であることは総当たりで確認できます (自分でやってみるべきです)。ここで注目してほしいのが、ランクが一位の病院に雇われた医師は一人もおらず、ランクが一位の医師を雇った病院も一つもない点です。さらに Country にいたっては 三位にランク付けした病院に雇われています。しかしそれでもこのマッチングは安定です。またこの入力に対する安定マッチングはこれだけではなく、例えば \(\lbrace Ar, Bs, Cq, Dt \rbrace\) も安定です。

実行時間

このアルゴリズムの実行中に出されるオファーの数を数えるのは比較的簡単です (なので最初にやってしまいます)。全ての病院は全ての医師に対して最大 1 回のオファーを出します。よって全体で \(n^{2}\) 個のオファーが出されます。

オファーの数ではなくて実際の実行時間を解析するには、アルゴリズムをさらに細かく規定していく必要があります。ランク表はどのように与えられる？ ある病院がマッチしていないことをどうやって判断する？ マッチしていない病院を見つけるにはどうすれば？ 暫定的なマッチングをどうやって保存すれば良い？ 医師にとって今のマッチと新しいオファーのどちらがいいかをどうやって判断する？ そして最も基本的なこととして: 医師と病院をどう表す？

医師と病院を表す一つの方法は、医師と病院を \(1\) から \(n\) の整数を使って表し、ランク表を二つの配列 \(\mathit{Dpref}[1..n, 1..n]\) と \(\mathit{Hpref}[1..n, 1..n]\) を使って表すというものです。ここで \(\mathit{Dpref}[i,r]\) は \(i\) 番目の医師が \(r\) 番目にランク付けする病院を表し、\(\mathit{Hpref}[j,r]\) は \(j\) 番目の病院が \(r\) 番目にランク付けする医師を表します。入力がこの形だとすれば、 Boston Pool のアルゴリズムは各オファーの処理を定数時間で行うことができ、それ以外に前処理が少しあるだけなので、全体の実行時間は \(\pmb{O(n^{2})}\) となります。残りの詳細は簡単な練習問題として残しておきます。

もう少し難しい練習問題としては、アルゴリズムが終了するまでに \(\Omega(n^{2})\) 回のオファーが必ず生じるような入力 (とオファーを出す病院の順番) を作る問題があります。この問題には答えがあることから、最悪ケースで \(O(n^{2})\) という実行時間の上界は厳密です。

正しさ

いったいどうしてこのアルゴリズムは正しいのでしょうか？ このアルゴリズムが安定マッチングを計算すること、さらに言えばそもそもアルゴリズムが停止して、出力が完全なマッチングであることだって、証明無しには分かりません。

医師が一度でもオファーを受け取ると、それ以降その医師は暫定的なマッチを持ち続けます。逆にマッチされていない医師がいる場合にはそれまでにどの病院もその医師にオファーを行っておらず、全ての医師にオファーを出した病院がないことが分かります。したがってこのアルゴリズムは (最大で \(n^{2}\) ラウンドの後に) 停止し、そのとき全ての医師と病院がマッチされることが分かります。つまり、Gale-Shapley のアルゴリズムは医師と病院の間の完全なマッチングを計算します (ヒュー！)。後はこのマッチングが安定であることを示すだけです。

このアルゴリズムが最終的に医師 \(\alpha\) と病院 \(A\) をマッチさせた場合に、\(\alpha\) が \(A\) よりも \(B\) を高くランク付けしていたとします。全ての医師は受け取ったオファーの中で一番いいものを選ぶことから、\(\alpha\) は \(A\) よりも良いオファーを受け取っていません。特に、\(\alpha\) は \(B\) からのオファーを受け取っていません。一方 \(B\) は最終的なマッチ相手 \(\beta\) を選ぶまでにそれよりランクの高い医師全員にオファーを出していることから、\(B\) にとって \(\alpha\) は \(\beta\) よりもランクが下です。したがって \((\alpha, B)\) は不安定ペアではありません。以上より、アルゴリズムが出力するマッチングに不安定ペアはありません: つまり、安定です！

最適性！

驚くべきことに、Gale-Shapley アルゴリズムの正しさの証明は各反復でオファーを出す病院の選択に依存していません。実は、各反復でオファーを出す病院をどのように選んだとしても、アルゴリズムは必ず同じマッチングを計算します！

病院 \(A\) と医師 \(\alpha\) をマッチさせる安定マッチングが存在する場合、\(\alpha\) は \(A\) に対して適合 (feasible) であると言うことにします。このとき、次の命題が成り立ちます。

命題 4.7 Gale-Shapley のアルゴリズムにおいて、病院 \(A\) のオファーは \(A\) に対して不適合な医師によってのみ断られる。

証明 反復の回数に関する帰納法で示す。アルゴリズムのある反復で、医師 \(\alpha\) が病院 \(A\) からのオファーを断って病院 \(B\) のオファーを受け入れたとする。オファーを断ったことから、\(\alpha\) は \(A\) よりも \(B\) を高くランク付けしている。また \(B\) のランク付けで \(\alpha\) よりも高い順位にある医師は全てこれまでの反復で \(B\) からのオファーを断っており、帰納法の仮定から、そのような医師は全員 \(B\) に対して不適合である。

\(\alpha\) と \(A\) をマッチさせる (同じ医師と病院の間の) 任意のマッチングを考える。 \(\alpha\) が \(A\) よりも \(B\) を高くランク付けしていることは見た。もし \(B\) が今のマッチ相手より \(\alpha\) を高くランク付けするなら、このマッチングは不安定である。そうでなくて \(B\) が今のマッチ相手よりも \(\alpha\) を低くランク付けするなら、(前の段落の議論より) その相手は \(B\) に対して不適合であり、マッチングは不安定となる。したがって \(\alpha\) と \(A\) をマッチさせるような安定マッチングは存在せず、\(\alpha\) は \(A\) に対して不適合である。 \(\Box\)

さらに、\(\pmb{\mathit{best}(A)}\) で病院 \(A\) に対して適合な医師の中で \(A\) のランク付けが最上位の医師を表すことにします。命題 4.7 から、任意の病院のランク付けにおいて最終的なマッチ相手よりもランクが上にある医師はその病院に対して不適合であることが言えるので、次の命題は明らかです。

系 4.8 任意の病院 \(A\) に対して、Gale-Shapley のアルゴリズムは \(A\) と \(\mathit{best}(A)\) をマッチさせる。

言い換えると、Gale-Shapley のアルゴリズムが計算するのは安定マッチングの中でも病院から見て最良のものであるということです。さらに、このマッチングは医師から見ると最悪のものであることが示せます！ \(\pmb{\mathit{worst}(\alpha)}\) で医師 \(\alpha\) に対して適合な病院の中でランク付けが最下位の病院を表すことにします。

系 4.9 任意の医師 \(\alpha\) に対して、Gale-Shapley のアルゴリズムは \(\alpha\) と \(\mathit{worst}(\alpha)\) をマッチさせる。

証明 Gale-Shapley のアルゴリズムが医師 \(\alpha\) を病院 \(A\) にマッチさせたとする。 \(A = \mathit{worst}(\alpha)\) を示せばよい。 \(A\) が \(\alpha\) ではない別の医師 \(\beta\) とマッチしている任意の安定マッチングを考える。一つ前の系から、\(A\) は \(\beta\) よりも \(\mathit{best}(A) = \alpha\) を高くランク付けする。マッチングが安定なことから、\(\alpha\) は \(A\) よりも現在のマッチ相手を高くランク付けしていなければならない。この議論は任意の安定マッチングに適用できるので、\(\alpha\) は \(A\) 以外の全ての適合な病院を \(A\) よりも高くランク付けする。すなわち \(A = \mathit{worst}(\alpha)\) である。 \(\Box\)

Lester Dubins (レスター・デュビンズ) と David Freedman (デイビット・フリードマン) によって 1981 年に示されたこの二つの系からの帰結によると、医師は自分のランク付けを偽ることでマッチング結果を改善できますが、病院にはできません (ただし複数の病院が結託すればその病院の一部のマッチングを改善できます)。このこともあって、National Residency Matching Program は今までの説明とは逆の、新米医師からランク付けに沿ってオファーを出して、病院がそれを受け入れるというアルゴリズムを 1998 年から採用しています。この方法では医師にとって最良、病院にとって最悪の安定マッチングとなります。実際のデータでは、この反転で生じるマッチングの変化は 1 % 以下です。また私の知っている限り、このアルゴリズムの変更で生じる患者への影響は誰も手を付けていない問題です。

  1. アメリカの (少なくとも情報科学の) アカデミアにおける求人市場でも似たようなギャンブルが生じます。早くも二月から決断のための締め切りが二週間の勧誘を開始する機関もあれば、三月まで面接も始めない機関もありますし、悪名高い MIT のように五月になって全ての面接が終了するまで全ての学部が一切のオファーを行わない機関もあります。言うまでもなく、勧誘とその決断の締め切りが統一されていないのは求職者と機関にとって大きなストレスです。似たような理由から、1965 年以降アメリカの大学は 4 月 15 日という共通の日付を将来の大学院生の経済的支援 (および入学) の申し込みを受け付ける締め切りとしています。[return]

  2. 現実ではほとんどの病院は複数のインターンを募集し、医師/病院は病院/医師の一部に対してだけランク付けを行い (この例を練習問題で見ます)、医師の数より募集されるインターンの方が多くなります。そのため問題はもっと複雑になります。[return]

  3. この例は Donald Knuth によって発見されました。[return]

  4. Boston Pool のアルゴリズムは Gale-Shapley のアルゴリズムの特殊ケースであり、オファーを特定の順番で出すようにしたものです。一言で言うと、次にオファーを出す病院は「まだオファーを断っていない医師の中で一番ランクが高い医師からのランク付けが一番高い病院」と決まっています。この方法だと次にオファーを出す病院がランク表全体に依存するので、アルゴリズムは必ず中央機関によって実行される必要があります。これに対して Gale-Shapley のアルゴリズムはランク表全体を事前に知っておく必要がなく、さらに言えば各病院/医師が事前にランク付けを完成させる必要さえありません。実行中に出されるクエリに対して一貫して答えるなら、それだけでアルゴリズムは正しく動きます。[return]

広告
このページの文章はテキストゆれないくんを使って校正されました。