IDEAS home Printed from https://ideas.repec.org/a/oup/restud/v87y2020i6p2473-2510..html
   My bibliography  Save this article

Approximate Random Allocation Mechanisms

Author

Listed:
  • Mohammad Akbarpour
  • Afshin Nikzad

Abstract

We generalize the scope of random allocation mechanisms, in which the mechanism first identifies a feasible “expected allocation” and then implements it by randomizing over nearby feasible integer allocations. The previous literature has shown that the cases in which this is possible are sharply limited. We show that if some of the feasibility constraints can be treated as goals rather than hard constraints, then, subject to weak conditions that we identify, any expected allocation that satisfies all the constraints and goals can be implemented by randomizing among nearby integer allocations that satisfy all the hard constraints exactly and the goals approximately. By defining ex post utilities as goals, we are able to improve the ex post properties of several classic assignment mechanisms, such as the random serial dictatorship. We use the same approach to prove the existence of $\epsilon$-competitive equilibrium in large markets with indivisible items and feasibility constraints.

Suggested Citation

  • Mohammad Akbarpour & Afshin Nikzad, 2020. "Approximate Random Allocation Mechanisms," The Review of Economic Studies, Review of Economic Studies Ltd, vol. 87(6), pages 2473-2510.
    • Handle: RePEc:oup:restud:v:87:y:2020:i:6:p:2473-2510.
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1093/restud/rdz066
    Download Restriction: Access to full text is restricted to subscribers.
    ---><---

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

    Citations

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


    Cited by:

    1. Freeman, Rupert & Pritchard, Geoffrey & Wilson, Mark, 2021. "Order Symmetry: A New Fairness Criterion for Assignment Mechanisms," SocArXiv xt37c, Center for Open Science.
    2. Aziz, Haris & Brandl, Florian, 2022. "The vigilant eating rule: A general approach for probabilistic economic design with constraints," Games and Economic Behavior, Elsevier, vol. 135(C), pages 168-187.
    3. 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.
    4. Balbuzanov, Ivan, 2022. "Constrained random matching," Journal of Economic Theory, Elsevier, vol. 203(C).
    5. Haris Aziz & Florian Brandl, 2020. "The Vigilant Eating Rule: A General Approach for Probabilistic Economic Design with Constraints," Papers 2008.08991, arXiv.org, revised Jul 2021.
    6. Hafalir, Isa E. & Kojima, Fuhito & Yenmez, M. Bumin, 2022. "Interdistrict school choice: A theory of student assignment," Journal of Economic Theory, Elsevier, vol. 201(C).
    7. Demeulemeester, Tom & Goossens, Dries & Hermans, Ben & Leus, Roel, 2023. "A pessimist’s approach to one-sided matching," European Journal of Operational Research, Elsevier, vol. 305(3), pages 1087-1099.
    8. Itai Ashlagi & Amin Saberi & Ali Shameli, 2020. "Assignment Mechanisms Under Distributional Constraints," Operations Research, INFORMS, vol. 68(2), pages 467-479, March.
    9. Paul Gölz & Dominik Peters & Ariel Procaccia, 2022. "In This Apportionment Lottery, the House Always Wins," Post-Print hal-03834513, HAL.
    10. Mehdi Feizi, 2023. "The object allocation problem with favoring upper ranks," International Journal of Economic Theory, The International Society for Economic Theory, vol. 19(2), pages 370-383, June.
    11. Eric Budish & Judd B. Kessler, 2022. "Can Market Participants Report Their Preferences Accurately (Enough)?," Management Science, INFORMS, vol. 68(2), pages 1107-1130, February.
    12. Haydar Evren & Manshu Khanna, 2021. "Affirmative Action's Cumulative Fractional Assignments," Papers 2111.11963, arXiv.org, revised Feb 2024.
    13. Jalota, Devansh & Pavone, Marco & Qi, Qi & Ye, Yinyu, 2023. "Fisher markets with linear constraints: Equilibrium properties and efficient distributed algorithms," Games and Economic Behavior, Elsevier, vol. 141(C), pages 223-260.
    14. Thanh Nguyen & Ahmad Peivandi & Rakesh Vohra, 2014. "One-Sided Matching with Limited Complementarities," PIER Working Paper Archive 14-030, Penn Institute for Economic Research, Department of Economics, University of Pennsylvania.
    15. Haris Aziz & Xinhang Lu & Mashbat Suzuki & Jeremy Vollen & Toby Walsh, 2023. "Best-of-Both-Worlds Fairness in Committee Voting," Papers 2303.03642, arXiv.org, revised Dec 2023.
    16. Marta Boczoń & Alistair J. Wilson, 2023. "Goals, Constraints, and Transparently Fair Assignments: A Field Study of Randomization Design in the UEFA Champions League," Management Science, INFORMS, vol. 69(6), pages 3474-3491, June.
    17. 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.

    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:oup:restud:v:87:y:2020:i:6:p:2473-2510.. 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.

    We have no bibliographic references for this item. You can help adding them by using 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: Oxford University Press (email available below). General contact details of provider: https://academic.oup.com/restud .

    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.