uu.seUppsala University Publications
Change search
ReferencesLink to record
Permanent link

Direct link
Analysis of a greedy algorithm for the winner determination problem in combinatorial auctions
Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Mathematics.
Manuscript (Other academic)
URN: urn:nbn:se:uu:diva-93880OAI: oai:DiVA.org:uu-93880DiVA: diva2:167508
Available from: 2005-12-30 Created: 2005-12-30 Last updated: 2010-01-13Bibliographically approved
In thesis
1. Analysis of Algorithms for Combinatorial Auctions and Related Problems
Open this publication in new window or tab >>Analysis of Algorithms for Combinatorial Auctions and Related Problems
2005 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

The thesis consists of four papers on combinatorial auctions and a summary. The first part is more of a practical nature and contains two papers. In the first paper, we study the performance of a caching technique in an optimal algorithm for a multi-unit combinatorial auction.

In the second paper, we compare the revenues from a second-price combinatorial auction against a second-price one-shot simultaneous auction. In particular, we show that when the synergy parameter is small, the combinatorial auction gives a higher expected revenue than the one-shot. This is in contrast to an earliear result by Krishna and Rosenthal. We also compare the two mechanisms under the assumption that bidders are risk-averse. Such bidders are more sensitive to financial loss (winner's curse) that they tend to bid less aggressively, which leads to lower revenues. Since a direct analytical approach turns out to be difficult, we present numerical results that show which auction mechanism maximizes the seller's revenue depending on the values of synergy and aversion parameter.

The second part is more theoretical. Here, we analyze the asymptotic performance of a greedy algorithm for a problem inspired by combinatorial auctions. In particular, we consider a special case in which every bid contains exactly 3 items, and use a Poisson process to model an auction with a random (Poisson) No. of bids. For this restricted case, winner determination problem is equivalent to a maximal 3-set packing on a weighted hypergraph, and hence NP-complete. However, the greedy algorithm approximates this special case within a factor of 3.

In the third paper, we compute the asymptotic expected size of the partial allocation and its corresponding expected total revenue from the greedy algorithm, for some distribution of bid prices.

In the final paper, we study the case of a deterministic number of bids, which is proportional to the number of distinguishable items in the auction, say M. Then, we prove that the number of bids allocated, suitably normalized, converges to a Normal random variable as M goes to infinity. As a prelude, we also prove that, both the number of bids allocated and those submitted, again suitably normalized, jointly converge in distribution to a continuous 2-dimensional Gaussian process as M goes to infinity.

Place, publisher, year, edition, pages
Uppsala: Matematiska institutionen, 2005. vii + 20 p.
Uppsala Dissertations in Mathematics, ISSN 1401-2049 ; 44
combinatorial auctions, approximation algorithm, greedy algorithm, optimal strategy
National Category
urn:nbn:se:uu:diva-6246 (URN)91-506-1842-3 (ISBN)
Public defence
2006-01-20, Room 2347, Building 2, Polacksbacken, Uppsala, 15:15
Available from: 2005-12-30 Created: 2005-12-30Bibliographically approved

Open Access in DiVA

No full text

By organisation
Department of Mathematics

Search outside of DiVA

GoogleGoogle Scholar

Total: 185 hits
ReferencesLink to record
Permanent link

Direct link