At What Cost? (In)efficiency in First-Price Procurement Auctions
cs.GT
Submitted: 2026-11-02
Updated: 2026-11-02
Comments: 19 pages
License: http://creativecommons.org/licenses/by/4.0/
The gist: We study the efficiency of Bayes-Nash equilibria in first-price procurement auctions.
Abstract
We study the efficiency of Bayes-Nash equilibria in first-price procurement auctions. We measure efficiency by the Price of Anarchy (PoA): the ratio between the expected social cost in equilibrium and the minimum expected social cost resulting from a socially optimal allocation. We first show that the standard first-price procurement auction has no bounded PoA guarantee. We construct equilibria in which every bidder is indifferent between all bids in a common interval, so that bids can be arbitrarily large, and the PoA is unbounded. If costs lie in an interval [c, c] but bids are not restricted, the PoA equals the trivial ratio c/ c. We hence study ways to restore a finite guarantee, first by characterizing the PoA when bids lie in [c, c], which leads to the tight bound 1 + 1 e 2 (c c-1). Alternatively, we introduce the notion of a phantom bidder: the auctioneer accepts the lowest bid only if it does not exceed a phantom bid, drawn independently of the costs, and otherwise buys from an outside option at cost c. We show that a simple fixed phantom bid, i.e., a deterministic cap, gives PoA = 1e sqrt c over c +O(1). We further show that no phantom mechanism whose construction depends only on the cost interval, under a mild regularity condition, whatever distribution it uses and whatever it reveals about the phantom bid before bidding, can improve on the sqrt c over c dependence.
Sources
Related papers
- How Many Votes is a Lie Worth? Measuring Strategyproofness through Resource Augmentation
- Effective Horizons for Prophet Inequalities with Discounted I.I.D. Rewards
- Truthful-in-Expectation Mechanism with Constant Maximin-Share Guarantee
- The Power of Recruiting the Smaller Side: Two Additional Traders Suffice in Two-Sided Markets
- From signaling to interviews in random matching markets
- Optimizing Social Utility in Sequential Experiments