Matching Markets: Equilibrium Computation, Indivisible Goods, and Positional Externalities

Abstract

Matching markets provide a mathematical framework for allocating scarce resources among strategic agents with heterogeneous preferences. While matching without money relies on ordinal stability and Pareto efficiency, Fisher and Arrow--Debreu markets mediate allocation through budgets and market-clearing prices. In this paper, we study the convex-analytic foundations, computational complexity, and external-utility extensions of Fisher matching markets. First, we formulate fractional resource allocation and linear Fisher markets via Fenchel conjugate duality and the Karush--Kuhn--Tucker (KKT) conditions of the Eisenberg--Gale convex program, showing how budget-weighted Nash social welfare characterizes competitive equilibria across linear and homothetic utility families. Second, we review topological existence via Sperner's lemma alongside polynomial-time combinatorial algorithms for divisible markets, including the Devanur--Papadimitriou--Saberi--Vazirani (DPSV) primal-dual max-flow algorithm and Orlin's strongly polynomial scaling algorithm. Third, we contrast the tractability of divisible markets with the $\mathsf{NP}$-hardness and $\mathsf{PPAD}$-completeness of indivisible Fisher markets and Competitive Equilibrium from Equal Incomes (CEEI), comparing $\epsilon$-approximate equilibria, CEEI-FRAC, and Budish's Approximate CEEI mechanism. Finally, we analyze Fisher markets with positional (snob-effect) externalities, where buyer $i$'s utility for good $j$ scales with her relative share $(x_{ij}/{\sum }_k{x}_{kj}{)}^{{\alpha }_i}$ for ${\alpha }_i>0$. We prove that positional utility summands are convex on the nonnegative orthant, so utilitarian social welfare is maximized at exclusive corner allocations, whereas decentralized price-taking admits a unique budget-proportional equilibrium in single-good snob markets with a Price of Anarchy of $n^{\alpha }$ among $n$ symmetric buyers.