Image
ISL events

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

Summary
Vijay Vazirani (Distinguished Professor, UC Irvine)
Packard 101
May
23
Date(s)
Content

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.

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.

This talk is hosted by the ISL Colloquium. To receive talk announcements, subscribe to the mailing list isl-colloq@lists.stanford.edu.