title: Statistical mechanics of combinatorial auctions.
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.
authors.affiliation: The Abdus Salam International Centre for Theoretical Physics, Strada Costiera 11, 34014 Trieste, Italy.
authors.forename: Tobias
authors.initials: T
authors.lastname: Galla
authors.forename: Michele
authors.initials: M
authors.lastname: Leone
authors.forename: Matteo
authors.initials: M
authors.lastname: Marsili
authors.forename: Mauro
authors.initials: M
authors.lastname: Sellitto
authors.forename: Martin
authors.initials: M
authors.lastname: Weigt
authors.forename: Riccardo
authors.initials: R
authors.lastname: Zecchina
mesh_terms: D000465:Algorithms; D001703:Biophysics / Q000379:methods*; D003198:Computer Simulation; D015233:Models, Statistical; D008962:Models, Theoretical; D012984:Software; D013269:Stochastic Processes