Home
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:
- Give attendees an overview of the field (without requiring any background in economics), highlighting the connection to typical TCS problems/techniques.
- Get attendees up to speed on the state-of-the-art.
- Give an overview of current/future research directions that are accessible to TCS researchers.
- 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.
- 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?"
- 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).