Videos

Workshop: Mathematics and Computer Science of Market and Mechanism Design: "A Recent History of Approximation for Interdependent Values'

Presenter
September 14, 2023
Keywords:
  • market design
  • mechanism design
  • auctions
  • matching
  • approximation
  • equilibrium analysis
  • algorithmic game theory
  • complexity
  • economic theory
  • discrete optimization
  • graph theory
  • mathematical programming
Abstract
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.