Mechanism Design for Queueing with Capacity-Constrained Shifts

Dube, Devwrat (2025): Mechanism Design for Queueing with Capacity-Constrained Shifts.

Abstract

We study a single-server queue with fixed-length shifts $T > 1$ where service of unit length jobs is non-pre-emptive; residual time shorter than one job, namely fractional part of $T$, at boundaries is lost. Agents have constant private unit waiting costs. The efficient rule partitions agents into feasible shifts, orders shifts by the sum of members' costs, and orders agents within each shift by their costs. We show, by \citet{Holmstrom} and \citet{Suijs} type arguments, that only Vickrey-Clarke-Groves (VCG) transfers implement efficiency in dominant strategies. We then delineate when efficiency and DSIC implementation can be combined with budget balance (first-best mechanisms). If shifts are of unit-capacity ($1<T<2$) and there are at least three agents, first-best mechanisms exist and are exactly the symmetrically-balanced-VCG family. Further the anonymous-symmetrically-balanced VCG mechanisms also satisfy equal treatment of equals. With two agents, no first-best mechanism exists. If shift capacity $T>2$ is non-integral (so each shift can host at least two agents but leaves residual slack), no first-best mechanism exists. The proof uses a the cubical-array lemma of \citet{Walker} adapted to our setting.

• Item Type: MPRA Paper
• Language: English
• Keywords: Queueing, Dominant Strategy Implementation, VCG, First-Best Mechanisms
• Subjects: C - Mathematical and Quantitative Methods > C7 - Game Theory and Bargaining Theory > C72 - Noncooperative Games; D - Microeconomics > D6 - Welfare Economics > D61 - Allocative Efficiency ; Cost-Benefit Analysis; D - Microeconomics > D6 - Welfare Economics > D63 - Equity, Justice, Inequality, and Other Normative Criteria and Measurement; D - Microeconomics > D8 - Information, Knowledge, and Uncertainty > D82 - Asymmetric and Private Information ; Mechanism Design

References

Banerjee S, De P, Mitra M (2024) Generalized welfare lower bounds and strat- egyproofness in sequencing problems. Social Choice and Welfare 63(2):323– 357. https://doi.org/10.1007/s00355-024-01531-4, URL https://doi.org/10.1007/ s00355-024-01531-4

Chun Y (2006a) No-envy in queueing problems. Economic Theory 29:151–162. URL https://doi.org/10.1007/s00199-005-0011-4

Chun Y (2006b) A pessimistic approach to the queueing problem. Mathematical Social Sciences 51(2):171–181. https://doi.org/https://doi.org/10.1016/j.mathsocsci.2005. 08.002

Chun Y, Yengin D (2017) Welfare lower bounds and strategy-proofness in the queueing problem. Games and Economic Behavior 102:462–476. https://doi.org/https://doi. org/10.1016/j.geb.2017.02.005

Chun Y, Yengin D (2018) Characterizing envy-free, strategy proof, and monotonic mechanisms in queueing problem. Tech. rep., University of Adelaide, School of Economics and Public Policy

Chun Y, Mitra M, Mutuswami S (2014a) Characterizations of pivotal mechanisms in the queueing problem. Mathematical Social Sciences 72:62–66. https://doi.org/ https://doi.org/10.1016/j.mathsocsci.2014.09.005

Chun Y, Mitra M, Mutuswami S (2014b) Egalitarian equivalence and strategyproof- ness in the queueing problem. Economic Theory 56:425–442. https://doi.org/https: //doi.org/10.1007/s00199-013-0793-8

Chun Y, Mitra M, Mutuswami S (2019) A characterization of the symmetri-cally balanced vcg rule in the queueing problem. Games and Economic Behavior 118:486–490. https://doi.org/https://doi.org/10.1016/j.geb.2015.04.001

Chun Y, Mitra M, Mutuswami S (2023) Balanced vcg mechanisms for sequencing problems. Social Choice and Welfare 60(1):35–46. https://doi.org/https://doi.org/ 10.1007/s00355-020-01306-7

Clarke EH (1971) Multipart pricing of public goods. Public choice pp 17–33

Cox D (2020) Queues. ISSN, CRC Press, URL https://books.google.co.in/books?id= GTwKEAAAQBAJ

De P (2013) Incentive and normative analysis on sequencing problem. Working paper URL https://mpra.ub.uni-muenchen.de/92952/1/MPRA paper 92952.pdf

De P, Dube D (2023) No-envy, strategyproofness and cost-monotonicity in sequencing problems. ISI Delhi ACEGD 2023 Archive URL https://www.isid.ac.in/∼acegd/ acegd2023/papers/DevwratDube.pdf

De P, Mitra M (2017) Incentives and justice for sequencing problems. Economic Theory 64:239–264. https://doi.org/10.1007/S00199-016-0983-2

