Fast Core Identification

Abstract

This paper examines the computational complexity of the \emph{Core Identification Problem} (CIP) in one-sided matching markets governed by the Top Trading Cycles (TTC) algorithm. The central contribution is a formal complexity separation: this paper proves that identifying which agents receive a core allocation is strictly easier than computing the full TTC allocation. Specifically, we show that CIP can be solved in $\bigO{Ln}$ time, where $L$ is the maximum number of preferences reported per agent, by computing the leading eigenvector of a preference-derived Markov transition matrix via randomized SVD\@. For sparse preference profiles ($L = \bigO{1}$, as in the NYC school choice where $L=12$), this yields an algorithm $\bigO{n}$. This result strictly improves on the $\bigO{n \log n}$ complexity of the full TTC allocation (\cite{SabanSethuraman2013}) and matches the $\Omg{n}$ information-theoretic lower bound, establishing asymptotic optimality. The method inherits all properties of TTC: Pareto efficiency, individual rationality, and strategy-proofness, and is robust to preference noise for sufficiently large~$n$.

23 pages