Algorithms for Stable Matching Problems toward Real-World Applications

2021年度研究会推薦博士論文速報
［アルゴリズム研究会］

濱田浩気
（日本電信電話（株）NTT社会情報研究所 主任研究員）

邦訳：現実世界での応用に向けた安定マッチング問題のアルゴリズム

■キーワード
アルゴリズム理論／計算複雑さ／安定結婚問題

【背景】世の中にはマッチングを求めたい場面が多い
【問題】実用の際に要望されるさまざまな条件付きの問題の難しさは不明
【貢献】いくつかの条件下の問題の難しさの解明

　生徒の学校への配属や大学での学生の研究室配属のように，2つの集合間で割り当て（マッチングと呼ぶ）を決めたい場面は多くある．安定マッチング問題は，各参加者がもう一方の集合内の参加者を好みの順に順位付けしているときに，どの参加者の2人組も現在の割り当てを壊す動機を持たないという，安定性と呼ばれる良い性質を持つマッチングを求める問題の総称である．

　安定マッチング問題の基本形に対しては，常に安定マッチングが存在してその1つを効率良く計算する方法（アルゴリズムと呼ばれる）が知られている．このような，良い性質を持つマッチングを効率良く計算できるという実用性の高さから，安定マッチング問題はボストンの高校配属や日本の研修医の病院配属にも使われている．

　安定マッチング問題の現実世界への応用をさらに進める際には，たとえばカップルを近くの病院に配属させたい，などのさまざまな追加の条件が望まれる．しかし条件次第で安定マッチングが存在しなかったり効率的な計算が難しかったりすることがある．そこで本研究ではさまざまな条件付きの安定マッチング問題の難しさの解明を目指し，以下の3つの観点から安定マッチング問題のアルゴリズムの研究を行った．

1．できるだけ安定なマッチングを求める問題
　これまでに提案された安定マッチング問題の多くでは，安定でできるだけ多くの人がマッチするマッチング，のように安定マッチングの中で条件を満たすものを求めていた．しかし，応用によっては安定性より別の条件を優先したい場合がある．たとえば，研究室配属ではいくらマッチングが安定であっても一部の研究室に学生が偏っては困る．そこで，偏りが一定以下でできるだけ安定なマッチングを求める問題の定式化や，効率的なアルゴリズムの研究を行った$${^{1），2）}}$$．

2．物理的制約下の安定マッチング問題
　現実世界では物理的な制約によりマッチングを実現できない場合がある．たとえば，配線同士の交差が許されないような場合である．このような制約を定式化して，参加者が平面上に配置されているときに，割り当てられた参加者同士を結ぶ線分が交差しないような安定マッチングを求める問題が考えられている．本研究ではこの問題を拡張したいくつかの問題を考え，効率的なアルゴリズムの提案や効率的に解くことが難しいことの証明を行った$${^{3）}}$$.

3．耐戦略性を持つアルゴリズム
　安定マッチング問題に対するアルゴリズムの性質の1つに，耐戦略性と呼ばれるものがある．耐戦略性は，どの参加者も希望順位を偽ってより望ましい結果を得ることができないという性質である．たとえば研究室配属を耐戦略性を持つアルゴリズムで行う場合は，あえて第2希望の研究室を第1希望と書いても得をしないため，学生は安心して正直な希望順位を提出することができる．本研究ではいくつかの拡張問題に対して耐戦略性を持つアルゴリズムの提案やアルゴリズムが存在しないことの証明を行った$${^{4）}}$$．

　本研究ではこれら3つの観点からの研究により，さまざまな条件下での安定マッチング問題の計算の難しさの解明に貢献できたと考えている．

参考文献
1）Hamada, K., Iwama, K. and Miyazaki, S. : An Improved Approximation Lower Bound for Finding Almost Stable Maximum Matchings, Inf. Process. Lett. 109(18): 1036-1040 (2009).
2）Hamada, K., Iwama, K. and Miyazaki, S. : The Hospitals/Residents Problem with Lower Quotas, Algorithmica 74(1): 440-465 (2016).
3）Hamada, K., Miyazaki, S. and Okamoto, K. : Strongly Stable and Maximum Weakly Stable Noncrossing Matchings, Algorithmica 83(9): 2678-2696 (2021).
4）Hamada, K., Miyazaki, S. and Yanagisawa, H. : Strategy-Proof Approximation Algorithms for the Stable Marriage Problem with Ties and Incomplete Lists, ISAAC 2019: 9:1-9:14.

（2022年5月31日受付）
（2022年8月15日note公開）

ー ー ー ー ー ー ー ー ー ー ー ー ー ー ー ー ー ー
　取得年月日：2022年3月
　学位種別：博士（情報学）
　大学：京都大学
　正会員
ー ー ー ー ー ー ー ー ー ー ー ー ー ー ー ー ー ー

推薦文［コンピュータサイエンス領域］アルゴリズム研究会
卒論生の研究室配属のようなシステムをモデル化した組合せ問題の一つとして，安定マッチング問題があります．本論文では，利用局面に応じて修正を施したいくつかの問題に対し，効率的なアルゴリズム設計や計算困難性に関する成果を得ています．得られた成果はAlgorithmica，IPL，ESA，ISAACといった国際的に評価の高い論文誌や国際会議で発表しています．

研究生活　　私は修士課程を修了して一般企業に就職後，会社員をしながら博士課程に進学した．研究テーマの候補としては，会社での研究と修士課程で研究していた安定マッチング問題の2つを考えた．選択の決め手は修士課程からお世話になっていた先生にご相談に伺ったところ受け入れてもかまわないと言ってくださったことと，安定マッチング問題がとてもおもしろいことであった．

進学後は，会社での研究活動と並行して博士課程の研究や執筆を進める必要があった．ある程度の困難は覚悟をしていたつもりであったが，なかなかまとまった時間を確保できない中での研究はやはり大変であった．それでも研究は楽しく，また鍛えていただける貴重な機会を得られ，進学することにしてよかったと思う．

最後に，この場を借りて博士課程でお世話になった皆様にあらためてお礼申し上げたい．多くの方に助けていただいたおかげでなんとか修了することができた．