インセンティブサイエンスの算法セミナー：マッチングと繰り返しゲームのフロンティア

インセンティブサイエンスの算法セミナー（発表は日本語で行われます）．

1件目はスタンフォード大学経済学研究科博士課程の野田俊也氏で，割当人数に複雑な制約が課される場合のマッチング問題を扱います．

2件目はスタンフォード大学ビジネススクール准教授である菅谷拓生氏で，ミクロ経済学／ゲーム理論の主要トピックの１つである繰り返しゲームの，計算機科学者向けのセミナーになります．とくに繰り返しゲームの均衡を求める問題は動的計画法と深く関係することが知られており，今後も計算機科学の技術の貢献が期待される分野です．

14:00～15:00
野田 俊也 (Shunya Noda) (Stanford University)
Truthful Large-Size Matching Mechanism for Large Markets with General Monotone and Convex Constraints

When all objects are not acceptable to all gents, the size of matching achieved by mechanisms can be an important policy concern. In this paper, I consider matching problems with a general class of constraints, and study truthful mechanisms that have a large guaranteed size ratio (defined as the worst case ratio of the expected size achieved by the mechanism to the size of maximum matching). A naive extension of the classical random serial dictatorship mechanism does not have non-trivial guarantees. Furthermore, when we have general constraints, finding a (first-best) maximum matching itself is NP-hard. However, in a large market, the preset random serial dictatorship mechanism established in this paper achieves the guaranteed size ratio close to 1-1/e (about 63.2%), which is the best possible ratio guaranteed by truthful mechanisms.

15:30～17:30
菅谷拓生 (Takuo Sugaya) (Stanford University)
Computational Issues of Repeated Games

We will talk about computational issues in repeated games. After explaining an algorithm by Abreu, Pearce, and Sttachetti (APS, 1990) for repeated games with public monitoring, we will survey the recent developments in the following three dimensions. First, Abreu and Sannikov (2014) and Abreau, Brooks, and Sannikov (2017) simply APS algorithm in perfect monitoring, taking computational feasibility seriously. Second, Sugaya and Wolitzky (2017a and 2017b) offer an upper bound of equilibrium payoffs in private monitoring. Third, Phelan and Skrzypacz (2012) and Kandori, Obara, Iwasaki, and Yokoo (2014) offer a verification of equilibria with automaton strategies in private monitoring.