Deterministic Implementation in Single-Item Auctions

Abstract

Deterministic auctions are attractive in practice due to their transparency, simplicity, and ease of implementation, motivating a sharper understanding of when they can attain the same outcomes as randomized mechanisms.

We study deterministic implementation in single-item auctions under two notions of outcomes: (revenue, welfare) pairs and interim allocations.

For (revenue, welfare) pairs, we show a separation in discrete settings: there exists a pair implementable by a deterministic Bayesian incentive-compatible (BIC) auction but not by any deterministic dominant-strategy incentive-compatible (DSIC) auction.

For continuous atomless priors, we identify conditions under which deterministic DSIC auctions are equivalent to randomized BIC auctions in terms of achievable outcomes.

For interim allocations, under a strict monotonicity condition, we establish a deterministic analogue of Border's theorem for two bidders, providing a necessary and sufficient condition for deterministic DSIC implementability.

Using this characterization, we exhibit an interim allocation implementable by a randomized BIC auction but not by any deterministic DSIC auction.