On the Coincidence of the Shapley Value and the Nucleolus in Queueing Problems

Youngsub Chun ; Toru Hokari

Professor, School of Economics, Seoul National University, Seoul 151-746, Korea, Tel: +82-2-880-6382 ychun@snu.ac.kr
Associate Professor, Institute of Social Sciences, University of Tsukuba, 1-1-1 Ten’no-dai, Tsukuba, Ibaraki 305-8571, Japan

JEL Classification: C71, D63, D71

Abstract

Given a group of agents to be served in a facility, the queueing problem is concerned with finding the order to serve agents and the (positive or negative) monetary compensations they should receive. As shown in Maniquet (2003), the minimal transfer rule coincides with the Shapley value of the game obtained by defining the worth of each coalition to be the minimum total waiting cost incurred by its members under the assumption that they are served before the non-coalitional members. Here, we show that it coincides with the nucleolus of the same game. Thereby, we establish the coincidence of the Shapley value and the nucleolus for queueing problems. We also investigate the relations between the minimal transfer rule and other rules discussed in the literature.

Keywords:

Queueing problems, Minimal transfer rule, Shapley value, Nucleolus, Coincidence

Acknowledgments

We are grateful to William Thomson, Yukihiko Funaki, René van den Brink, Eun Jeong Heo, and a referee for their comments. Chun acknowledges the support from the Advanced Strategy Program (ASP) of the Institute of Economic Research, Seoul National University, and Hokari from the Ministry of Education, Culture, Sports, Science, and Technology in Japan under grant No. 15730089 and 18730125.

References

Chun, Y. Consistency and Monotonicity in Sequencing Problems. Mimeograph, 2004.
Chun, Y. “A Pessimistic Approach to the Queueing Problem.” Mathematical Social Sciences 51 (No. 2 2006a): 171-81. [https://doi.org/10.1016/j.mathsocsci.2005.08.002]
Chun, Y. “No-envy in Queueing Problems.” Economic Theory 29 (No. 1 2006b): 151-62. [https://doi.org/10.1007/s00199-005-0011-4]
Curiel, I., Pederzoli, G., and Tijs, S. “Sequencing Games.” European Journal of Operations Research 40 (No. 3 1989): 344-51. [https://doi.org/10.1016/0377-2217(89)90427-X]
Deng, X., and Papadimitriou, C. H. “On the Complexity of Cooperative Solution Concepts.” Mathematics of Operations Research 19 (No. 2 1994): 257-66. [https://doi.org/10.1287/moor.19.2.257]
Dolan, R. “Incentive Mechanisms for Priority Queueing Problems.” Bell Journal of Economics 9 (No. 2 1978): 421-36. [https://doi.org/10.2307/3003591]
Dutta, B., and Ray, D. “A Concept of Egalitarianism under Participation Constraints.” Econometrica 57 (No. 3 1989): 615-35. [https://doi.org/10.2307/1911055]
de Frutos, M. A. “Decreasing Serial Cost Sharing under Economies of Scale.” Journal of Economic Theory 79 (No. 2 1998): 245-75. [https://doi.org/10.1006/jeth.1998.2393]
Kohlberg, E. “On the Nucleolus of a Characteristic Function Game.” SIAM Journal on Applied Mathematics 20 (No. 1 1971): 62-6. [https://doi.org/10.1137/0120009]
Maniquet, F. “A Characterization of the Shapley Value in Queueing Problems.” Journal of Economic Theory 109 (No. 1 2003): 90-103. [https://doi.org/10.1016/S0022-0531(02)00036-4]
Mitra, M. “Mechanism Design in Queueing Problems.” Economic Theory 17 (No. 2 2001): 277-305. [https://doi.org/10.1007/PL00004107]
Mitra, M. “Achieving the First Best in Sequencing Problems.” Review of Economic Design 7 (No. 1 2002): 75-91. [https://doi.org/10.1007/s100580200071]
Moulin, H. On Scheduling Fees to Prevent Merging, Splitting and Trasnferring of Jobs. Mimeograph, 2004, Forthcoming in Mathematics of Operations Research.
van den Nouweland, A., Borm, P., van Golstein Brouwers, W., Groot Bruinderink, R., and Tijs, S. “A Game Theoretic Approach to Problems in Telecommunication.” Management Science 42 (No. 2 1996): 294-303. [https://doi.org/10.1287/mnsc.42.2.294]
Schmeidler, D. “The Nucleolus of a Characteristic Function Game.” SIAM Journal on Applied Mathematics 17 (No. 6 1969): 1163-70. [https://doi.org/10.1137/0117107]
Shapley, L. S. “A Value for n-Person Games.” in H. W. Kuhn and A. W. Tucker (eds.), Contributions to the Theory of Games II, Annals of Mathematics Studies. No. 28, pp. 307-17, Princeton, NJ: Princeton University Press, 1953. [https://doi.org/10.1515/9781400881970-018]
Suijs, J. “On Incentive Compatibility and Budget Balancedness in Public Decision Making.” Review of Economic Design 2 (No. 1 1996): 193-209. [https://doi.org/10.1007/BF02499133]
Tijs, S. H. “An Axiomatization of the τ-value.” Mathematical Social Sciences 13 (No. 2 1987): 177-81. [https://doi.org/10.1016/0165-4896(87)90054-0]