Bereiche | Tage | Auswahl | Suche | Downloads | Hilfe
AKSOE: Arbeitskreis Physik sozio-ökonomischer Systeme
AKSOE 7: Economic Models and Evolutionary Game Theory I
AKSOE 7.1: Vortrag
Dienstag, 27. März 2007, 10:15–10:45, H8
Combinatorial auctions as frustrated lattice gases — •Tobias Galla1,2, Michele Leone3, Matteo Marsili1, Mauro Sellitto1, Martin Weigt3, and Riccardo Zecchina1 — 1International Centre for Theoretical Physics, Strada Costiera 11, I-34014 Trieste, Italy — 2SISSA-CNR-INFM, Via Beirut 2-4, I-34014 Trieste, Italy — 3ISI Foundation, Viale S. Severo 65, I-10133 Torino, Italy
Combinatorial auctions are auctions in which bidders bid on combinations of items, as opposed to single items in conventional formats. The winner-determination problem of such multi-item auctions turns out to be non-trivial and computationally complex due to overlapping bids and overall frustration. In particular, the highest bid is not guaranteed to win.
We show how combinatorial auctions can be 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.