Cost sharing in a job scheduling problem
AbstractA 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 InfoIf 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.
Bibliographic InfoPaper provided by Université catholique de Louvain, Center for Operations Research and Econometrics (CORE) in its series CORE Discussion Papers with number 2005053.
Date of creation: 00 Aug 2005
Date of revision:
Contact details of provider:
Postal: Voie du Roman Pays 34, 1348 Louvain-la-Neuve (Belgium)
Fax: +32 10474304
Web page: http://www.uclouvain.be/core
More information through EDIRC
queueing problems; Shapley value; cost sharing; job scheduling;
Other versions of this item:
- 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; Programming Models; Mathematical and Simulation Modeling - - - Existence and Stability Conditions of Equilibrium
- D71 - Microeconomics - - Analysis of Collective Decision-Making - - - Social Choice; Clubs; Committees; Associations
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.:
- Moulin, Herve, 2004. "On Scheduling Fees to Prevent Merging, Splitting and Transferring of Jobs," Working Papers 2004-04, Rice University, Department of Economics.
- Flip Klijn & Estela S?chez, 2004. "Sequencing Games without Initial Order," UFAE and IAE Working Papers 622.04, Unitat de Fonaments de l'Anàlisi Econòmica (UAB) and Institut d'Anàlisi Econòmica (CSIC).
- Roth,Alvin E. (ed.), 2005. "The Shapley Value," Cambridge Books, Cambridge University Press, number 9780521021333, November.
- 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).
- Curiel, Imma & Pederzoli, Giorgio & Tijs, Stef, 1989. "Sequencing games," European Journal of Operational Research, Elsevier, vol. 40(3), pages 344-351, June.
- Maniquet, F., 2000.
"A Characterization of the Shapley Value in Queueing Problems,"
222, Notre-Dame de la Paix, Sciences Economiques et Sociales.
- Maniquet, Francois, 2003. "A characterization of the Shapley value in queueing problems," Journal of Economic Theory, Elsevier, vol. 109(1), pages 90-103, March.
- Moulin, Herve, 1992. "An Application of the Shapley Value to Fair Division with Money," Econometrica, Econometric Society, vol. 60(6), pages 1331-49, November.
- 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.
- Manipushpak Mitra, 2002.
"Achieving the first best in sequencing problems,"
Review of Economic Design,
Springer, vol. 7(1), pages 75-91.
- Curiel, I. & Pederzoli, G. & Tijs, S.H., 1989. "Sequencing games," Open Access publications from Tilburg University urn:nbn:nl:ui:12-154243, Tilburg University.
- 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).
- 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.
- Fan Zhang & Pramode Verma, 2011. "Pricing multi-class network services using the Shapley Value," Netnomics, Springer, vol. 12(1), pages 61-75, April.
- Alex Gershkov & Paul Schweinzer, 2010.
"When queueing is better than push and shove,"
International Journal of Game Theory,
Springer, vol. 39(3), pages 409-430, July.
- 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.
- Alex Gershkov & Paul Schweinzer, 2006. "When Queuening is Better than Push and Shove," Bonn Econ Discussion Papers bgse10_2006, University of Bonn, Germany.
- Debasis Mishra & Bharath Rangarajan, 2007.
"Cost sharing in a job scheduling problem,"
Social Choice and Welfare,
Springer, vol. 29(3), pages 369-382, October.
- René Brink & Youngsub Chun, 2012. "Balanced consistency and balanced cost reduction for sequencing problems," Social Choice and Welfare, Springer, vol. 38(3), pages 519-529, March.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Alain GILLIS).
If references are entirely missing, you can add them using this form.