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



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.


※ こちらのイベント情報は、外部サイトから取得した情報を掲載しています。
※ 掲載タイミングや更新頻度によっては、情報提供元ページの内容と差異が発生しますので予めご了承ください。
※ 最新情報の確認や参加申込手続き、イベントに関するお問い合わせ等は情報提供元ページにてお願いします。