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.