提携形成／最適化／利得配分の同時解決による協力ゲーム理論の再構築

点击翻译按钮获取中文摘要

平成25年度は, 昨年度から引き続き協力ゲーム理論における利得配分および提携構造形成を同時に解決するアルゴリズム, マッチング理論における制約付きマッチングのためのメカニズムについて研究した. 具体的には, 協力ゲーム理論については, locally constrained coalition form gamesというモデルに従い, 最適な提携構造(グループ分け)および安定な利得配分を計算するアルゴリズムを開発した. このモデルにおいて利用可能な提携は制限されており, 提案アルゴリズムは従来個別に解かれていた問題を同時に解決している. そのため従来手法にくらべ, より高速な計算が可能となっている. また, このアルゴリズムでは安定な利得配分であり計算が容易な解概念である弱εコア+を計算する. この研究成果に関して, 国際会議The 2013 IEEE/WIC/ACM Intemational Conference on Intelligent Agent Technologyおよび国内フォーラム第12回情報科学技術フォーラムにおいて発表し, 現在国際論文誌に投稿中である.また, 制約付きマッチング問題に関して, 従来手法を拡張し, 地域(病院もしくは学校の集合)に関して上限および下限制約が課される場合のマッチングメカニズムを開発した. マッチング理論は研修医配属問題や, 学校選択制等に応用されている研究分野である. 提案メカニズムは, 従来は人為的に割当数を調整する等して間接的にしか扱えなかった地域における割当数に関する制約を, 直接扱うことができる. そのため, 僻地の病院における研修医の確保など, より現実で重要な問題を扱えるようになった. 現在, これらの研究成果を国際論文誌, 国際会議に投稿中である.