The Knapsack Sequencing Problem: Computational Complexity and Mechanism Design

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.