Computational Complexity in Mechanism Design

Computer Science/Discrete Mathematics Seminar II
Topic:Computational Complexity in Mechanism Design
Speaker:Jing Chen
Affiliation:Massachusetts Institute of Technology; Member, School of Mathematics
Date:Tuesday, November 27
Time/Room:10:30am - 12:30pm/S-101
Video Link:https://video.ias.edu/csdm/chen2012Nov27

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.