A Strongly Polynomial Algorithm for Arctic Auctions

ArXiv.org · 2026-04-27

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.

Towards a Practical, Budget-Oblivious Algorithm for the Adwords Problem Under Small Bids

Algorithmica · 2026-02-19

Abstract Motivated by recent insights into the online bipartite matching problem ( OBM ), our goal was to extend the optimal algorithm for it, namely Ranking , all the way to the special case of adwords problem, called Small , in which bids are small compared to budgets; the latter has been of considerable practical significance in ad auctions (Mehta et al. in J. ACM (JACM) 54:22-es, 2007). This approach would yield a budget-oblivious algorithm , i.e., the algorithm would not need to know budgets of advertisers and therefore could be used in autobidding platforms. We present such an algorithm for Single-Valued , a special case of Small . However, an extension to Small failed because of failure of the No-Surpassing Property . Since the probabilistic ideas underlying our algorithm are quite substantial, we have stated them formally, after assuming the No-Surpassing Property, and we leave the open problem of removing this assumption.

Robust Stable Matchings: Dealing with Changes in Preferences

arXiv (Cornell University) · 2026-01-12

We study stable matchings that are robust to preference changes in the two-sided stable matching setting of Gale and Shapley [GS62]. Given two instances $A$ and $B$ on the same set of agents, a matching is said to be robust if it is stable under both instances. This notion captures desirable robustness properties in matching markets where preferences may evolve, be misreported, or be subject to uncertainty. While the classical theory of stable matchings reveals rich lattice, algorithmic, and polyhedral structure for a single instance, it is unclear which of these properties persist when stability is required across multiple instances. Our work initiates a systematic study of the structural and computational behavior of robust stable matchings under increasingly general models of preference changes. We analyze robustness under a hierarchy of perturbation models: 1. a single upward shift in one agent's preference list, 2. an arbitrary permutation change by a single agent, and 3. arbitrary preference changes by multiple agents on both sides. For each regime, we characterize when: 1. the set of robust stable matchings forms a sublattice, 2. the lattice of robust stable matchings admits a succinct Birkhoff partial order enabling efficient enumeration, 3. worker-optimal and firm-optimal robust stable matchings can be computed efficiently, and 4. the robust stable matching polytope is integral (by studying its LP formulation). We provide explicit counterexamples demonstrating where these structural and geometric properties break down, and complement these results with XP-time algorithms running in $O(n^k)$ time, parameterized by $k$, the number of agents whose preferences change. Our results precisely delineate the boundary between tractable and intractable cases for robust stable matchings.

Robust Stable Matchings: Dealing with Changes in Preferences

ArXiv.org · 2026-01-12

We study stable matchings that are robust to preference changes in the two-sided stable matching setting of Gale and Shapley [GS62]. Given two instances $A$ and $B$ on the same set of agents, a matching is said to be robust if it is stable under both instances. This notion captures desirable robustness properties in matching markets where preferences may evolve, be misreported, or be subject to uncertainty. While the classical theory of stable matchings reveals rich lattice, algorithmic, and polyhedral structure for a single instance, it is unclear which of these properties persist when stability is required across multiple instances. Our work initiates a systematic study of the structural and computational behavior of robust stable matchings under increasingly general models of preference changes. We analyze robustness under a hierarchy of perturbation models: 1. a single upward shift in one agent's preference list, 2. an arbitrary permutation change by a single agent, and 3. arbitrary preference changes by multiple agents on both sides. For each regime, we characterize when: 1. the set of robust stable matchings forms a sublattice, 2. the lattice of robust stable matchings admits a succinct Birkhoff partial order enabling efficient enumeration, 3. worker-optimal and firm-optimal robust stable matchings can be computed efficiently, and 4. the robust stable matching polytope is integral (by studying its LP formulation). We provide explicit counterexamples demonstrating where these structural and geometric properties break down, and complement these results with XP-time algorithms running in $O(n^k)$ time, parameterized by $k$, the number of agents whose preferences change. Our results precisely delineate the boundary between tractable and intractable cases for robust stable matchings.

Equitable Core Imputations for Max-Flow, MST and b-Matching Games

2026-05-24

We study fair allocation of profit (or cost) for three central problems from combinatorial optimization: Max-Flow, MST and b-matching. The essentially unequivocal choice of solution concept for this purpose would be the core, because of its highly desirable properties. However, recent work observed that for the assignment game, an arbitrary core imputation makes no fairness guarantee at the level of individual agents. To rectify this deficiency, special core imputations, called equitable core imputations, were defined - there are two such imputations, leximin and leximax - and efficient algorithms were given for finding them.

Time-Efficient Algorithms for Nash-Bargaining-Based Matching Market Models

Lecture notes in computer science · 2026-01-01 · 1 citations

A Strongly Polynomial Algorithm for Arctic Auctions

arXiv (Cornell University) · 2026-04-27

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.

Computational Complexity of the Hylland–Zeckhauser Mechanism for One-Sided Matching Markets

SIAM Journal on Computing · 2025-03-03 · 2 citations

Arctic Auctions, Linear Fisher Markets, and Rational Convex Programs

ArXiv.org · 2025-11-26

This paper unifies two foundational constructs from economics and algorithmic game theory, the Arctic Auction and the linear Fisher market, to address the efficient allocation of differentiated goods in complex markets. Our main contributions are showing that an equilibrium for the Arctic Auction is captured by a Rational Convex Program, and deriving the first combinatorial polynomial-time algorithm for computing Arctic Auction equilibria.

Matching Markets with Chores

2025-05-28

The fair division of chores, as well as mixed manna (goods and chores), has received substantial recent attention in the fair division literature; however, ours is the first paper to extend this research to matching markets. Indeed, our contention is that matching markets are a natural setting for this purpose, since the manna that fit into the limited number of hours available in a day can be viewed as one unit of allocation. We extend several well-known results that hold for goods to the settings of chores and mixed manna. In addition, we show that the natural notion of an earnings-based equilibrium, which is more natural in the case of all chores, is equivalent to the pricing-based equilibrium given by Hylland and Zeckhauser for the case of goods.