Algorithms, Approximation, and Learning in Market and Mechanism Design: "Stable Matching as Transportation"
Presenter
November 6, 2023
Keywords:
- market design
- mechanism design
- auctions
- matching
- approximation
- equilibrium analysis
- algorithmic game theory
- complexity
- economic theory
- discrete optimization
- graph theory
- mathematical programming
Abstract
We study matching markets with aligned preferences and establish a connection with the canonical optimal transportation problem. Stable matchings are approximated by solutions to certain convex optimal transport problems, while egalitarian matchings are approximated by concave problems. Our approach describes structural properties of stable matchings in specific markets. The results generalize to multi-sided matching problems, and allow us to consider team formation, supply chain, and other applications.