地域制約の下での戦略的操作不可能なマッチングメカニズム

橋本 直幸  後藤 誠大  上田 俊  岩崎 敦  安田 洋祐  横尾 真  
(FIT2013推薦論文)

誌名
電子情報通信学会論文誌 D   Vol.J97-D   No.8   pp.1336-1346
発行日: 2014/08/01
Online ISSN: 1881-0225
DOI: 
論文種別: 論文
専門分野: 情報ネットワーク
キーワード: 
マッチング,  学校選択,  下限制約,  戦略的操作不可能性,  

本文: PDF(745.5KB)
>>論文を購入


あらまし: 
マッチングとは,学生と学校,研修医と病院のように,二種類のエージェント間の望ましい組合せを求める問題を表現できる一般的な枠組みであり,学校選択制や研修医配属といった様々な応用例がある.従来は,学校に割り当てる学生数に関して,個別の学校に上限/下限といった制約を課す場合のみを考慮していた.しかし,現実の多くの問題では学校の集合(地域)に対する制約を課す場合がある.例えば,研修医と病院のマッチングにおいて,離島のような僻地にある複数の病院に対して一定数の研修医の配属を保証するために,その地域に対して下限を課すことが想定される.本論文では,個別の上限/下限制約に加え,そのような地域制約を考慮したマッチング問題を扱う.まず,地域制約の構造に制限がない場合に,その制約を満たすマッチングが存在するか否かを問う決定問題の計算量がNP完全であることを示す.次に,その構造を階層的な場合に限定し,地域下限制約及び個別の上限制約を同時に扱えるメカニズムを提案する.