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

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Bidding in Combinatorial Auctions
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Division of Computing Science. Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
2009 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

This thesis concerns the interdisciplinary field of combinatorial auctions, combining the fields of computer science, optimization and economics. A combinatorial auction is an auction where many items are sold simultaneously and where bidders may submit indivisible combinatorial bids on groups of items. It is commonly believed that good solutions to the allocation problem can be achieved by allowing combinatorial bidding.

Determining who wins in a combinatorial auction is fundamentally different from a traditional single-item auction because we are faced with a hard and potentially intractable optimization problem. Also, unless we are limited to truthful mechanisms, game theoretic analysis of the strategic behavior of bidders is still an open problem.

We have chosen primarily to study the first-price combinatorial auction, a natural auction widely used in practice. Theoretical analysis of this type of auction is difficult and little has been done previously. In this thesis we investigate and discuss three fundamental questions with significant practical implications for combinatorial auctions.

First, because the number of possible bids grows exponentially with the number of items, limitations on the number of bids are typically required. This gives rise to a problem since bidders are unlikely to choose the "correct" bids that make up the globally optimal solution. We provide evidence that an expressive and compact bidding language can be more important than finding the optimal solution. Second, given a first-price (sealed-bid) combinatorial auction, the question of equilibrium bidding strategies remains an open problem. We propose a heuristic for finding such strategies and also present feasible strategies. And finally, is a first-price combinatorial auction worth pursuing compared to the simpler simultaneous (single-item) auction? We prove, through a model capturing many fundamental properties of multiple items scenarios with synergies, that the first-price combinatorial auction produces higher revenue than simultaneous single-item auctions. We provide bounds on revenue, given a significantly more general model, in contrast to previous work.

Place, publisher, year, edition, pages
Uppsala: Acta Universitatis Upsaliensis , 2009. , p. 143
Series
Digital Comprehensive Summaries of Uppsala Dissertations from the Faculty of Science and Technology, ISSN 1651-6214 ; 656
Keywords [en]
combinatorial auction, multiple-object, first-price, sealed-bid, game theory, multiple items, simultaneous auction, integer programming, equilibrium, strategy, reveue
National Category
Computer and Information Sciences
Research subject
Computer Science
Identifiers
URN: urn:nbn:se:uu:diva-102960ISBN: 978-91-554-7554-3 (print)OAI: oai:DiVA.org:uu-102960DiVA, id: diva2:218682
Public defence
2009-09-18, Room 2446, Polacksbacken, Lägerhyddsvägen 2D, Uppsala, 13:15 (English)
Opponent
Supervisors
Available from: 2009-06-11 Created: 2009-05-13 Last updated: 2018-01-13Bibliographically approved
List of papers
1. An Auction Mechanism for Polynomial-time Execution with Combinatorial Constraints
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
2. Discovering Equilibrium Strategies for a Combinatorial First Price Auction
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
3. 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
4. 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

Open Access in DiVA

fulltext(1142 kB)992 downloads
File information
File name FULLTEXT01.pdfFile size 1142 kBChecksum SHA-512
6ce4da8ffca594aa6ba9f292cef926808e072c5dd79c44e760fd6c583865ae1960e8b3d2fe8d56fcd21c7c878c865622a954aec3aedb7ef005cddfe61f8321ac
Type fulltextMimetype application/pdf
Buy this publication >>

Authority records BETA

Wilenius, Jim

Search in DiVA

By author/editor
Wilenius, Jim
By organisation
Division of Computing ScienceComputing Science
Computer and Information Sciences

Search outside of DiVA

GoogleGoogle Scholar
Total: 992 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 1783 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf