Learning in Repeated Multi-Unit Pay-As-Bid Auctions
Rigel Galgana and Negin Golrezaei
October 2023
Motivated by Carbon Emissions Trading Schemes, Treasury Auctions, Procurement Auctions, and Wholesale Electricity Markets, which all involve the auctioning of homogeneous multiple units, we consider the problem of learning how to bid in repeated multi-unit pay-as-bid auctions. In each of these auctions, a large number of (identical) items are to be allocated to the largest submitted bids, where the price of each of the winning bids is equal to the bid itself. In this work, we study the problem of optimizing bidding strategies from the perspective of a single bidder.
This problem is challenging due to the combinatorial nature of the action space. We overcome this challenge by focusing on the offline setting, where the bidder optimizes their vector of bids while only having access to the past submitted bids by other bidders. We show that the optimal solution to the offline problem can be obtained using a polynomial time dynamic programming (DP) scheme under which the bidder’s utility is decoupled across units. We leverage the structure of the DP scheme to design online learning algorithms with polynomial time and space complexity under full information and bandit feedback settings. Under these two feedback structures, we achieve an upper bound on regret of O(M√(T log |B|)) and O(M’√(|B|T log |B|)) respectively, where M is the number of units demanded by the bidder, T is the total number of auctions, and |B| is the size of the discretized bid space. We accompany these results with a regret lower bound, which match the linear dependency in M.
Our numerical results suggest that when all agents behave according to our proposed no regret learning algorithms, the resulting market dynamics mainly converge to a welfare maximizing equilibrium where bidders submit uniform bids. We further show that added competition reduces the impact of strategization and bidders converge more rapidly to a higher revenue and welfare steady state. Lastly, our experiments demonstrate that the pay-as-bid auction consistently generates significantly higher revenue compared to its popular alternative, the uniform price auction. This advantage positions the pay-as-bid auction as an appealing auction format in settings where earning high revenue holds significant social value, such as the Carbon Emissions Trading Scheme.
Keywords: Multi-unit pay-as-bid auctions, Bidding strategies, Regret analysis, Market dynamics.
