A Strongly Polynomial Algorithm for Arctic Auctions

Researchers Jugal Garg, Shayan Taherijam, and Vijay V. Vazirani have published a new algorithm that solves Arctic Auctions in strongly polynomial time. Arctic Auctions are a quasi-linear extension of the linear Fisher market model, originally developed by Paul Klemperer for the Government of Iceland to exchange blocked offshore assets. They are a variant of the product-mix auction used by the Bank of England to allocate liquidity efficiently across banks pledging heterogeneous collateral.

The algorithm builds directly on Orlin's strongly polynomial algorithm for the linear Fisher market from 2010, which itself followed the first combinatorial polynomial algorithm by Devanur et al. in 2008. The key motivation is that banks need to run Arctic Auctions under many parameter settings to find the optimal one, making time efficiency critical. This advance allows them to compute equilibria much faster, enabling more thorough scenario analysis without computational bottlenecks.