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.
Combinatorial auctions: From a statistical-mechanics analysis to efficient message-passing algorithms
SELLITTO, Mauro;
2005
Abstract
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.File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
