Discussion Papers, Department of Finance and Management Science, Norwegian School of Economics (NHH)
No 2005/6:
Non-linear anonymous pricing in combinatorial auctions
Andreas Drexl ()
, Kurt Jörnsten ()
and Diether Knof ()
Abstract: In combinatorial auctions the pricing problem is of main
concern since it is the means by which the auctioneer signals the result of
the auction to the participants. In order for the auction to be regarded as
fair among the various participants the price signals should be such that a
participant that has won a subset of items knows why his bid was a winning
bid and that agents that have not acquired any item easily can detect why
they lost. The problem in the combinatorial auction setting is that the
winner determination problem is a hard integer programming problem and
hence in general there does not exist a linear pricing scheme supporting
the optimal allocation. This means that single item prices, that support
the optimal allocation can in general not be found. In this article we
present an alternative.
From integer programming duality theory we know
that there exist non-linear anonymous price functions that support the
optimal allocation. In this paper we will provide a means to obtain a
simple form of a non-linear anonymous price system that supports the
optimal allocation. Our method relies on the fact that we separate the
solution of the winner determination problem and the pricing problem. This
separation yields a non-linear price function of a much simpler form
compared to when the two problems are solved simultaneously. The pure
pricing problem is formulated as a mixed-integer program. If solving this
program is too demanding computationally a heuristic can be used which
essentially requires us to solve a sequence of linear programming
relaxations of a new mixed-integer programming formulation of the pricing
problem. The procedure is computationally tested using instances of the
combinatorial auctions test suite.
Keywords: Combinatorial auctions; set packing; duality theory; non-linear anonymous prices; (follow links to similar papers)
JEL-Codes: D44; (follow links to similar papers)
22 pages, October 12, 2005
Before downloading any of the electronic versions below
you should read our statement on
copyright.
Download GhostScript
for viewing Postscript files and the
Acrobat Reader for viewing and printing pdf files.
Full text versions of the paper:
0605.pdf 
Download Statistics
Questions (including download problems) about the papers in this series should be directed to Stein Fossen ()
Report other problems with accessing this service to Sune Karlsson ()
or Helena Lundin ().
Programing by
Design by Joachim Ekebom
