文献

J-GLOBAL ID：201402203133615660   整理番号：14A1239121

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

著者 (6件)： 橋本直幸 (九大 大学院システム情報科学府) ,  後藤誠大 (九大 大学院システム情報科学府) ,  上田俊 (九大 大学院システム情報科学府) ,  岩崎敦 (電通大 大学院情報システム学研究科) ,  安田洋祐 (政策研究大学院大) ,  横尾真 (九大 大学院システム情報科学府)
資料名： 電子情報通信学会論文誌 D(Web)
巻： J97-D  号： 8  ページ： 1336-1346 (WEB ONLY)  発行年： 2014年08月01日 
JST資料番号： U0473A  ISSN： 1881-0225  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

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

シソーラス用語： *マッチング ,  上限 ,  下限 ,  *制約条件 ,  *地域 ,  決定問題 ,  計算量 ,  NP完全問題 ,  階層構造 ,  機構 ,  集合論 ,  数学モデル ,  ゲーム理論 ,  *制約付最適化問題
準シソーラス用語： メカニズム

分類 (1件)： 数理計画法  (KA03030M)

引用文献 (10件)：

• A.E. Roth and M.A.O. Sotomayor, Two-Sided Matching: A Study in Game-Theoretic Modeling and Analysis (Econometric Society Monographs), Cambridge University Press., 1990.
• D. Gale and L.S. Shapley, “College admissions and the stability of marriage,” The American Mathematical Monthly, vol.69, no.1, pp.9-15, 1996.
• Y. Kamada and F. Kojima, “Stability and strategyproofness for matching with constraints: A problem in the Japanese medical match and its solution,” American Economic Review, vol.102, no.3, pp.366- 370, 2012.
• D. Fragiadakis, A. Iwasaki, P. Troyan, S. Ueda, and M. Yokoo, “Strategyproof matching with minimum quotas,” 2012. mimeo (An extended abstract version appeared in AAMAS, pp.1327-1328, 2012).
• R.W. Irving, D.F. Manlove, and S. Scott, “The stable marriage problem with master preference lists,” Discrete Applied Mathematics, vol.156, pp.2959-2977, 2008.

タイトルに関連する用語 (5件)： 地域 ,  制約 ,  戦略 ,  マッチング ,  メカニズム