Algorithmic Game Theory, Complexity and Learning (Constantinos Daskalakis)

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

Constantinos Daskalakis, MIT

Venue

T5, Shanghai University of Finance & Economics

Application and Registration

No registration fee.

Program

Attachments

  1. Problem set A. The due date is Wednesday, July 19
  2. Problem Set A Solutions
  3. Slide 1 – equilibrium complexity
  4. Lecture 1.1: The Minimax Theorem .
  5. Lecture 1.2: Nash’s Theorem
  6. Lecture 1.3: Learning from Expert Advice
  7. Lecture 1.4: Online Convex Optimization
  8. Problem set 2A. The due date is Friday, July 28
  9. Problem set 2B. The due date is Friday, July 28
  10. Slide 2 – mechanism design intro
  11. Part 2.1 – Proof of Myerson’s Lemma
  12. Part 2.2 – Expected Revenue Equals Virtual Welfare

Contact Us

Huili Liang

Directions to ITCS

View Direction Page