著者

岡本 吉央

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告アルゴリズム(AL) (ISSN:09196072)

巻号頁・発行日

vol.2002, no.70, pp.17-24, 2002-07-25

---

協力ゲーム理論において劣モジュラ性は非常に重要な性質であると認識されている.本論では,最小彩色ゲームと最小頂点被覆ゲームが劣モジュラ性を有する場合の特徴づけを示す.この特徴づけにより,与えられたグラフに対する最小彩色ゲーム/最小頂点被覆ゲームが劣モジュラであるかどうかを判定することが多項式時間で出来ることが分かる.それに関連して,ゲーム理論におけるシャプレイ値,および,付随するマトロイド構造についても述べる.Submodularity is considered as an important property in the field of cooperative game theory. In this report, we characterize submodular minimum coloring games and submodular minimum vertex cover games. These characterizations immediately show that it can be decided in polynomial time that the minimum coloring game or the minimum vertex cover game is submodular or not for a given graph. Related to these results, the Shapley values and the associated matroid structures are also investigated.