The literature on mechanism design almost exclusively considers the design of mechanisms that have truthtelling as an equilibrium. Mechanisms in the practice do not have truthtelling as an equilibrium. It is generally not straightforward to convert the truthful mechanisms from the literature into practical mechanisms. Thus, a theory for the design of non-truthful mechanisms with good equilibria is needed. This tutorial aims to survey nascent research that is developing into a foundation for non-truthful mechanism design.
The tutorial focuses on canonical payment formats in non-truthful mechanisms, namely, winner-pays-bid and all-pay. Winner-pays-bid rules are typical when bids are contracts. All-pay rules are typical for games of effort and the subscription model of online markets. Open questions will be identified in each part. Exercises will be provided for students to solve in small groups.
Some of the material from this tutorial can be found in Chapters 2 and 6 of Mechanism Design and Approximation. Other material is from the original sources listed below.
Jason Hartline (Northwestern U)
Pre-recording Session: (registered participants receive the Zoom password by email)
|Pre-recording, Part I (Slides) (Zoom)||Wednesday, June 17||10-10:45am, 11-11:45am Eastern|
|Exercise Session (Exercises) (Zoom)||Wednesday, June 17||12-1pm Eastern|
|Pre-recording, Part II (Slides) (Zoom)||Thursday, June 18||10-10:45am, 11-11:45am Eastern|
|Watch party, Part I||Monday, July 13||10-10:45am, 11-11:45am Eastern|
|Watch party, Part II||Monday, July 13||3-3:45pm, 4-4:45pm Eastern|
Part I: Equilibrium Analysis
In this part we survey equilibrium analysis of non-truthful mechanisms:
- solving for equilibria in i.i.d. first-price auctions with revenue equivalence.
- unique of equilibria of i.i.d. rank-based auctions (Chawla, Hartline 2013).
- robust analysis of welfare and revenue in winner-pays-bid and all-pay mechanisms (Borodin, Lucier 2010; Syrgkanis, Tardos 2013; Hartline, Hoy, Taggart 2014; Dütting, Kesselheim, 2015; Hoy, Nekipelov, Syrgkanis 2017).
Part IIa: Non-truthful Sample Complexity
In this part we give a simple framework for analysis of non-truthful sample complexity. The focus is on two results:
- estimating revenue and welfare in a mechanism from equilibrium bids in another mechanism (Chawla, Hartline, Nekipelov 2014, 2016).
- non-truthful sample complexity and the surrogate ranking mechanism (Hartline, Taggart 2019).
Part IIb: Simplicity, Robustness, the Revelation Gap
In this part we discuss the relationship between the key desiderata of simplicity and robustness for which the revelation principle is not without loss. Context will be provided by contrasting result from implementation theory.