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

• URL: http://arxiv.org/abs/2510.19591v1
• Date: Wed, 22 Oct 2025 13:41:27 GMT
• Title: Comparing Uniform Price and Discriminatory Multi-Unit Auctions through Regret Minimization
• Authors: Marius Potfer, Vianney Perchet,
• Abstract summary: Repeated multi-unit auctions are common mechanisms in electricity markets and treasury auctions.<n>We compare the two predominant formats: uniform-price and discriminatory auctions, focusing on the perspective of a single bidder learning to bid against adversaries.<n>We show that uniform-price auctions may admit faster learning rates, with regret scaling as $tildeTheta ( sqrtT )$ in settings where discriminatory auctions remain at $tildeTheta ( T2/3 )$.
• Score: 28.946496440127603
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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 full-information and bandit feedback, as $\tilde{\Theta} ( \sqrt{T} )$ and $\tilde{\Theta} ( 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 $\tilde{\Theta} ( \sqrt{T} )$ in settings where discriminatory auctions remain at $\tilde{\Theta} ( T^{2/3} )$. Finally, we provide a specific analysis for auctions in which the other participants are symmetric and have unit-demand, and show that in these instances, a similar regret rate separation appears.

Related papers

• Improved learning rates in multi-unit uniform price auctions [20.8319469276025]
  We study the problem of online learning in repeated multi-unit uniform price auctions focusing on the adversarial opposing bid setting.<n>We prove that a learning algorithm leveraging the structure of this problem achieves a regret of $tildeO(K4/3T2/3)$ under bandit feedback.<n>Inspired by electricity reserve markets, we introduce a different feedback model under which all winning bids are revealed.
  arXiv  Detail & Related papers  (2025-01-17T13:26:12Z)
• Randomized Truthful Auctions with Learning Agents [10.39657928150242]
  We study a setting where agents use no-regret learning to participate in repeated auctions. We show that when bidders participate in second-price auctions using no-regret bidding algorithms, the runner-up bidder may not converge to bidding truthfully. We define a notion of em auctioneer regret comparing the revenue generated to the revenue of a second price auction with bids.
  arXiv  Detail & Related papers  (2024-11-14T15:28:40Z)
• Variance-Aware Regret Bounds for Stochastic Contextual Dueling Bandits [53.281230333364505]
  This paper studies the problem of contextual dueling bandits, where the binary comparison of dueling arms is generated from a generalized linear model (GLM) We propose a new SupLinUCB-type algorithm that enjoys computational efficiency and a variance-aware regret bound $tilde Obig(dsqrtsum_t=1Tsigma_t2 + dbig)$. Our regret bound naturally aligns with the intuitive expectation in scenarios where the comparison is deterministic, the algorithm only suffers from an $tilde O(d)$ regret.
  arXiv  Detail & Related papers  (2023-10-02T08:15:52Z)
• Learning in Repeated Multi-Unit Pay-As-Bid Auctions [3.6294895527930504]
  We study the problem of bidding strategies in pay-as-bid (PAB) auctions from the perspective of single bidder. We show that a utility trick enables a time algorithm to solve the offline problem where competing bids are known in advance. We also present additional findings on the characterization of PAB equilibria.
  arXiv  Detail & Related papers  (2023-07-27T20:49:28Z)
• A Black-box Approach for Non-stationary Multi-agent Reinforcement Learning [53.83345471268163]
  We investigate learning the equilibria in non-stationary multi-agent systems. We show how to test for various types of equilibria by a black-box reduction to single-agent learning.
  arXiv  Detail & Related papers  (2023-06-12T23:48:24Z)
• Autobidders with Budget and ROI Constraints: Efficiency, Regret, and Pacing Dynamics [53.62091043347035]
  We study a game between autobidding algorithms that compete in an online advertising platform.<n>We propose a gradient-based learning algorithm that is guaranteed to satisfy all constraints and achieves vanishing individual regret.
  arXiv  Detail & Related papers  (2023-01-30T21:59:30Z)
• A Reinforcement Learning Approach in Multi-Phase Second-Price Auction Design [158.0041488194202]
  We study reserve price optimization in multi-phase second price auctions. From the seller's perspective, we need to efficiently explore the environment in the presence of potentially nontruthful bidders. Third, the seller's per-step revenue is unknown, nonlinear, and cannot even be directly observed from the environment.
  arXiv  Detail & Related papers  (2022-10-19T03:49:05Z)
• Fast Rate Learning in Stochastic First Price Bidding [0.0]
  First-price auctions have largely replaced traditional bidding approaches based on Vickrey auctions in programmatic advertising. We show how to achieve significantly lower regret when the opponents' maximal bid distribution is known. Our algorithms converge much faster than alternatives proposed in the literature for various bid distributions.
  arXiv  Detail & Related papers  (2021-07-05T07:48:52Z)
• Adversarial Dueling Bandits [85.14061196945599]
  We introduce the problem of regret in Adversarial Dueling Bandits. The learner has to repeatedly choose a pair of items and observe only a relative binary win-loss' feedback for this pair. Our main result is an algorithm whose $T$-round regret compared to the emphBorda-winner from a set of $K$ items.
  arXiv  Detail & Related papers  (2020-10-27T19:09:08Z)
• Optimal No-regret Learning in Repeated First-price Auctions [38.908235632001116]
  We study online learning in repeated first-price auctions. We develop the first learning algorithm that achieves a near-optimal $widetildeO(sqrtT)$ regret bound.
  arXiv  Detail & Related papers  (2020-03-22T03:32:09Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.