Strongly polynomial algorithm solves auctions with budget limits and costs

Solving the Arctic Product-Mix Auction

Computer Science and Game Theory

Summary

Auctions often need to manage bidders who have budgets and want multiple similar goods. This paper presents the first efficient method to find stable prices and allocations in auctions where the seller has certain cost structures. The authors connect this problem to other well-studied market models, showing relationships between them. They also prove that if a good is sold in more than one stable outcome, its price remains consistent.

What this means in practice

  • For auction platform developers: Implement auction software that efficiently computes prices and allocations for bidders with budgets and multiple substitute goods when sellers face cost constraints.$Commercial implications: Enables sales platforms to offer complex product-mix auctions with cost structures, improving marketplace efficiency and bidder satisfaction.
  • For market design engineers: Use the algorithm to design stable and fair multi-product markets that handle bidders with spending limits and sellers with increasing costs.

Authors

Elizabeth Baldwin, Paul Klemperer, Edwin Lock

Abstract

Arctic product-mix auctions allow budget-constrained bidders to express preferences over multiple substitute goods. We give the first strongly polynomial algorithm to find the competitive equilibria when the auctioneer has separable convex piecewise-linear costs. It combines a strongly polynomial reduction to the costless Arctic auction with an existing strongly polynomial algorithm for costless Arctic auctions. We also give a polynomial-time Turing reduction from costless Arctic auctions to linear Fisher markets, and a strongly polynomial many-to-one reduction to linear Arrow-Debreu exchange markets. If a good is sold in positive quantity in two competitive equilibria, its price is the same in both.