IDEAS home Printed from https://ideas.repec.org/p/mtl/montec/14-2014.html
   My bibliography  Save this paper

Object Allocation via Deferred-Acceptance : Strategy-Proofness and Comparative Statics

Author

Listed:
  • Lars EHLERS
  • Bettina KLAUS

Abstract

We study the problem of assigning indivisible and heterogenous objects (e.g., houses, jobs, offices, school or university admissions etc.) to agents. Each agent receives at most one object and monetary compensations are not possible. We consider mechanisms satisfying a set of basic properties (unavailable-type-invariance, individual-rationality, weak non-wastefulness, or truncation-invariance). In the house allocation problem, where at most one copy of each object is available, deferred-acceptance (DA)-mechanisms allocate objects based on exogenously fixed objects' priorities over agents and the agent-proposing deferred-acceptance-algorithm. For house allocation we show that DA-mechanisms are characterized by our basic properties and (i) strategy-proofness and population-monotonicity or (ii) strategy-proofness and resource-monotonicity. Once we allow for multiple identical copies of objects, on the one hand the first characterization breaks down and there are unstable mechanisms satisfying our basic properties and (i) strategy-proofness and population-monotonicity. On the other hand, our basic properties and (ii) strategy-proofness and resource-monotonicity characterize (the most general) class of DA-mechanisms based on objects' fixed choice functions that are acceptant, monotonic, substitutable, and consistent. These choice functions are used by objects to reject agents in the agent-proposing deferred-acceptance-algorithm. Therefore, in the general model resource-monotonicity is the “stronger” comparative statics requirement because it characterizes (together with our basic requirements and strategy-proofness) choice-based DA-mechanisms whereas population-monotonicity (together with our basic properties and strategy-proofness) does not.

