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

Size versus truncation robustness in the assignment problem

Author

Listed:
  • Noda, Shunya

Abstract

We study the size of matchings (expected number of agents matched to some objects) generated by random mechanisms in the assignment problem. We show that no mechanism that satisfies two weak axioms, weak truncation robustness and weak regularity, achieves an approximation ratio better than 1−1∕e≈63.2%. This result indicates that it is impossible to achieve a matching size larger than 63.2% of the maximum feasible size in the worst case, as long as agents’ preferences over objects are private information. Our result indicates that the random serial dictatorship mechanism and probabilistic serial mechanism (which indeed has an approximation ratio of 1−1∕e) have the best approximation ratio among a broad class of mechanisms.

Suggested Citation

  • Noda, Shunya, 2020. "Size versus truncation robustness in the assignment problem," Journal of Mathematical Economics, Elsevier, vol. 87(C), pages 1-5.
    • Handle: RePEc:eee:mateco:v:87:y:2020:i:c:p:1-5
    DOI: 10.1016/j.jmateco.2019.12.001
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0304406819301211
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.jmateco.2019.12.001?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. Bogomolnaia, Anna & Moulin, Herve, 2015. "Size versus fairness in the assignment problem," Games and Economic Behavior, Elsevier, vol. 90(C), pages 119-127.
    2. Tommy ANDERSSON & Lars EHLERS, 2016. "Assigning Refugees to Landlords in Sweden : Stable Maximum Matchings," Cahiers de recherche 13-2016, Centre interuniversitaire de recherche en économie quantitative, CIREQ.
    3. Alvin E. Roth & Tayfun Sönmez & M. Utku Ünver, 2004. "Kidney Exchange," The Quarterly Journal of Economics, President and Fellows of Harvard College, vol. 119(2), pages 457-488.
    4. Afacan, Mustafa Oğuz & Bó, Inácio Guerberoff Lanari & Turhan, Bertan, 2018. "Assignment maximization," Discussion Papers, Research Unit: Market Behavior SP II 2018-201, WZB Berlin Social Science Center.
    5. Eric Budish & Yeon-Koo Che & Fuhito Kojima & Paul Milgrom, 2013. "Designing Random Allocation Mechanisms: Theory and Applications," American Economic Review, American Economic Association, vol. 103(2), pages 585-623, April.
    6. Andersson, Tommy & Ehlers, Lars, 2016. "Assigning Refugees to Landlords in Sweden: Efficient Stable Maximum Matchings," Working Papers 2016:18, Lund University, Department of Economics, revised 27 Aug 2018.
    7. 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.
    8. Anna Bogomolnaia & Herve Moulin, 2004. "Random Matching Under Dichotomous Preferences," Econometrica, Econometric Society, vol. 72(1), pages 257-279, January.
    9. Shapley, Lloyd & Scarf, Herbert, 1974. "On cores and indivisibility," Journal of Mathematical Economics, Elsevier, vol. 1(1), pages 23-37, March.
    10. Hashimoto, Tadashi & Hirata, Daisuke & Kesten, Onur & Kurino, Morimitsu & Unver, Utku, 2014. "Two axiomatic approaches to the probabilistic serial mechanism," Theoretical Economics, Econometric Society, vol. 9(1), January.
    11. Szilvia Pápai, 2001. "Strategyproof and Nonbossy Multiple Assignments," Journal of Public Economic Theory, Association for Public Economic Theory, vol. 3(3), pages 257-271, July.
    12. Erdil, Aytek, 2014. "Strategy-proof stochastic assignment," Journal of Economic Theory, Elsevier, vol. 151(C), pages 146-162.
    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. Noda, Shunya, 2023. "A planner-optimal matching mechanism and its incentive compatibility in a restricted domain," Games and Economic Behavior, Elsevier, vol. 141(C), pages 364-379.

    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. 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.
    2. 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.
    3. 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.
    4. Huang, Chao & Tian, Guoqiang, 2017. "Guaranteed size ratio of ordinally efficient and envy-free mechanisms in the assignment problem," Games and Economic Behavior, Elsevier, vol. 105(C), pages 1-8.
    5. Balbuzanov, Ivan, 2020. "Short trading cycles: Paired kidney exchange with strict ordinal preferences," Mathematical Social Sciences, Elsevier, vol. 104(C), pages 78-87.
    6. Anno, Hidekazu & Kurino, Morimitsu, 2016. "On the operation of multiple matching markets," Games and Economic Behavior, Elsevier, vol. 100(C), pages 166-185.
    7. Nesterov, Alexander S., 2017. "Fairness and efficiency in strategy-proof object allocation mechanisms," Journal of Economic Theory, Elsevier, vol. 170(C), pages 145-168.
    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. 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.
    10. Mennle, Timo & Seuken, Sven, 2021. "Partial strategyproofness: Relaxing strategyproofness for the random assignment problem," Journal of Economic Theory, Elsevier, vol. 191(C).
    11. Zhang, Jun, 2023. "Strategy-proof allocation with outside option," Games and Economic Behavior, Elsevier, vol. 137(C), pages 50-67.
    12. Jens Gudmundsson, 2014. "Sequences in Pairing Problems: A new approach to reconcile stability with strategy-proofness for elementary matching problems," 2014 Papers pgu351, Job Market Papers.
    13. Yajing Chen & Patrick Harless & Zhenhua Jiao, 2021. "The probabilistic rank random assignment rule and its axiomatic characterization," Papers 2104.09165, arXiv.org.
    14. Jingsheng Yu & Jun Zhang, 2020. "Efficient and fair trading algorithms in market design environments," Papers 2005.06878, arXiv.org, revised May 2021.
    15. Ramezanian, Rasoul & Feizi, Mehdi, 2022. "Robust ex-post Pareto efficiency and fairness in random assignments: Two impossibility results," Games and Economic Behavior, Elsevier, vol. 135(C), pages 356-367.
    16. Tommy Andersson & Lars Ehlers, 2020. "Assigning Refugees to Landlords in Sweden: Efficient, Stable, and Maximum Matchings," Scandinavian Journal of Economics, Wiley Blackwell, vol. 122(3), pages 937-965, July.
    17. Kondratev, Aleksei Y. & Nesterov, Alexander S., 2022. "Minimal envy and popular matchings," European Journal of Operational Research, Elsevier, vol. 296(3), pages 776-787.
    18. Noda, Shunya, 2023. "A planner-optimal matching mechanism and its incentive compatibility in a restricted domain," Games and Economic Behavior, Elsevier, vol. 141(C), pages 364-379.
    19. Hugh-Jones, David & Kurino, Morimitsu & Vanberg, Christoph, 2014. "An experimental study on the incentives of the probabilistic serial mechanism," Games and Economic Behavior, Elsevier, vol. 87(C), pages 367-380.
    20. Bogomolnaia, Anna & Moulin, Herve, 2015. "Size versus fairness in the assignment problem," Games and Economic Behavior, Elsevier, vol. 90(C), pages 119-127.

    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:87:y:2020:i:c:p:1-5. 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.