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

Bruce Changlong Xu, Andrew Yang and Ivan Villa-Renteria

Papers from arXiv.org

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 $\varepsilon$-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.

Date: 2021-09, Revised 2026-10
New Economics Papers: this item is included in nep-cwa, nep-des and nep-upt
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://arxiv.org/pdf/2109.14850 Latest version (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:arx:papers:2109.14850

Access Statistics for this paper

More papers in Papers from arXiv.org
Bibliographic data for series maintained by arXiv administrators ().