ゲールとシャプレーの1962年アルゴリズムがマッチング市場を正直にした

デイヴィッド・ゲールとロイド・シャプレーは1962年、『College Admissions and the Stability of Marriage』をAmerican Mathematical Monthlyに発表した。彼らは、結婚や大学入学のような両側市場において、安定マッチング——どの二者のエージェントも互いにより強く望むことがない割り当て——が常に存在するかどうかを問うた。

彼らの答えは構成的であった。すなわち、一方が提案し他方が暫定的な申し出を保持する受諾保留アルゴリズム（deferred-acceptance algorithm）は、常に安定マッチングで終了する。同じ手続きは提案側に可能な限り最良の安定結果を与えるため、真の順位付けが提案側にとって支配戦略となる。

50年後、スウェーデン王立科学アカデミーは2012年経済学賞をシャプレーとアルヴィン・ロスに「安定配分の理論と市場設計の実践に対して」授与した。ロスは、安定性がどの実市場が生き残るかを説明することを示し、このアルゴリズムに基づいて研修医マッチング、学校選択、腎臓交換を再構築した。

受諾保留は全員に安定マッチを見つける

存在証明とアルゴリズムが、安定性を抽象的なものではなく利用可能なものにした。

真の選好リストが提案側の支配戦略となった。

設計者にレンズを与えた。安定した市場は生き残り、不安定な市場は崩壊する。

医療、教育、臓器交換における実践的な再設計を支えた。

市場を構築する前に、マッチングのメカニズムが安定かつ戦略的操作不可能（strategy-proof）であることを確認せよ。虚偽の報告が得になるなら、市場は操作で満ちる。正直さを最適にするアルゴリズムこそが市場設計である。

このアルゴリズムは、米国の研修医マッチング再設計、ボストンとニューヨークの学校選択、腎臓交換の連鎖のエンジンとなった——いずれもノーベル賞の授賞理由に挙げられている。ゲール＝シャプレーは今や市場設計、オペレーションズ・リサーチ、計算機科学における標準的な語彙である。