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

Direct link
BETA
Holmström, Jim
Alternative names
Publications (4 of 4) Show all publications
Andersson, A. & Wilenius, J. (2009). A New Analysis of Revenue in the Combinatorial and Simultaneous Auction.
Open this publication in new window or tab >>A New Analysis of Revenue in the Combinatorial and Simultaneous Auction
2009 (English)Report (Other academic)
Abstract [en]

We prove that in many cases, a first-price sealed-bid combinatorial auction gives higher expected revenue than a sealed-bid simultaneous auction. This is the first theoretical evidence that combinatorial auctions indeed generate higher revenue, which has been a common belief for decades.

We use a model with many bidders and items, where bidders are of two types: (i) single-bidders interested in only one item and (ii) synergy-bidders, each interested in one random combination of items. We provide an upper bound on the expected revenue for simultaneous auctions and a lower bound on combinatorial auctions. Our bounds are parameterized on the number of bidders and items, combination size, and synergy.

We derive an asymptotic result, proving that as the number of bidders approach infinity, expected revenue of the combinatorial auction will be higher than that of the simultaneous auction. We also provide concrete examples where the combinatorial auction is revenue-superior.

Series
Technical report / Department of Information Technology, Uppsala University, ISSN 1404-3203 ; 2009-001
Keywords
combinatorial auction, first-price, equilibrium, strategy, expected revenue, multi-object auction, auction, multiple-item, simulatneous auction, bidding, synergy, synergies, game theory
National Category
Computer Sciences
Identifiers
urn:nbn:se:uu:diva-102935 (URN)
Available from: 2009-05-13 Created: 2009-05-13 Last updated: 2018-01-13Bibliographically approved
Wilenius, J. (2009). Combinatorial and Simultaneous Auction: A Pragmatic Approach to Tighter Bounds on Expected Revenue.
Open this publication in new window or tab >>Combinatorial and Simultaneous Auction: A Pragmatic Approach to Tighter Bounds on Expected Revenue
2009 (English)Report (Other academic)
Abstract [en]

It is a common belief that combinatorial auctions provide good solutions to resource-allocation in multiple-object markets with synergies. In this work we adopt a pragmatic approach to examining the revenue bounds on combinatorial and simultaneous auctions. The theoretical bounds from our previous work utilize a large number of bidders in order to show that combinatorial auctions yield a higher expected revenue. It is reasonable to believe that the true bounds are much tighter. We argue that this is the indeed the case and that the first-price combinatorial auction is revenue superior even when a relatively small number of bidders participate. The argument is based on three methods. (i) heuristic equilibrium-strategy search, (ii) sampling of the expected revenue in the first-price sealed-bid combinatorial auction, and (iii) a tightened theoretical upper bound on the sealed-bid simultaneous auction in the case of few bidders.

Series
Technical report / Department of Information Technology, Uppsala University, ISSN 1404-3203 ; 2009-013
Keywords
combinatorial auction, first-price, heuristic, equilibrium, strategy, expected revenue, multi-object auction, auction, multiple-item, simulatneous auction, bidding, synergy, synergies
National Category
Computer Sciences
Identifiers
urn:nbn:se:uu:diva-102933 (URN)
Available from: 2009-05-13 Created: 2009-05-13 Last updated: 2018-01-13Bibliographically approved
Wilenius, J. & Andersson, A. (2007). Discovering Equilibrium Strategies for a Combinatorial First Price Auction. In: 9th IEEE International Conference on E-Commerce Technology/4th IEEE International Conference on Enterprise Computing, E-Commerce and E-Services. Paper presented at 9th IEEE International Conference on E-Commerce Technology/4th IEEE International Conference on Enterprise Computing, E-Commerce and E-Services Tokyo, JAPAN, JUL 23-26, 2007 (pp. 13-20).
Open this publication in new window or tab >>Discovering Equilibrium Strategies for a Combinatorial First Price Auction
2007 (English)In: 9th IEEE International Conference on E-Commerce Technology/4th IEEE International Conference on Enterprise Computing, E-Commerce and E-Services, 2007, p. 13-20Conference paper, Published paper (Refereed)
Abstract [en]

In this paper the unresolved and fundamental strategy problem of the first price single round sealed bid combinatorial auction is addressed. As a step toward discovering equilibrium strategies, a new heuristic based on simple and intuitive methods is presented. The heuristic is evaluated using two different independently and uniformly distributed valuation models, one very general model where bidders bid on all combinations and one restricted model where bidders bid on one specific combination and single bids on the remaining items. Results yield natural explainable strategies with good characteristics based on comparisons of payoff, revenue and allocative efficiency.

National Category
Computer Sciences
Identifiers
urn:nbn:se:uu:diva-10758 (URN)10.1109/CEC-EEE.2007.41 (DOI)000250044300001 ()978-0-7695-2913-4 (ISBN)
Conference
9th IEEE International Conference on E-Commerce Technology/4th IEEE International Conference on Enterprise Computing, E-Commerce and E-Services Tokyo, JAPAN, JUL 23-26, 2007
Available from: 2008-01-25 Created: 2008-01-25 Last updated: 2018-01-12Bibliographically approved
Andersson, A., Holmström, J. & Willman, M. (2005). An Auction Mechanism for Polynomial-time Execution with Combinatorial Constraints. In: Proc. 7th International Conference on E-Commerce Technology (pp. 17-24). Piscataway, NJ: IEEE
Open this publication in new window or tab >>An Auction Mechanism for Polynomial-time Execution with Combinatorial Constraints
2005 (English)In: Proc. 7th International Conference on E-Commerce Technology, Piscataway, NJ: IEEE , 2005, p. 17-24Conference paper, Published paper (Refereed)
Place, publisher, year, edition, pages
Piscataway, NJ: IEEE, 2005
National Category
Computer Sciences
Identifiers
urn:nbn:se:uu:diva-78654 (URN)10.1109/ICECT.2005.103 (DOI)0-7695-2277-7 (ISBN)
Available from: 2007-04-18 Created: 2007-04-18 Last updated: 2018-01-13Bibliographically approved
Organisations

Search in DiVA

Show all publications