IDEAS home Printed from https://ideas.repec.org/a/spr/joecth/v54y2013i1p181-197.html
   My bibliography  Save this article

An alternative characterization of top trading cycles

Author

Listed:
  • Thayer Morrill

Abstract

This paper introduces two new characterizations of the top trading cycles algorithm. The key to our characterizations is a new condition, independence of irrelevant rankings (IIR). Intuitively, a mechanism satisfies IIR if whenever an agent’s ranking at an object is irrelevant to her assignment, then it is irrelevant to the assignment of all agents. We demonstrate that a mechanism is Pareto efficient, strategy-proof, IIR, and satisfies mutual best if and only if it is top trading cycles. This provides a new insight into what distinguishes top trading cycles from all other efficient and strategy-proof assignment mechanisms. We provide a second characterization in terms of weak Maskin monotonicity. A mechanism satisfies Pareto efficiency, weak Maskin monotonicity, IIR, and mutual best if and only if it is top trading cycles. This allows us to directly compare top trading cycles to known characterizations of the deferred acceptance algorithm in terms of weak Maskin monotonicity. Copyright Springer-Verlag 2013

Suggested Citation

  • 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.
    • Handle: RePEc:spr:joecth:v:54:y:2013:i:1:p:181-197
    DOI: 10.1007/s00199-012-0713-3
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1007/s00199-012-0713-3
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1007/s00199-012-0713-3?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Szilvia Papai, 2000. "Strategyproof Assignment by Hierarchical Exchange," Econometrica, Econometric Society, vol. 68(6), pages 1403-1434, November.
    2. Bettina Klaus & Flip Klijn, 2006. "Procedurally fair and stable matching," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 27(2), pages 431-447, January.
    3. Fuhito Kojima & M. Utku Ünver, 2010. "The 'Boston' School-Choice Mechanism," Boston College Working Papers in Economics 729, Boston College Department of Economics, revised 08 Oct 2010.
    4. Fuhito Kojima & Mihai Manea, 2010. "Axioms for Deferred Acceptance," Econometrica, Econometric Society, vol. 78(2), pages 633-653, March.
    5. Abdulkadiroglu, Atila & Sonmez, Tayfun, 1999. "House Allocation with Existing Tenants," Journal of Economic Theory, Elsevier, vol. 88(2), pages 233-260, October.
    6. Takamiya, Koji, 2001. "Coalition strategy-proofness and monotonicity in Shapley-Scarf housing markets," Mathematical Social Sciences, Elsevier, vol. 41(2), pages 201-213, March.
    7. Onur Kesten & Ayşe Yazıcı, 2012. "The Pareto-dominant strategy-proof and fair rule for problems with indivisible goods," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 50(2), pages 463-488, June.
    8. Pycia, Marek & Unver, Utku, 2017. "Incentive compatible allocation and exchange of discrete resources," Theoretical Economics, Econometric Society, vol. 12(1), January.
    9. EHLERS, Lars & KLAUS, Bettina, 2009. "Allocation via Deferred-Acceptance under Responsive Priorities," Cahiers de recherche 2009-16, Universite de Montreal, Departement de sciences economiques.
    10. Kesten, Onur, 2006. "On two competing mechanisms for priority-based allocation problems," Journal of Economic Theory, Elsevier, vol. 127(1), pages 155-171, March.
    11. 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.
    12. Bogomolnaia, Anna & Moulin, Herve, 2001. "A New Solution to the Random Assignment Problem," Journal of Economic Theory, Elsevier, vol. 100(2), pages 295-328, October.
    13. Hervé Moulin & Anna Bogomolnaia, 2002. "A simple random assignment problem with a unique solution," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 19(3), pages 623-636.
    14. Atila Abdulkadiroglu & Tayfun Sönmez, 2003. "School Choice: A Mechanism Design Approach," American Economic Review, American Economic Association, vol. 93(3), pages 729-747, June.
    15. Onur Kesten, 2010. "School Choice with Consent," The Quarterly Journal of Economics, President and Fellows of Harvard College, vol. 125(3), pages 1297-1348.
    16. Alvin E. Roth, 1982. "The Economics of Matching: Stability and Incentives," Mathematics of Operations Research, INFORMS, vol. 7(4), pages 617-628, November.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Can, Burak & Pourpouneh, Mohsen & Storcken, Ton, 2017. "Cost of transformation: a measure on matchings," Research Memorandum 015, Maastricht University, Graduate School of Business and Economics (GSBE).
    2. 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.
    3. Dur, Umut Mert, 2019. "The modified Boston mechanism," Mathematical Social Sciences, Elsevier, vol. 101(C), pages 31-40.
    4. Umut Dur & Yifan Xie, 2023. "Responsiveness to priority‐based affirmative action policy in school choice," Journal of Public Economic Theory, Association for Public Economic Theory, vol. 25(2), pages 229-244, April.
    5. Afacan, Mustafa Og̃uz & Dur, Umut Mert, 2017. "When preference misreporting is Harm[less]ful?," Journal of Mathematical Economics, Elsevier, vol. 72(C), pages 16-24.
    6. Carroll, Gabriel, 2014. "A general equivalence theorem for allocation of indivisible objects," Journal of Mathematical Economics, Elsevier, vol. 51(C), pages 163-177.
    7. Dur, Umut & Morrill, Thayer, 2018. "Competitive equilibria in school assignment," Games and Economic Behavior, Elsevier, vol. 108(C), pages 269-274.
    8. Umut Mert Dur & M. Utku Unver, 2015. "Two-Sided Matching via Balanced Exchange: Tuition and Worker Exchanges," Koç University-TUSIAD Economic Research Forum Working Papers 1508, Koc University-TUSIAD Economic Research Forum.
    9. Atila Abdulkadiroglu & Tommy Andersson, 2022. "School Choice," NBER Working Papers 29822, National Bureau of Economic Research, Inc.
    10. Duddy, Conal, 2017. "The structure of priority in the school choice problem," MPRA Paper 81057, University Library of Munich, Germany.
    11. Ayoade, Nickesha & Pápai, Szilvia, 2023. "School choice with preference rank classes," Games and Economic Behavior, Elsevier, vol. 137(C), pages 317-341.
    12. Altuntaş, Açelya & Phan, William, 2022. "Trading probabilities along cycles," Journal of Mathematical Economics, Elsevier, vol. 100(C).
    13. Nadja Stroh-Maraun, 2020. "Pareto Efficiency in Weighted School Choice Problems," Working Papers Dissertations 64, Paderborn University, Faculty of Business Administration and Economics.
    14. Siwei Chen & Yajing Chen & Chia‐Ling Hsu, 2023. "New axioms for top trading cycles," Bulletin of Economic Research, Wiley Blackwell, vol. 75(4), pages 1064-1077, October.
    15. Martin Bichler & Alexander Hammerl & Thayer Morrill & Stefan Waldherr, 2021. "How to Assign Scarce Resources Without Money: Designing Information Systems that are Efficient, Truthful, and (Pretty) Fair," Information Systems Research, INFORMS, vol. 32(2), pages 335-355, June.
    16. Morrill, Thayer, 2015. "Making just school assignments," Games and Economic Behavior, Elsevier, vol. 92(C), pages 18-27.
    17. Jingsheng Yu & Jun Zhang, 2020. "Efficient and fair trading algorithms in market design environments," Papers 2005.06878, arXiv.org, revised May 2021.
    18. Fujinaka, Yuji & Wakayama, Takuma, 2018. "Endowments-swapping-proof house allocation," Games and Economic Behavior, Elsevier, vol. 111(C), pages 187-202.
    19. Marek Pycia & M. Utku Ünver, 2016. "Arrovian Efficiency in Allocation of Discrete Resources," Boston College Working Papers in Economics 916, Boston College Department of Economics.
    20. Dilek Sayedahmed, 2022. "Centralized refugee matching mechanisms with hierarchical priority classes," The Journal of Mechanism and Institution Design, Society for the Promotion of Mechanism and Institution Design, University of York, vol. 7(1), pages 71-111, December.
    21. Ekici, Özgün, 0. "Pair-efficient reallocation of indivisible objects," Theoretical Economics, Econometric Society.

    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. Fuhito Kojima & M. Ünver, 2014. "The “Boston” school-choice mechanism: an axiomatic approach," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 55(3), pages 515-544, April.
    2. Morrill, Thayer, 2015. "Making just school assignments," Games and Economic Behavior, Elsevier, vol. 92(C), pages 18-27.
    3. Thayer Morrill, 2015. "Two simple variations of top trading cycles," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 60(1), pages 123-140, September.
    4. Kesten, Onur & Unver, Utku, 2015. "A theory of school choice lotteries," Theoretical Economics, Econometric Society, vol. 10(2), May.
    5. Anno, Hidekazu & Kurino, Morimitsu, 2016. "On the operation of multiple matching markets," Games and Economic Behavior, Elsevier, vol. 100(C), pages 166-185.
    6. Onur Kesten & Ayşe Yazıcı, 2012. "The Pareto-dominant strategy-proof and fair rule for problems with indivisible goods," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 50(2), pages 463-488, June.
    7. Can, Burak & Pourpouneh, Mohsen & Storcken, Ton, 2017. "Cost of transformation: a measure on matchings," Research Memorandum 015, Maastricht University, Graduate School of Business and Economics (GSBE).
    8. Roth, Alvin E. & Sonmez, Tayfun & Utku Unver, M., 2005. "Pairwise kidney exchange," Journal of Economic Theory, Elsevier, vol. 125(2), pages 151-188, December.
    9. Kojima, Fuhito, 2013. "Efficient resource allocation under multi-unit demand," Games and Economic Behavior, Elsevier, vol. 82(C), pages 1-14.
    10. 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).
    11. Han, Xiang, 2018. "Stable and efficient resource allocation under weak priorities," Games and Economic Behavior, Elsevier, vol. 107(C), pages 1-20.
    12. Harless, Patrick, 2014. "A School Choice Compromise: Between Immediate and Deferred Acceptance," MPRA Paper 61417, University Library of Munich, Germany.
    13. Rong, Kang & Tang, Qianfeng & Zhang, Yongchao, 2020. "On stable and efficient mechanisms for priority-based allocation problems," Journal of Economic Theory, Elsevier, vol. 187(C).
    14. Marek Pycia & M. Utku Ünver, 2022. "Outside options in neutral allocation of discrete resources," Review of Economic Design, Springer;Society for Economic Design, vol. 26(4), pages 581-604, December.
    15. Alcalde, Jose & Silva-Reus, José Ángel, 2013. "Allocating via Priorities," QM&ET Working Papers 13-3, University of Alicante, D. Quantitative Methods and Economic Theory.
    16. Scott Duke Kominers & Alexander Teytelboym & Vincent P Crawford, 2017. "An invitation to market design," Oxford Review of Economic Policy, Oxford University Press and Oxford Review of Economic Policy Limited, vol. 33(4), pages 541-571.
    17. Ivan Balbuzanov & Maciej H. Kotowski, 2019. "Endowments, Exclusion, and Exchange," Econometrica, Econometric Society, vol. 87(5), pages 1663-1692, September.
    18. Onur Kesten, 2012. "On two kinds of manipulation for school choice problems," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 51(3), pages 677-693, November.
    19. Bettina Klaus & David F. Manlove & Francesca Rossi, 2014. "Matching under Preferences," Cahiers de Recherches Economiques du Département d'économie 14.07, Université de Lausanne, Faculté des HEC, Département d’économie.
    20. Monte, Daniel & Tumennasan, Norovsambuu, 2015. "Centralized allocation in multiple markets," Journal of Mathematical Economics, Elsevier, vol. 61(C), pages 74-85.

    More about this item

    Keywords

    Top trading cycles; School choice; Assignment; C78; D61; J15; D78; I20;
    All these keywords.

    JEL classification:

    • C78 - Mathematical and Quantitative Methods - - Game Theory and Bargaining Theory - - - Bargaining Theory; Matching Theory
    • D61 - Microeconomics - - Welfare Economics - - - Allocative Efficiency; Cost-Benefit Analysis
    • J15 - Labor and Demographic Economics - - Demographic Economics - - - Economics of Minorities, Races, Indigenous Peoples, and Immigrants; Non-labor Discrimination
    • D78 - Microeconomics - - Analysis of Collective Decision-Making - - - Positive Analysis of Policy Formulation and Implementation
    • I20 - Health, Education, and Welfare - - Education - - - General

    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:spr:joecth:v:54:y:2013:i:1:p:181-197. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.