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

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

Author

Listed:
  • Moulin, Herve

    (Rice U)

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 its user, thus merging, splitting or partially transferring jobs offer cooperative strategic opportunities. Can we design cash transfers to neutralize such manipulations? We prove that merge-proofness and split-proofness are not compatible, and that it is similarly impossible to prevent all transfers of jobs involving three agents or more. On the other hand, robustness against pair-wise transfers is feasible, and essentially characterize 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

  • Moulin, Herve, 2004. "On Scheduling Fees to Prevent Merging, Splitting and Transferring of Jobs," Working Papers 2004-04, Rice University, Department of Economics.
    • Handle: RePEc:ecl:riceco:2004-04
    as

    Download full text from publisher

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

    References listed on IDEAS

    as
    1. Maniquet, Francois, 2003. "A characterization of the Shapley value in queueing problems," Journal of Economic Theory, Elsevier, vol. 109(1), pages 90-103, March.
    2. Hain, Roland & Mitra, Manipushpak, 2004. "Simple sequencing problems with interdependent costs," Games and Economic Behavior, Elsevier, vol. 48(2), pages 271-291, August.
    3. Moulin, Herve, 1985. "Egalitarianism and Utilitarianism in Quasi-linear Bargaining," Econometrica, Econometric Society, vol. 53(1), pages 49-67, January.
    4. 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.
    5. 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.
    6. 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.
    7. Manipushpak Mitra, 2001. "Mechanism design in queueing problems," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 17(2), pages 277-305.
    8. 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.
    9. Youngsub Chun, 2000. "Agreement, separability, and other axioms for quasi-linear social choice problems," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 17(3), pages 507-521.
    10. 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.
    11. Friedman, Eric & Moulin, Herve, 1999. "Three Methods to Share Joint Costs or Surplus," Journal of Economic Theory, Elsevier, vol. 87(2), pages 275-312, August.
    12. 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.
    13. 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.
    14. 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.
    15. 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.
    16. Youngsub Chun, 2011. "Consistency and monotonicity in sequencing problems," International Journal of Game Theory, Springer;Game Theory Society, vol. 40(1), pages 29-41, February.
    17. 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. Biung-Ghi Ju & Juan D. Moreno-Ternero, 2006. "Progressivity, Inequality Reduction, and Merging-Proofness in Taxation," WORKING PAPERS SERIES IN THEORETICAL AND APPLIED ECONOMICS 200603, University of Kansas, Department of Economics, revised Feb 2006.
    2. Fan Zhang & Pramode Verma, 2011. "Pricing multi-class network services using the Shapley Value," Netnomics, Springer, vol. 12(1), pages 61-75, April.
    3. Moulin, Hervé, 2008. "Proportional scheduling, split-proofness, and merge-proofness," Games and Economic Behavior, Elsevier, vol. 63(2), pages 567-587, July.
    4. Moulin, Herve, 2005. "Split-Proof Probabilistic Scheduling," Working Papers 2004-06, Rice University, Department of Economics.
    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, vol. 29(3), pages 369-382, October.

    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. "Split-Proof Probabilistic Scheduling," Working Papers 2004-06, Rice University, Department of Economics.
    2. 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.
    3. Moulin, Hervé, 2008. "Proportional scheduling, split-proofness, and merge-proofness," Games and Economic Behavior, Elsevier, vol. 63(2), pages 567-587, July.
    4. 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.
    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, vol. 29(3), pages 369-382, October.
    6. 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.
    7. Kazuhiko Hashimoto & Hiroki Saitoh, 2008. "Strategy-Proof and Anonymous Rule in Queueing Problems: A Relationship between Equity and Efficiency," Discussion Papers in Economics and Business 08-17, Osaka University, Graduate School of Economics.
    8. Kazuhiko Hashimoto & Hiroki Saitoh, 2012. "Strategy-proof and anonymous rule in queueing problems: a relationship between equity and efficiency," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 38(3), pages 473-480, March.
    9. De, Parikshit, 2013. "Incentive and normative analysis on sequencing problem," MPRA Paper 55127, University Library of Munich, Germany.
    10. Chun, Youngsub & Mitra, Manipushpak, 2014. "Subgroup additivity in the queueing problem," European Journal of Operational Research, Elsevier, vol. 238(1), pages 281-289.
    11. 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.
    12. 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.
    13. 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.
    14. Chun, Youngsub, 2006. "A pessimistic approach to the queueing problem," Mathematical Social Sciences, Elsevier, vol. 51(2), pages 171-181, March.
    15. De, Parikshit, 2014. "Rawlsian Allocation In Queueing And Sequencing Problem," MPRA Paper 58744, University Library of Munich, Germany.
    16. Mitra, Manipushpak, 2005. "Incomplete information and multiple machine queueing problems," European Journal of Operational Research, Elsevier, vol. 165(1), pages 251-266, August.
    17. 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.
    18. 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.
    19. Youngsub Chun, 2011. "Consistency and monotonicity in sequencing problems," International Journal of Game Theory, Springer;Game Theory Society, vol. 40(1), pages 29-41, February.
    20. Youngsub Chun & Manipushpak Mitra & Suresh Mutuswami, 2023. "Balanced VCG mechanisms for sequencing problems," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 60(1), pages 35-46, 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:2004-04. 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.