Vijay Vazirani教授特邀讲座回顾：基数效用市场机制算法

 IIIS Distinguished Lecture

Vijay Vazirani教授特邀学术讲座

姚期智院长以Vijay Vazirani教授在理论计算机科学领域的开创性贡献为引，特别强调了其在算法博弈论和匹配理论中的里程碑式工作。随后，在全场期待的目光中，Vijay Vazirani教授开启了一场关于市场机制设计算法的精彩演讲。

Vijay Vazirani教授以经典的Gale-Shapley稳定匹配算法为切入点，深入剖析了市场机制设计与纳什均衡等核心问题，并分享了团队最新突破——Micali-Vazirani最大匹配算法的理论证明。2021级博士生迟舒乘感到：“这一系列研究精彩展现了理论严谨性与计算可行性之间的精妙平衡，生动诠释了理论计算机科学对现实市场设计的深远影响与强大推动力。”

在场师生与Vazirani教授积极互动，探讨了匹配市场机制的本质和应用可能性。2021级博士生尹龙晖表示：“Vijay Vazirani教授从基于基数效用的单向匹配市场问题出发，向我们讲解机制设计问题中强博弈论性质与解的高效计算的两大难点。然后他介绍了如何对性质优秀但计算困难的Hylland-Zeckhauser经典工作进行改进，使其尽可能兼顾机制的有效性与计算高效性。讲座拓展了我们的学科视野，对科研工作也有启发。”

4月18日，Vazirani教授以“A Theory of Alternating Paths and Blossoms, from the Perspective of Minimum Length”为题，在三个多小时的深度学术对话中系统呈现了其对Micali-Vazirani算法数十年的研究成果。这场高密度的学术盛宴让在场师生收益颇丰。

"这场讲座堪称科研精神的生动注脚。"2021级博士生谢添乐感慨道，“Vazirani教授在1980年初步完成了一般图最大匹配算法，经过40年的不断打磨，最终完成了其图论证明。这不仅展现了算法设计的智慧，也体现了科学家在探索真理道路上的坚持与不懈追求。”

图文 | 姜月亮

编辑 | 吕厦敏

审核 | 马雄峰