| |
Click here for full text:
Generalized Knapsack Solvers for Multi-Unit Combinatorial Auctions: Analysis and Application to Computational Resource Allocation
Kelly, Terence
HPL-2004-21
Keyword(s): knapsack problems; combinatorial auctions; dynamic
programming; optimization; economics; markets; pricing
Abstract: 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 clean separation between E-Commerce research and
Operations Research.
11 Pages
Back to Index
|
printable version
