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

- Games,equilibria, minimax theorem, LP duality.
- Online learning, online convex optimization, minimax theorem from no-regret learning.
- Nash’s theorem,complexity of Nash equilibria,PPAD.
- Online learning and general games:correlated equilibrium via no-regret learning,quality of no-regret outcomes(price of anarchy)
- Mechanism design: truthfulness, revelation principle, Myerson’s lemma, Vickrey auction, Myerson’s optimal auction
- Multi-dimensional mechanism design:Vickrey-Clarke-Groves mechanism,complexity, learning,multi-item revenue optimization.

Attachments

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

Contact Us

Directions to ITCS