Workshop on Connections between Theory of Computing and Mechanism Design


The workshop on Connections between Theory of Computation and Mechanism Design will be held in conjunction with the Theory Fest: the 49th Annual ACM Symposium on the Theory of Computation (STOC '17) in Montreal, CA on June 23, 2017, and will feature invited speakers and a poster session.

Mechanism Design is a subarea at the intersection of economics and algorithms that has in recent years benefited tremendously from TCS-centric approaches and the TCS toolkit. At a high level, the goals of this workshop are to:

The workshop will address the following three themes, each with a 30-minute survey/tutorial and 2-3 short invited talks.
  1. Duality in mechanism design: Even certifying the optimality of a mechanism is often a non-trivial task. In recent years, duality theories have provided a principled approach using tools similar to those used in approximation algorithms to analyze and design (approximately) optimal mechanisms.
  2. Learning and mechanism design: This area covers traditional questions like "how much data is necessary and sufficient to find near-optimal mechanisms?" as well as "how does one learn when the data itself behaves strategically?"
  3. Simple versus optimal mechanisms: Optimal mechanisms are rarely simple enough to deploy in practice, but fortunately much recent work shows that often simple mechanisms are approximately optimal. This area also covers quantitative tradeoffs between simplicity and optimality (menu complexity), resource augmentation (Bulow-Klemperer results) and other notions of "approximation."

Please contact the organizers with any questions.

Organizers: Yang Cai, Shuchi Chawla, and Matt Weinberg

Also check out the first workshop on Mechanism Design for Social Good, 3 days later at EC 2017 (and the source of this template).