『アルゴリズムデザイン』メモ

第1章の「結婚したくない相手がいる場合」で、確かにG-Sアルゴリズムで安定マッチングは得られるけど、ペア数はマックスにならないケースがあるという話がマーケットデザインにある。

もちろん、安定性と比べて、ペア数をどの程度重視すべきなのかは明らかではないでしょう。ただ、結婚市場における成立カップル数や、労働市場における就業者数のように、ペアの数自体が大きな意味を持つ市場は少なくありません。こうした問題意識のもと、筆者は安定性とペア数との間のトレードオフに関する研究を進めています。成果の一部として、上の例のように参加者の好みが似ているときに、トレードオフがより深刻になることが分かってきました。今後の進展にぜひご注目ください！

らしいです。