Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Auction Basics Read chapter Read first chapter

2015 | OriginalPaper | Chapter

7. Introduction to Combinatorial Auctions

Authors : Asunción Mochón, Yago Sáez

Published in: Understanding Auctions

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

In this chapter, we introduce the concept of combinatorial auction (CA), or package auction. In this model, the seller offers multiple items (usually heterogeneous but related) in a single auction, in which the bidders are allowed to bid for the items or combinations of items that they want. These auctions are particularly suitable when substitutes and complements items are auctioned, because the risk of aggregation or exposure is reduced.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Double Auctions
next chapter Combinatorial Auction Models
Footnotes
1
The chopstick auction is an example in which complements are auctioned and bidders have to face the exposure problem. The seller simultaneously offers three chopsticks, and the bidder with the highest bid wins two chopsticks. Therefore, the player with the second highest bid will be affected by the exposure problem because he will win one useless chopstick for which he must pay, see [29].
 
2
In this chapter, we assume that bidders can only win with one of the bids; that is, the bids are mutually exclusive, XOR bidding language. With this rule, the bidders are assured that they will not face the exposure problem.
 
3
In the final allocation the seller may not sell all items.
 
4
There are different ways of mathematically expressing this problem; in this manual, we use the formulation presented by Day and Raghavan [24].
 
5
The bidding languages that are most common in CAs are the OR bidding language and XOR bidding. With OR bidding, each bidder may win multiple bids. However, with XOR bidding, each bidder may win, at most, one bid. The problem with the OR bidding language is that when there are complements items, the bidders are affected by exposure problem, which does not occur when XOR bidding is used. In this book, all of the CAs will be explained using the XOR bidding language.
 
6
The bidders are not obliged to bid for all the items or combinations.
 
7
If the seller were to opt for an OR bidding language, then this allocation could be another solution to the WDP.
 
8
Several studies related to solving the WDP have been presented by Sandholm and Suri [71], Sandholm et al. [72], Saez et al. [68], among others.
 
9
With three items, there is a total of seven possible combinations. However, to simplify, in this example we have considered only four combinations and that all bidders do not bid for all of them.
 
10
See Vickrey [79], Clarke [17], and Groves [35].
 
11
An auction has bidder monotonicity if, upon including another bidder, the bidders’ surplus always decreases (weakly) and the seller’s revenue increases (weakly).
 
12
Multiple bidding identities by a single bidder.
 
13
These weaknesses do not surface in environments in which all of the items are substitutes for all of the bidders. However, when this condition is violated, even for a single bidder, these problems can occur. The fact that the bidders have budget restrictions may also affect the auction result when applying the VCG mechanism.
 
14
In this example, the winning combination could be either b 2 ∗(A), b 3 ∗(B) or b 3 ∗(A), b 2 ∗(B), but the result would be the same.
 
15
Given the complexity of the core-selecting package auction, the calculation of the final payments made by the winning bidders is beyond the scope of this book.
 
Literature
5.
L.M. Ausubel and O. Baranov. Core-selecting auctions with incomplete information. Working Paper, University of Maryland, 2010.
7.
L.M. Ausubel, P. Cramton, P. McAfee, and J. McMillan. Synergies in wireless telephony: Evidence from the broadband pcs auctions. Journal of Economics and Management Strategy, 6(3):497–527, 1997.CrossRef
10.
L.M. Ausubel and P. Milgrom. The lovely but lonely vickrey auction. In P. Cramton, Y. Shoham, and R. Steinberg, editors, Combinatorial Auctions, pages 17–40. The MIT Press, 2006.
15.
E. Cantillon and M. Pesendorfer. Auctioning bus routes: The london experience. In P. Cramton, Y. Shoham, and R. Steinberg, editors, Combinatorial Auctions, pages 573–592. The MIT Press, 2005.
17.
E.H. Clarke. Multipart pricing of public goods. Public Choice, 11(1):7–33, 1971.CrossRef
22.
R. Day and P. Cramton. The quadratic core-selecting payment rule for combinatorial auctions. Working Paper, University of Maryland, 2008.
23.
R. Day and P. Milgrom. Core-selecting package auctions. International Journal of Game Theory, 36(3–4):393–407, 2008.CrossRef
24.
R.W. Day and S. Raghavan. Fair payments for efficient allocations in public sector combinatorial auctions. Management Science, 53(9):1389–1406, 2007.CrossRef
29.
F. Englmaier, P. Guillen, L. Llorente, S. Onderstal, and R. Sausgruber. The chopstick auction: a study of the exposure problem in multi-unit auctions. International Journal of Industrial Organization, 27(2):286–291, 2009.CrossRef
30.
A. Erdil and P. Klemperer. A new payment rule for core-selecting package auctions. Journal of the European Economic Association, 8(2–3):537–547, 2010.CrossRef
33.
N. Gandal. Sequential auctions of interdependent objects: Israeli cable television licenses. The Journal of Industrial Economics, 45(3):227–244, 1997.CrossRef
35.
68.
Y. Saez, A. Mochon, J.L. Gomez-Barroso, and P. Isasi. Testing boi and bob algorithms for solving the winner determination problem in radio spectrum auctions. HIS 08 Proceedings of the 2008 8th International Conference on Hybrid Intelligent Systems, pages 732–737, 2008.
70.
T. Sandholm. Algorithm for optimal winner determination in combinatorial auctions. Artificial Intelligence, 135:1–54, 2002.CrossRef
71.
T. Sandholm and S. Suri. Bob: Improved winner determination in combinatorial auctions and generalizations. Artificial Intelligence, 145:33–58, 2003.CrossRef
72.
T. Sandholm, S. Suri, A. Gilpin, and D. Levine. Cabob: A fast optimal algorithm for winner determination in combinatorial auctions. Management Science, 51(3):374–390, 2005.CrossRef
76.
D.G. Silva. Synergies in recurring procurement auctions: An empirical investigation. Economic Inquiry, 43(1):55–66, 2005.CrossRef
79.
W. Vickrey. Counterspeculation, auctions, and competitive sealed tenders. The Journal of Finance, 16:8–37, 1961.CrossRef
Metadata
Title
Introduction to Combinatorial Auctions
Authors
Asunción Mochón
Yago Sáez
Copyright Year
2015
Book
Understanding Auctions

Print ISBN: 978-3-319-08812-9

Electronic ISBN: 978-3-319-08813-6

Copyright Year: 2015

DOI
https://doi.org/10.1007/978-3-319-08813-6_7