文献

J-GLOBAL ID：201602218370461602   整理番号：16A0456217

ネットワーク型交渉ゲームの安定化アルゴリズム

著者 (5件)： 伊藤健洋 (東北大) ,  垣村尚徳 (東大) ,  神山直之 (九大) ,  小林佑輔 (筑波大) ,  岡本吉央 (電通大)
資料名： 情報処理学会研究報告(Web)  (IPSJ Technical Report (Web))
巻： 2016  号： AL-157  ページ： VOL.2016-AL-157,NO.3 (WEB ONLY)  発行年： 2016年02月28日 
JST資料番号： U0451A  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： ネットワーク型環境における交渉問題をゲーム理論的に研究する。そのような状況で安定解が存在すると常に言えるわけではないため,ネットワークに修正を加えて,安定解が存在するようにしたい。そのような修正は最小限に留めたいので,考える問題はグラフ上の組合せ最適化問題となる。過去の研究において,辺削除については,問題がNP困難になることが示されていた。本研究では,その他の可能な変更,つまり,辺追加,点削除,点追加に関して,問題が多項式時間で解けることを証明する。また,重み付きバージョンにおいて,辺追加と点削除がともにNP困難となることを証明する。(著者抄録)

シソーラス用語： *ゲーム理論 ,  *折衝 ,  *ビジネスゲーム ,  ネットワーク ,  組合せ最適化問題 ,  NP困難 ,  *アルゴリズム
準シソーラス用語： 交渉 ,  *交渉ゲーム ,  ネットワークゲーム ,  多項式時間アルゴリズム

分類 (1件)： ゲーム理論  (KA03060T)

引用文献 (27件)：

• Ahmadian, S., Sanita, L. and Hosseinzadeh, H.: Stabilizing network bargaining games by blocking players, Proceedings of 18th IPCO (2016). To appear.
• Aziz, H. and de Keijzer, B.: Shapley meets Shapley, Proceedings of 31st STACS, pp. 99-111 (2014).
• Bachrach, Y., Elkind, E., Meir, R., Pasechnik, D. V., Zuckerman, M., Rothe, J. and Rosenschein, J. S.: The cost of stability in coalitional games, Proceedings of 2nd SAGT, pp. 122-134 (2009).
• Bateni, M., Hajiaghayi, M., Immorlica, N. and Mahini, H.: The cooperative game theory foundations of network bargaining games, Proceedings of 37th ICALP, Part I, pp. 67-78 (2010).
• Berge, C.: Sur le couplage maximum d’un graphe, Comptes Rendus Hebdomadaires des S?ances de l’Acad?mie des Sciences [Paris], Vol. 247, pp. 258-259 (1958).

タイトルに関連する用語 (4件)： 交渉 ,  ゲーム ,  安定化 ,  アルゴリズム