Galla Tobias, Leone Michele, Marsili Matteo, Sellitto Mauro, Weigt Martin, Zecchina Riccardo
The Abdus Salam International Centre for Theoretical Physics, Strada Costiera 11, 34014 Trieste, Italy.
Phys Rev Lett. 2006 Sep 22;97(12):128701. doi: 10.1103/PhysRevLett.97.128701. Epub 2006 Sep 20.
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.
组合拍卖被表述为稀疏随机图上的受挫晶格气体，从而能够通过统计物理方法确定最优收益。我们发现了计算上容易和困难模式之间的转变，并根据解空间的几何结构对其进行了解释。我们引入了一种迭代算法来解决中等规模和大规模的实例，并讨论了最优收益和最大数量的满意竞拍者的竞争状态。该算法可以推广到困难阶段以及更复杂的拍卖协议。
