The Knapsack Sequencing Problem: Computational Complexity and Mechanism Design

Devwrat Dube

MPRA Paper from University Library of Munich, Germany

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.

Keywords: Knapsack Sequencing Problem; Combinatorial Optimisation; Mechanism Design; VCG Mechanisms; Strategy-proofness; Budget-balance; Computational Complexity (search for similar items in EconPapers)
JEL-codes: C61 C63 D61 D82 (search for similar items in EconPapers)
Date: 2025-10-25
References: Add references at CitEc
Citations:

Downloads: (external link)
https://mpra.ub.uni-muenchen.de/126600/1/MPRA_paper_126600.pdf original version (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:pra:mprapa:126600

Access Statistics for this paper

More papers in MPRA Paper from University Library of Munich, Germany Ludwigstraße 33, D-80539 Munich, Germany. Contact information at EDIRC.
Bibliographic data for series maintained by Joachim Winter ().