A Strongly Polynomial Algorithm for Arctic Auctions
For banks and policymakers using Arctic Auctions to allocate liquidity, this algorithm provides a time-efficient method to compute equilibria, enabling faster parameter exploration.
The paper presents the first strongly polynomial algorithm for computing an equilibrium in the Arctic Auction, a quasi-linear extension of the linear Fisher market. This algorithm builds on Orlin's strongly polynomial algorithm for the linear Fisher market, addressing the need for time-efficient computation when banks run Arctic Auctions under many parameter settings.
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.