EC 2020 Tutorial: Foundations of Non-truthful Mechanism Design

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)

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:

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:

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:

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.