野田 俊也 (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.
菅谷拓生 (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.
Public events of RIKEN Center for Advanced Intelligence Project (AIP)Join community