This file is part of IDEAS, which uses RePEc data


[ Papers | Articles | Software | Books | Chapters | Authors | Institutions | JEL Classification | NEP reports | Search | New papers by email | Author registration | Rankings | Volunteers | FAQ | Blog | Help! ]

Cost sharing in a job scheduling problem

Author info | Abstract | Publisher info | Download info | Related research | Statistics
Author Info
MISHRA, Debasis
RANGARAJAN, Bharath
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.

Download Info
To download:

If you experience problems downloading a file, check if you have the proper application to view it first. Information about this may be contained in the File-Format links below. 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://www.core.ucl.ac.be/services/psfiles/dp05/dp2005_53.pdf
File Format: application/pdf
File Function:
Download Restriction: no

Publisher Info
Paper provided by Université catholique de Louvain, Center for Operations Research and Econometrics (CORE) in its series CORE Discussion Papers with number 2005053.

Download reference. The following formats are available: HTML (with abstract), plain text (with abstract), BibTeX, RIS (EndNote, RefMan, ProCite), ReDIF
Length:
Date of creation: 01 Aug 2005
Date of revision:
Handle: RePEc:cor:louvco:2005053

Contact details of provider:
Postal: Voie du Roman Pays 34, 1348 Louvain-la-Neuve (Belgium)
Phone: 32(10)474321
Fax: +32 10474301
Email:
Web page: http://www.uclouvain.be/core
More information through EDIRC

For technical questions regarding this item, or to correct its listing, contact: (Alain GILLIS).

Related research
Keywords: queueing problems; Shapley value; cost sharing; job scheduling;

Find related papers by JEL classification:
C71 - Mathematical and Quantitative Methods - - Game Theory and Bargaining Theory - - - Cooperative Games
D63 - Microeconomics - - Welfare Economics - - - Equity, Justice, Inequality, and Other Normative Criteria and Measurement
C62 - Mathematical and Quantitative Methods - - Mathematical Methods and Programming - - - Existence and Stability Conditions of Equilibrium
D71 - Microeconomics - - Analysis of Collective Decision-Making - - - Social Choice; Clubs; Committees; Associations

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

  1. 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. [Downloadable!] (restricted)
  2. Maniquet, Francois, 2003. "A characterization of the Shapley value in queueing problems," Journal of Economic Theory, Elsevier, vol. 109(1), pages 90-103, March. [Downloadable!] (restricted)
    Other versions:
  3. Moulin, Herve, 2004. "On Scheduling Fees to Prevent Merging, Splitting and Transferring of Jobs," Working Papers 2004-04, Rice University, Department of Economics. [Downloadable!]
  4. Moulin, Herve, 1992. "An Application of the Shapley Value to Fair Division with Money," Econometrica, Econometric Society, vol. 60(6), pages 1331-49, November. [Downloadable!] (restricted)
  5. Curiel, Imma & Pederzoli, Giorgio & Tijs, Stef, 1989. "Sequencing games," European Journal of Operational Research, Elsevier, vol. 40(3), pages 344-351, June. [Downloadable!] (restricted)
Full references

Cited by:
(explanations, 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.)

  1. Debasis Mishra & Bharath Rangarajan, 2007. "Cost sharing in a job scheduling problem," Social Choice and Welfare, Springer, vol. 29(3), pages 369-382, October. [Downloadable!] (restricted)
  2. Alex Gershkov & Paul Schweinzer, 2006. "When queueing is better than push and shove," Discussion Papers 144, SFB/TR 15 Governance and the Efficiency of Economic Systems, Free University of Berlin, Humboldt University of Berlin, University of Bonn, University of Mannheim, University of Munich. [Downloadable!]
    Other versions:
Statistics
Access and download statistics

Did you know? Springer Verlag was the first commercial publisher to be listed on RePEc.

This page was last updated on 2009-11-19.

This information is provided to you by IDEAS at the Department of Economics, College of Liberal Arts and Sciences, University of Connecticut using RePEc data on a server sponsored by the Society for Economic Dynamics.