Arctic Auctions, Linear Fisher Markets, and Rational Convex Programs

2025/11/26 by Vazirani, Vijay V. · 1 citation
#Computer Science and Game Theory (cs.GT) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Economics and business #Theoretical Economics (econ.TH)

paper · doi:10.48550/arxiv.2511.21637

Abstract

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.

Citations

• Convex Program Duality, Fisher Markets, and Nash Social Welfare
• An Improved Combinatorial Polynomial Algorithm for the Linear Arrow-Debreu Market
• A Rational Convex Program for Linear Arrow-Debreu Markets
• A Combinatorial Polynomial Algorithm for the Linear Arrow-Debreu Market
• Competitive and Revenue-Optimal Pricing with Budgets
• Computing Candidate Prices in Budget-Constrained Product-Mix Auctions
• One-Sided Matching Markets with Endowments: Equilibria and Algorithms
• Solving Strong-Substitutes Product-Mix Auctions

Cited by

• Efficiently Restructuring Sovereign Debt via Arctic Auctions with Convex Costs

Related

• Efficiently Restructuring Sovereign Debt via Arctic Auctions with Convex Costs
• An Alternating Algorithm for Finding Linear Arrow-Debreu Market Equilibria
• Rational Convex Programs, Their Feasibility, and the Arrow-Debreu Nash Bargaining Game
• Computing Equilibria in Markets with Budget-Additive Utilities
• Fisher Markets with Linear Constraints: Equilibrium Properties and Efficient Distributed Algorithms