Comparing Uniform Price and Discriminatory Multi-Unit Auctions through Regret Minimization

Repeated multi-unit auctions, where a seller allocates multiple identical items over many rounds, are common mechanisms in electricity markets and treasury auctions. We compare the two predominant formats: uniform-price and discriminatory auctions, focusing on the perspective of a single bidder learning to bid against stochastic adversaries. We characterize the learning difficulty in each format, showing that the regret scales similarly for both auction formats under both fullinformation and bandit feedback, as Θ( √ T ) and Θ(T 2/3 ), respectively. However, analysis beyond worst-case regret reveals structural differences: uniform-price auctions may admit faster learning rates, with regret scaling as Θ( √ T ) in settings where discriminatory auctions remain at Θ(T 2/3 ). Finally, we provide a specific analysis for auctions in which the other participants are symmetric and have unitdemand, and show that in these instances, a similar regret rate separation appears. dependency on the time horizon T of Õ( √ T ) under full-information feedback and Õ(T 2/3 ) under bandit feedback. These rates have been proven to be tight, except for the usual uniform price auction (referred to as the First Rejected Bid in Potfer et al., 2024).

We study the learning-to-bid problem in the case where opposing bids are stochastic. The stochasticity assumption ensures that our analysis characterizes the inherent difficulty of the auction format, rather than the difficulty arising from facing strategic or adversarial agents. We characterize when both problems can be learned with similar regret rates and when the rates differ. In the process, we provide the first worst-case tight lower bounds for uniform price auctions with bandit feedback, as well as the first instance-dependent regret bounds. Finally, we show that, against symmetric unit-demand adversaries, a clear separation of achievable regret appears, and we provide an efficient algorithm for the uniform auction that leverages the specific structure of this setting.

Simultaneous auctions of multiple identical items, including uniform, discriminatory, and Vickrey-Clarke-Groves pricing, are standard in auction theory, as described in Krishna, 2009. Uniform and discriminatory auctions have been studied and compared from an empirical point of view (Nyborg & Sundaresan, 1996;Nyborg et al., 2002), and by theoretical approaches, focusing on the revenue they generate (Ausubel et al., 2014) as well as the social welfare they generate (De Keijzer et al., 2013;Syrgkanis & Tardos, 2013). Special cases involving symmetry and unit-demand participant are also of particular interest (Anderson & Holmberg, 2023).

The repeated setting of auctions has recently attracted some focus, as covered by Nedelec et al., 2022. This setting allows for leveraging online and statistical learning tools (Lattimore & Szepesvári, 2020) to explore dynamic strategies. These repeated settings were first studied with a focus on the auctioneer, enabling the learning of reserve prices as in the work of Mohri and Medina, 2014. Learning to bid, from the bidder's perspective, was introduced later and studied in several settings, including sealed-bid first-price and second-price auctions (Achddou et al., 2021b;Balseiro et al., 2019;Weed et al., 2016).

Learning to bid in multi-unit auctions has only recently started to be studied, except for a partial result for uniform auctions by Feng et al., 2018 used as an example. The discriminatory pricing auction was studied by Galgana and Golrezaei, 2025, who proved regret rates of Õ(K √ T ) and Õ KT 2/3 under full-information and bandit feedback, respectively. Regret bounds of Õ(K 3/2 √ T ) were also obtained for the uniform-price format in the full-information case by Brânzei et al., 2023, as well as sub-optimal rates in the bandit case. Potfer et al., 2024 provided algorithms with a Õ K 4/3 T 2/3 regret upper bound for uniform auction in bandit feedback and showed that it is tight for a less common variant of uniform pricing (Last Accepted Bid pricing, or LAB). They provide no matching lower bound for the usual uniform price auction (First Rejected Bid, or FRB). Golrezaei and Sahoo, 2024 has also studied uniform pricing in a repeated setting, but focuses on bidders with return-over-investment constraints; they obtain similar regret bounds of Õ K 5/3 T 2/3 in their setting.

We propose a regret-based comparison of repeated uniform and discriminatory multi-unit auctions with stochastic opposing bids. For this comparison, we provide the first analysis of learning to bid in repeated multi-unit auctions when facing stochastic bids for both auction types.

We show that both auction formats admit tight worst-case regret rates of Õ(K √ T ) under the full-information setting (improving the best known rates for uniform price auction by a factor of √ K). We provide the first lower bound for a uniform price auction designed specifically for bandit feedback, showing that the regret must grow a