Randomized Truthful Auctions with Learning Agents

Prior research showed that in repeated second-price auctions with learning bidders, the runner-up bidder may not converge to bidding truthfully, limiting revenue. This paper extends this surprising result to general deterministic auctions and shows how the ratio of learning rates among bidders affects convergence. This raises the question of whether truthful auctions exist that promote convergence to true valuations in a learning environment and maintain strong revenue performance.

This research introduces strictly-IC auctions, a class of randomized truthful auctions that guarantee convergence to truthful bidding. The study demonstrates that randomized auctions can provide strictly better revenue guarantees compared to second-price auctions with reserves when dealing with large numbers of interactions. Further, a non-asymptotic analysis is performed, providing regret bounds for auctioneer revenue compared to the optimal strategy with truthful bids. These bounds are (almost) tight whether the auctioneer uses the same auction throughout the interactions or can change auctions in an oblivious manner. This work offers practical guidance for designing revenue-maximizing auctions with learning bidders and has important implications for online advertising and other auction settings.