Approximation Mechanisms with Interdependent Values

The interdependent values model has gained a lot of recent attention as it provides a tractable yet challenging theoretical framework to study strategic settings beyond the standard assumption of independent private values. Interdependence is well studied in economics, where the existence of efficient (optimal) mechanism requires strong assumptions. In response, works in computer science have tackled the impossibility through the lens of approximation.

In this tutorial, we plan to present recent advances taking an algorithmic approach, relaxing assumptions and achieving approximately optimal welfare. 

The tutorial will start with an introduction to the interdependent values model and a brief survey of results on truthful mechanisms that obtain (approximately) optimal welfare. We will then expand on two recent directions that study more realistic information structures: (i) online agents and (ii) private valuation functions. 

1. Introduction to the Interdependent Values Model:

   • Krishna. Auction Theory (Chapters 6-10). Academic press, 2009.

   • Roughgarden, Talgam-Cohen. Optimal and Robust Mechanism Design with Interdependent Values. ACM TEAC, 2016.

   • Eden, Feldman, Fiat, Goldner. Interdependent Values without Single-Crossing. EC 2018.

   • Eden, Feldman, Fiat, Goldner, Karlin. Combinatorial Auctions with Interdependent Valuations: SOS to the Rescue. EC 2019.

2. Online Selection with Interdependent Values:

   • Gupta. Prophets and Secretaries. IPCO Summer School Lecture Notes 2017.

   • Mauras, Mohan, Reiffenhäuser. Optimal Stopping with Interdependent Values. EC 2024.  (*)

3. Private Interdependent Valuations:

   • Eden, Goldner, Zhang. Private Interdependent Valuations. SODA 2022.

   • Eden, Feldman, Goldner, Mauras, Mohan. Constant Approximation for Private Interdependent Valuations. FOCS 2023.  (*)
     
     (*) focus papers