Matching Outcomes in TTC vs. The Crawler
Journal: Modern Economics & Management Forum DOI: 10.32629/memf.v5i5.2854
Abstract
This paper compares the matching outcomes and mechanism characteristics of two algorithms: TTC (Gale's Top Trading Cycles) and the Crawler, under single-peaked preferences. The TTC algorithm matches through a cycle-pointing process, which theoretically guarantees efficiency and strategy-proofness, but in practice, it is more complex, particularly when implementing obviously dominant strategies. In contrast, the Crawler algorithm provides a more intuitive and easier-to-understand matching process by screening agents in order of house sizes, making it particularly suitable for environments with single-peaked preferences. This paper analyzes the strengths and weaknesses of both algorithms and explores their applicability and differences in matching outcomes across various scenarios. The conclusion drawn is that in the domain of single-peaked preferences, the Crawler algorithm offers significant advantages in terms of comprehension and implementation, while TTC, despite its broader applicability, poses higher operational complexity under specific preference structures.
Keywords
TTC; the Crawler; matching
Full Text
PDF - Viewed/Downloaded: 2 TimesReferences
[1] Shapley, Lloyd, and Herbert Scarf. (1974), On cores and indivisibility. Journal of mathematical economics. 1, 23-37.
[2] Roth, A. (1982), Incentive compatibility in a market with indivisible goods, Economics letters, 9, 127-132.
[3] Ma, J. (1994), Strategyproofness and the Strict Core in a Market with Indivisibilites, International Journal of Game Theory, 23, 75-83.
[4] Bade, S. (2019), Matching with single-peaked preferences, Journal of Economic Theory, 180, 81-99.
[5] Li, S. (2017), Obviously Strategy-Proof Mechanisms, American Economic Review, 107, 3257-87.
[2] Roth, A. (1982), Incentive compatibility in a market with indivisible goods, Economics letters, 9, 127-132.
[3] Ma, J. (1994), Strategyproofness and the Strict Core in a Market with Indivisibilites, International Journal of Game Theory, 23, 75-83.
[4] Bade, S. (2019), Matching with single-peaked preferences, Journal of Economic Theory, 180, 81-99.
[5] Li, S. (2017), Obviously Strategy-Proof Mechanisms, American Economic Review, 107, 3257-87.
Copyright © 2024 Conghui Bi
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License