The Knapsack Sequencing Problem: Computational Complexity and Mechanism Design

Dube, Devwrat (2025): The Knapsack Sequencing Problem: Computational Complexity and Mechanism Design.

Abstract

This paper introduces a combinatorial optimisation problem that we call the knapsack sequencing problem (KSP). KSP arises when the server in a sequencing problem is constrained to work in fixed-duration shifts. Each shift can be viewed as a knapsack, but unlike standard knapsack or bin-packing problems, KSP incorporates a temporal structure that distinguishes early and late shifts. The main challenge lies not in incentivising truth-telling but in algorithmically identifying the optimal partition of agents into shifts; a challenge compounded by the fact that KSP is strongly NP-hard, with the decision version being strongly NP-complete. We propose necessary conditions that efficient sequencing rules must satisfy, which help reduce the search space for feasible partitions. We show that the Vickrey–Clarke–Groves (VCG) mechanism, using the efficient sequencing rule and VCG transfers, is strategy-proof for KSP. We establish the existence of first-best mechanisms—mechanisms that are efficient, strategy-proof, and budget balanced—for a subclass (unit-capacity) of KSP requiring n shifts to serve n agents. We also show, via a three-agent example, that when budget balance is imposed together with efficiency, strategy-proofness may fail. This research highlights the difficulties in extending classical sequencing results to settings with shift constraints and contributes both theoretical insights and algorithmic considerations relevant to resource allocation mechanisms.

• Item Type: MPRA Paper
• Language: English
• Keywords: Knapsack Sequencing Problem, Combinatorial Optimisation, Mechanism Design, VCG Mechanisms, Strategy-proofness, Budget-balance, Computational Complexity
• Subjects: C - Mathematical and Quantitative Methods > C6 - Mathematical Methods ; Programming Models ; Mathematical and Simulation Modeling > C61 - Optimization Techniques ; Programming Models ; Dynamic Analysis; C - Mathematical and Quantitative Methods > C6 - Mathematical Methods ; Programming Models ; Mathematical and Simulation Modeling > C63 - Computational Techniques ; Simulation Modeling; D - Microeconomics > D6 - Welfare Economics > D61 - Allocative Efficiency ; Cost-Benefit Analysis; D - Microeconomics > D8 - Information, Knowledge, and Uncertainty > D82 - Asymmetric and Private Information ; Mechanism Design

References

Anily S, Bramel J, Simchi-Levi D (1994) Worst-case analysis of heuristics for the bin packing problem with general cost structures. Operations research 42(2):287–298. https://doi.org/https://doi.org/10.1287/opre.42.2.287

Banerjee S, De P, Mitra M (2020) A welfarist approach to sequencing problems with incentives. Working paper https://doi.org/https://doi.org/10.1007/ s00355-024-01531-4

Bikhchandani S, Chatterji S, Lavi R, et al (2006) Weak monotonicity characterizes deterministic dominant-strategy implementation. Econometrica 74(4):1109–1132. https://doi.org/https://doi.org/10.1111/j.1468-0262.2006.00695. x, URL https://onlinelibrary.wiley.com/doi/abs/10.1111/j.1468-0262.2006.00695.x, https://onlinelibrary.wiley.com/doi/pdf/10.1111/j.1468-0262.2006.00695.x

B¨orgers T (2015) An introduction to the theory of mechanism design. Oxford University Press, USA

Carbajal JC, McLennan A, Tourky R (2013) Truthful implementation and preference aggregation in restricted domains. Journal of Economic Theory 148(3):1074–1101

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.49org/10.1016/j.geb.2017.02.005

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 strategyproofness in the queueing problem. Economic Theory 56:425–442. https://doi.org/10.1007/s00199-013-0793-8

Chun Y, Mitra M, Mutuswami S (2019) A characterization of the symmetrically 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

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-250

De P, Mitra M (2019) Balanced implementability of sequencing rules. Games and Economic Behavior 118:342–353. https://doi.org/https://doi.org/10.1016/ j.geb.2019.09.005, URL https://www.sciencedirect.com/science/article/pii/ S0899825619301368

Dobzinski S, Nisan N (2009) A modular approach to roberts’ theorem. In: Mavronicolas M, Papadopoulou VG (eds) Algorithmic Game Theory. Springer Berlin Heidelberg, Berlin, Heidelberg, pp 14–23

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

Dube D (2025) Mechanism design for queueing with capacity-constrained shifts, URL https://mpra.ub.uni-muenchen.de/126465/, unpublished

Duives J, Heydenreich B, Mishra D, et al (2015) On optimal mechanism design for a sequencing problem. Journal of scheduling 18:45–59. https://doi.org/https://doi. org/10.1007/s10951-014-0378-9

Garey MR, Johnson DS (1979) Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, San Francisco

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

Hain R, Mitra M (2004) Simple sequencing problems with interdependent costs. Games and Economic Behavior 48:271–291. https://doi.org/10.1016/J.GEB.2003.09.005

Hashimoto K, Saitoh H (2012) Strategy-proof and anonymous rule in queueing problems: 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 51

Hoeksma R, Uetz M (2016) Optimal mechanism design for a sequencing problem with two-dimensional types. Operations Research 64:1438–1450. https://doi.org/10. 1287/OPRE.2016.1522

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 existence 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

Jehiel P, Meyer-ter Vehn M, Moldovanu B, et al (2006) The limits of ex post implementation. Econometrica 74(3):585–610

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 strategyproof 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

Lavi R, Mu’Alem A, Nisan N (2003) Towards a characterization of truthful combinatorial auctions. In: 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings., IEEE, pp 574–583 52

Maniquet F (2003) A characterization of the shapley value in queueing problems. Journal 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

Marchant T, Mishra D (2015) Mechanism design with two alternatives in quasi-linear environments. Social Choice and Welfare 44:433–455

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

Mishra D, Quadir A (2014) Non-bossy single object auctions. Economic Theory Bulletin 2:93–110

Mishra D, Sen A (2012) Roberts theorem with neutrality: A social welfare ordering approach. Games and Economic Behavior 75(1):283–298. https://doi.org/https: //doi.org/10.1016/j.geb.2011.11.005, URL https://www.sciencedirect.com/science/ article/pii/S0899825611001837

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 identical 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 53

Moulin H (2007) On scheduling fees to prevent merging, splitting, and transferring of jobs. Mathematics of Operations Research 32(2):266–283. https://doi.org/10.1287/ moor.1060.0239, URL https://doi.org/10.1287/moor.1060.0239

Myerson RB (1979) Incentive compatibility and the bargaining problem. Econometrica: 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 Nath S, Sen A (2015) Affine maximizers in domains with selfish valuations. ACM Transactions on Economics and Computation (TEAC) 3(4):1–19

Roberts K (1979) The characterization of implementable choice rules. Aggregation and revelation of preferences 12(2):321–348

Rochet JC (1987) A necessary and sufficient condition for rationalizability in a quasilinear context. Journal of Mathematical Economics 16(2):191–200. https://doi.org/ https://doi.org/10.1016/0304-4068(87)90007-3, URL https://www.sciencedirect. com/science/article/pii/0304406887900073

Rockafellar RT (1997) Convex Analysis, vol 18. Princeton University Press

Shao R, Zhou L (2016) Optimal allocation of an indivisible good. Games and Economic 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 54

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

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