Bidding in Combinatorial Auctions

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…


1 Introduction
2 Combinatorial Auctions
2.1 Basic Terminology
2.2 Valuations and Bids
2.3 Winner Determination
2.4 Bidding Language
2.5 Single-minded Bidders
2.6 Real World Application
2.7 Types of Combinatorial Auctions
3 Game Theory
3.1 Introduction
3.2 Bayesian Games
3.3 Equilibrium
3.4 Mechanisms
4 The Auction Game
4.1 Single-Item Auctions
4.1.1 Example – Second-Price Auction
4.1.2 Example–First-Price Auction
4.2 Combinatorial Auction Game
4.2.1 Analyzing the First-Price Combinatorial Auction
4.3 Finite Game–Discrete Strategies
5 Summaries of Included Papers
5.1 Paper-I: An Auction Mechanism for Polynomial- time Execution with Combinatorial Constraints
5.2 Paper-II: Discovering Equilibrium Strategies for a Combinatorial First Price Auction
5.3 Paper-III: A New Analysis of Revenue in the Combinatorial and Simultaneous Auction
5.4 Paper-IV: Combinatorial and Simultaneous Auction: A Pragmatic Approach to Tighter Bounds on Expected Revenue
4 Revisiting the Simultaneous Auction
5 Combining the Results
6 Conclusions
7 Acknowledgment

Author: Wilenius, Jim

Source: Uppsala University Library

Download URL 2: Visit Now

Leave a Comment