Suggested Citation

  • Lars EHLERS & Bettina KLAUS, 2014. "Object Allocation via Deferred-Acceptance : Strategy-Proofness and Comparative Statics," Cahiers de recherche 14-2014, Centre interuniversitaire de recherche en économie quantitative, CIREQ.
    • Handle: RePEc:mtl:montec:14-2014
    as

    Download full text from publisher

    File URL: http://www.cireqmontreal.com/wp-content/uploads/cahiers/14-2014-cah.pdf
    Download Restriction: no
    ---><---

    Other versions of this item:

    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. Shapley, Lloyd & Scarf, Herbert, 1974. "On cores and indivisibility," Journal of Mathematical Economics, Elsevier, vol. 1(1), pages 23-37, March.
    3. Lars Ehlers & Bettina Klaus, 2007. "Consistent House Allocation," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 30(3), pages 561-574, March.
    4. Chun, Youngsub & Thomson, William, 1988. "Monotonicity properties of bargaining solutions when applied to economics," Mathematical Social Sciences, Elsevier, vol. 15(1), pages 11-27, February.
    5. Thayer Morrill, 2013. "An alternative characterization of the deferred acceptance algorithm," International Journal of Game Theory, Springer;Game Theory Society, vol. 42(1), pages 19-28, February.
    6. Lars Ehlers & Bettina Klaus, 2011. "Corrigendum to “Resource-monotonicity for house allocation problems”," International Journal of Game Theory, Springer;Game Theory Society, vol. 40(2), pages 281-287, May.
    7. Ehlers, Lars & Hafalir, Isa E. & Yenmez, M. Bumin & Yildirim, Muhammed A., 2014. "School choice with controlled choice constraints: Hard bounds versus soft bounds," Journal of Economic Theory, Elsevier, vol. 153(C), pages 648-683.
    8. Ehlers, Lars & Klaus, Bettina & Papai, Szilvia, 2002. "Strategy-proofness and population-monotonicity for house allocation problems," Journal of Mathematical Economics, Elsevier, vol. 38(3), pages 329-339, November.
    9. Lars Ehlers & Bettina Klaus, 2004. "Resource-monotonicity for house allocation problems," International Journal of Game Theory, Springer;Game Theory Society, vol. 32(4), pages 545-560, August.
    10. Lars Ehlers & Bettina Klaus, 2014. "Strategy-Proofness Makes the Difference: Deferred-Acceptance with Responsive Priorities," Mathematics of Operations Research, INFORMS, vol. 39(4), pages 949-966, November.
    11. Kelso, Alexander S, Jr & Crawford, Vincent P, 1982. "Job Matching, Coalition Formation, and Gross Substitutes," Econometrica, Econometric Society, vol. 50(6), pages 1483-1504, November.
    12. Haluk I. Ergin, 2002. "Efficient Resource Allocation on the Basis of Priorities," Econometrica, Econometric Society, vol. 70(6), pages 2489-2497, November.
    13. Marc Fleurbaey & Koichi Tadenuma, 2007. "Do Irrelevant Commodities Matter?," Econometrica, Econometric Society, vol. 75(4), pages 1143-1174, July.
    14. Balinski, Michel & Sonmez, Tayfun, 1999. "A Tale of Two Mechanisms: Student Placement," Journal of Economic Theory, Elsevier, vol. 84(1), pages 73-94, January.
    15. William Thomson, 1983. "The Fair Division of a Fixed Supply Among a Growing Population," Mathematics of Operations Research, INFORMS, vol. 8(3), pages 319-326, August.
    16. Lars Ehlers & Bettina Klaus, 2013. "House Allocation via Deferred-Acceptance," Cahiers de recherche 06-2013, Centre interuniversitaire de recherche en économie quantitative, CIREQ.
    17. Onur Kesten, 2009. "Coalitional strategy-proofness and resource monotonicity for house allocation problems," International Journal of Game Theory, Springer;Game Theory Society, vol. 38(1), pages 17-21, March.
    18. Christopher P. Chambers & M. Bumin Yenmez, 2017. "Choice and Matching," American Economic Journal: Microeconomics, American Economic Association, vol. 9(3), pages 126-147, August.
    19. Orhan Ayg?n & Tayfun S?nmez, 2013. "Matching with Contracts: Comment," American Economic Review, American Economic Association, vol. 103(5), pages 2050-2051, August.
    20. John William Hatfield & Paul R. Milgrom, 2005. "Matching with Contracts," American Economic Review, American Economic Association, vol. 95(4), pages 913-935, September.
    21. Crawford, Vincent P., 1991. "Comparative statics in matching markets," Journal of Economic Theory, Elsevier, vol. 54(2), pages 389-400, August.
    22. Barnett,William A. & Moulin,Hervé & Salles,Maurice & Schofield,Norman J. (ed.), 1995. "Social Choice, Welfare, and Ethics," Cambridge Books, Cambridge University Press, number 9780521443401, September.
    23. Roth, Alvin E, 1984. "Stability and Polarization of Interests in Job Matching," Econometrica, Econometric Society, vol. 52(1), pages 47-57, January.
    24. Ehlers, Lars, 2002. "Coalitional Strategy-Proof House Allocation," Journal of Economic Theory, Elsevier, vol. 105(2), pages 298-317, August.
    25. Fuhito Kojima & Mihai Manea, 2010. "Axioms for Deferred Acceptance," Econometrica, Econometric Society, vol. 78(2), pages 633-653, March.
    26. 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. Basteck, Christian & Klaus, Bettina & Kübler, Dorothea, 2021. "How lotteries in school choice help to level the playing field," Games and Economic Behavior, Elsevier, vol. 129(C), pages 198-237.
    2. Bettina Klaus & Alexandru Nichifor, 2020. "Serial dictatorship mechanisms with reservation prices," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 70(3), pages 665-684, October.
    3. Mustafa Oğuz Afacan & Umut Mert Dur, 2020. "Constrained stability in two-sided matching markets," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 55(3), pages 477-494, October.
    4. BONKOUNGOU, Somouaoga, 2016. "Pareto dominance of deferred acceptance through early decision," Cahiers de recherche 2016-07, Universite de Montreal, Departement de sciences economiques.
    5. Bettina Klaus & Alexandru Nichifor, 2021. "Serial dictatorship mechanisms with reservation prices: heterogeneous objects," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 57(1), pages 145-162, July.
    6. Ayoade, Nickesha & Pápai, Szilvia, 2023. "School choice with preference rank classes," Games and Economic Behavior, Elsevier, vol. 137(C), pages 317-341.
    7. 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).
    8. Bilancini, Ennio & Boncinelli, Leonardo & Newton, Jonathan, 2020. "Evolution and Rawlsian social choice in matching," Games and Economic Behavior, Elsevier, vol. 123(C), pages 68-80.
    9. Afacan, Mustafa Oğuz & Dur, Umut & Van der Linden, Martin, 2024. "Capacity design in school choice," Games and Economic Behavior, Elsevier, vol. 146(C), pages 277-291.
    10. Battal Dou{g}an & Kenzo Imamura & M. Bumin Yenmez, 2022. "Market Design with Deferred Acceptance: A Recipe for Policymaking," Papers 2209.06777, arXiv.org.
    11. Battal Doğan & Serhat Doğan & Kemal Yıldız, 2021. "Lexicographic choice under variable capacity constraints," Journal of Public Economic Theory, Association for Public Economic Theory, vol. 23(1), pages 172-196, February.
    12. Julien Combe & Jan Christoph Schlegel, 2021. "Reallocation with Priorities," Working Papers 2021-09, Center for Research in Economics and Statistics.
    13. Doğan, Battal & Klaus, Bettina, 2018. "Object allocation via immediate-acceptance: Characterizations and an affirmative action application," Journal of Mathematical Economics, Elsevier, vol. 79(C), pages 140-156.
    14. Combe, Julien & Schlegel, Jan Christoph, 2024. "Reallocation with priorities," Games and Economic Behavior, Elsevier, vol. 143(C), pages 287-299.
    15. Somouaoga Bonkoungou, 2021. "Decentralized college admissions under single application," Review of Economic Design, Springer;Society for Economic Design, vol. 25(1), pages 65-91, June.
    16. Keisuke Bando & Kenzo Imamura, 2016. "A necessary and sufficient condition for weak Maskin monotonicity in an allocation problem with indivisible goods," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 47(3), pages 589-606, October.
    17. Afacan, Mustafa Oǧuz, 2017. "Some further properties of the cumulative offer process," Games and Economic Behavior, Elsevier, vol. 104(C), pages 656-665.
    18. Kasajima, Yoichi & Toda, Manabu, 2024. "Singles monotonicity and stability in one-to-one matching problems," Games and Economic Behavior, Elsevier, vol. 143(C), pages 269-286.
    19. Mustafa Oğuz Afacan & Umut Dur, 2023. "Strategy‐proof size improvement: is it possible?," Scandinavian Journal of Economics, Wiley Blackwell, vol. 125(2), pages 321-338, April.
    20. Somouaoga BONKOUNGOU, 2016. "Pareto Dominance of Deferred Acceptance through Early Decision," Cahiers de recherche 11-2016, Centre interuniversitaire de recherche en économie quantitative, CIREQ.
    21. Zhang, Jun, 2023. "Strategy-proof allocation with outside option," Games and Economic Behavior, Elsevier, vol. 137(C), pages 50-67.

    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. Lars Ehlers & Bettina Klaus, 2013. "House Allocation via Deferred-Acceptance," Cahiers de recherche 06-2013, Centre interuniversitaire de recherche en économie quantitative, CIREQ.
    2. Lars Ehlers & Bettina Klaus, 2013. "House Allocation via Deferred-Acceptance (N.B.: This paper has been extended and results are now contained in working paper 14.08.)," Cahiers de Recherches Economiques du Département d'économie 13.10, Université de Lausanne, Faculté des HEC, Département d’économie.
    3. Lars Ehlers & Bettina Klaus, 2012. "Strategy-Proofness Makes the Difference : Deferred-Acceptance with Responsive Priorities," Cahiers de recherche 15-2012, Centre interuniversitaire de recherche en économie quantitative, CIREQ.
    4. Lars Ehlers & Bettina Klaus, 2014. "Strategy-Proofness Makes the Difference: Deferred-Acceptance with Responsive Priorities," Mathematics of Operations Research, INFORMS, vol. 39(4), pages 949-966, November.
    5. Doğan, Battal & Klaus, Bettina, 2018. "Object allocation via immediate-acceptance: Characterizations and an affirmative action application," Journal of Mathematical Economics, Elsevier, vol. 79(C), pages 140-156.
    6. EHLERS, Lars & KLAUS, Bettina, 2009. "Allocation via Deferred-Acceptance under Responsive Priorities," Cahiers de recherche 17-2009, Centre interuniversitaire de recherche en économie quantitative, CIREQ.
    7. Dur, Umut & Paiement, Scott, 2024. "A characterization of the top trading cycles mechanism for the school choice problem," Mathematical Social Sciences, Elsevier, vol. 129(C), pages 93-100.
    8. Thomson, William, 2011. "Chapter Twenty-One - Fair Allocation Rules," Handbook of Social Choice and Welfare, in: K. J. Arrow & A. K. Sen & K. Suzumura (ed.), Handbook of Social Choice and Welfare, edition 1, volume 2, chapter 21, pages 393-506, Elsevier.
    9. Kesten, Onur, 2006. "On two competing mechanisms for priority-based allocation problems," Journal of Economic Theory, Elsevier, vol. 127(1), pages 155-171, March.
    10. Ehlers, Lars & Klaus, Bettina, 2006. "Efficient priority rules," Games and Economic Behavior, Elsevier, vol. 55(2), pages 372-384, May.
    11. 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.
    12. 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).
    13. Klaus, Bettina & Klijn, Flip, 2013. "Local and global consistency properties for student placement," Journal of Mathematical Economics, Elsevier, vol. 49(3), pages 222-229.
    14. Bettina Klaus & Flip Klijn, 2007. "Fair and efficient student placement with couples," International Journal of Game Theory, Springer;Game Theory Society, vol. 36(2), pages 177-207, October.
    15. Schummer, James & Abizada, Azar, 2017. "Incentives in landing slot problems," Journal of Economic Theory, Elsevier, vol. 170(C), pages 29-55.
    16. Afacan, Mustafa Oǧuz, 2017. "Some further properties of the cumulative offer process," Games and Economic Behavior, Elsevier, vol. 104(C), pages 656-665.
    17. 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.
    18. Sonmez, Tayfun & Utku Unver, M., 2005. "House allocation with existing tenants: an equivalence," Games and Economic Behavior, Elsevier, vol. 52(1), pages 153-185, July.
    19. Avataneo, Michelle & Turhan, Bertan, 2021. "Slot-specific priorities with capacity transfers," Games and Economic Behavior, Elsevier, vol. 129(C), pages 536-548.
    20. 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.

    More about this item

    Keywords

    indivisible objects allocation; deferred-acceptance-algorithm; strategy-proofness; resource-monotonicity; population-monotonicity;
    All these keywords.

    JEL classification:

    • D63 - Microeconomics - - Welfare Economics - - - Equity, Justice, Inequality, and Other Normative Criteria and Measurement
    • D70 - Microeconomics - - Analysis of Collective Decision-Making - - - General

    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:mtl:montec:14-2014. 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: Sharon BREWER (email available below). General contact details of provider: https://edirc.repec.org/data/cdmtlca.html .

    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.