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 .

• 저널Manufacturing & Service Operations Management · 27(1) · 200–229
• 토픽Auction Theory and Applications · Management Science and Operations Research
• DOI10.1287/msom.2023.0403
• 저자Rigel Galgana, Negin Golrezaei