Thu, 23-May-2024 / 4:00pm / Packard 101
Note that the room has been changed to Packard 101!
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.
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.
Packard Building
Electrical Engineering Department
350 Jane Stanford Way
Stanford, CA 94305-9515
Thursdays, 4pm, Packard 202
