Uppsala University Department of Information Technology

Technical Report 1999-016

Integer Programming for Automated Auctions

Arne Andersson, Mattias Tenhunen, and Fredrik Ygge

November 1999


Auctions allowing bids for combinations of items are important for (agent mediated) electronic commerce; compared to other auction mechanisms, they often increase the efficiency of the auction, while keeping risks for bidders low. The determination of an optimal winner combination in this type of auctions is a complex computational problem, which has recently attracted some research, and in this paper, we look further into the topic.

It is well known that the winner determination problem for a certain class of auctions is equivalent to what in the operations research community is referred to as (weighted) set packing. In this paper we compare some of the recent winner determination algorithms to traditional set packing algorithms, and study how more general auctions can be modeled by use of standard integer programming methods.

Note: Final version published at ICMAS-00 available from http://www.csd.uu.se/~arnea/abs/icmas00.html

Available as compressed Postscript (149 kB, no cover), Postscript (335 kB, no cover), compressed Postscript (202 kB), Postscript (452 kB), and PDF (197 kB)

Download BibTeX entry.

Uppsala Universitet