Paper: arXiv 2604.25954

Authors: Irene Aldridge

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

Complexity vs Empirical Score

  • Math Complexity: 6.5/10
  • Empirical Rigor: 3.0/10
  • Quadrant: Lab Rats — theoretically deep, empirically untested

Why this score: The paper relies on advanced linear algebra concepts like randomized SVD, Markov chain theory, and eigenvector decomposition to derive complexity bounds. However, it lacks empirical validation, backtesting on real-world market datasets, or performance comparisons against standard implementation benchmarks, remaining primarily a theoretical computational geometry approach.

Research Flowchart

  flowchart TD
    A[<b>Goal:</b> Complexity of Core Identification Problem (CIP)] --> B[<b>Input:</b> TTC Matching Market Preferences]
    B --> C[<b>Process:</b> Markov Matrix Construction]
    C --> D[<b>Mechanism:</b> Randomized SVD / Eigenvector Computation]
    D --> E[<b>Finding:</b> $\mathcal{O}(Ln)$ Complexity (Asymptotically Optimal)]
    E --> F[<b>Outcomes:</b> Faster than TTC; Strategy-proof & Pareto Efficient]

Cited References (194)

  1. Incentive compatibility in a market with indivisible goods (1982) — link
  2. College admissions and the stability of marriage (1962) — link
  3. The redesign of the matching market for American physicians: Some engineering aspects of economic design (1999) — link
  4. Kidney exchange (2004) — link
  5. School admissions reform in Chicago and England: Comparing mechanisms by their vulnerability to manipulation (2013) — link
  6. The complexity of counting stable marriages (1986) — link
  7. Hard variants of stable marriage (2002) — link
  8. Strategy-proofness versus efficiency in matching with indifferences: Redesigning the NYC high school match (2009) — link
