Cardinal-Utility Matching Markets: From Tractability to Intractability ... and Back!

Note: The room was changed to Packard 101!

Abstract

For a mechanism to be highly impactful, it must have both good game-theoretic properties and computational efficiency. A poster child in this respect is the Gale-Shapley work (1962) on stable matching. This talk concerns cardinal-utility matching markets, for which the most prominent mechanism was due to Hylland and Zeckhauser (1979); this pricing-based mechanism has all the game-theoretic properties one could ask for. However, recent work has established it to be computationally intractable in theory and practice.

This talk will summarize several papers which:

• Established intractability.
• Proposed a replacement mechanism based on Nash bargaining.
• Established its game-theoretic and computational properties and gave evidence that there may not be a better alternative.

Based on these (1, 2, 3, 4, 5) and other papers.

Bio

Vijay Vazirani is Distinguished Professor at the University of California, Irvine. A description of his research appears in the citation of his 2022 INFORMS John von Neumann Theory Prize. Recently he completed a proof of the Micali-Vazirani maximum matching algorithm, over four decades after the publication of the algorithm itself. His most recent book (co-edited), Online and Matching-Based Market Design, appeared in July 2023.