Non-linear anonymous pricing in combinatorial auctions

Andreas Drexl (), Kurt Jörnsten and Diether Knof ()
Additional contact information
Andreas Drexl: Lehrstuhl für Produktion und Logistik, Institut für Betriebswirtschaftslehre, Christian-Albrechts-Universität zu Kiel, Postal: Lehrstuhl für Produktion und Logistik , Institut für Betriebswirtschaftslehre , Christian-Albrechts-Universität zu Kiel , Olshausenstraße 40 , D-24098 Kiel, Germany
Diether Knof: Fachgruppe Stochastik, Mathematisches Seminar, Christian-Albrechts-Universität zu Kiel, Postal: Mathematisches Seminar, Christian-Albrechts-Universität zu Kiel, Ludewig-Meyn-Str. 4, D-24098 Kiel, Germany

No 2005/6, Discussion Papers from Norwegian School of Economics, Department of Business and Management Science

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 (search for similar items in EconPapers)
JEL-codes: D44 (search for similar items in EconPapers)
Pages: 22 pages
Date: 2005-10-12
New Economics Papers: this item is included in nep-mic
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://hdl.handle.net/11250/163568 (application/pdf)
Our link check indicates that this URL is bad, the error code is: 404 Not Found (http://hdl.handle.net/11250/163568 [302 Found]--> https://www.unit.no/brage-denne-lenken-er-ikke-lenger-gyldig [301 Moved Permanently]--> https://sikt.no/brage-denne-lenken-er-ikke-lenger-gyldig)

Related works:
Journal Article: Non-linear anonymous pricing combinatorial auctions (2009)
Working Paper: Non-linear anonymous pricing combinatorial auctions (2007)
Working Paper: Non-linear anonymous pricing in combinatorial auctions (2005)
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:hhs:nhhfms:2005_006

Access Statistics for this paper

More papers in Discussion Papers from Norwegian School of Economics, Department of Business and Management Science NHH, Department of Business and Management Science, Helleveien 30, N-5045 Bergen, Norway. Contact information at EDIRC.
Bibliographic data for series maintained by Stein Fossen ().