and 186 more
  1. Incentive compatible allocation and exchange of discrete resources (2017) — link
  2. Optimal pricing in networks with externalities (2012) — link
  3. Financial networks and contagion (2014) — link
  4. Preserving statistical validity in adaptive data analysis (2020) — link
  5. Algorithmic Game Theory (2007) — link
  6. Equilibrium in a discrete exchange economy with money (1974)
  7. The computational complexity of the housing market (2024) — link
  8. Settling the complexity of Arrow-Debreu equilibria in markets with additively separable utilities (2009) — link
  9. Settling the complexity of computing two-player Nash equilibria (2009) — link
  10. The complexity of computing a Nash equilibrium (2009) — link
  11. House allocation with fractional endowments (2011) — link
  12. On the asymptotics of random forests (2016) — link
  13. The Cutoff Structure of Top Trading Cycles in School Choice (2020) — link
  14. Random matching under dichotomous preferences (2004) — link
  15. A new solution to the random assignment problem (2001) — link
  16. Local graph partitioning using PageRank vectors (2006) — link
  17. In-memory eigenvector computation in time O(1) (2020) — link
  18. Discovering faster matrix multiplication algorithms with reinforcement learning (2022) — link
  19. The efficient allocation of individuals to positions (1979) — link
  20. School choice: A mechanism design approach (2003) — link
  21. The Boston public school match (2005) — link
  22. The New York City high school match (2005) — link
  23. School choice: An experimental study (2006) — link
  24. Games of school choice under the Boston mechanism (2006) — link
  25. On a conjecture by Gale about one-sided matching problems (1990) — link
  26. Envy freedom and prior-free mechanism design (2015) — link
  27. A truthful cardinal mechanism for one-sided matching (2020) — link
  28. Sequential fair allocation: Achieving the optimal envy-efficiency tradeoff curve (2022) — link
  29. A supply and demand framework for two-sided matching markets (2016) — link
  30. Efficient GPU implementation of randomized SVD and its applications (2024) — link
  31. Persuasion and Welfare (2024)
  32. School Choice Design, Risk Aversion and Cardinal Segregation (2020) — link
  33. A New Solution to the Random Assignment Problem (2001)
  34. Balancing Producer Fairness and Efficiency via Prior-Weighted Rating System Design (2024) — link
  35. Prospect Theory: An Analysis of Decision under Risk (1979)
  36. The Theory of Statistical Decision (1951)
  37. The complexity of constrained min-max optimization (2021)
  38. Zur Theorie der Gesellschaftsspiele (1928)
  39. The equivalence of linear programs and zero-sum games (2013)
  40. Job Market Signaling* (1973) — link
  41. “The Market for ‘Lemons’: Quality Uncertainty and the Market Mechanism.” (1970)
  42. Academic interest determines the academic performance of undergraduate accounting students: Multinomial logit evidence (2022)
  43. Helping struggling students and benefiting all: Peer effects in primary education (2023)
  44. EQUALITY OF EDUCATIONAL OPPORTUNITY (1968)
  45. The Effect of School Choice on Participants: Evidence from Randomized Lotteries (2006)
  46. Family networks and school enrolment: Evidence from a randomized social experiment (2010) — link
  47. Equilibrium in Competitive Insurance Markets: An Essay on the Economics of Imperfect Information (1976)
  48. Fast TTC and Probabilistic Core Identification (2024) — link
  49. The total matching polytope of complete bipartite graphs (2024) — link
  50. Machine Learning-Powered Course Allocation (2024) — link
  51. Course Match: A Large-Scale Implementation of Approximate Competitive Equilibrium from Equal Incomes for Combinatorial Allocation (2017) — link
  52. Identification and Parametric Estimation of Empirical Dynamic Marriage Matching Models (2022)
  53. Stability in the hospitals/residents problem with couples and ties: Mathematical models and computational studies (2021) — link
  54. “On the Allocation of Residents to Rural Hospitals: A General Property of Two-Sided Matching Markets.” (1986)
  55. Balancing Producer Fairness and Efficiency via Prior-Weighted Rating System Design (2024) — link
  56. Least squares quantization in PCM (1982) — link
  57. On the Optimality of Greedy Policies in Dynamic Matching (2023)
  58. Dynamic Matching: Characterizing and Achieving Constant Regret (2024)
  59. Group incentive compatibility in a market with indivisible goods (1984) — link
  60. Weak versus strong domination in a market with indivisible goods (1977) — link
  61. Strategy-proof and fair assignment is wasteful (2016) — link
  62. On cores and indivisibility (1974) — link
  63. The Computational Complexity of the Housing Market (2024) — link
  64. Random Serial Dictatorship and the Core from Random Endowments in House Allocation Problems (1998) — link
  65. Random Matching Under Dichotomous Preferences (2004) — link
  66. On a conjecture by gale about one-sided matching problems (1990) — link
  67. A New Solution to the House Allocation Problem with Existing Tenants (2001)
  68. House Allocation With Fractional Endowments (2011)
  69. School Choice: An Experimental Study. (2006)
  70. The Boston Public School Match (2005)
  71. The New York City High School Match (2005)
  72. School Choice: A Mechanism Design Approach (2003)
  73. School Choice: A Mechanism Design Approach (2006)
  74. School Choice: A Mechanism Design Approach (2013) — link
  75. In-Memory Eigenvector Computation in Time O(1) (2020) — link
  76. Zur Theorie der Matrices (1907) — link
  77. Über Matrizen aus nicht negativen Elementen (1912)
  78. A Supply and Demand Framework for Two-Sided Matching Markets (2016)
  79. A Continuum Model for the Top Trading Cycles Mechanism (2016)
  80. The Cutoff Structure of Top Trading Cycles in School Choice (2020) — link
  81. Smart Matching Platforms and Heterogeneous Beliefs in Centralized School Choice* (2022) — link
  82. Difficult Lessons on Social Prediction from Wisconsin Public Schools (2023) — link
  83. Large Covariance Estimation by Thresholding Principal Orthogonal Complements (2013) — link
  84. Matrix completion with noise (2010)
  85. Foundations of Data Science (2020)
  86. The High-Frequency Trading Arms Race: Frequent Batch Auctions as a Market Design Response * (2015) — link
  87. A Jump-Diffusion Model for Option Pricing (2002)
  88. Option pricing when underlying stock returns are discontinuous (1976)
  89. Order Flow, Transaction Clock, and Normality of Asset Returns (2000)
  90. The Volume Clock: Insights into the High-Frequency Paradigm (2012)
  91. The Pricing of Options and Corporate Liabilities (1973)
  92. A Subordinated Stochastic Process Model with Finite Variance for Speculative Prices
  93. A Stochastic Model for Order Book Dynamics (2010)
  94. Miners as intermediaries: extractable value and market manipulation in crypto and DeFi (2022)
  95. The Regulation of Queue Size by Levying Tolls (1969)
  96. Optimal Queue Design (2023)
  97. On the Optimality of First Come Last Served Queues (1985)
  98. Price Discovery on Decentralized Exchanges (2023) — link
  99. High-Frequency Trading: A Practical Guide to Algorithmic Strategies and Trading Systems (2009, 2013)
  100. Market Microstructure Theory (1998)
  101. Do Dark Pools Harm Price Discovery? (2013)
  102. Crypto Wash Trading (2022)
  103. Determining the Number of Factors in Approximate Factor Models (2002) — link
  104. What Data Series Matter? Explaining key trends and factors generated by Artificial Intelligence (2021) — link
  105. The AI Revolution: From Linear Regression to ChatGPT and beyond and How It All Connects to Finance. (2023)
  106. Inside the Black Box of Ability Peer Effects: Evidence from Variation in the Proportion of Low Achievers in the Classroom* (2012)
  107. Ability Peer Effects in University: Evidence from a Randomized Experiment (2016)
  108. Two-sided matching with interdependent values (2010)
  109. Algorithmic Transparency and Accountability through Crowdsourcing: A Study of the NYC School Admission Lottery (2023) — link
  110. Two-Stage Stochastic Stable Matching (2024)
  111. “A simple model of herd behavior” (1992)
  112. Information cascades and social learning (2021)
  113. “A theory of fads, fashion, custom, and cultural change as informational cascades” (1992)
  114. Rational herds: Economic models of social learning (2004)
  115. Preference Elicitation and Query Learning (2003)
  116. Preference Elicitation and Generalized Additive Utility (2006)
  117. Robust principal component analysis? (2011) — link
  118. Optimal Strategies in Ranked Choice Voting (2024) — link
  119. Choosing the Right Weights: Balancing Value, Strategy, and Noise in Recommender Systems (2024) — link
  120. The Evolution of the Labor Market for Medical Interns and Residents: A Case Study in Game Theory (1984)
  121. A Natural Experiment in the Organization of Entry-Level Labor Markets: Regional Markets for New Physicians and Surgeons in the United Kingdom (1991)
  122. Search and Matching for Adoption from Foster Care (2024) — link
  123. Dynamic Placement in Refugee Resettlement (2024)
  124. Modeling Assumptions Clash with the Real World: Transparency, Equity, and Community Challenges for Student Assignment Algorithms (2021) — link
  125. Definitions of Fairness Differ Across Socioeconomic Groups & Shape Perceptions of Algorithmic Decisions (2024) — link
  126. Not Another School Resource Map: Meeting Underserved Families’ Information Needs Requires Trusting Relationships and Personalized Care (2022) — link
  127. Customer Preference and Station Network in the London Bike-Share System (2021) — link
  128. Two-sided Assortment Optimization: Adaptivity Gaps and Approximation Algorithms (2024) — link
  129. The Power of Optimization Over Randomization in Designing Experiments Involving Small Samples (2015) — link
  130. School Choice and Equity: Current Policies in OECD Countries and a Literature Review (2012)
  131. A Pure Theory of Local Expenditures (1956)
  132. Equilibrium and inefficiency in a community model with peer group effects (1990)
  133. Competition between Private and Public Schools, Vouchers, and Peer-Group Effects (1998) — link
  134. Hoxby, C.M. (Ed.), The Economics of School Choice (2003)
  135. Preference intensities and risk aversion in school choice: a laboratory experiment. (2013)
  136. College Admissions and the Stability of Marriage (1962)
  137. Frictions Between Formal Education Policy and Actual School Choice: Case Studies in an International Comparative Perspective. (2005)
  138. Ex Ante Efficiency in School Choice Mechanisms: An Experimental Investigation. NBER Working Paper No. 14618 (2008)
  139. School choice and information: An experimental study on matching mechanisms (2008) — link
  140. Information acquisition and provision in school choice: An experimental study (2021) — link
  141. Presenting School Choice Information to Parents: An Evidence-Based Guide (2019)
  142. Preferences, Information, and Parental Choice Behavior in Public School Choice (2007)
  143. A Truthful Cardinal Mechanism for One-Sided Matching (2020) — link
  144. Auctions: A Survey of Experimental Research (1995)
  145. Can agents “report their types”? an experiment that changed the course allocation mechanism at wharton (2016)
  146. The Efficient Allocation of Individuals to Positions (1979) — link
  147. Distributionally Robust Optimization with Data Geometry (2022) — link
  148. Envy freedom and prior-free mechanism design (2015) — link
  149. Multidimensional mechanism design: Revenue maximization and the multiple-good monopoly (2007) — link
  150. Multi-parameter mechanism design and sequential posted pricing (2010) — link
  151. The Kolmogorov-Smirnov Statistic Revisited (2025) — link
  152. The Tight Constant in the Dvoretzky-Kiefer-Wolfowitz Inequality (1990)
  153. Asymptotic Minimax Character of the Sample Distribution Function and of the Classical Multinomial Estimator (1956)
  154. Local Graph Partitioning using PageRank Vectors (2006) — link
  155. On the asymptotics of random forests (2016) — link
  156. Beyond Chat GPT: Managing Lack of Stationarity with Unsupervised AI (2024)
  157. A Tutorial on the Spectral Theory of Markov Chains (2023) — link
  158. Sequential Fair Allocation: Achieving the Optimal Envy-Efficiency Tradeoff Curve (2022)
  159. Dynamically stable matching (2022)
  160. Discovering faster matrix multiplication algorithms with reinforcement learning. (2022)
  161. Efficient GPU implementation of randomized SVD and its applications (2024) — link
  162. Equilibrium in a discrete exchange economy with money. (1984)
  163. Settling the Complexity of Arrow-Debreu Equilibria in Markets with Additively Separable Utilities (2009) — link
  164. The Complexity of Computing a Nash Equilibrium (2009) — link
  165. Settling the complexity of computing two-player Nash equilibria (2009) — link
  166. Non-negative Matrices and Markov Chains (2006) — link
  167. Matrix Analysis (2012) — link
  168. Matrix Analysis and Applied Linear Algebra (2000) — link
  169. PageRank beyond the Web (2015) — link
  170. Spectral Graph Theory (1997)
  171. Markov Chains (1997) — link
  172. Markov Chains and Mixing Times (2017) — link
  173. Nonnegative Matrices in the Mathematical Sciences (1994) — link
  174. Introduction to the Numerical Solution of Markov Chains (1994)
  175. Eigenvalue computation in the 20th century (2000) — link
  176. Matrix Computations (2013)
  177. Weak versus strong domination in a market with indivisible goods (1977) — link
  178. On cores and indivisibility (1974) — link
  179. The PageRank Citation Ranking: Bringing Order to the Web (1999) — link
  180. Google’s PageRank and Beyond: The Science of Search Engine Rankings (2006)
  181. Probability: Theory and Examples (2019) — link
  182. Probability and Random Processes (2001)
  183. Spectral sparsification of graphs (2011) — link
  184. Local graph partitioning using PageRank vectors (2006) — link
  185. Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions (2011) — link
  186. A fast randomized algorithm for the approximation of matrices (2008) — link

0 of 194 cited works are in the corpus; resolved via arXiv source bundles, Semantic Scholar and OpenAlex. Corpus-wide: 2518 linked papers.