※　本セミナーでの報告後、『離散凸解析とゲーム理論』（田村明久著）が2009年11月に朝倉書店から出版されました。

　
 2009年6月13日、VCASIでは組み合わせ最適化、数理計画法がご専門の田村明久氏（慶応義塾大学理工学部数理科学科）を迎え、第13回VCASIセミナー「離散凸解析とゲーム理論」を開催した。参加者はVCASIフェローの宇井貴志氏（横浜国立大学経済学部）、神取道宏氏（東京大学経済学部）、小島武仁氏（Stanford大学経済学部）、安田洋祐氏（政策研究大学院大学）をはじめ、応用数学、ゲーム理論、コンピューターサイエンス、数理計画法、数理経済学、論理学などを専門とする実務家、若手研究者、大学院生、学部生などを中心に30名余りに及んだ。 
＜当日の発表資料＞

 　 発表の前半では、室田一雄氏、田村氏やその共同研究者らによって90年代中頃に産み出された「離散凸解析」と呼ばれる離散数学の新分野の背景と概要が紹介された。離散世界のマトロイド理論と連続世界の凸解析を融合することで成立する離散凸解析の枠組みによれば、離散関数に対しては（連続関数の場合とは対照的に）単一の離散凸性の定義を採用することは困難である。そのため、連続凸性と等価な様々な性質の内、いわゆる中点凸性に着目した場合に得られる離散L凸性といわゆる等近凸性に着目した場合に得られる離散M凸性が必要に応じて使い分けられてきた。現在のところ、離散凸解析のゲーム理論や数理経済学への応用においては、主にM凹関数が重要な役割を果たす。前半の最後に行われたのが、M凹関数の数学的、経済学的性質（凹拡張可能性、劣モジュラ性、単改良性、（粗）代替性など）についてのサーベイである。

＜第一部目次＞

離散凸解析とは
Mナチュラル凹関数の定義
層型凹関数
Mナチュラル凹関数の性質

　後半では、離散凸解析の社会科学への応用例として、ゲーム理論、特にマッチング理論における安定性の存在問題を扱った

Fujishige, S. and Tamura, A., (2007), "A two-sided discrete-concave market with bounded side payments: An approach by discrete convex analysis,'' Mathematics of Operations Research.

の紹介が行われた。近年では公立学校選択、臓器移植、研修医インターンといった数多くの実際の制度設計に活用されつつあるマッチング理論においては、参加者が他の参加者への（正当化されえる）嫉妬を感じずに済むという意味での安定性を持つ結果の実現がしばしば重要になる。古典的には

Gale, D. and Shapley, L. S., (1962), "College admissions and the stability of marriage," American Mathematical Monthly.
Shapley, L. S. and Shubik, M., (1971), "The assignment game I: the core," International Journal of Game Theory.

などが前者の結婚モデルや後者の割当モデルにおいて安定性を持つ結果の存在を証明した。Fijishige-Tamura(2007)は、離散凸解析の枠組みに立脚して、それらを含むはるかに一般化したマッチングモデルについて、安定性を持つ結果の存在を証明し、それを求めるためのアルゴリズムを提示した。

＜第二部目次＞

Shapley-Shubikの割当モデル
Mナチュラル凹関数を用いた割当モデル
Gale-Shapleyの結婚モデル
Mナチュラル凹関数を用いた結婚モデル
 

　発表と並行して進められた議論では、Fujishige-Tamuraモデルと類似した問題意識を持つ

Adachi, H., (2000), "A characterization of stable matchings," Economic Letters.
Hatfield, J. and Milgrom, P., (2005), "Matching with contracts,"American Economic Review.

との関係（特にFijishige-TamuraモデルのHatfield-Milgromモデルへの埋め込み可能性）、安定性と（それ以上に厳しい条件を課す）厳安定性の関係（特に両者が一致するための条件）、Fijishige-TamuraアルゴリズムとGale-Shapleyアルゴリズムの関係やFujishige-Tamuraモデルの更なる拡張可能性などについて意見が交わされた。

＜第三部目次＞

Fujishige-Tamuraの上下限制約付割当モデル
安定性と厳安定性の関係
ディスカッション


―――――――――――

田村先生より発表内容についての訂正文をいただきましたのであわせて御報告いたします。

＜訂正文＞
手付けに上下限がない場合は，「安定解＝厳安定解か」という話で成立するようなことを言ったのですが，実効定義域が{0,1}^E に含まれないときは成立しませんでした．発言内容を訂正します．

例えば，
E={i,j}
f_i(x) = 2x if x=0,1; otherwise -infinity
f_i(x) = 2x if x=0,1,2 ; otherwise -infinity

とします．x=1, s=0 は安定解になるのですが，厳安定ではありません．
なぜならば，s を微少量εだけ増やすと i の利得 はf_i[+ε](1)となり，
厳密に増加します．一方 f_i[0](1) < f_i[-ε](2)であり，jの利得も厳密に増加します．

私が勘違いを点は上にも現れていて，jにとって，動機制約を満たすためx <= 1という条件下では，x=1が最適ですが，この条件を外すとx=2が最適になる状況が起きてしまいます．