Back to Search
Start Over
Combinatorial auctions: From a statistical-mechanics analysis to efficient message-passing algorithms
- Publication Year :
- 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.
- Subjects :
- Computer Science::Computer Science and Game Theory
Subjects
Details
- Language :
- English
- Database :
- OpenAIRE
- Accession number :
- edsair.od......3977..e26482cc7b5c4ebda3e5ccd50f5675c1