IDEAS home Printed from https://ideas.repec.org/a/eee/mateco/v84y2019icp176-194.html
   My bibliography  Save this article

Random assignments on preference domains with a tier structure

Author

Listed:
  • Liu, Peng
  • Zeng, Huaxia

Abstract

We address a standard random assignment problem (Bogomolnaia and Moulin, 2001). A weakly connected domain admitting an sd-strategy-proof, sd-efficient and equal-treatment-of-equals rule is characterized to be a restricted tier domain. Conversely, on such a domain, the probabilistic serial rule is uniquely characterized by either sd-strategy-proofness, sd-efficiency and equal treatment of equals, or sd-efficiency and sd-envy-freeness. Moreover, we provide an algorithm to construct unions of multiple restricted tier domains, each of which admits an sd-strategy-proof, sd-efficient and sd-envy-free rule.

Suggested Citation

  • Liu, Peng & Zeng, Huaxia, 2019. "Random assignments on preference domains with a tier structure," Journal of Mathematical Economics, Elsevier, vol. 84(C), pages 176-194.
    • Handle: RePEc:eee:mateco:v:84:y:2019:i:c:p:176-194
    DOI: 10.1016/j.jmateco.2019.04.010
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0304406819300515
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.jmateco.2019.04.010?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. Sato, Shin, 2013. "A sufficient condition for the equivalence of strategy-proofness and nonmanipulability by preferences adjacent to the sincere one," Journal of Economic Theory, Elsevier, vol. 148(1), pages 259-278.
    3. Chatterji, Shurojit & Zeng, Huaxia, 2019. "Random mechanism design on multidimensional domains," Journal of Economic Theory, Elsevier, vol. 182(C), pages 25-105.
    4. Hervé Crès & Hervé Moulin, 2001. "Scheduling with Opting Out: Improving upon Random Priority," Operations Research, INFORMS, vol. 49(4), pages 565-577, August.
    5. Sushil Bikhchandani & Shurojit Chatterji & Ron Lavi & Ahuva Mu'alem & Noam Nisan & Arunava Sen, 2006. "Weak Monotonicity Characterizes Deterministic Dominant-Strategy Implementation," Econometrica, Econometric Society, vol. 74(4), pages 1109-1132, July.
    6. Michel Le Breton & Arunava Sen, 1999. "Separable Preferences, Strategyproofness, and Decomposability," Econometrica, Econometric Society, vol. 67(3), pages 605-628, May.
    7. Chang, Hee-In & Chun, Youngsub, 2017. "Probabilistic assignment of indivisible objects when agents have the same preferences except the ordinal ranking of one object," Mathematical Social Sciences, Elsevier, vol. 90(C), pages 80-92.
    8. Puppe, Clemens, 2018. "The single-peaked domain revisited: A simple global characterization," Journal of Economic Theory, Elsevier, vol. 176(C), pages 55-80.
    9. Abdulkadiroglu, Atila & Sonmez, Tayfun, 2003. "Ordinal efficiency and dominated sets of assignments," Journal of Economic Theory, Elsevier, vol. 112(1), pages 157-172, September.
    10. Kojima, Fuhito & Manea, Mihai, 2010. "Incentives in the probabilistic serial mechanism," Journal of Economic Theory, Elsevier, vol. 145(1), pages 106-123, January.
    11. Pycia, Marek & Unver, Utku, 2017. "Incentive compatible allocation and exchange of discrete resources," Theoretical Economics, Econometric Society, vol. 12(1), January.
    12. H. Moulin, 1980. "On strategy-proofness and single peakedness," Public Choice, Springer, vol. 35(4), pages 437-455, January.
    13. Bernard Monjardet, 2009. "Acyclic Domains of Linear Orders: A Survey," Studies in Choice and Welfare, in: Steven J. Brams & William V. Gehrlein & Fred S. Roberts (ed.), The Mathematics of Preference, Choice and Order, pages 139-160, Springer.
    14. Yoichi Kasajima, 2013. "Probabilistic assignment of indivisible goods with single-peaked preferences," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 41(1), pages 203-215, June.
    15. Barbera Salvador & Gul Faruk & Stacchetti Ennio, 1993. "Generalized Median Voter Schemes and Committees," Journal of Economic Theory, Elsevier, vol. 61(2), pages 262-289, December.
    16. Wonki Jo Cho, 2018. "Probabilistic assignment: an extension approach," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 51(1), pages 137-162, June.
    17. 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.
    18. ,, 2009. "Strategy-proofness and single-crossing," Theoretical Economics, Econometric Society, vol. 4(2), June.
    19. Salvador Barberà & Dolors Berga & Bernardo Moreno, 2012. "Domains, ranges and strategy-proofness: the case of single-dipped preferences," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 39(2), pages 335-352, July.
    20. Bogomolnaia, Anna, 2015. "Random assignment: Redefining the serial rule," Journal of Economic Theory, Elsevier, vol. 158(PA), pages 308-318.
    21. Atila Abdulkadiroglu & Tayfun Sonmez, 1998. "Random Serial Dictatorship and the Core from Random Endowments in House Allocation Problems," Econometrica, Econometric Society, vol. 66(3), pages 689-702, May.
    22. Zhou, Yu & Serizawa, Shigehiro, 2018. "Strategy-proofness and efficiency for non-quasi-linear and common-tiered-object preferences: Characterization of minimum price rule," Games and Economic Behavior, Elsevier, vol. 109(C), pages 327-363.
    23. Cho, Wonki Jo, 2016. "Incentive properties for ordinal mechanisms," Games and Economic Behavior, Elsevier, vol. 95(C), pages 168-177.
    24. 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.
    25. 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.
    26. Gibbard, Allan, 1977. "Manipulation of Schemes That Mix Voting with Chance," Econometrica, Econometric Society, vol. 45(3), pages 665-681, April.
    27. Shapley, Lloyd & Scarf, Herbert, 1974. "On cores and indivisibility," Journal of Mathematical Economics, Elsevier, vol. 1(1), pages 23-37, March.
    28. Takashi Akahoshi, 2014. "A necessary and sufficient condition for stable matching rules to be strategy-proof," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 43(3), pages 683-702, October.
    29. Gabriel Carroll, 2012. "When Are Local Incentive Constraints Sufficient?," Econometrica, Econometric Society, vol. 80(2), pages 661-686, March.
    30. Cho, Wonki Jo, 2016. "When is the probabilistic serial assignment uniquely efficient and envy-free?," Journal of Mathematical Economics, Elsevier, vol. 66(C), pages 14-25.
    31. Le Breton, Michel & Weymark, John A., 1999. "Strategy-proof social choice with continuous separable preferences," Journal of Mathematical Economics, Elsevier, vol. 32(1), pages 47-85, August.
    32. Onur Kesten, 2010. "School Choice with Consent," The Quarterly Journal of Economics, President and Fellows of Harvard College, vol. 125(3), pages 1297-1348.
    33. Ehlers, Lars, 2002. "Coalitional Strategy-Proof House Allocation," Journal of Economic Theory, Elsevier, vol. 105(2), pages 298-317, August.
    34. Kesten, Onur, 2009. "Why do popular mechanisms lack efficiency in random environments?," Journal of Economic Theory, Elsevier, vol. 144(5), pages 2209-2226, September.
    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 & Ehlers, Lars, 2023. "Strategy-proof and envy-free random assignment," Journal of Economic Theory, Elsevier, vol. 209(C).
    2. Youngsub Chun & Kiyong Yun, 2020. "Upper-contour strategy-proofness in the probabilistic assignment problem," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 54(4), pages 667-687, April.
    3. Basteck, Christian & Ehlers, Lars H., 2022. "Strategy-proof and envy-free random assignment," Discussion Papers, Research Unit: Market Behavior SP II 2022-208, WZB Berlin Social Science Center.
    4. Sulagna Dasgupta & Debasis Mishra, 2022. "Ordinal Bayesian incentive compatibility in random assignment model," Review of Economic Design, Springer;Society for Economic Design, vol. 26(4), pages 651-664, December.
    5. Basteck, Christian & Ehlers, Lars, 2021. "Strategy-Proof and Envy-Free Random Assignment," Rationality and Competition Discussion Paper Series 307, CRC TRR 190 Rationality and Competition.
    6. Sulagna Dasgupta & Debasis Mishra, 2020. "Ordinal Bayesian incentive compatibility in random assignment model," Discussion Papers 20-06, Indian Statistical Institute, Delhi.
    7. Chatterji, Shurojit & Liu, Peng, 2020. "Random assignments of bundles," Journal of Mathematical Economics, Elsevier, vol. 87(C), pages 15-30.

    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. Liu, Peng, 2020. "Random assignments on sequentially dichotomous domains," Games and Economic Behavior, Elsevier, vol. 121(C), pages 565-584.
    2. Chatterji, Shurojit & Zeng, Huaxia, 2018. "On random social choice functions with the tops-only property," Games and Economic Behavior, Elsevier, vol. 109(C), pages 413-435.
    3. Chatterji, Shurojit & Zeng, Huaxia, 2019. "Random mechanism design on multidimensional domains," Journal of Economic Theory, Elsevier, vol. 182(C), pages 25-105.
    4. Zhang, Jun, 2020. "When are efficient and fair assignment mechanisms group strategy-proof?," Games and Economic Behavior, Elsevier, vol. 119(C), pages 251-266.
    5. YIlmaz, Özgür, 2010. "The probabilistic serial mechanism with private endowments," Games and Economic Behavior, Elsevier, vol. 69(2), pages 475-491, July.
    6. Chatterji, Shurojit & Zeng, Huaxia, 2023. "A taxonomy of non-dictatorial unidimensional domains," Games and Economic Behavior, Elsevier, vol. 137(C), pages 228-269.
    7. Shurojit Chatterji & Huaxia Zeng, 2022. "A Taxonomy of Non-dictatorial Unidimensional Domains," Papers 2201.00496, arXiv.org, revised Oct 2022.
    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. Kesten, Onur, 2009. "Why do popular mechanisms lack efficiency in random environments?," Journal of Economic Theory, Elsevier, vol. 144(5), pages 2209-2226, September.
    10. Pycia, Marek & Ünver, M. Utku, 2015. "Decomposing random mechanisms," Journal of Mathematical Economics, Elsevier, vol. 61(C), pages 21-33.
    11. 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.
    12. Onur Kesten & Morimitsu Kurino & Alexander S. Nesterov, 2017. "Efficient lottery design," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 48(1), pages 31-57, January.
    13. Hougaard, Jens Leth & Moreno-Ternero, Juan D. & Østerdal, Lars Peter, 2014. "Assigning agents to a line," Games and Economic Behavior, Elsevier, vol. 87(C), pages 539-553.
    14. Chatterji, Shurojit & Liu, Peng, 2020. "Random assignments of bundles," Journal of Mathematical Economics, Elsevier, vol. 87(C), pages 15-30.
    15. 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.
    16. Wonki Jo Cho, 2018. "Probabilistic assignment: an extension approach," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 51(1), pages 137-162, June.
    17. 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.
    18. Chatterji, Shurojit & Roy, Souvik & Sadhukhan, Soumyarup & Sen, Arunava & Zeng, Huaxia, 2022. "Probabilistic fixed ballot rules and hybrid domains," Journal of Mathematical Economics, Elsevier, vol. 100(C).
    19. Andrew McLennan & Shino Takayama & Yuki Tamura, 2024. "An Efficient, Computationally Tractable School Choice Mechanism," Discussion Papers Series 668, School of Economics, University of Queensland, Australia.
    20. Chatterji, Shurojit & Sen, Arunava & Zeng, Huaxia, 2016. "A characterization of single-peaked preferences via random social choice functions," Theoretical Economics, Econometric Society, vol. 11(2), May.

    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:eee:mateco:v:84:y:2019:i:c:p:176-194. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/jmateco .

    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.