  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.

Statistical Mechanics;Statistical Finance