IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v55y2007i5p876-889.html
   My bibliography  Save this article

Minimizing the Worst Slowdown: Offline, Online

Author

Listed:
  • Hervé Moulin

    (Economics Department, Rice University, Houston, Texas 77005)

Abstract

We look for protocols (service disciplines) setting an upper bound on the slowdown (expected sojourn time divided by job size) a job may face, irrespective of the processing times of other jobs. We call this worst slowdown the liability of a job. In a scheduling problem with identical release dates, allowing the server to randomize the order of service cuts almost in half the liability profiles feasible under deterministic protocols. The same is true if cash transfers are feasible and users have linear waiting costs. When release times are arbitrary, we characterize liability functions implementable by a deterministic online protocol, where the liability depends on the number of jobs in the queue upon release of the job. In an M/D /1 queue with a given arrival rate, the liability of a job is at least its slowdown when all other jobs are of the same size. We conjecture that this liability is feasible online, and identify a probabilistic protocol exceeding it by at most 130%.

Suggested Citation

  • Hervé Moulin, 2007. "Minimizing the Worst Slowdown: Offline, Online," Operations Research, INFORMS, vol. 55(5), pages 876-889, October.
    • Handle: RePEc:inm:oropre:v:55:y:2007:i:5:p:876-889
    DOI: 10.1287/opre.1070.0447
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.1070.0447
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.1070.0447?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
    ---><---

    References listed on IDEAS

    as
    1. 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.
    2. Moulin, Herve, 1992. "Welfare bounds in the cooperative production problem," Games and Economic Behavior, Elsevier, vol. 4(3), pages 373-401, July.
    3. Demko, Stephen & Hill, Theodore P., 1988. "Equitable distribution of indivisible objects," Mathematical Social Sciences, Elsevier, vol. 16(2), pages 145-158, October.
    4. Sprumont, Yves, 1998. "Ordinal Cost Sharing," Journal of Economic Theory, Elsevier, vol. 81(1), pages 126-162, July.
    5. Moulin, Herve, 1990. "Uniform externalities : Two axioms for fair allocation," Journal of Public Economics, Elsevier, vol. 43(3), pages 305-326, December.
    6. Moulin, Herve, 1991. "Welfare bounds in the fair division problem," Journal of Economic Theory, Elsevier, vol. 54(2), pages 321-337, August.
    7. Maniquet, Francois, 2003. "A characterization of the Shapley value in queueing problems," Journal of Economic Theory, Elsevier, vol. 109(1), pages 90-103, March.
    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. Xiaotie Deng & Qi Qi & Amin Saberi, 2012. "Algorithmic Solutions for Envy-Free Cake Cutting," Operations Research, INFORMS, vol. 60(6), pages 1461-1476, December.

    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. Moulin, Herve, 2005. "Minimizing the Worst Slowdown: Off-Line and On-Line," Working Papers 2005-03, Rice University, Department of Economics.
    2. 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.
    3. Banerjee, Sreoshi, 2023. "Stability and fairness in sequencing games: optimistic approach and pessimistic scenarios," MPRA Paper 118680, University Library of Munich, Germany.
    4. Youngsub Chun & Manipushpak Mitra & Suresh Mutuswami, 2019. "Recent developments in the queueing problem," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 27(1), pages 1-23, April.
    5. Jens Hougaard & Hervé Moulin & Lars Østerdal, 2010. "Decentralized pricing in minimum cost spanning trees," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 44(2), pages 293-306, August.
    6. Chun, Youngsub & Yengin, Duygu, 2017. "Welfare lower bounds and strategy-proofness in the queueing problem," Games and Economic Behavior, Elsevier, vol. 102(C), pages 462-476.
    7. Eve Ramaekers, 2013. "Fair allocation of indivisible goods: the two-agent case," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 41(2), pages 359-380, July.
    8. Moulin, Herve, 2005. "Split-Proof Probabilistic Scheduling," Working Papers 2004-06, Rice University, Department of Economics.
    9. Banerjee, Sreoshi, 2024. "On identifying efficient, fair and stable allocations in "generalized" sequencing games," MPRA Paper 120188, University Library of Munich, Germany.
    10. Sreoshi Banerjee & Parikshit De & Manipushpak Mitra, 2024. "Generalized welfare lower bounds and strategyproofness in sequencing problems," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 63(2), pages 323-357, September.
    11. Banerjee, Sreoshi & De, Parikshit & Mitra, Manipushpak, 2020. "A welfarist approach to sequencing problems with incentives," MPRA Paper 107188, University Library of Munich, Germany.
    12. René Brink & Youngsub Chun, 2012. "Balanced consistency and balanced cost reduction for sequencing problems," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 38(3), pages 519-529, March.
    13. Maniquet, Francois, 2003. "A characterization of the Shapley value in queueing problems," Journal of Economic Theory, Elsevier, vol. 109(1), pages 90-103, March.
    14. Atay, Ata & Trudeau, Christian, 2024. "Queueing games with an endogenous number of machines," Games and Economic Behavior, Elsevier, vol. 144(C), pages 104-125.
    15. Alex Gershkov & Paul Schweinzer, 2010. "When queueing is better than push and shove," International Journal of Game Theory, Springer;Game Theory Society, vol. 39(3), pages 409-430, July.
    16. Conan Mukherjee, 2013. "Weak group strategy-proof and queue-efficient mechanisms for the queueing problem with multiple machines," International Journal of Game Theory, Springer;Game Theory Society, vol. 42(1), pages 131-163, February.
    17. Parikshit De & Manipushpak Mitra, 2017. "Incentives and justice for sequencing problems," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 64(2), pages 239-264, August.
    18. Mitra, Manipushpak & Mutuswami, Suresh, 2011. "Group strategyproofness in queueing models," Games and Economic Behavior, Elsevier, vol. 72(1), pages 242-254, May.
    19. Anna Bogomolnaia & Herv'e Moulin, 2024. "Guaranteed shares of benefits and costs," Papers 2406.14198, arXiv.org, revised Nov 2024.
    20. Ju, Yuan & Chun, Youngsub & van den Brink, René, 2014. "Auctioning and selling positions: A non-cooperative approach to queueing conflicts," Journal of Economic Theory, Elsevier, vol. 153(C), pages 33-45.

    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:inm:oropre:v:55:y:2007:i:5:p:876-889. 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: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.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.