Talk by Shunya Noda: Large Matching in Large Market with Flexible Supply, Stanford University

Mon, 06 Aug 2018 16:00 - 17:30

理化学研究所 革新知能統合研究センター (AIP) 会議室3

〒103-0027 東京都中央区日本橋1-4-1 日本橋一丁目三井ビルディング 15階

5 participants

Registration is closed

Get invited to future events

Free admission


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.

About this community


Public events of RIKEN Center for Advanced Intelligence Project (AIP)

Join community