Brief Introduction
Computational complexity and learning provide a fruitful perspective through which to study rational behavior and to design economic systems. Indeed, learning and computation is an integral part of economic activity as rational agents learn from their interaction and are ultimately computationally bounded, while economic systems are often complex and implemented on computational platforms such those enabled by the Internet. I will showcase important insights of complexity and learning theory to Economics focusing on solution concepts and mechanism design.
In the first part of the lectures, I will talk about the complexity of Nash equilibrium and other solution concepts, the intimate relationship between equilibria and linear programming, online learning and fixed points. I will define the class PPAD and overview the proof that Nash equilibrium is PPAD-complete, concluding with approaches for overcoming this computational intractability result.
In the second part of my lectures, I will turn to mechanism design, the “engineering side of Economics.” I will overview classic mechanisms such as the Vickrey-Clarke-Groves mechanism, the Myerson’s auction. I will review intractability results for welfare optimization in combinatorial auctions, and describe an analytical framework for overcoming these intractability results using online learning. I will then turn to revenue maximization in multi-item settings, presenting how duality theory has led to exciting progress on this front.
Time
2017-07-17 ~ 2017-07-21 13:20 - 17:05
Lecturers
Venue
T5, Shanghai University of Finance & Economics
Application and Registration
No registration fee.Program
Attachments
Contact Us
Directions to ITCS
