Advanced Search
MyIDEAS: Login to save this article or follow this journal

Cost sharing in a job scheduling problem

Contents:

Author Info

  • Debasis Mishra

    ()

  • Bharath Rangarajan

    ()

Abstract

A set of jobs need to be served by a server which can serve only one job at a time. Jobs have processing times and incur waiting costs (linear in their waiting time). The jobs share their costs through compensation using monetary transfers. In the first part, we provide an axiomatic characterization of the Shapley value rule by introducing some fairness axioms that are new in the literature. In the second part, we use linear programming duality to provide an alternate characterization of the Shapley value rule. Here, we use the idea of decomposition of transfers and the notion of pairwise no-envy allocation. Of the family of allocation rules that satisfy pairwise noenvy, the Shapley value rule is the one with the minimum sum of absolute values of transfers. We discuss no-envy rules and show that no-envy is not possible in general. If processing times of all jobs are equal, then it is possible to design no-envy rules, and we characterize all no-envy rules for this case.

(This abstract was borrowed from another version of this item.)

Download Info

If you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.
File URL: http://hdl.handle.net/10.1007/s00355-006-0210-3
Download Restriction: Access to full text is restricted to subscribers.

As the access to this document is restricted, you may want to look for a different version under "Related research" (further below) or search for a different version of it.

Bibliographic Info

Article provided by Springer in its journal Social Choice and Welfare.

Volume (Year): 29 (2007)
Issue (Month): 3 (October)
Pages: 369-382

as in new window
Handle: RePEc:spr:sochwe:v:29:y:2007:i:3:p:369-382

Contact details of provider:
Web page: http://link.springer.de/link/service/journals/00355/index.htm

Order Information:
Web: http://link.springer.de/orders.htm

Related research

Keywords:

Other versions of this item:

Find related papers by JEL classification:

References

References listed on IDEAS
Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:
as in new window
  1. Flip Klijn & Estela Sánchez, 2006. "Sequencing games without initial order," Computational Statistics, Springer, vol. 63(1), pages 53-62, February.
  2. Moulin, Herve, 1992. "An Application of the Shapley Value to Fair Division with Money," Econometrica, Econometric Society, vol. 60(6), pages 1331-49, November.
  3. MISHRA, Debasis & RANGARAJAN, Bharath, 2005. "Cost sharing in a job scheduling problem," CORE Discussion Papers 2005053, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
  4. Manipushpak Mitra, 2002. "Achieving the first best in sequencing problems," Review of Economic Design, Springer, vol. 7(1), pages 75-91.
  5. Curiel, I. & Pederzoli, G. & Tijs, S.H., 1989. "Sequencing games," Open Access publications from Tilburg University urn:nbn:nl:ui:12-154243, Tilburg University.
  6. Roth,Alvin E. (ed.), 2005. "The Shapley Value," Cambridge Books, Cambridge University Press, number 9780521021333, April.
  7. Curiel, Imma & Pederzoli, Giorgio & Tijs, Stef, 1989. "Sequencing games," European Journal of Operational Research, Elsevier, vol. 40(3), pages 344-351, June.
  8. Maniquet, F., 2000. "A Characterization of the Shapley Value in Queueing Problems," Papers 222, Notre-Dame de la Paix, Sciences Economiques et Sociales.
  9. Hamers, H.J.M. & Suijs, J.P.M. & Tijs, S.H. & Borm, P.E.M., 1996. "The split core of sequencing games," Open Access publications from Tilburg University urn:nbn:nl:ui:12-72471, Tilburg University.
  10. Moulin, Herve, 2004. "On Scheduling Fees to Prevent Merging, Splitting and Transferring of Jobs," Working Papers 2004-04, Rice University, Department of Economics.
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 in new window

Cited by:
  1. Gershkov, Alex & Schweinzer, Paul, 2006. "When queueing is better than push and shove," Discussion Paper Series of SFB/TR 15 Governance and the Efficiency of Economic Systems 144, Free University of Berlin, Humboldt University of Berlin, University of Bonn, University of Mannheim, University of Munich.
  2. Rene van den Brink & Youngsub Chun, 2010. "Balanced Consistency and Balanced Cost Reduction for Sequencing Problems," Tinbergen Institute Discussion Papers 10-035/1, Tinbergen Institute.
  3. 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 and Osaka School of International Public Policy (OSIPP).
  4. Debasis Mishra & Bharath Rangarajan, 2007. "Cost sharing in a job scheduling problem," Social Choice and Welfare, Springer, vol. 29(3), pages 369-382, October.
  5. Kazuhiko Hashimoto & Hiroki Saitoh, 2012. "Strategy-proof and anonymous rule in queueing problems: a relationship between equity and efficiency," Social Choice and Welfare, Springer, vol. 38(3), pages 473-480, March.
  6. Rene van den Brink & Youngsub Chun & Yuan Ju, 2014. "Auctioning and Selling Positions: A Non-cooperative Approach to Queuing Conflicts," Tinbergen Institute Discussion Papers 14-016/II, Tinbergen Institute.
  7. Fan Zhang & Pramode Verma, 2011. "Pricing multi-class network services using the Shapley Value," Netnomics, Springer, vol. 12(1), pages 61-75, April.

Lists

This item is not listed on Wikipedia, on a reading list or among the top items on IDEAS.

Statistics

Access and download statistics

Corrections

When requesting a correction, please mention this item's handle: RePEc:spr:sochwe:v:29:y:2007:i:3:p:369-382. 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: (Guenther Eichhorn) or (Christopher F Baum).

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 references are entirely missing, you can add them using this form.

If the full references list an item that is present in RePEc, but the system did not link 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 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.