Sökning: WFRF:(Miltersen Peter Bro) >
Bidding in Combinat...
Bidding in Combinatorial Auctions
-
- Wilenius, Jim, 1976- (författare)
- Uppsala universitet,Avdelningen för datalogi,Datalogi
-
- Andersson, Arne, Professor (preses)
- Uppsala universitet,Avdelningen för datalogi
-
- Miltersen, Peter Bro, Professor (opponent)
- Aarhus University, Department of Computer Science
-
(creator_code:org_t)
- ISBN 9789155475543
- Uppsala : Acta Universitatis Upsaliensis, 2009
- Engelska 143 s.
-
Serie: Digital Comprehensive Summaries of Uppsala Dissertations from the Faculty of Science and Technology, 1651-6214 ; 656
- Relaterad länk:
-
https://uu.diva-port... (primary) (Raw object)
-
visa fler...
-
https://urn.kb.se/re...
-
visa färre...
Abstract
Ämnesord
Stäng
- 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.
Ämnesord
- NATURVETENSKAP -- Data- och informationsvetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences (hsv//eng)
Nyckelord
- combinatorial auction
- multiple-object
- first-price
- sealed-bid
- game theory
- multiple items
- simultaneous auction
- integer programming
- equilibrium
- strategy
- reveue
- Information technology
- Informationsteknik
- Datavetenskap
- Computer Science
Publikations- och innehållstyp
- vet (ämneskategori)
- dok (ämneskategori)
Hitta via bibliotek
Till lärosätets databas