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

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{N}\mathsf{P}$-hardness and $\mathsf{P}\mathsf{P}\mathsf{A}\mathsf{D}$-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}\mathrm{/}{\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.