Combinatorial auctions: From a statistical-mechanics analysis to efficient message-passing algorithms

In this note, we present a statistical-physics framework for combinatorial auctions, i.e. multi-item auctions where bidders bid on combinations of items. The combinatorial problem is represented as a lattice-gas model, such that methods from the statistical physics of complex, disordered systems can be applied. In a minimal probabilistic setting, we find a phase transition from an easily solvable to a harder phase, where the solution space becomes clustered. In addition, the reformulation as a statistical-physics model allows the introduction of new and efficient message passing algorithms for single CA instances.