Statistical mechanics of combinatorial auctions

Tobias Galla, Michele Leone, Matteo Marsili, Mauro Sellitto, Martin Weigt and Riccardo Zecchina

Papers from arXiv.org

Abstract: Combinatorial auctions are formulated as frustrated lattice gases on sparse random graphs, allowing the determination of the optimal revenue by methods of statistical physics. Transitions between computationally easy and hard regimes are found and interpreted in terms of the geometric structure of the space of solutions. We introduce an iterative algorithm to solve intermediate and large instances, and discuss competing states of optimal revenue and maximal number of satisfied bidders. The algorithm can be generalized to the hard phase and to more sophisticated auction protocols.

Date: 2006-05, Revised 2006-08
References: Add references at CitEc
Citations:

Published in Phys. Rev. Lett. 97, 128701 (2006)

Downloads: (external link)
http://arxiv.org/pdf/cond-mat/0605623 Latest version (application/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:arx:papers:cond-mat/0605623

Access Statistics for this paper

More papers in Papers from arXiv.org
Bibliographic data for series maintained by arXiv administrators ().