uu.seUppsala universitets publikasjoner
Endre søk
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
An Auction Mechanism for Polynomial-time Execution with Combinatorial Constraints
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.
Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datalogi.
2005 (engelsk)Inngår i: Proc. 7th International Conference on E-Commerce Technology, Piscataway, NJ: IEEE , 2005, s. 17-24Konferansepaper, Publicerat paper (Fagfellevurdert)
sted, utgiver, år, opplag, sider
Piscataway, NJ: IEEE , 2005. s. 17-24
HSV kategori
Identifikatorer
URN: urn:nbn:se:uu:diva-78654DOI: 10.1109/ICECT.2005.103ISBN: 0-7695-2277-7 (tryckt)OAI: oai:DiVA.org:uu-78654DiVA, id: diva2:106567
Tilgjengelig fra: 2007-04-18 Laget: 2007-04-18 Sist oppdatert: 2018-01-13bibliografisk kontrollert
Inngår i avhandling
1. Bidding in Combinatorial Auctions
Åpne denne publikasjonen i ny fane eller vindu >>Bidding in Combinatorial Auctions
2009 (engelsk)Doktoravhandling, med artikler (Annet vitenskapelig)
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.

sted, utgiver, år, opplag, sider
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
Emneord
combinatorial auction, multiple-object, first-price, sealed-bid, game theory, multiple items, simultaneous auction, integer programming, equilibrium, strategy, reveue
HSV kategori
Forskningsprogram
Datavetenskap
Identifikatorer
urn:nbn:se:uu:diva-102960 (URN)978-91-554-7554-3 (ISBN)
Disputas
2009-09-18, Room 2446, Polacksbacken, Lägerhyddsvägen 2D, Uppsala, 13:15 (engelsk)
Opponent
Veileder
Tilgjengelig fra: 2009-06-11 Laget: 2009-05-13 Sist oppdatert: 2018-01-13bibliografisk kontrollert

Open Access i DiVA

Fulltekst mangler i DiVA

Andre lenker

Forlagets fulltekst

Personposter BETA

Andersson, ArneHolmström, JimWillman, Mattias

Søk i DiVA

Av forfatter/redaktør
Andersson, ArneHolmström, JimWillman, Mattias
Av organisasjonen

Søk utenfor DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric

doi
isbn
urn-nbn
Totalt: 1225 treff
RefereraExporteraLink to record
Permanent link

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