The Distinguished Lecture Series of School of Computing and Data Science, host distinguished scholars around the world who will share their expertise and insights in the areas of computer science, data science, artificial intelligence, and statistics.

Our second Distinguished Lecture, titled “Cardinal-Utility Matching Markets: From Tractability to Intractability … and Back!”, will be presented by Professor Vijay VAZIRANI, a Distinguished Professor at the University of California, Irvine.

Please find the event details below:

Date: 10 April, 2025 (Thurs)

Time: 11:30am – 12:30pm (Reception starts at 11:00am)

Venue: CB308, 3/F, Chow Yei Ching Building, HKU
Medium: English

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 lecture 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 lecture will summarise 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

Biography:

Professor Vijay VAZIRANI is a Distinguished Professor at the University of California, Irvine. Professor Vazirani was awarded the 2022 INFORMS John von Neumann Theory Prize for his fundamental and sustained contributions to the design of algorithms, including approximation algorithms, computational complexity theory, and algorithmic game theory, central to operations research and the management sciences. Recently he completed a proof of the Micali-Vazirani maximum matching algorithm, over four decades after the publication of the algorithm itself.

All are welcome to attend.