理化学研究所 革新知能統合研究センター (AIP) 会議室３
〒103-0027 東京都中央区日本橋1-4-1 日本橋一丁目三井ビルディング 15階
Shunya Noda (Stanford University)
Large Matching in Large Market with Flexible Supply
We study truthful mechanisms that achieve a large size of matching (expected number of agents matched to some objects) in an environment where the planner can decide which and how many objects to provide subject to linear upper bound constraints. Naïve extensions of the classical serial mechanisms may generate an arbitrarily small matching in such environments. Assuming the market to be large (in that the variety of objects is fixed but the capacity to be large), we establish several mechanisms that have a constant guarantee for the size achieved. As a main result, we propose the adaptive parallel polymatroid serial mechanism, which (i) is not too computationally difficult to implement, (ii) achieves 1-1/e ≈ 63.2% of the maximum feasible size even in the worst case, and (iii) keeps agents' choice sets as large as possible.
Public events of RIKEN Center for Advanced Intelligence Project (AIP)Join community