Abstract
A group of agents must be served in a facility. The facility can serve only one agent at a time and agents incur waiting costs. The queueing problems is concerned with finding the order to serve agents and the monetary transfers. It can be solved by taking various approaches: the cooperative game theoretic approach, the normative approach, the strategic approach, the bargaining approach, and the combination of these approaches. In this paper, we provide a survey on the recent developments in the queueing problem.
Similar content being viewed by others
Notes
See Chun (2016) for a survey of the literature on the queueing problem.
For any set A, |A| denotes the cardinality of A.
\(\mathbb {R}_{+}\) denotes the non-negative orthant of the real line.
For example, the bankruptcy problem discussed in Thomson (2003).
Kar et al. (2009), by taking a general set of queueing games that includes all convex combinations of the optimistic queueing game and the pessimistic queueing game, obtained the coincidence between the Shapley value and the prenucleolus.
Moulin (2007) makes the same observation for the scheduling problem.
Since we assume an existence of a tie-breaking rule, we always have a unique queue satisfying queue-efficiency. As a consequence, we do not need either Pareto-indifference or anonymity in the statement of our theorems.
For this, a position in a queue is considered as an indivisible good.
Group no-envy extends the notion of no-envy to groups. See Svensson (1983) for details.
These are allocations that can be supported as Walrasian equilibrium with an equal implicit income.
Object-efficiency requires that there is no feasible allocation which makes every agent better off and at least one agent strictly better off.
Since t depends on the choice of the queue, we should denote the transfers by \(t(\sigma (\theta ))\) instead of \(t(\theta )\). Note that our (single-valued) rule chooses a unique queue which in turn determines the unique transfers. Therefore, we abuse the notation and write \(t(\theta )\).
References
Barberà S (2011) Strategyproof social choice. In: Arrow KJ, Sen AK, Suzumura K (eds) Handbook of social choice and welfare, vol 2. Elsevier, Amsterdam, pp 731–831
Bevia C (1996) Identical preferences lower bound solution and consistency in economies with indivisible goods. Soc Choice Welf 13:113–126
Chun Y (2006a) A pessimistic approach to the queueing problem. Math Socl Sc 51:171–181
Chun Y (2006b) No-envy in queueing problems. Econ Theory 29:151–162
Chun Y (2011) Consistency and monotonicity in sequencing problems. Int J Game Theory 40:29–41
Chun Y (2016) Fair queueing. Springer, Berlin
Chun Y, Heo EJ (2008) Queueing problems with two parallel servers. Int J Econ Theory 4:299–315
Chun Y, Hokari T (2007) On the coincidence of the Shapley value and the nucleolus in queueing problems. Seoul J Econ 20(2):223–237
Chun Y, Mitra M, Mutuswami S (2014a) Characterizations of pivotal mechanisms in the queueing problem. Math Socl Sci 72:62–66
Chun Y, Mitra M, Mutuswami S (2014b) Egalitarian equivalence and strategyproofness in the queueing problem. Econc Theory 56(2):425–442
Chun Y, Mitra M, Mutuswami S (2017) Reordering an existing queue. Soc Choice Welf 49:65–87
Chun Y, Mitra M, Mutuswami S. A characterization of the symmetrically balanced VCG rule in the queueing problem. Games Econ Behav. https://doi.org/10.1016/j.geb.2015.04.001 (in press)
Chun Y, Park B (2017) A graph theoretic approach to the slot allocation problem. Soc Choice Welf 48:133–152
Chun Y, Yengin D (2017) Welfare lower bounds and strategy-proofness in the queueing problem. Games Econo Behav 102:462–476
Clarke EH (1971) Multi-part pricing of public goods. Public Choice 11:17–33
Cres H, Moulin H (2001) Scheduling with opting out: Improving upon random priority. Oper Res 49:565–577
Curiel I, Pederzoli G, Tijs S (1989) Sequencing games. Eur J Oper Res 40:344–351
de Frutos MA (1998) Decreasing serial cost sharing under economies of scale. J Econ Theory 79:245–275
Deng X, Papadimitriou CH (1994) On the complexity of cooperative solution concepts. Math Oper Res 19:257–266
Dolan RJ (1978) Incentive mechanisms for priority queuing problems. Bell J Econ 9:421–436
Foley D (1967) Resource allocation and the public sector. Yale Econ Essays 7:45–98
Gershkov A, Schweinzer P (2010) When queueing is better than push and shove. Int J Game Theory 39:409–430
Ghosh S, Long Y, Mitra M (2018) Prior-free on-line mechanisms for the dynamic queueing problem. Mimeo
Groves T (1973) Incentives in teams. Econometrica 41:617–631
Gul F (1989) Bargaining foundations of Shapely value. Econometrica 57:81–95
Hain R, Mitra M (2004) Simple sequencing problems with interdependent costs. Games Econ Behav 48:271–291
Hart S, Mas-Colell A (1996) Bargaining and value. Econometrica 64:357–380
Hashimoto K, Saitoh H (2012) Strategy-proof and anonymous rule in queueing problems: a relationship between equity and efficiency. Soc Choice Welf 38:473–480
Holmström B (1979) Groves’ schemes on restricted domains. Econometrica 47:1137–1144
Hougaard J, Moreno-Ternero J, Østerdal LP (2014) Assigning agents to a line. Games Econ Behav 87:539–553
Ju Y (2013) Efficiency and compromise: a bid-offer counteroffer mechanism with two players. Int J Game Theory 42:501–520
Ju Y, Chun Y, van den Brink R (2014) Auctioning and selling positions: a non-cooperative approach to queueing conflicts. J Econ Theory 153:33–45
Ju Y, Wettstein D (2009) Implementing cooperative solution concepts: a generalized bidding approach. Econ Theory 39:307–330
Kar A, Mitra M, Mutuswami S (2009) On the coincidence of the prenucleolus and the Shapley vlaue. Math Socl Sci 57:16–25
Kayi C, Ramaekers E (2010) Characterizations of Pareto-efficient, fair, and strategy-proof allocation rules in queueing problems. Games Econ Behav 68:220–232
Kayi C, Ramaekers E (2015) Corrigendum to “Characterizations of Pareto-efficient, fair, and strategy-proof allocation rules in queueing problems” [Games Econ. Behav. 68 (1) (2010) 220–232]. Games Econ Behav. https://doi.org/10.1016/j.geb.2015.01.006
Maniquet F (2003) A characterization of the Shapley value in queueing problems. J Econ Theory 109:90–103
Mitra M (2001) Mechanism design in queueing problems. Econ Theory 17:277–305
Mitra M (2002) Achieving the first best in sequencing problems. Rev Econ Design 7:75–91
Mitra M (2005) Incomplete information and multiple machine queueing problems. Eur J Oper Res 165:251–266
Mitra M (2007) Preferences lower bound in the queueing model. In: Chakrabarti BK, Chatterjee A (eds) Econophysics of markets and business networks, new economic window series. Springer, Milan, pp 233–237
Mitra M, Mutuswami S (2011) Group strategyproofness in queueing models. Games Econ Behav 72:242–254
Moulin H (1981) Implementing just and efficient decision making. J Public Econ 16:193–213
Moulin H (1990) Fair division under joint ownership: recent results and open problems. Soc Choice Welf 7:149–170
Moulin H (1991) Welfare bounds in the fair division problem. J Econ Theory 54:321–337
Moulin H (2007) On scheduling fees to prevent merging, splitting, and transferring of jobs. Math Oper Res 32:266–283
Moulin H, Shenker S (1992) Serial cost sharing. Econometrica 50(5):1009–1039
Mukherjee C (2013) Weak group strategy-proof and queue-efficient mechanisms for the queueing problem with multiple machines. Int J Game Theory 42:131–163
Parikshit D, Mitra M (2017) Incentives and justice for sequencing problems. Econ Theory 64:239–264
Pazner E, Schmeidler D (1978) Egalitarian equivalent allocations: a new concept of equity. Q J Econ 92:671–687
Pérez-Castrillo D, Wettstein D (2001) Bidding for the surplus: a non-cooperative approach to the Shapley value. J Econ Theory 100:274–294
Schmeidler D (1969) The nucleolus of a characteristic function game. SIAM J Appl Math 17:1163–1170
Schummer J, Abizada A (2017) Incentives in landing slot problems. J Econ Theory 170:29–55
Schummer J, Vohra R (2013) Assignment of arrival slsots. Am Econ J Microecon 5(2):164–185
Shapley LS (1953) A value for \(n\)-person games. In: Kuhn HW, Tucker AW (eds) Contributions to the theory of games II, annals of mathematical studies 28. Princeton University Press, Princeton, pp 307–317
Suijs J (1996) On incentive compatibility and budget balancedness in public decision making. Econ Design 2:193–209
Svensson LG (1983) Large indivisibiities: an analysis with respect to price equilibrium and fairness. Econometrica 51:939–954
Thomson W (1990) On the non-existence of envy-free and egalitarian-equivalent allocations in economies with indivisibilities. Econ Lett 34:227–229
Thomson W (2003) How to divide when there isn’t enough: from the Talmud to game theory. Book Manuscript. University of Rochester
Thomson W (2013) Strategy-proof allocation rules. Book manuscript. University of Rochester
Thomson W, Varian H (1985) Theories of justice based on symmetry, chapter 4. In: Hurwicz L, Schmeidler D, Sonnenschein H (eds) Social goals and social organization: essays in memory of E. Pazner. Cambridge University Press, Cambridge, pp 107–129
Tijs SH (1987) An axiomatization of the \(\tau \)-value. Math Soc Sci 13:177–181
van den Brink R, Chun Y (2012) Balanced consistency and balanced cost reduction for sequencing problems. Soc Choice Welf 38:519–529
van den Nouweland A, Borm P, van Golstein Brouwers W, Groot Bruinderink R, Tijs S (1996) A game theoretic approach to problems in telecommunication. Manag Sci 42:294–303
Vickrey W (1961) Counterspeculation, auctions and competitive sealed tenders. J Finance 16:8–37
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
This invited paper is discussed in the comments available at https://doi.org/10.1007/s11750-019-00500-w, https://doi.org/10.1007/s11750-019-00501-9, https://doi.org/10.1007/s11750-019-00502-8.
We are grateful to Gustavo Bergantiños for his comments. Chun’s work was supported by the National Research Foundation of Korea Grant funded by the Korean Government (NRF-2016S1A3A2924944).
Rights and permissions
About this article
Cite this article
Chun, Y., Mitra, M. & Mutuswami, S. Recent developments in the queueing problem. TOP 27, 1–23 (2019). https://doi.org/10.1007/s11750-019-00499-0
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11750-019-00499-0
Keywords
- Queueing problem
- Cooperative game theoretic approach
- Normative approach
- Strategic approach
- Bargaining approach