A Recent History of Approximation for Interdependent Values

Most of the algorithmic mechanism design literature assumes that a buyer's value for an item is private and independent from other buyers.  In contrast, the interdependent values model [Milgrom Weber '82] captures when one buyer's private information about an item impacts how much another buyer is willing to pay for it.  

In order to allocate a single-item efficiently and subject to incentive compatibility, valuations must satisfy a restrictive "single-crossing" condition, and prior to 2018, all work made this assumption.  However, since then, a series of work has broadened the domain of study by aiming for approximation and leveraging more natural structural assumptions.  

I will introduce the model, develop intuition for how it differs from the standard independent private value setting, and survey approximation results from recent years.

Based on joint works with Alon Eden, Michal Feldman, Amos Fiat, Anna Karlin, Simon Mauras, Divyarthi Mohan, and Shuran Zheng.

Please report video problems to itsupport@slmath.org.

See more of our Streaming videos on our main VMath Videos page.