Speaker: Vijay Vazirani University of California, Irvine
Time: 2025-04-17 14:00-2025-04-17 15:00
Venue: Lecture Hall, FIT

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:
a. Established intractability.
b. Proposed a replacement mechanism based on Nash bargaining.
c. 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.

Short 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.