uu.seUppsala universitets publikationer
Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
A New Analysis of Revenue in the Combinatorial and Simultaneous Auction
Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datalogi.
Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datalogi.
2009 (Engelska)Rapport (Övrigt vetenskapligt)
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.

Ort, förlag, år, upplaga, sidor
2009.
Serie
Technical report / Department of Information Technology, Uppsala University, ISSN 1404-3203 ; 2009-001
Nyckelord [en]
combinatorial auction, first-price, equilibrium, strategy, expected revenue, multi-object auction, auction, multiple-item, simulatneous auction, bidding, synergy, synergies, game theory
Nationell ämneskategori
Datavetenskap (datalogi)
Identifikatorer
URN: urn:nbn:se:uu:diva-102935OAI: oai:DiVA.org:uu-102935DiVA, id: diva2:217102
Tillgänglig från: 2009-05-13 Skapad: 2009-05-13 Senast uppdaterad: 2018-01-13Bibliografiskt granskad
Ingår i avhandling
1. Bidding in Combinatorial Auctions
Öppna denna publikation i ny flik eller fönster >>Bidding in Combinatorial Auctions
2009 (Engelska)Doktorsavhandling, sammanläggning (Övrigt vetenskapligt)
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.

Ort, förlag, år, upplaga, sidor
Uppsala: Acta Universitatis Upsaliensis, 2009. s. 143
Serie
Digital Comprehensive Summaries of Uppsala Dissertations from the Faculty of Science and Technology, ISSN 1651-6214 ; 656
Nyckelord
combinatorial auction, multiple-object, first-price, sealed-bid, game theory, multiple items, simultaneous auction, integer programming, equilibrium, strategy, reveue
Nationell ämneskategori
Data- och informationsvetenskap
Forskningsämne
Datavetenskap
Identifikatorer
urn:nbn:se:uu:diva-102960 (URN)978-91-554-7554-3 (ISBN)
Disputation
2009-09-18, Room 2446, Polacksbacken, Lägerhyddsvägen 2D, Uppsala, 13:15 (Engelska)
Opponent
Handledare
Tillgänglig från: 2009-06-11 Skapad: 2009-05-13 Senast uppdaterad: 2018-01-13Bibliografiskt granskad

Open Access i DiVA

Fulltext saknas i DiVA

Övriga länkar

http://www.it.uu.se/research/publications/reports/2009-001/

Personposter BETA

Andersson, ArneWilenius, Jim

Sök vidare i DiVA

Av författaren/redaktören
Andersson, ArneWilenius, Jim
Av organisationen
Datalogi
Datavetenskap (datalogi)

Sök vidare utanför DiVA

GoogleGoogle Scholar

urn-nbn

Altmetricpoäng

urn-nbn
Totalt: 1028 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf