Market Clearing Beyond Submodularity

The ability to coordinate market sides at speed and scale is a cornerstone of modern platform business models and resource allocation systems more broadly. At its core, market clearing involves two fundamental tasks: allocation and pricing. This talk develops primal-dual based approaches to tackle each task in settings that go beyond the submodular structure typically required for tractable, optimal solutions.

On the allocation side, we study multi-sided matching under supply and demand uncertainty with capacity constraints. The key technical contribution is identifying a relaxation of submodularity that emerges naturally from primal-dual analysis of a linear programming formulation of the allocation task. Leveraging this, we establish constant-factor approximation guarantees for a broad class of problems that subsume not only matching but also flexibility design, facility location, and subset selection. On the pricing side, we consider when anonymous per-unit prices can support an approximately efficient allocation. Motivated by settings such as standardized procurement, cloud resource pricing, and posted-price sales of homogeneous goods, we leverage a linear programming representation of the market-clearing objective and again utilize the primal-dual approach to define a suitable approximation of Walrasian equilibrium. Building on this, we design and analyze algorithms that yield the uniform price that clears the market and supports an approximate equilibrium with corresponding welfare guarantees.