Videos

Algorithms, Approximation, and Learning in Market and Mechanism Design: "(Near) Substitute Preferences and Equilibria with Indivisibilities"

Presenter
November 7, 2023
Keywords:
  • market design
  • mechanism design
  • auctions
  • matching
  • approximation
  • equilibrium analysis
  • algorithmic game theory
  • complexity
  • economic theory
  • discrete optimization
  • graph theory
  • mathematical programming
Abstract
An obstacle to using market mechanisms to allocate indivisible goods (such as courses to students) is the non-existence of competitive equilibria (CE). To surmount this, Arrow and Hahn proposed the notion of social-approximate equilibria: a price vector and corresponding excess demands that are `small'. We identify a class of preferences called $\Delta$-substitutes, and show that social approximate equilibria where the bound on excess demand, good-by-good, is $2(\Delta-1)$ independent of the size of the economy. When $\Delta=1$ existence of CE is guaranteed even in the presence of income effects. This sufficient condition strictly generalizes prior conditions. These results rely on a new type of Shapley-Folkman-Starr Lemma which could be of independent interest. This is joint work with Thanh Nguyen.