Deterministic Implementation in Single-Item Auctions
Yan Liu, Zeyu Ren, Pingzhong Tang, Zihe Wang, Yulong Zeng, Jie Zhang
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.
BibTeX
@inproceedings{ijcai2026_deterministicimp,
title = {Deterministic Implementation in Single-Item Auctions},
author = {Yan Liu and Zeyu Ren and Pingzhong Tang and Zihe Wang and Yulong Zeng and Jie Zhang},
booktitle = {IJCAI 2026},
year = {2026}
}