We study the computational power and limitations of iterative combinatorial auctions. Most existing iterative combinatorial auctions are based on repeatedly suggesting prices for bundles of items, and querying the bidders for their ``demand'' under these prices. We prove several results regarding such auctions that use a polynomial number of demand queries: (1) that such auctions can simulate several other natural types of queries; (2) that such auctions can solve linear programming relaxations of winner determination problems; (3) that they can approximate the optimal allocation as well as generally possible using polynomial communication or computation, while weaker types of queries can not do so. We also initiate the study of how can the prices of bundles be represented when they are not linear, and show that the ``default'' representation has severe limitations.
Download Info
To download:
If you experience problems downloading a file, check if you have the
proper application to
view it first. Information about this may be contained
in the File-Format links below. In case of further problems read
the IDEAS help
file. Note that these files are not on the IDEAS
site. Please be patient as the files may be large.
Publisher Info
Paper provided by Center for Rationality and Interactive Decision Theory, Hebrew University, Jerusalem in its series Discussion Paper Series with number
dp381.
For technical questions regarding this item, or to correct its listing, contact: (Ziv Gorodeisky).
Related research
Keywords:
Other versions of this item:
Find related papers by JEL classification: C7 - Mathematical and Quantitative Methods - - Game Theory and Bargaining Theory D83 - Microeconomics - - Information, Knowledge, and Uncertainty - - - Search, Learning, and Information
This paper has been announced in the following NEP Reports:
References listed on IDEAS Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:
Peter Cramton & Yoav Shoham & Richard Steinberg, 2004.
"Combinatorial Auctions,"
Papers of Peter Cramton
04mit, University of Maryland, Department of Economics - Peter Cramton, revised 2004.
[Downloadable!]
Demange, Gabrielle & Gale, David & Sotomayor, Marilda, 1986.
"Multi-Item Auctions,"
Journal of Political Economy,
University of Chicago Press, vol. 94(4), pages 863-72, August.
[Downloadable!] (restricted)
Cited by: (explanations, Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.)