A Strongly Polynomial Algorithm for Arctic Auctions
2026-04-27 • Computer Science and Game Theory
Computer Science and Game TheoryData Structures and Algorithms
AI summaryⓘ
The authors developed a strongly polynomial algorithm that efficiently finds equilibrium prices and allocations in the Arctic Auction, which is a more complex version of the linear Fisher market model. Their work builds on previous algorithms for the Fisher market, especially Orlin's scaling method. The Arctic Auction was created for real-world applications like the Icelandic government's asset exchange and the Bank of England's liquidity allocation. The authors were motivated by the need for faster algorithms to handle many auction parameter settings in practice.
strongly polynomial algorithmequilibriumArctic Auctionlinear Fisher marketquasi-linear extensionprimal-dual paradigmscaling algorithmproduct-mix auctionliquidity allocationcombinatorial algorithm
Authors
Jugal Garg, Shayan Taherijam, Vijay V Vazirani
Abstract
Our main contribution is a strongly polynomial algorithm for computing an equilibrium for the Arctic Auction, which is the quasi-linear extension of the linear Fisher market model. We build directly on Orlin's strongly polynomial algorithm for the linear Fisher market (Orlin, 2010). The first combinatorial polynomial algorithm for the linear Fisher market was based on the primal-dual paradigm (Devanur et al., 2008). This was followed by Orlin's scaling-based algorithms. The Arctic Auction (Klemperer 2018) was developed for the Government of Iceland to allow individuals to exchange blocked offshore assets. It is a variant of the product-mix auction (Klemperer 2008, 2010, 2018) that was designed for, and used by, the Bank of England, to allocate liquidity efficiently across banks pledging heterogeneous collateral of varying quality. Our work was motivated by the fact that banks often need to run Arctic Auctions under many different settings of the parameters in order to home in on the right one, making it essential to find a time-efficient algorithm for Arctic Auction.