IDEAS home Printed from https://ideas.repec.org/p/ecl/riceco/2000-03.html
   My bibliography  Save this paper

Scheduling with Opting Out: Improving upon Random Priority

Author

Listed:
  • Moulin, Herve

    (Rice U)

  • Cres, Moulin

    (HEC School of Management)

Abstract

In a scheduling problem where agents can opt out, we show that the familiar Random Priority (RP) a rule can be improved upon by another mechanism dubbed Probabilistic Serial (PS). Both mechanisms are nonmanipulable in a strong sense, but the latter is Pareto superior to the former and serves a larger (expected number of agents. The PS equilibrium outcome is easier to compute than the RP outcome; on the other hand RP is easier to implement than PS. We show that the improvement of PS over RP is significant but small: at most a couple of percentage points in the relative welfare gain and the relative difference in quantity served. We conjecture that the latter never exceeds 8.33 %. Both gains vanish when the number of agents is large.

Suggested Citation

  • Moulin, Herve & Cres, Moulin, 2000. "Scheduling with Opting Out: Improving upon Random Priority," Working Papers 2000-03, Rice University, Department of Economics.
    • Handle: RePEc:ecl:riceco:2000-03
    as

    Download full text from publisher

    File URL: http://www.ruf.rice.edu/~econ/papers/2000papers/03Moulin.pdf
    Download Restriction: no
    ---><---

    Other versions of this item:

    References listed on IDEAS

    as
    1. 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.
    2. Jeroen Suijs, 1996. "On incentive compatibility and budget balancedness in public decision making," Review of Economic Design, Springer;Society for Economic Design, vol. 2(1), pages 193-209, December.
    3. 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.
    4. Naor, P, 1969. "The Regulation of Queue Size by Levying Tolls," Econometrica, Econometric Society, vol. 37(1), pages 15-24, January.
    5. Barbera, S., 1995. "Notes on a Strategy-Proof Social Choice Functions," UFAE and IAE Working Papers 292.95, Unitat de Fonaments de l'Anàlisi Econòmica (UAB) and Institut d'Anàlisi Econòmica (CSIC).
    6. 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.
    Full references (including those not matched with items on IDEAS)

    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. 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.
    2. Francoise Forges, 2006. "The Ex Ante Incentive Compatible Core in Exchange Economies with and without Indivisibilities," CESifo Working Paper Series 1686, CESifo.
    3. Anna Bogomolnaia & Herve Moulin, 2004. "Random Matching Under Dichotomous Preferences," Econometrica, Econometric Society, vol. 72(1), pages 257-279, January.
    4. 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.
    5. 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.
    6. José Alcalde & José Ángel Silva-Reus, 2013. "Allocating via Priorities," QM&ET Working Papers 13-3, University of Alicante, D. Quantitative Methods and Economic Theory.
    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. repec:cdl:ucsdec:qt3xp2110t is not listed on IDEAS
    9. Ivan Balbuzanov & Maciej H. Kotowski, 2019. "Endowments, Exclusion, and Exchange," Econometrica, Econometric Society, vol. 87(5), pages 1663-1692, September.
    10. Miralles, Antonio & Pycia, Marek, 2021. "Foundations of pseudomarkets: Walrasian equilibria for discrete resources," Journal of Economic Theory, Elsevier, vol. 196(C).
    11. Rustamdjan Hakimov & C.-Philipp Heller & Dorothea Kübler & Morimitsu Kurino, 2021. "How to Avoid Black Markets for Appointments with Online Booking Systems," American Economic Review, American Economic Association, vol. 111(7), pages 2127-2151, July.
    12. Youngsub Chun & Manipushpak Mitra & Suresh Mutuswami, 2017. "Reordering an existing queue," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 49(1), pages 65-87, June.
    13. Bogomolnaia, Anna & Moulin, Herve, 2015. "Size versus fairness in the assignment problem," Games and Economic Behavior, Elsevier, vol. 90(C), pages 119-127.
    14. Abdulkadiroglu, Atila & Sonmez, Tayfun, 2003. "Ordinal efficiency and dominated sets of assignments," Journal of Economic Theory, Elsevier, vol. 112(1), pages 157-172, September.
    15. Korpela, Ville & Lombardi, Michele & Saulle, Riccardo D., 2024. "Designing rotation programs: Limits and possibilities," Games and Economic Behavior, Elsevier, vol. 143(C), pages 77-102.
    16. Roth, Alvin E. & Sonmez, Tayfun & Utku Unver, M., 2005. "Pairwise kidney exchange," Journal of Economic Theory, Elsevier, vol. 125(2), pages 151-188, December.
    17. 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.
    18. Kesten, Onur & Kurino, Morimitsu & Ünver, M. Utku, 2017. "On characterizations of the probabilistic serial mechanism involving incentive and invariance properties," Mathematical Social Sciences, Elsevier, vol. 90(C), pages 56-62.
    19. Han, Xiang, 2024. "On the efficiency and fairness of deferred acceptance with single tie-breaking," Journal of Economic Theory, Elsevier, vol. 218(C).
    20. 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.
    21. Eun Jeong Heo & Vikram Manjunath, 2017. "Implementation in stochastic dominance Nash equilibria," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 48(1), pages 5-30, January.

    More about this item

    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:ecl:riceco:2000-03. 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: the person in charge (email available below). General contact details of provider: https://edirc.repec.org/data/dericus.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.