Optimization Issues in Combinatorial Auctions

Stan van Hoesel () and Rudolf Müller ()
Additional contact information
Stan van Hoesel: Maastricht University, Department of Quantitative Economics
Rudolf Müller: Maastricht University, Department of Quantitative Economics

Chapter 36 in Handbook of Optimization in Telecommunications, 2006, pp 1051-1071 from Springer

Abstract: Abstract Auctions are used more and more to sell a large variety of goods. In this chapter, it is our objective to concentrate on applications of auctions in telecommunication, which possess a part or a feature that can be optimized. Optimization methods are necessary, in particular, when auctions are used to sell or purchase goods which consist of combinations of items, and where combinations have higher or lower value than the sum of values of individual items: combinatorial auctions. In the first part, we review the theory on combinatorial auctions, starting with the various properties and mechanisms found in the literature on combinatorial auctions. Then the allocation decision is identified as the winner determination problem (WDP), which is the central subject of this chapter. The winner determination problem is formulated as an Integer Linear Program (ILP) with the structure of a set-packing problem. Therefore, complexity results, polynomial special cases, and general solution methods for the WDP are often obtained from results for the set-packing problem. In the second part of this chapter, we turn to applications from telecommunications. First, a model for bandwidth allocation in networks is discussed. The problem is translated into a formulation that has close relations to multi-commodity flow and network synthesis. This guides us to alternative formulations and to solution methods. Second, the auctions of radio spectrum in the US and Europe are reviewed. The WDP of these multi-round auctions can be modeled using the XOR-of-OR bidding language, and solved by methods originally developed for set-packing.

Keywords: Auctions; combinatorial auctions; telecommunications; optimization; bandwidth allocation (search for similar items in EconPapers)
Date: 2006
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-0-387-30165-5_36

Ordering information: This item can be ordered from
http://www.springer.com/9780387301655

DOI: 10.1007/978-0-387-30165-5_36

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().