Algorithms, Approximation, and Learning in Market and Mechanism Design: "Walrasian Mechanisms for Non-Convex Economies and the Bound-Form First Welfare Theorem"
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
We introduce two extensions of the Walrasian mechanism for quasilinear economies to allow agents to report non-concave values and non-convex costs. The extended mechanisms, which always deliver feasible, near-efficient allocations with no budget deficit, are computationally undemanding and nearly incentive-compatible. We also introduce an extension of the First Welfare Theorem allowing us to upper bound the welfare losses from these mechanisms.