Abstract
A set of jobs need to be served by a server which can serve only one job at a time. Every job has a processing time and incurs cost due to waiting (linear in its waiting time). The jobs share their costs using monetary transfers. We provide an axiomatic characterization of the Shapley value solution for this problem.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Chun Y (2004a) A note on Maniquet’s characterization of the Shapley value in queueing problems. Working Paper, Rochester University
Chun Y (2004b) Consistency and monotonicity in sequencing problems. Working Paper, Seoul National University
Curiel I, Pederzoli G, Tijs S (1989) Sequencing games. Eur J Oper Res 40:344–351
Hamers H, Suijs J, Tijs S, Borm P (1996) The split core for sequencing games. Games Econ Behav 15:165–176
Katta A-K, Sethuraman J (2005) Cooperation in queues. Working Paper, Columbia University
Maniquet F (2003) A characterization of the Shapley value in queueing problems. J Econ Theory 109:90–103
Mishra D, Rangarajan B (2005a) Cost sharing in a job scheduling problem. Technical report, CORE, Discussion Paper 2005-53
Mishra D, Rangarajan B (2005b) Cost sharing in a job scheduling problem using the Shapley Value. In: Proceedings of 6th ACM conference on electronic commerce (EC’ 05)
Mitra M (2002) Achieving the first best in sequencing problems. Rev Econ Des 7:75–91
Moulin H (1992a) An Application of the Shapley value to fair division with money. Econometrica 6(60):1331–1349
Moulin H (2004) On scheduling fees to prevent merging, splitting and transferring of jobs. Working Paper, Rice University
Shapley LS (1953) Contributions to the theory of games II. In: Kuhn HW, Tucker AW (eds) Value for n-person games. Annals of mathematics studies, pp 307–317, chapt A
Smith WE (1956) Various optimizers for single-stage production. Naval Res Logistics Quarterly 3:59–66
Suijs J (1996) On incentive compatibility and budget balancedness in public decision making. Econ Des 2:193–209
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Mishra, D., Rangarajan, B. Cost sharing in a job scheduling problem. Soc Choice Welfare 29, 369–382 (2007). https://doi.org/10.1007/s00355-006-0210-3
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00355-006-0210-3