Learning in Repeated Multiunit Pay-as-Bid Auctions
研究了在重复多单位按报价支付拍卖中，单个竞拍者如何学习优化投标策略，提出了多项式时间算法和在线学习算法，并分析了均衡性质，对碳交易和国债拍卖有管理启示。
Problem definition: Motivated by carbon emissions trading schemes (ETSs), 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 multiunit pay-as-bid (PAB) 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. Methodology/results: Effective bidding in PAB auctions is complex due to the combinatorial nature of the action space. We show that a utility decoupling trick enables a polynomial time algorithm to solve the offline problem where competing bids are known in advance. Leveraging this structure, we design efficient algorithms for the online problem under both full information and bandit feedback settings that achieve an upper bound on regret of [Formula: see text] and [Formula: see text], respectively, where M is the number of units demanded by the bidder, and T is the total number of auctions. We accompany these results with a regret lower bound of [Formula: see text] for the full information setting and [Formula: see text] for the bandit setting. We also present additional findings on the characterization of PAB equilibria. Managerial implications: Although the Nash equilibria of PAB auctions possess nice properties such as winning bid uniformity and high welfare and revenue, they are not guaranteed under no-regret learning dynamics. Nevertheless, our simulations suggest that these properties hold anyways, regardless of Nash equilibrium existence. Compared with its uniform price counterpart, the PAB dynamics converge faster and achieve higher revenue, making PAB appealing whenever revenue holds significant social value—for example, ETSs and Treasury auctions. Funding: R. Galgana and N. Golrezaei were supported in part by the Young Investigator Program Award from the Office of Naval Research [Grant N00014-21-1-2776] and the Massachusetts Institute of Technology Research Support Award. Supplemental Material: The online appendix is available at https://doi.org/10.1287/msom.2023.0403 .