uu.seUppsala University Publications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Caching in Multi-unit combinatorial auctions
Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Mathematics.
Department of Information Technology. Datalogi.
2002 (English)In: International Joint Conference on Autonomous Agents & Multiagent systems, 2002Conference paper, Published paper (Refereed)
Abstract [en]

Combinatorial Auctions are preferable to traditional (sequential) auctions since they allow bidders to express complementarity and substitutability relationships between items, and hence may enhance economic efficiency. However, in such auctions, the problem of determining the optimal winning bids is \textitNP-hard in the general case. In a recent paper, Leyton-Brown et al. have proposed an algorithm for computing the winners in a multi-unit combinatorial auction. It is a branch and bound algorithm that makes use of a caching technique. In this note, we present a counterexample to show that caching, as described by the authors, may fail and the algorithm may eventually give a suboptimal solution. We discuss why it fails and propose how it could be fixed and properly used in a General (multi-unit) combinatorial auction.

Place, publisher, year, edition, pages
2002.
Identifiers
URN: urn:nbn:se:uu:diva-10663OAI: oai:DiVA.org:uu-10663DiVA: diva2:38431
Available from: 2007-04-18 Created: 2007-04-18

Open Access in DiVA

No full text

Other links

http://portal.acm.org/citation.cfm?coll=GUIDE&dl=GUIDE&id=544779
By organisation
Department of MathematicsDepartment of Information Technology

Search outside of DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric score

urn-nbn
Total: 488 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf