IDEAS home Printed from https://ideas.repec.org/p/arx/papers/2501.15422.html
   My bibliography  Save this paper

TTC Domains

Author

Listed:
  • Sumit Goel
  • Yuki Tamura

Abstract

We study the object reallocation problem under strict preferences. On the unrestricted domain, Ekici (2024) showed that the Top Trading Cycles (TTC) mechanism is the unique mechanism that is individually rational, pair efficient, and strategyproof. We provide an alternative proof of this result, assuming only minimal richness of the unrestricted domain. This allows us to identify a broad class of restricted domains, those satisfying our top-two condition, on which the characterization continues to hold. The condition requires that, within any subset of objects, if two objects can each be most-preferred, they can also be the top two most-preferred objects (in both possible orders). We show that this condition is also necessary in the special case of three objects. These results unify and strengthen prior findings on specific domains such as single-peaked and single-dipped domain, and more broadly, offer a useful criterion for analyzing restricted preference domains.

Suggested Citation

  • Sumit Goel & Yuki Tamura, 2025. "TTC Domains," Papers 2501.15422, arXiv.org, revised Apr 2025.
    • Handle: RePEc:arx:papers:2501.15422
    as

    Download full text from publisher

    File URL: http://arxiv.org/pdf/2501.15422
    File Function: Latest version
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. James Schummer & Rakesh V. Vohra, 2013. "Assignment of Arrival Slots," American Economic Journal: Microeconomics, American Economic Association, vol. 5(2), pages 164-185, May.
    2. Ehlers, Lars, 2014. "Top trading with fixed tie-breaking in markets with indivisible goods," Journal of Economic Theory, Elsevier, vol. 151(C), pages 64-87.
    3. Nicolò, Antonio & Rodríguez-Álvarez, Carmelo, 2017. "Age-based preferences in paired kidney exchange," Games and Economic Behavior, Elsevier, vol. 102(C), pages 508-524.
    4. Bird, Charles G., 1984. "Group incentive compatibility in a market with indivisible goods," Economics Letters, Elsevier, vol. 14(4), pages 309-313.
    5. Pycia, Marek & Unver, Utku, 2017. "Incentive compatible allocation and exchange of discrete resources," Theoretical Economics, Econometric Society, vol. 12(1), January.
    6. Bade, Sophie, 2019. "Matching with single-peaked preferences," Journal of Economic Theory, Elsevier, vol. 180(C), pages 81-99.
    7. Anno, Hidekazu, 2015. "A short proof for the characterization of the core in housing markets," Economics Letters, Elsevier, vol. 126(C), pages 66-67.
    8. Lars-Gunnar Svensson, 1999. "Strategy-proof allocation of indivisible goods," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 16(4), pages 557-567.
    9. Miyagawa, Eiichi, 2002. "Strategy-Proofness and the Core in House Allocation Problems," Games and Economic Behavior, Elsevier, vol. 38(2), pages 347-361, February.
    10. Fujinaka, Yuji & Wakayama, Takuma, 2018. "Endowments-swapping-proof house allocation," Games and Economic Behavior, Elsevier, vol. 111(C), pages 187-202.
    11. Edith Elkind & Martin Lackner & Dominik Peters, 2022. "Preference Restrictions in Computational Social Choice: A Survey," Papers 2205.09092, arXiv.org, revised Mar 2025.
    12. Shapley, Lloyd & Scarf, Herbert, 1974. "On cores and indivisibility," Journal of Mathematical Economics, Elsevier, vol. 1(1), pages 23-37, March.
    13. Thayer Morrill, 2013. "An alternative characterization of top trading cycles," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 54(1), pages 181-197, September.
    14. Carroll, Gabriel, 2014. "A general equivalence theorem for allocation of indivisible objects," Journal of Mathematical Economics, Elsevier, vol. 51(C), pages 163-177.
    15. Ekici, Özgün, 2024. "Pair-efficient reallocation of indivisible objects," Theoretical Economics, Econometric Society, vol. 19(2), May.
    16. Hylland, Aanund & Zeckhauser, Richard, 1979. "The Efficient Allocation of Individuals to Positions," Journal of Political Economy, University of Chicago Press, vol. 87(2), pages 293-314, April.
    17. Ma, Jinpeng, 1994. "Strategy-Proofness and the Strict Core in a Market with Indivisibilities," International Journal of Game Theory, Springer;Game Theory Society, vol. 23(1), pages 75-83.
    18. Ekici, Özgün & Sethuraman, Jay, 2024. "Characterizing the TTC rule via pair-efficiency: A short proof," Economics Letters, Elsevier, vol. 234(C).
    19. Roth, Alvin E., 1982. "Incentive compatibility in a market with indivisible goods," Economics Letters, Elsevier, vol. 9(2), pages 127-132.
    20. Takamiya, Koji, 2001. "Coalition strategy-proofness and monotonicity in Shapley-Scarf housing markets," Mathematical Social Sciences, Elsevier, vol. 41(2), pages 201-213, March.
    21. Yuki Tamura, 2022. "Object reallocation problems under single-peaked preferences: two characterizations of the crawler," International Journal of Game Theory, Springer;Game Theory Society, vol. 51(3), pages 537-565, November.
    22. Roth, Alvin E. & Postlewaite, Andrew, 1977. "Weak versus strong domination in a market with indivisible goods," Journal of Mathematical Economics, Elsevier, vol. 4(2), pages 131-137, August.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Morrill, Thayer & Roth, Alvin E., 2024. "Top trading cycles," Journal of Mathematical Economics, Elsevier, vol. 112(C).
    2. Fujinaka, Yuji & Wakayama, Takuma, 2018. "Endowments-swapping-proof house allocation," Games and Economic Behavior, Elsevier, vol. 111(C), pages 187-202.
    3. Fujinaka, Yuji & Miyakawa, Toshiji, 2020. "Ex-post incentive compatible and individually rational assignments in housing markets with interdependent values," Journal of Mathematical Economics, Elsevier, vol. 91(C), pages 157-164.
    4. Ivan Balbuzanov & Maciej H. Kotowski, 2019. "Endowments, Exclusion, and Exchange," Econometrica, Econometric Society, vol. 87(5), pages 1663-1692, September.
    5. Karakaya, Mehmet & Klaus, Bettina & Schlegel, Jan Christoph, 2019. "Top trading cycles, consistency, and acyclic priorities for house allocation with existing tenants," Journal of Economic Theory, Elsevier, vol. 184(C).
    6. Ekici, Özgün & Sethuraman, Jay, 2024. "Characterizing the TTC rule via pair-efficiency: A short proof," Economics Letters, Elsevier, vol. 234(C).
    7. Klaus, Bettina & Klijn, Flip & Sethuraman, Jay, 2025. "A characterization of the top-trading-cycles mechanism for housing markets via respecting-improvement," Economics Letters, Elsevier, vol. 247(C).
    8. Tamura, Yuki & Hosseini, Hadi, 2022. "The crawler: Three equivalence results for object (re)allocation problems when preferences are single-peaked," Journal of Economic Theory, Elsevier, vol. 203(C).
    9. Ekici, Özgün, 2024. "Pair-efficient reallocation of indivisible objects," Theoretical Economics, Econometric Society, vol. 19(2), May.
    10. Yuji Fujinaka & Takuma Wakayama, 2011. "Secure implementation in Shapley–Scarf housing markets," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 48(1), pages 147-169, September.
    11. Hong, Miho & Park, Jaeok, 2022. "Core and top trading cycles in a market with indivisible goods and externalities," Journal of Mathematical Economics, Elsevier, vol. 100(C).
    12. Di Feng & Bettina Klaus & Flip Klijn, 2022. "A Characterization of the Coordinate-Wise Top-Trading-Cycles Mechanism for Multiple-Type Housing Markets," Cahiers de Recherches Economiques du Département d'économie 22.06, Université de Lausanne, Faculté des HEC, Département d’économie.
    13. Jaramillo, Paula & Manjunath, Vikram, 2012. "The difference indifference makes in strategy-proof allocation of objects," Journal of Economic Theory, Elsevier, vol. 147(5), pages 1913-1946.
    14. Feng, Di & Klaus, Bettina & Klijn, Flip, 2024. "Characterizing the typewise top-trading-cycles mechanism for multiple-type housing markets," Games and Economic Behavior, Elsevier, vol. 146(C), pages 234-254.
    15. Afacan, Mustafa Oğuz & Hu, Gaoji & Li, Jiangtao, 2024. "Housing markets since Shapley and Scarf," Journal of Mathematical Economics, Elsevier, vol. 111(C).
    16. Chen, Yajing & Zhao, Fang, 2021. "Alternative characterizations of the top trading cycles rule in housing markets," Economics Letters, Elsevier, vol. 201(C).
    17. Patrick Harless & William Phan, 2020. "On endowments and indivisibility: partial ownership in the Shapley–Scarf model," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 70(2), pages 411-435, September.
    18. Bettina Klaus, 2024. "Characterizing the top trading cycles rule for housing markets with lexicographic preferences," Papers 2410.16745, arXiv.org.
    19. Nicolò, Antonio & Rodríguez-Álvarez, Carmelo, 2017. "Age-based preferences in paired kidney exchange," Games and Economic Behavior, Elsevier, vol. 102(C), pages 508-524.
    20. Di Feng, 2023. "Endowments-swapping-proofness and Efficiency in Multiple-Type Housing Markets," Discussion Paper Series DP2023-14, Research Institute for Economics & Business Administration, Kobe University.

    More about this item

    NEP fields

    This paper has been announced in the following NEP Reports:

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:arx:papers:2501.15422. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: arXiv administrators (email available below). General contact details of provider: http://arxiv.org/ .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.