Four ICTP scientistsâ€”Tobias Galla, Matteo Marsili, Mauro Sellitto and Riccardo Zecchinaâ€”have recently uncovered ways to use statistical mechanics to optimize the outcome of combinatorial auctions. Such auctions have been used to determine landing and takeoff priorities at airports and to distribute licenses for radio spectrums. Their findings have been published in the 22 September edition of Physical Review Letters.
When there is one item on the auction block, auctioneers have no trouble determining the winning bid: it simply goes to the highest bidder.
However, in so-called combinatorial auctions, in which multiple buyers bid ‘in combination’ on multiple objects, the winning bid, or should we say bids, is not so easy to determine. Moreover, when there is a large number of bidders and objects, which holds true, for example, in the case of airport takeoff and landing slot allocations, determining the optimal allocation can consume unrealistic amounts of time even when the information is being processed by the world’s fastest computers.
ICTP scientists turned to the statistical mechanics of disordered systems and, in particular, to the behaviour of granular particles to provide a mathematical approach to such a problem. Their approach relies on an algorithm previously devised as an analytical tool for spin-glass physics. They hope that their finding may vastly improve upon existing time-exhausting approaches and therefore more quickly solve the bedeviling winner-determination problem that to date has restricted the use of combinatorial auctions.