On the Computational Power of Iterative Auctions I: Demand Queries

Liad Blumrosen () and Noam Nisan

Discussion Paper Series from The Federmann Center for the Study of Rationality, the Hebrew University, Jerusalem

Abstract: 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.

JEL-codes: C7 D83 (search for similar items in EconPapers)
Pages: 20 pages
Date: 2005-02
New Economics Papers: this item is included in nep-cmp
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (7)

Downloads: (external link)
http://ratio.huji.ac.il/sites/default/files/publications/dp381.pdf (application/pdf)
Our link check indicates that this URL is bad, the error code is: 404 Not Found (http://ratio.huji.ac.il/sites/default/files/publications/dp381.pdf [302 Moved Temporarily]--> https://ratio.huji.ac.il/sites/default/files/publications/dp381.pdf)

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:huj:dispap:dp381

Access Statistics for this paper

More papers in Discussion Paper Series from The Federmann Center for the Study of Rationality, the Hebrew University, Jerusalem Contact information at EDIRC.
Bibliographic data for series maintained by Michael Simkin ().