Papers for

market design engineers

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Strongly polynomial algorithm solves auctions with budget limits and costs

Solving the Arctic Product-Mix Auction

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.

Mon 28 SeptComputer Science and Game Theory
The gist
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.
Open → 2609.36346v1