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.
Tutor: Jason Hartline (Northwestern U)
Part I: Non-truthful Mechanisms and Equilibrium
In this part we will compare equilibrium outcomes of the second-price auction and first-price auction and present a formal framework for designing and analyzing non-truthful mechanisms for single-dimensional agents. [video]
Topics:
- Bayes-Nash equilibrium and its characterization (Myerson, 1981)
Part II: Equilibrium Analysis
In this part we survey equilibrium analysis of non-truthful mechanisms. [video]
Topics:
- 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 III: Non-truthful Sample Complexity
In this part we give a simple framework for analysis of non-truthful sample complexity. [video]
Topics:
- 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 IV: 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. [video]
Topics:
- a prior-independent revelation gap (Feng, Hartline 2018)
- implementation of the revenue maximization by an ignorant seller (Caillaud, Robert, 2005)