Computation in a Strategic World

Duke Computer Science Colloquium
Speaker Name
Yang Cai
Date and Time
Lunch served at 11:45 am

Engineering complex systems become 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, the design of road networks, spectrum auctions, online markets, and learning with crowdsourced data. 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 combinatorial and convex optimization to design and analyze systems that are immune to strategic manipulations. As an application, I extend Myerson's celebrated characterization of the optimal single-item auction to multi-item settings. I will also touch upon my other work motivated by the study of strategic settings including a multi-player generalization of the min-max theorem, two-sided markets, and the connection between game theory and learning.

Short Biography

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. His Ph.D. thesis on algorithmic mechanism design was recognized by the MIT and the ACM SIGecom dissertation awards.

Debmalya Panigrahi