Generalized knapsack solvers for multi-unit combinatorial auctions

knapsack problems, combinatorial auctions, dynamic programming, optimization, economics, markets, pricing The problem of allocating discrete computational resources among agents motivates interest in general multi-unit combinatorial exchanges. This paper considers the problem of computing optimal (surplus-maximizing) allocations, assuming that agent utility functions are quasi-linear but otherwise unrestricted. We present a solver whose time and memory requirements are linear (in the pseudo-polynomial sense) in three of four natural measures of problem size: number of agents, length of bids, and units of each resource. In applications where the number of resource types is inherently a small constant, e.g., computational resource allocation, such a solver offers advantages over more elaborate approaches developed for high-dimensional problems. In this context, we also describe the deep connection between auction winner determination problems and generalized knapsack problems, which has received remarkably little attention in the literature. This connection leads directly to pseudo-polynomial solvers, informs solver benchmarking by exploiting extensive research on hard knapsack problems, and encourages a clea