IDEAS home Printed from https://ideas.repec.org/a/inm/ormoor/v32y2007i2p266-283.html
   My bibliography  Save this article

On Scheduling Fees to Prevent Merging, Splitting, and Transferring of Jobs

Author

Listed:
  • Hervé Moulin

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

Abstract

A deterministic server is shared by users with identical linear waiting costs, requesting jobs of arbitrary lengths. Shortest jobs are served first for efficiency. The server can monitor the length of a job but not the identity of the job’s user, thus merging, splitting, or partially transferring jobs offer cooperative strategic opportunities. Can we design cash transfers to neutralize such manipulations? We prove that mergeproofness and splitproofness are not compatible, and that it is similarly impossible to prevent all transfers of jobs involving three or more agents. On the other hand, robustness against pairwise transfers is feasible and essentially characterizes a one-dimensional set of scheduling methods. This line is borne by two outstanding methods: the merge-proof S + and the split-proof S - . Splitproofness, unlike mergeproofness, is not compatible with several simple tests of equity. Thus, the two properties are far from equally demanding.

Suggested Citation

  • Hervé Moulin, 2007. "On Scheduling Fees to Prevent Merging, Splitting, and Transferring of Jobs," Mathematics of Operations Research, INFORMS, vol. 32(2), pages 266-283, May.
  • Handle: RePEc:inm:ormoor:v:32:y:2007:i:2:p:266-283
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/moor.1060.0239
    Download Restriction: no

    Other versions of this item:

    References listed on IDEAS

    as
    1. Maniquet, Francois, 2003. "A characterization of the Shapley value in queueing problems," Journal of Economic Theory, Elsevier, pages 90-103.
    2. Thomas Kittsteiner & Benny Moldovanu, 2005. "Priority Auctions and Queue Disciplines That Depend on Processing Time," Management Science, INFORMS, vol. 51(2), pages 236-248, February.
    3. Moulin, Herve, 1985. "Egalitarianism and Utilitarianism in Quasi-linear Bargaining," Econometrica, Econometric Society, vol. 53(1), pages 49-67, January.
    4. Biung-Ghi Ju, 2003. "Manipulation via merging and splitting in claims problems," Review of Economic Design, Springer;Society for Economic Design, vol. 8(2), pages 205-215, October.
    5. Friedman, Eric & Moulin, Herve, 1999. "Three Methods to Share Joint Costs or Surplus," Journal of Economic Theory, Elsevier, pages 275-312.
    6. M. Angeles de Frutos, 1999. "Coalitional manipulations in a bankruptcy problem," Review of Economic Design, Springer;Society for Economic Design, vol. 4(3), pages 255-272.
    7. SPRUMONT, Yves, 2004. "Aumann-Shapley Pricing: A Reconsideration of the Discrete Case," Cahiers de recherche 11-2004, Centre interuniversitaire de recherche en économie quantitative, CIREQ.
    8. Curiel, I. & Pederzoli, G. & Tijs, S.H., 1989. "Sequencing games," Other publications TiSEM cd695be5-0f54-4548-a952-2, Tilburg University, School of Economics and Management.
    9. Hamers, Herbert & Suijs, Jeroen & Tijs, Stef & Borm, Peter, 1996. "The Split Core for Sequencing Games," Games and Economic Behavior, Elsevier, vol. 15(2), pages 165-176, August.
    10. Hain, Roland & Mitra, Manipushpak, 2004. "Simple sequencing problems with interdependent costs," Games and Economic Behavior, Elsevier, vol. 48(2), pages 271-291, August.
    11. Manipushpak Mitra, 2001. "Mechanism design in queueing problems," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), pages 277-305.
    12. Manipushpak Mitra, 2002. "Achieving the first best in sequencing problems," Review of Economic Design, Springer;Society for Economic Design, vol. 7(1), pages 75-91.
    13. Flip Klijn & Estela Sánchez, 2006. "Sequencing games without initial order," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 63(1), pages 53-62, February.
    14. Curiel, Imma & Pederzoli, Giorgio & Tijs, Stef, 1989. "Sequencing games," European Journal of Operational Research, Elsevier, vol. 40(3), pages 344-351, June.
    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. JU, Biung-Ghi & MORENO-TERNERO, Juan D., 2006. "Progressivity, inequality reduction and merging-proofness in taxation," CORE Discussion Papers 2006075, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    2. 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.
    3. Moulin, Herve, 2005. "Split-Proof Probabilistic Scheduling," Working Papers 2004-06, Rice University, Department of Economics.
    4. repec:eee:matsoc:v:90:y:2017:i:c:p:73-79 is not listed on IDEAS
    5. Debasis Mishra & Bharath Rangarajan, 2007. "Cost sharing in a job scheduling problem," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, pages 369-382.

    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:ormoor:v:32:y:2007:i:2:p:266-283. See general information about how to correct material in RePEc.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Mirko Janc). General contact details of provider: http://edirc.repec.org/data/inforea.html .

    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 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.

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service hosted by the Research Division of the Federal Reserve Bank of St. Louis . RePEc uses bibliographic data supplied by the respective publishers.