表題番号：2004A-122 日付：2005/03/25
研究課題最適化協力ゲームの数学的構造および解の計算量に関する研究
研究者所属（当時） 資格 氏名
（代表者） 商学学術院 助教授 毛利　裕昭
研究成果概要
いままでの特定課題の研究成果を受けた形での研究である。
研究題名に入っている「数学的構造」とは、大きく以下の
ように考えられる。まず、離散最適化問題を考える上での
グラフのトポロジカルな構造、そしてそれ以外のグラフの
属性（距離、容量等）が第一にあげられる。そして、離散
最適化問題を離散最適化関数と見なした時、良いとされる
構造は、計算量の理論の視点から（強）多項式時間で解ける
構造を持つこと、特に劣モジュラ性（さらに広くは離散凸性）
の構造を持つことである。

こういった性質を調べることはゲーム理論の特性関数の構造
を研究するに当たり、重要な役割を果たす。

今年度の成果としては、以前から研究しているネットワーク・
デザイン問題および、ネットワーク・デザイン問題と施設配置
問題を合成した問題について、グラフが森（木を含む）、
直並列枝グラフについて研究を進め、多項式時間で解ける
グラフ構造に関していくつかの定理を証明し、国際学会等で
論文発表した。

　また、ゲームの確率過程の要素についても研究し、それが
情報ネットワークの制御や数理ファイナンスへの応用につながる
ということも示し、確率過程ゲームまで含めた幅の広い研究を
進めている。
　
　さらに、こうした数学モデルが現実問題への広く応用されるため
の指針となる論文も発表した。