Understanding Computational Complexity in Mechanism Design 🧩
Explore how computational challenges impact the design of game theory mechanisms with insights from Jing Chen of MIT. Learn key concepts and recent developments in this fascinating intersection of computer science and economics.
Institute for Advanced Study
448 views • Aug 17, 2016
About this video
Jing Chen
Massachusetts Institute of Technology; Member, School of Mathematics
November 27, 2012
Some important mechanisms considered in game theory require solving optimization problems that are computationally hard. Solving these problems approximately may not help, as it may change the players’ rational behavior in the original mechanisms, leading to undesirable outcomes. This is particularly the case in combinatorial auctions.
I’ll present special cases of combinatorial auctions where approximation algorithms do lead to mechanisms that are both computationally efficient and economically well behaved. If time allows, I’ll also present conditions under which such mechanisms do not exist.
For more videos, visit http://video.ias.edu
Massachusetts Institute of Technology; Member, School of Mathematics
November 27, 2012
Some important mechanisms considered in game theory require solving optimization problems that are computationally hard. Solving these problems approximately may not help, as it may change the players’ rational behavior in the original mechanisms, leading to undesirable outcomes. This is particularly the case in combinatorial auctions.
I’ll present special cases of combinatorial auctions where approximation algorithms do lead to mechanisms that are both computationally efficient and economically well behaved. If time allows, I’ll also present conditions under which such mechanisms do not exist.
For more videos, visit http://video.ias.edu
Video Information
Views
448
Likes
5
Duration
01:48:55
Published
Aug 17, 2016