At What Cost? (In)efficiency in First-Price Procurement Auctions

arXiv:2611.03386 · cs.GT · Submitted 2026-11-02 · Read on arXiv

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