臨床研修マッチングで、順位を上げても受かりやすくなるわけではない理由

背景

臨床研修マッチングは、Gale-Shapleyの安定マッチングというアルゴリズムを用いて決定されている。
臨床研修マッチングには、中間報告というよく分からない文化があり、志望者の集まる受からなさそうな病院よりも、受かりそうな病院の志望順位を上げておかないと不利になってしまうという説が囁かれているがこれは正しくない。
マッチングに初めて参加する学生がそういった説を信じてしまうのならまだしも、先日自大学の臨床研修担当の先生が説明に来た際に同様のことを仰っており、この説を信じてしまう人が一定数いるのだと思わされた。
私自身は、このアルゴリズムについて初めて知った際に直感的にそのようなことは起きないだろうと思っていたものの、この説を厳密に否定するのは実は容易ではない。
以下にこの説を否定する。

直感的な説明

臨床研修マッチングの仕組みは、どういう順番で仮マッチを決めていったとしても最終的には同じ結果になるはずである。もしそうでなければ、〇〇大学の人は第一志望に受かりやすいとか、名前順が早いひとは受かりやすいとかが起こり得てしまう。

すなわち、全てのマッチング参加者の中であなたが一番最後に仮マッチを決める人（アルゴリズム図解でいうところの工藤さん）であったとしても結果は同じになる。
そうすればあなた自身は仮マッチなどという煩わしいことは考えずとも、純粋に合格ラインに達しているかどうかという点のみに着目して考えれば、志望順位など関係なく、マッチング結果が決まるということがご理解いただけるのではないだろうか。

問題定義

命題 $${P}$$を「ある病院$${H_1}$$と$${H_2}$$の2つを志望しているときに,$${H_1}$$の志望順位が$${H_2}$$の志望順位より高いときには$${H_1}$$にマッチし,$${H_2}$$の志望順位が$${H_1}$$より高い場合には$${H_2}$$にも$${H_1}$$にもマッチしないという組み合わせが存在する」と定義する.

ただし,マッチングに参加する人の総数を$${N}$$とし,$${i}$$番目の応募者を$${X_i}$$とする.$${X_1,X_2,\cdots,X_N}$$の順に、マッチングを行っていったときの最終的なマッチング結果を$${F(X_1,X_2,\cdots,X_N)}$$と定義する.
ある順列$${Y_1,Y_2}$$について,$${F(Y_1)}$$と$${F(Y_2)}$$が同じであるとき,$${F(Y_1)=F(Y_2)}$$と表すものとする.
$${j}$$を1以上の整数として,
病院$${H_j}$$が決める学生$${X_i}$$の希望順位を$${Q_j(i)}$$と定義する.
病院$${H_j}$$の定員を$${M_j}$$とする.

なお説明が面倒くさいので「仮マッチ」などの用語は定義なく用います.

証明

Gale-Shapleyの安定マッチングには,最終的なマッチング結果は、応募者の順番によらないという有名事実がある.これを補題1とする。

補題1より、任意の$${1\leq K \leq N}$$を満たす整数$${K}$$について$${X_K}$$と$${X_N}$$を入れ替えてもよい.
すなわち$${F(X_1,X_2,\cdots,X_N)\\=F(X_1,X_2,\cdots,X_{K-1},X_N,X_{K+1}, \cdots,X_{N-1},X_K)}$$
である.
ここで$${X_K}$$について命題$${P}$$が成立しないことを示す.

$${(i)}$$ 既に$${X_K}$$を除く$${N-1}$$人について,マッチングを行っている状態において,$${H_1}$$に仮マッチ者が$${M_1}$$人おり,全ての仮マッチ者$${a_1,a_2, \cdots,a_{M_1}}$$の希望順位$${Q_1(a_1),Q_1(a_2),\cdots,Q_1(a_{M_1})}$$が全て$${Q_1(a_{X_K})}$$よりも高いとき

$${X_K}$$は$${H_1}$$の志望順位を$${H_2}$$よりも高くしても、$${H_1}$$にマッチすることができないので不成立.

$${(ii)}$$ それ以外のとき

$${X_K}$$は$${H_2}$$の志望順位を$${H_1}$$よりも高くしたときに$${H_2}$$にマッチングできるかどうかに依らず,$${H_1}$$にマッチすることができるので不成立.

よって命題$${P}$$は否定される.