Dolan RJ (1978) Incentive mechanisms for priority queuing problems. The Bell Journal of Economics 9(2):421–436. URL http://www.jstor.org/stable/3003591 Green JR, Laffont JJ (1979) Incentives in Public Decision Making. North-Holland, Amsterdam

Groves T (1973) Incentives in teams. Econometrica 41(4):617–631. https://doi.org/ https://doi.org/10.2307/1914085, URL http://www.jstor.org/stable/1914085

Hashimoto K, Saitoh H (2012) Strategy-proof and anonymous rule in queueing prob- lems: a relationship between equity and efficiency. Social Choice and Welfare 38(3):473–480. https://doi.org/https://doi.org/10.1007/s00355-011-0540-7

Holmstr¨om B (1979) Groves’ scheme on restricted domains. Econometrica: Journal of the Econometric Society pp 1137–1144. https://doi.org/https://doi.org/10.2307/ 1911954

Hurwicz L, Schmeidler D (1978) Construction of outcome functions guaranteeing exis- tence and pareto optimality of nash equilibria. Econometrica 46(6):1447–1474. URL http://www.jstor.org/stable/1913838

Hurwicz L, Walker M (1990) On the generic nonoptimality of dominant-strategy allocation mechanisms: A general theorem that includes pure exchange economies. Econometrica 58(3):683–704. URL http://www.jstor.org/stable/2938196

Ju Y, Chun Y, van den Brink R (2014) Auctioning and selling positions: A non- cooperative approach to queueing conflicts. Journal of Economic Theory 153:33–45. https://doi.org/https://doi.org/10.1016/j.jet.2014.05.007

Kayı C¸ , Ramaekers E (2010) Characterizations of pareto-efficient, fair, and strategy- proof allocation rules in queueing problems. Games and Economic Behavior 68(1):220–232. https://doi.org/https://doi.org/10.1016/j.geb.2009.07.003

Maniquet F (2003) A characterization of the shapley value in queueing problems. Jour- nal of Economic Theory 109(1):90–103. https://doi.org/https://doi.org/10.1016/ S0022-0531(02)00036-4, URL https://www.sciencedirect.com/science/article/pii/ S0022053102000364

Martello S, Toth P (1990) Knapsack problems: algorithms and computer implemen- tations. John Wiley & Sons, Inc., USA

Mitra M (2001) Mechanism design in queueing problems. Economic Theory 17:277– 305. https://doi.org/https://doi.org/10.1007/PL00004107 Mitra M (2002) Achieving the first best in sequencing problems. Review of Economic Design 7:75–91. https://doi.org/https://doi.org/10.1007/s100580200071

Mitra M, Mutuswami S (2021) No-envy in the queueing problem with multiple iden- tical machines. Game Theory and Networks: New Perspectives and Directions pp 161–176

Mitra M, Sen A (2010) Efficient allocation of heterogenous commodities with balanced transfers. Social Choice and Welfare 35:29–48

Mukherjee C (2013) Weak group strategy-proof and queue-efficient mechanisms for the queueing problem with multiple machines. International Journal of Game Theory 42:131–163

Myerson RB (1979) Incentive compatibility and the bargaining problem. Economet- rica: journal of the Econometric Society pp 61–73. https://doi.org/https://doi.org/ 10.2307/1912346

Myerson RB (1981) Optimal auction design. Mathematics of operations research 6(1):58–73

´Angel Plaza (2016) Proof without words: Alternating row sums in pascal’s triangle. Mathematics Magazine 89(4):281–281. https://doi.org/10. 4169/math.mag.89.4.281, URL https://doi.org/10.4169/math.mag.89.4.281, https://doi.org/10.4169/math.mag.89.4.281

Shao R, Zhou L (2016) Optimal allocation of an indivisible good. Games and Eco- nomic Behavior 100:95–112. https://doi.org/https://doi.org/10.1016/j.geb.2016.09. 004, URL https://www.sciencedirect.com/science/article/pii/S0899825616300938

Smith WE (1956) Various optimizers for single-stage production. Naval Research Logistics Quarterly 3(1-2):59–66. https://doi.org/https://doi.org/10.1002/nav. 3800030106, https://onlinelibrary.wiley.com/doi/pdf/10.1002/nav.3800030106

Suijs J (1996) On incentive compatibility and budget balancedness in public deci- sion making. Economic design 2:193–209. https://doi.org/https://doi.org/10.1007/ BF02499133

Vickrey W (1961) Counterspeculation, auctions, and competitive sealed tenders. The Journal of finance 16(1):8–37

Walker M (1980) On the nonexistence of a dominant strategy mechanism for making optimal public decisions. Econometrica 48(6):1521–1540. https://doi.org/https:// doi.org/10.2307/1912822, URL http://www.jstor.org/stable/1912822

Yenmez MB (2015) Incentive compatible market design with applications. International Journal of Game Theory 44:543–569. https://doi.org/https://doi.org/10. 1007/s00182-014-0444-8