Spring 2022

Learning & Games Reading Group: Learning in the Presence of Strategic Behavior

Thursday, April 21st, 2022, 10:00 am11:30 am

Add to Calendar

Parent Program: 

Vidya Muthukumar (Georgia Institute of Technology)


Calvin Lab Room 116

Title: Sample complexity for non-truthful mechanisms

Authors: Jason Hartline and Sam Taggart


Abstract: This paper considers the design of non-truthful mechanisms from samples. We identify a parameterized family of mechanisms with strategically simple winner-pays-bid, all-pay, and truthful payment formats. In general (not necessarily downward-closed) single-parameter feasibility environments we prove that the family has low representation and generalization error. Specifically, polynomially many bid samples suffice to identify and run a mechanism that is ε-close in Bayes-Nash equilibrium revenue or welfare to that of the optimal truthful mechanism.