Center for Advanced Intelligence Project

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.