演讲人:
Vijay Vazirani University of California, Irvine
时间: 2025-04-17 14:00-2025-04-17 15:00
地点:Lecture Hall, FIT
内容:
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.