CS Colloquium
Speaker: Yang Cai
Title: Computation in a Strategic World
Host: Joan Feigenbaum
Abstract:
Engineering complex systems becomes even more challenging in the presence of strategic agents whose behavior is guided by their own incentives. Examples include important applications such as scheduling jobs in the cloud, auctions, online markets, sharing economy, and crowdsourcing platforms. How does one design a system so that the designer’s objective is achieved robustly despite the existence of strategic behavior?
In this talk, I will present a framework based on duality theory and combinatorial optimization to design and analyze systems that are immune to strategic manipulations. I will apply this framework to extend Myerson’s celebrated characterization of the optimal single-item auction to multi-item settings and design simple and approximately optimal trading mechanisms for online markets. I will also touch upon my other work motivated by the study of strategic behavior including a multi-player generalization of the min-max theorem, spectrum auctions, and the connection between game theory and learning.
Bio:
Yang Cai is a William Dawson Assistant Professor of Computer Science at McGill University. He received his Ph.D. in computer science from MIT and was a postdoctoral researcher at UC Berkeley. He did his undergraduate study at Peking University. Yang’s research interests include theoretical computer science, economics and computation, learning, statistics, and probability, as well as online algorithms.