Comparing Uniform Price and Discriminatory Multi-Unit Auctions through Regret Minimization
Authors: Marius Potfer
Vianney Perchet
Venue: NeurIPS 2025 poster ()
Keywords: Auction
Online Learning
Primary area: theory
TL;DR: We compare the difficulty of learning to bid optimally in two predominant multi-unit auction formats: uniform-price and discriminatory auctions.

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.

Comparing Uniform Price and Discriminatory Multi-Unit Auctions through Regret Minimization
Marius Potfer!.2
Vianney Perchet 1,3
Crest (Fairplay joint team), ENSAE
2 EDF R&D
3 Criteo AI Lab
Abstract
Repeated multi-unit auctions, where 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 @(VT) and é(T2/3), respectively. However, analysis beyond worst-case regret reveals structural differences: uniform-pri price auctions may admit faster learning rates, with regret scaling @(vT) in settings where discriminatory auctions remain @(T2/3). Finally, we provide specific analysis for auctions in which the other participants are symmetric and have unit- demand, and show that in these instances, similar regret rate separation appears.
Introduction
Uniform price auctions and discriminatory auctions are widely used market mechanisms for the allocation of resources. They have been widely implemented and studied for electricity markets (Elmaghraby & Oren, 1999, Hortaçsu & Puller, 20088 and treasury auctions (Nyborg al., 2002). They are the most widespread simultaneous multi-unit auctions of identical goods (Krishna. 2009). Uniform price and discriminatory auctions are both standard mechanisms that allocate items to buyers willing to pay the most; their rules are identical except for the prices buyers pay. Since the two mechanisms are so similar, they can easily replace each other and have been frequently compared (De Keijzer et al., 2013). Their differences have been studied from several points of view: from their efficiency in Ausubel al., 2014 the revenue they generate for the auctioneer, to the expected social welfare in different types of equilibria (Syrgkanis & Tardos, 2013).
Participating in these auctions be challenging from bidder's standpoint since the bidding process is not truthful (i.c., the best strategy depends on other buyers' behavior). However, when auctions oceur repeatedly, buyers can improve their strategies over time using online learning techniques; this is referred to as learning to bid (Feng et al., 2018). The performance of these online learning strategies is often measured by regret, which compares the cumulative rewards with that of the best fixed strategy in hindsight (Lattimore & Szepesvári, (020). We propose to leverage this online learning framework quantify the difficulty learning to bid optimally, therefore providing a new approach to compare uniform and discriminatory price auctions.
Learning to bid in repeated multiunit auctions has recently been studied, both in the uniform pricing case Brânzei et al., 2023 and Potfer al., 2024,, and in the discriminatory pricing case by Galgana and Golrezaei, 2025 These works focus adversarial bids and provide regret rates with similar
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

dependency on the time horizon T of (VT)) under full-information feedback and ((72/3) under bandit feedback. These rates have been proven to be tight. except for the usual uniform price auction (refemed 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 desendeed 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.
1.1 Related Work
Simultaneous auctions of multiple identical items, including uniform, discriminatory, and Vickrey- Clavke-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 al., 2014) as well as the social welfare they generate (De Keijzer al., 20033] Syrgkanis & Tardos, 2013). 3). 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, covered by Nedelec al., 2022 This setting allows for leveraging online and statistical learning tools (Lattimore & Szepesvári, 2020) 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 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 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 (KT2/3) under full- mall-infommatin and bandit feedback, respectively. Regret bounds of 0(K3/2 VT) were also obtained for the uniform- -rrioem--riceeteee price format in the full hull-information case by Brânzei et al., 2203 as well as sub-optimal rates in the bandit case. Potfer et al., 2024 provided algorithms with a O (K 44/31//33 regret upper bound for uniform auction in bandit feedback and showed that it is tight for 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 returnover-investmenl constraints; they obtain similar regret bounds of Ô (K5/372/3) in their setting.
1.2 Contribution
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 under the full-information setting (improving the best known rates for uniform price auction by factor of VK). We provide the first lower bound for uniform price auction designed specifically for bandit feedback, showing that the regret must grow as Ω (T2/3), which, in light of previously known upper bounds (Potfer et al., [024), fully characterizes how the regrets must scale with respect to T. Our algorithm analysis also yields more precise regret characterization for the bandit setting of uniform price auctions: while the upper bound scales as Ô (K3/372/3) for general demand, better regret rates can be achieved when the bidder has low demand: regret for unit-demand and Ō ((TT) for two-unit-demand.
We further provide an instance-dependent quantity characterizing other instances (with general demand) for which regret bounds scaling O(VT) can be obtained for the uniform auction under

---

bandit feedback. The discriminatory auction's 's lower bound of Ω (T2/3) remains valid in these instances.
Finally, in the bandit feedback when the adversaries are unit-demand and symmetric we show similar regret separation providing an algorithm which guarantees regret of ((vT) in uniform auctions while lower bound of 52 (Te/s) for the discriminatory price auctions remains valid. In the analysis, we derive a concentration inequality for partially observed ordered statistics based on the DKW inequality, which may be of independent interest.
The following table summarizes the achievable regret rates for the different auction formats under bandit feedback considered in this work, we use the notation (()) when we have matching lower bounds (2()) and upper bounds O()), up to log factors. Results that are entirely novel are highlighted
in green, while blue denotes marginal improvements or generalizations over existing work.
Worst Case
Instance Dependent
Unit Demand
Two-unit Demand
Any Demand
A- sep 4
L.D.D
Discriminatory
(T2/3)
Uniform
@
((VT)
Table 1: Achievable regret under bandit feedback.
1.3 Technical novelty and Challenges
While we study a similar setting, our approach departs significantly from prior work (Potfer et al., Branzei et al., Galgana al.) in both algorithmic design and theoretical analysis. Unlike existing methods that discretize the bid space and rely on randomized bandit algorithms, we propose a deterministic algorithm tailored the stochastic opposing bids setting. The main technical novelty lies in the use of statistical CDF estimation and concentration bands, which allow us to operate directly in a continuous action space without discretization. This analysis yields a cleaner and more interpretable analysis. From a technical standpoint, the main challenges is to carefully choose and apply the right concentration bounds and results ensure the tightness of our bounds.
We establish two complementary lower bounds that characterize the fundamental limits of learning in these stochastic auctions. The first provides general lower bound that extends prior discrete-space results to continuous bid domains, ensuring that the regret scaling remains valid regardless of the action granularity. More importantly, deriving the lower bound for uniform price auctions under bandit feedback required particular care. As shown in [emma 2) the feedback is richer than standard bandit feedback (since it includes local observation of opposing bids), making it necessary to finely manage the feedback available to obtain our tight lower bound.
2 Models
The following encompasses both uniform and discriminatory price multi-unit auctions, and matches those used in Brânzei et al., 2023 and Galgana and Golrezaei, 2025 Indeed, because both auction formats are very similar, we only need specify different payment rules (equations ( and to describe the mechanisms.
Repeated auction Let (K,T) E N2 be, respectively, the number of items sold at each auction and the number of repeated auctions. We describe the repeated K-item uniform and discriminatory price auctions from the point of view of one buyer, that we call the hidder, facing other stochastic buyers, whose bids are aggregated and who, as a group, are called the adversary. The bidder has fixed set of valuations that quantifies how much utility it derives from being allocated any number of items. We denote by (U,,..., uK) E [0, 1 1] the bidder's marginal valuations, they are assumed to be non-increasing. These are marginal the sense that when the bidder obtains n items, derives Eisn 2y from it. At each time-step E [T), an instance of the auction proceeds as follows:
1. The bidder transmits its bids b' == (bi, by. .... b&x } to the auctioneer. For convenience, we consider b ordered in non-increasing order and the bids in [0, 1] We call B the corresponding subset of [0, 1
3

---

2. The bids of the adversary 3 := (39, 5kg B are drawn according to distribution over B, denoted D, and then transmitted to the auctioneer. Note that since opposing bids belong to B, they are also assumed to be already sorted in non-increasing order.
3. The auctioneer orders all the bids in non-increasing order and determines the allocation (the number of items won) of the bidder that we denote x: (b', 33) E [K] as well as the prices
p (b*, E [0, 1]K
4. The bidder receives their allocated items and pays the price for each item. This gives rise to
the following utillit: (b', := =>i , [u: p(b',3')(
5. The bidder may receive additional information, referred to as the feedback.
Allocation Both auctions we study are standard; therefore, the items are allocated to the buyers who submitted the K highest bids. Thus, the allocation is formulated follows
x- b, B) == max E [K] Vj S k. by 2 3k+1-j}
Pricing As we noted previously, the pricing rules of the uniform and discriminatory auctions are different. We describe below how the price is set in both auctions:
The uniform price auction sets the price of all allocated units identically: the value of the first rejected bid. Formally, it the (K + 1)th largest element of (b, 33), written:
p(,, 3) =
8K- kE[K]
(2)
The discriminatory price auction sets the price of each allocated unit as the value of the corresponding bid (the bid that won its emitter this item). Formally, the discriminatory price is written as follows:
p(b, B) = (EE))
Regret The performance of learning algorithm is quantified by the regret. This metric quantifies the expected cumulative difference between the maximum utility the bidder could have obtained and the utility they actually received. We define it as follows:
R
T sup bEB
Iu (b, B~D
E
DE (u(b',p') B'
E
This definition aligns with what is usually defined as pseudo-regret. Note that, with the previous definition, minimizing the regret is equivalent to maximizing the cumulative expected utility. Using this metric allows us take into account both how well and quickly a bidder can approximate the best bid, as well as how costly it is to acquire information about D.
The bidder can sequentially improve its bids since it receives some information after each auction, which intuitively provides it with some knowledge about the distribution D. We describe below the feedback, defined as the information received after one instance of the auction. We focus on two feedback types: the full-information and bandit feedback setting, which the most common in online learning literature (Lattimore & Szepesvári, 2020) and in online learning in auctions (Achddou al., 2021a] Feng al., al., 2018). At time E [T]. at the end of the auction:
Feedback
in the full- iall-information feedback setting, the bidder observes 3 in the bandit feedback setting, the bidder observes only 2(b', , and p(b',
*
Note that the full-information feedback is strictly more informative than the bandit feedback, because abb', , and p(b',,3 can be computed by the bidder who knows both its bids b' and the auction's rules.
3 Learning with full-information feedback
We first focus on the full information feedback setting where the learner observes the full vector e at each time step. The bidder aims to minimize regret by choosing bids as close as possible to the optimal bid vector, namely b* == argmaxbes Eg<D (u,b, B)). Because the auction mechanisms
'This allocation breaks ties in favor of the bidder. The results can be extended to any tie di-bbrakinn rule by ensuring that ties occur with probability zero.

---

are not truthful, ba depends on D. To describe this dependence, let us define, for all &o E [K]] and x E [0, 1). (x == Pa ( S x) the 1eth marginal cumulative distribution function.
The following lemma provides the main intuition for our learning algorithms, which mainly focus on estimating the marginal CDFs rather than the optimal bid vector b".
Lemma 1. In both auction formats, the expected utility be expressed a function of the bidder's bid vector b and the marginal cumulative distribution functions (Fk) (FK)
The proof follows from writing the utility and taking the expectation, it is provided in Appendix A We denote UA the functions such that, in the discriminatory auction, for b E B, Ua((Fi) [e(])]])))))))))]]{])))) (b)
EgnD "u,,, [3)]. and U,, the equivalent in the uniform auction. Explicit formulas are provided in the
appendix (see (14) and (13 to save space.
3.1 Algorithm
At time E [T'. the bidder has observed ......,'-' which are i.id. samples from D. These sufficient to compute empirical marginal CDFs, which are known to have strong convergence proper-
ties Massart, 1990 They are defined, for ho E [K], and x E [0, 1] as (z()) = [-1 E/= ( s z}. Depending on the auction, we define the expected utility estimate as either ú' ú'(b) := ((F)) b) or
1
(b) == Ua((F2 (2), b). Equipped with these, we can now provide an algorithm that guarantees tight regret bounds for both auction formats.
Algorithm 1: Full-information feedback
Input: time horizon
2 Output: bids for each time step (b', De....,b--!.b'? E (B)T.
3 for t = .. T do
Play b' == argmaxbeB û' (b).
Receive the utility u(b', B²) and observe B
Under full- full-information feedback, Algorithm 1 achieves a regret Ry - Ô ( (KVT) for both the discriminatory and the uniform price auction.
Theorem 1.
Proof Sketch. The proof for the discriminatory auction uses the D Kiefer- Wolfowitz inequal- ity from Massart, 1990 to build high-probability confidence bands for Fg. which yields confidence bands for the utility estimate. Combining that with the optimality of b' with respect to û' allows us show that the per-round regret is upper bounded by 2K 2K /ln(2/a)/22 therefore providing the
correct regret rates when summing.
The proof for the uniform auction's 's is very similar. The main difference appears when ensuring bands scales as К and not K2, this requires our concentration bnads to leverage the strong negative correlation between the different terms estimated in excepted utility. This is achieved by using the Natarajan dimension, a multi-class classifier generalization of VC dimension Shalev-Shi Shalev-Shwartz and Ben-David, 2014
The complete proof is in Appendix These regret bounds are tight, it known that any algorithm must ineur a regret growing as Q(K VT) in both auction format (Brânzei et al., 2023 Galgana Golrezaei, 2025).
Remark 1. Note that, because it' is always a piece-wise linear function and is separable into functions that only depend on two components of b, maximizer can be found by using dynamic programming in (23
4 Learning with bandit feedback
We now focus on learning in the bandit feedback setting. Let us recall that in this setting, at time t, the bidder only observes his allocation =(b',g')) ,') and the price paid per unit p(b',3') Since the allocation function is the same across both auction's 's type (T). the observed allocation provides the same information
(1 2 3k- [E[K]
(5)
5

---

However, the information conveyed by the price differs:
The discriminatory price depends only on the bidder's own bid and therfore provides no additional information.
The uniform price can be set by an opposing bid 8K-i+1, potentially revealing information about the distribution D.
The following lemma formalizes the feedback the bidder receives in the uniform price auction. Lemma 2. At time & (T), let b', B E B be the bids of the learner and the adversary, in the uniform auction with bandit feedback the bidder observes (1l (1{ {
This feedback reveals components of 3² if they fall into the right intervals, providing richer feedback than in the discriminatory case. We now examine achievable regret rates in both auction types and the effects of this feedback discrepancy.
4.1 Discriminatory price auction
The discriminatory price auction with fixed valuation has been studied by Galgana and Golrezaei, 2025 who provided algorithms guaranteeing regret upper bounds of O (KT2/3). They also provided a regret lower bound of (K2/ST2/3) for discretized bid strategies. We provide a strengthening of this result with lower bound that holds for any algorithm, including those operating over continuous bid spaces.
Lemma 3. Any algorithms for bidding in repeated first price auctions with known valuation must incur a regret of S2 (I2/3)
Given this result and the almost matching upper bound, we believe the achievable regret rates are well characterized. In the following we characterize what can be achieved in the uniform price auction, and when the richer feedback allows for better rates than discriminatory auctions.
4.2 Uniform price auction
The additional information provided by the richer bandit feedback in the uniform price auction can be used to design learning algorithms. We illustrate how the feedback allows estimate the marginal CDFs F& with Algorithm 2 During its estimation phase, it leverages the feedback detailed in Lemma to ensure observation of each Bg in round robbin fashion. Once the estimated CDFs are precise enought, an estimated best bid b Tewyi is computed and then played repeatedly during the exploitation phase.
We define the empirical CDFs for the uniform price auction with bandit feedback follows for E [K]
Va E [0, [0,1), = Ei= 1 fo (6K+2- 0k+1- al} 1 18) S sz}
(6)
Ej for E (bk-2-A x
We also define the empirical expected utility ü, for b B as U ((F(F))(e )E((K)) b). With these we can provide our algorithms and the associated regret guarantees.
Algorithm 2: Estimate then commit for uniform price auction
Input: time horizon 7', Tempt duration of the exploration.
Output: bids for each time step (b) ba ...., bT (.-'bbb) E BT.
.e....,b"'!
Estimate: for t 1, 2, ... Tezpt do + K [T/K] + 1.
Play b' such that < k. bf. = and > k 0.
Receive the utility n' = u(b', ,²)) and the feedback.
Commit: for = Temp + 1, 1...., T do Play b' argmaxpe Team (b)
Theorem 2.
The estimate then commit algorithms, with the exploration time Tempt = K2/372/3 achieves a regret bound of Ô (33/3T2233

---

Proof Sketch. The proof separates the analysis of the regret incurred during the exploration phase and the commitment. During the exploration phase it is no bigger than K5/3m2/3 The regret of the exploitation phase can be upper bounded by K5/372/3; obtaining this bound requires the use of variants of the DKW concentration inequality, which exhibit local dependencies as in Bartl and Mendelson, 2023] Blanchard and Voracek, 2024] A simpler analysis, using DKW inequalities (Massart, 1990) yields a looser bound of K2T2/3 when setting Teepl = KT2/3
These regret guarantees match the rates in T of the ones for the discriminatory price auction. Since the regret rates in the discriminatory auction are tight in T, it is natural to ask whether that is also true for the uniform price auction. [Thoorem provides matching lower bound, proving that regret that grows as T2/3 is optimal.
Theorem 3. In the uniform price auction, any algorithms must incur a regret of (T2 for learning to bid with known valuations, when valuations are such that V/ > 0.
Proof idea. The proof of this theorems relies on standard approach (Cesa-Bianchi al., 2024 Kleinberg & Leighton, 2003) to create regret lower bounds in bandit setting with continuous action space by embedding into our auction model a hard instance which is akin multiarmed bandit problem with O (3) arms. The main challenge is that the bandit feedback in the uniform price auction is relatively rich, as pointed out in Lemma We overcome this difficulty with the two following techniques, for specifie i [K]:
the optimal bids are such that 6ī b,+1
while the bidder needs to observe BK-i+1-
when submitting bid with b * b,41, the bidder suffers an additional regret term which scales linearly with b; - b,+1-
We have shown that the achievable regret in the two auction formats behaves similarly regardless of the feedback types. The remainder of the paper is dedicated to showing that, beyond worst cases, the uniform auction can be casier to learn (regret scaling with vT) across different families of instances for which the discriminatory auctions remain equally hard (regret scaling as T2/3). We provide general algorithms that exhibit better regret scaling when possible without information about the instance and then focus on an I.I.D setting, whose structure especially interesting.
Bandit feedback, beyond worst-case
5.1 Instance dependant regret
To exhibit that the regret scales as vT on family of instances that are well-suited for the uniform price auction, we need an algorithm which adapts to such instances. This adaptability is key in guaranteing worst-case regret, as in Theorem 2) while also leveraging easy instances when presented with one. Algorithm 2 llacks such fiexibility, because of both its fixed-length estimation and commitment phases, as well as its fixed marginal CDF estimation intervals (namely [0. 1)..
We propose two natural improvements: (i) using sequentially shrinking estimation intervals and (1i) using distinct intervals for each marginal CDF Intuitively. the shrinking rule should allow us to estimate CDFs only However, the choice of the shrinking rule must be made with care. We propose successive elimination approach (Audibert & Bubeck, 2010) which iteratively reduces a set of candidate bids B' C based on the current utility estimates and their uncertainty. As the set of relevant bids Be gets smaller, the intervals where estimates of the marginal CDFs are useful to estimate the utility do as well; this yields our shrinking rules for the intervals, that we denote (I)) KE[K]]
7

---

Algorithm 3: Bandit Feedback
Input: Time horizon 7 Initialize: For each E [K] initialize D < [0, 1]
Output: Bids (b'...., b²) E B", with A
for [ - 1,..... do
if T expi and A A'-1 < 0 then
k + T K K + 1;
by f max{ba E
1---1 k
b + min E I
b' arg by bu=bi be41=bb11
BEB
ib);;;
else
1 - T ( + + [k/2];
b/ (b E }
if is even
min(br (b E I
if is odd
b' c arg max BEB (bbb:;
b
Play b' and receive feedback; Update (Ti) A' using Algorithm 4
Algorithm 4: Interval Refinement
Input: Time horizon T, intervals (I--) kE(K) utility estimate at Output: Updated intervals (I)) kE(K>> gap A
T f max maxbell z4-1 (b))
// Max observed utility
II I + conv (U-1 ((-((unn U V kE(K]
ln(272)
Wimax 1))
U-1 denote the preimage of at
2|1KK|
3 A + minke(2.....i (inin I max 1
Let denote 8 C. B the of maximizers of the expected utility and the optimal intervals the smallest closed intervals such that B* c II Ii- We introduce the interval gap I == minxee2,....f (m maxI the following theorem provides instance dependant bounds, valid when > 0 (O(-) hides terms constant in T). Theorem 4. Algorithum guarantee a regret of (155337//3) general and, when A > 0, an instance-dependen regret bounds of ÖKKTT).
Proof. Worst-case regret bounds essentially proved in Theorem 2 We only need check that our shrinking rule is well-behaved. Noticing that with high probability, the intervals Z always contain the best-response set B* suffices.
Instance-dependent bounds proofs rely on the fact that as soon as intervals become disjoint (ie A' 0), the observation of Lemma covers the whole intervals, which is why recover full- information type bounds.
5.2 Regret separation
We illustrate the implications of Theorem by describing instance families for which the achievable regret rates in uniform and discriminatory price auctions diverge significantly. This highlights how the choice of auction impacts learning complexity.
straightforward example is when bidder has unit demand, meaning only values single unit (vi and v; 0 for i 1). In this case, the uniform auction is truthful (Lemma 7). the bidder can bid truthfully and incur zero regret. In contrast, the discriminatory auction still requires strategic bidding, and the lower bound from Lemma 3 apppies, resulting in a regret of Ω (T2/3).
Two unit demand A similar but weaker regret rate discrepancy also appears the two-unit demand setting (i.c. U1 > 0, v2 0 and 0 for i > 2). In that setting, both auctions require strategic

---

bidding; in discriminatory auction, Luctinn,Lemma 3 still applies resulting in regret S2(T2/3) while Theorem yields regret of O(VT)) the regret in the uniform auction.
A separated distributions We finally consider a more general condition on the distribution of adversary bids. Let D be a distribution over B such that when ~ 'D each coordinate 3y. almost surely lies in disjoint intervals Zg, and adjacent intervals are at least separated by a gap A. We refer these A separated. To rule out degenerate cases, we focus on A Zे
Lemma 4. Learning in discriminatory or uniform auction when the adversary's 's distribution is A separated, with A < 2K can be achieved with respectively regret of Q(T2/33 and (VVT).
Proof sketch. The lower bound from Lemma 3 for the discriminatory auction can be easily extended by leveraging the fact that A > K
1-e1 Proving the upper bound is straightforward by noticing the
following (i) there is always optimal bids against A --separated distribution whose component only Os and 1s, (ii) the of A Asepaarated distribution are A --separated.
5.3 LLD. adversaries
This section characterizes achievable regret when the bidder faces N E N symmetric, unit-demand participants. Each participant submits single bid, so the opposing bid vector B consists of the K highest bids among them. By symmetry, all bids are i.i.d. from a distribution P, and we assume independence in their bidding. We denote by PN the induced distribution on B.
Opposing bids The first K order statistics of N ii.d. samples from P constitute the opposing bids. This structure provides additional information on the relationships between marginal CDFs (Casella & Berger. 2024 Letting F [0, 1] [0, 1] denote the CDF of P, we have for all A: E [K]]
Fx)x
P A-PN
(Bx S x) NNN (z)
Σ
N N N-
p.k (2)
(7)
Note that this is a polynomial F; in the following, we denote it Ps.
Concentration Inequalities for order statistics Exploiting 7 we build edf bands for all order statistics based on observations of a single order statistic. For simplicity, it is stated in the full information feedback. For k, k' E [K]² define the empirical estimate of the CDF of the trth order statistics based on the ktth, Pk == (P (TT))
Lemma 5. Let t, N, and let Xj E [4]. [k] be i.idd samples from distribution P with cdf F. With probability 1 a
(k) aRK S (x) (x) + aR
(8)
1 2t
Where 6
and agg is constant which only depends on k. k and N.
Proof. The lemma is proved using the DKW inequality (Massart, 1990), the order statistics edf formula 7 and by noticing that all Ps are strictly increasing on (0, 1).
Algorithm These concentration inequalities effectively enable recovery of full-information feed- back in the uniform price auction by selecting the best estimate. For & E [K] and [0. 1], let t (x) be the number of times {3x= < xx) was observed (Lemma 2}. Define k* (x) = argmax t (z)
as the index with the most observations, and estimate marginal CDFs (x) F (e (2). The resulting utility estimate is at()) == Ua Ua((F()
Algorithm 5: UBIID algorithm
Input: time horizon T, number of adversary N.
2 Output:
bids for each time step (b b2....,,'? T- b"") E B", for t = 1,2,..., do Play == argmaxpe ū' ubb
Theorem 5.
When facing i..dd adversaries in the uniform auction with bandit feedback, Algorithm
guarantees the regret is upper bounded by δ (VT)

---

Proof sketch. The previous result is essentially proved as the bound for the coll-information feedback, by noticing that for all r E 00, (x)r) 2 K. This ensures that the estimates F concentrate as well as in the full-information feedback up to additional factors which only depedn on K, techniques similar to the ones for Theorem T then yield the result.
Lower bounds Because the opposing bids order statisties, previous lower bounds may not apply. Intuitively, this is because constraining the opposing bids to be ordered i.i.d. can make learning to bid easier (as Theorem 5hswws). Let consider the discriminatory auction first. Notice that for l-unit auction, the general setting and the i.i.d. setting coincide. Therfore the lower bound form Lemma 3 applies and regret is at least (T2/3). The uniform auction requires a new lower bound, that we provide below:
Lemma 6. When facing i..dd adversaries in the uniform auction with bandit feedback, any learning algorithm must incur at least regret of ((VT).
Proof idea. Focusing on two-item auctions, we build upon the proof of the lower bound of Brânzei al., 2023 the uniform auction in the full information feedback. Since they use opposing bids which can only be worth 0 or 2/3, it is possible to build distributions that mimic the behavior of the ones used in their lower bound, even when using i.i.d. bids.
Remark 2. We assume knowledge of the number of adversaries N in this section, However, since the components of ß are order statistics, N can also be estimated from a finite number of samples.
6 Conclusion
We characterized the difficulty of learning to bid in multi unit auctions through achievable regret rates. We show that, under iillmmmffomtnonn feedback, both auction formats be learned with matching regret rates. In the bandit feedback setting, the picture is more nuanced: while worst-case regret guarantees similar for both formats, the richer feedback structure of the uniform auction make easier to learn in instances that do not correspond to the worst-case distribution.
A key simplification in our analysis is the stochasticity assumption for opposing bids. It remains an open question whether similar results hold when adversaries are strategic, which would also enable the study of social welfare when multiple bidders learn simultaneously. Another interesting direction to consider settings where bidders' valuations must also be learned, and investigate how auction transparency (Cesa-Bine Bianchi et al., 2024) impacts the learning process.
Acknowledgements
Vianney Perchet acknowledges the support of ANR through the PEPR IA FOUNDRY project (ANR- 23-PEIA-00033 and the Doom project (ANR-23-CE23-0000), as well as the ERC through the Ocean project
10

---

References
Achddou, J., Cappé, O., & Garivier, A. (2021a). Efficient algorithms for stochastic repeated second- price auctions. Algorithmic Learning Theory, 99-150.
Achddou, J., Cappé, O., & Garivier, A. (2021b). Fast rate learning in stochastic first price bidding. Asian Conference on Machine Learning, 1754-1769.
Anderson, E., & Holmberg, (2023). Multi-unit auctions with uncertain supply and single-unit demand (tech. rep.). Faculty of Economics, University of Cambridge.
Audibert, J.-Y., & Bubeck, S. (2010). Best arm identification in multi-armed bandits. COLT-23th Conference on learning theory-2010, 13-p.
Ausubel, L.. M., Cramton, P., Pycia, M., Rostek, M., & Weretka, M. (2014). Demand reduction and inefficiency in multi-unit auctions. The Review of Economic Studies, 8I(4), 1366-1400.
Balseiro, S., Golrezaei, N., Mahdian, M., Mirrokni, V., & Schneider, J. (2019). Contextual bandits with cross-leamning Advances in Neural Information Processing Systems, 32.
Bartl, D., Mendelson, S. (2023). On a variance dependent wvoretzky-kieferr.ee arXiv preprint www.iv:230800775..
inequality.
Blanchard, M., & Voracek, V. (2024). Tight bounds for local glivenko-cantelli. International Confer- ence on Algorithmic Learning Theory, 179-220.
Boucheron, S., Lugosi, G., & Massart, P. (2013). Concentration inequalities: A nonasymptotic theory of independence. Oxford University Press.
Brânzei. S., Derakhshan, M.. Golrezaei, N., & Han, Y. (2023). Learning and collusion in multi-unit auctions. Advances in Neural Information Processing Systems, 36, 22191-22225.
Casella, G., & Berger, R. (2024). Statistical inference. CRC press.
Cesa-Bianchi, N., Cesari, T., Colomboni, R., Fusco, F., & Leonardi, S. (2024). The role of transparency repeated first-price auctions with unknown valuations. Proceedings of the 56th Annual ACM Symposium Theory of Computing, 225-236.
Combes, R., Proutière, A., & Fauquette, A. (2020). Unimodal bandits with continuous arms: Order- optimal regret without smoothness. Proceedings of the ACM on Measurement and Analysis Computing Systems, 4(1), 1-28.
De Keijzer, B., Markakis, E., Schäfer, G., & Telelis, O. (2013). Inefficiency of standard multi-unit auctions. European Symposium on Algorithms, 385-396.
Elmaghraby, W., & Oren, S. S. (1999). The efficiency of multi-unit electricity auctions. The Energy Journal, 20(4), 89-116.
Feng, Z.. Podimata, C., & Syrgkanis. V. (2018). Learning bid without knowing your value. Proceedings of the 2018 ACM Conference on Economics and Computation, 505-522.
Galgana, R., & Golrezaci, N. (2025). Learning in repeated multiunit pay-as-bid auctions. Manufac- turing & Service Operations Management, 27(1), 200-229.
Golrezaei, N., & Sahoo, S. (2024). Bidding in uniform price auctions for value maximizing buyers. arXiv preprint arXiv:2406.0366
Hortaçsu, A., & Puller, S. L. (2008). Understanding strategic bidding in multi-unit auctions: A case study of the texas electricity spot market. The RAND Journal of Economics, 39(1), 86-114

---

Kleinberg, R., & Leighton, T. (2003). The value of knowing a demand curve: Bounds on regret for online posted-price auctions. 44th Annual IEEE Symposium Foundations of Computer Science, 2003. Proceedings. 594-605.
Krishna, V. (2009). Auction theory. Academic press.
Lattimore, T., & Szepesvári, C. (2020). Bandit algorithms. Cambridge University Press.
Massart, P. (1990). The tight constant in the dvoretzky- wolfowitz inequality. The annals of Probability, 1269-1283.
Mohri, M., & Medina, A. M. (2014). Learning theory and algorithms for revenue optimization in second price auctions with reserve. International conference on machine learning, 262-270.
Naaman, M. (2021). On the tight constant in the multivariate storerrky-kiefer-woofovvi inequality.
Statistics & Probability Letters, 173, 109088.
Nedelec, T., Calauzènes, C., El Karoui, N., Perchet, V., et al. (2022). Learning in repeated auctions. Foundations and Trends in Machine Learning, 15(3), 176-334.
Nyborg, K. G., Rydqvist, K., & Sundaresan, S. M. (2002). Bidder behavior in multiunit auctions: Evidence from swedish treasury auctions. Journal of Political Economy, / //0(2), 394-424 4244.
Nyborg, K. G., & Sundaresan, S. (1996). Discriminatory versus uniform treasury auctions: Evidence from when-issued transactions. Journal of Financial Economics, 42(1), 63-104. https //boi.org/htpps://do..oog http://///..ooooooo/o00000000000 10166000044405509500033
Potfer, M., Baudry, D., Richard, H., Perchet, V., & Wan, C. (2024). Improved learning rates in
multi-unit uniform price auctions. Advances Neural Information Processing Systems, 37, 130237-130264.
Shalev-Shwartz, S., & Ben-David, S. (2014). Understanding machine learning: From theory to algorithms. Cambridge university press.
Syrgkanis, V., Tardos, E. (2013). Composable and efficient mechanisms. Proceedings of the forty-fifth annual ACM symposium on Theory of computing, 211-220.
Weed, J., Perchet, V., & Rigollet, (2016). Online learning in repeated auctions. Conference on Learning Theory, 1562-1583.
12

---

NeurIPS Paper Checklist
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
The claims in the abstract are provided in more details in the contribution subsection. These claims are thenprovided in the main paper. Proofs available in the appendix.
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Limitation are discussed in the conclusion. The result stated are clearly only valid the limit our modelling.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best
13

---

judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: The proof's are mostly in the supplementary material. high level overview of the ideas in the proof's are provided in the main paper.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm.
14

---

(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g.. a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (c.g., to registered users), but it should be possible for other researchers have some path reproducing verifying the results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https:/nips..c/public guides/CodeSuumissoooooii for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce results. See the NeurlPS code and data submission guidelines (https) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Question:
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
15

---

The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics httppp///eeeiiipcccooooeecciiiit
16

---

Answer:
[Yes]
Justification:
The research is conform neurips code of ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.g., there a special consid- eration due to laws regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: This is theoretical paper, and as such it has very limited societal implication. The main possible implication are discussed in the conclusion section.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA No, they should explain why their work has societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses such risk.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring
17

---

that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: The paper does not any existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g.. CC-BY 4.0) should be included for each asset.
For scraped data from particular source (e.g., website), the copyright and terms of service of that source should provided.
If assett are released, the license, copyright information, and terms of the package should be provided. For popular datasets, paperswithcode. com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release new assets
Guidelines:
The answer NA means that the paper does not release assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and research with human subjects
18

---

Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsoureing nor research with human subject
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subject
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if' applicable), such the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: The paper does involve any LLM in the models and theoretical framework studied.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy [ttp:://eeuripecccooomeeeeeee//s for what should or should not be described.
19

---

Appendix
This appendix provides additional technical details, proof', and supporting results for the main paper. It is organized as follows:
Section A presents general simplifications and key properties of the auction models that are useful for our analysis.
Section B contains detailed proofs of the regret upper bounds for both the full-information and bandit feedback settings, including concentration inequalities and technical lemmas.
Section C
provides the proof' of the main regret lower bounds for the discriminatory (first price) and uniform price auctions.
Section D covers proofs and results specific certain instances, such as A --separated distributions and the i..d. unil-demand adversary setting.
Throughout, all notation, definitions, and assumptions are consistent with those in the main text, unless explicitly stated otherwise. Where appropriate, we restate key lemmas and theorems for clarity, Cross-references to the main text and within the appendix are provided for ease of navigation.
A
Appendix
A.1
General simplifications
This section presents general properties and simplifications of the auction models considered in the main paper. We highlight structural results that are useful for the design and analysis of learning algorithms. such as truthfulness in uniform price auctions and the implications for optimal bidding strategies. These results serve as foundational tools for the regret analyses in subsequent sections.
Uniform price auction with unit demand We focus our attention on the unit demand uniform price auction, in which the bidder only wishes to acquire one item. Formally, this means that v1 > 0 and for all k: > 1, fkk = O. One can notice that in this specific case, the optimal bid is straightforwardly b' (v1, 0, ......... 0). Therefore, in this case, there is no need for online learning algorithm and bidder playing b* for every time t E [T] incurs regret O.
The following lemma shows a more general property of which the previous claim is a direct conse- quence.
Lemma 7. In the uniform price auction, for any distribution of opposing bid D, let ba (bi, (5....,,k)) = argmaxbe E [u(b, 3)] then b* = -V1, min(bj, v2)...., mii...,,.ii......... Uk)) is also maximizer.
BND
Proof. We will provide stronger result, which is that, given any opposing bids B, when we denote u(b", 33 the utility of the bidder against these bids when bidding b", then u(b",8) s u(b",3). Let k* be the biggest index such that 69. > Denote b the bid with b7. replaced by ug.. Let consider z(b", .3) and a(b; (), either they equals or xrbb () 3))
In the first case, noticing that the price function p(: is increasing in all the components of the bids, yields w(b", ,3 < u(b 3).
In the second case, we have rrbb. (3) xx <bb uk- Therefore, fk- ppbb ,3) < O, noticing that this is the last term the utility when playing b' and that the price is increasing in all the components of the bids, we can conclude that u(b', (] < u(b u(bj. (3)
3),, which necessarily implies that bj. p(b', B) >
We can repeat this process for all the components of the bids. Combining this with the fact that the utility is only increasing in the first component of the bid vector (usually denoted by) allows us get that u(b", (3) < u( u(b",, 3).
Because of the previous property, when analyzing learning algorithms for the uniform price auction, we will always consider the algorithms' pick bids such that by = en when maximizing estimates of expected utility.
20

---

We now move on to providing the proofs and formulas necessary to justify our approach. We recall the Lemma I
Lemma 1. In both auction formats, the expected utility can be expressed function of the bidder's s bid vector b and the marginal cumulative distribution fanctions (Fi ke(K]-
In fact, for the discriminatory auction, the utility can be written as follows:
E (b, 3)]
Σ FK-iti(b)) (oi b;)
(9)
AND
In the uniform price auction, the expected utility can be written as follows:
K
E
lu(b,))
=
(FK- (bb+t)) - FK FK-
Σ
bi+1
(10)
AND
1m1
)
E
1 lbe 3K- bet1
Σ 1t- 20--Bk-it) 8k-itt)
(11)
Proof. We begin by proving the lemma for the discriminatory auction. The utility can be rewritten as u(b, 33 E (b; 2 (8xi++) (e; - b,). Taking the expectation and rewriting by using the definition Fg. leads the following equation, which concludes the proof.
K
(ub,))) BND
Σ FK +41 (b:) (v, - b;)
(12)
We now move the uniform price auction. To have convenient formula, we write the utility of the bidder in the uniform price auction by decomposing it depending on the K + 1 bid.
K
u(b, B) = Σ
(Bx-i > bit1 2 3x- 3x-i41}
Σ 1=1
vr
bi+1
i=1
+
(b: BK-i- > bi-b}
Σ
-i--it1
BK
1=1
When taking the expectation, this leads to
K
E
(ubb,))
Σ P (Bk > bi+1 2 (k-itt)
Σ bi+1
BND
1=1
i
+
Σ P (b. 2 BK- bit1)
Σ 11
iE [1 (be 2 3K-++1 > b++1 Bx-it1]
Which simplify
i
[u(b
Σ (Fx (b4441) (b+1))
Σ 1j
bi+1
BND
(FR-iti(b)) - (bi+1))
Σ 11
(13)
fo
b.Fk-142(bb)
FK- (t)dt
Jon
This concludes the proof.
21

---

With the previous proof in mind, we can define Uy and Us. the corresponding functions that, given the CDFs, allow to compute the expected utility.
Let (G& Kek) be sequence of CDF functions. The following equations define the functions mentioned in Lemma for: the discriminatory auction for b E B:
Ua((Gk)kE(K) b) b) Σ 1=1
G Gki+1 (bs) (vs bz),
(14)
the uniform auction for b E B:
U. ((((G))) (Gk-iti - Gx-
b): Σ
Σ 1=1
21
bitl)
i=1
(15)
Σ (Gk-141(0)) GK GK-s+1
E
u1
xdGK
(bc1
Lemma 2. At time t [T]. let b', B E B be the bids of the learner and the adversary, in the uniform auction with bandit feedback the bidder observes (1l { (b/+1. B (4- (E(K)
Proof. At time let i then turn equivalent to (ar(b', 1) (p(b', ,3¹) & b4 which is an observable event. Note that when the event realized, the value of 0 observed since it is the price.
then 0K-++1 (b(+1, bb], is equivalent to 4 kk S which is
Therefore, since it is the case for i E [K]. bt]] 3
the bidder has observed
(1 (5K-i41 [b
Remark 3. Notice that the previous Lemma 2 implies that all times and for all i [K]. the following function is also observed Vz E (b/+1, b4]. (8k-s E x0,
B Regret Upper Bounds
In this section, we provide detailed proofs of the regret upper bounds stated in the main text for both the full-information and bandit feedback settings. We include all necessary technical lemmas, concentration inequalities, and step-by-ster arguments for the algorithms analyzed. Our goal is to make the derivations transparent and self-contained, enabling readers to verify each step of the analysis.
B.1 Full-information feedback
Recall that in the full information feedback, the bidder observes 3 the end of each time-step. therefore, at time f, it has observed s.....,tt_.
The following lemma, which links the quality of the estimates of the marginal CDF to the quality of the estimates of the utility, can be used to derive regret guarantees for both auction formats.
9
Lemma 8. Given (F()RE(K) the empirircal estimates of the cumulative marginal distributions of DD from samples, let a E [0, 1), then in both the uniform price auction (with û(-) == ((F(()))E(K)) and in the discriminatory auction (with û(-) : U.. ((((())s)(K)))))) The following inequality holds
Vk E [K], IP
sup ((bb) - IE [[(bb, [)] S Ké((a)) 2 1 - 1- bEB
(16)
Where for the discriminatory auction (a(a) = / [In(2) 3v c22 log(2K)+log(
and for the uniform auction e'aa) =
2t
22

---

Proof. We begin with the proof of the guarantees for the discriminatory auction. which is more concise: Let T N, time E [T], we apply the result from Massart, 1990 which in our notations provides that, for E [0, 1):
In (2) V
Ak E [ P
sup =E(0,]]
1F2 Fa(1))
(17)
2t
Doing a union over the opposite events, one easily gets:
In ( 2t
P
Yk
[K], sup =E[0.1]
Fv (x) Fa(x))
$
1 - Ka
(18)
We can write the expected utility in the discriminatory price auction, for b= (bi,..., bx) E as [u(b, ExE(K) F& (bb) (vk by). Using the expression of ú, we get:
sup i (b) E [u(b, s sup bEB
Σ kE(K]
Pa(bb)) - F%(()a)
beB
(a(bb) - Pa(ba))
sup kE[K] b
Using (8) then yields the desired result.
We now proceed with the proof for the uniform price auction. We start by rewriting the utility from as follows:
K
E
[u(b,,)) 9)] =
Σ
1l (8x-i >> biti 2 3x iit1
Σ
bs+1
BDD
B
i=1
1=1
1
Σ
1 {b; 2 8K--+11 > bHit
Σ
Us
i=1
K
b,F b.Fk-it1(b)) - bi+t Fx Px- (bbt)))))) - f
bb
Σ
Fr FK-=+1(()d))
K
1l {8x-s > bit1 2 3k-141)
Σ 1j - b
A
1=1
K
Σ im1
1 (b, 2 8K-H+1 > b+1t
Σ Ug bit1
K
Σ
{(b - b.+1) FK-1+1
K
(hi Fx-1+i(t)dt
bb
Σ
i=1
23

---

The estimated utility can also be written similarly, yielding:
K
d'(b)
E
Σ
13k-i > but1 2 3x-itil
Σ
2 - bi+1
1=1
+
Σ
11 {b; 2 3k- lit1)
Σ
Vij bb+1
1=1
K
Σ
i (b; - -b+22) F (x-1t2(bb)
1=1
K
f Fi-itz(f)dt
Σ
Where E' denotes the empirical expectation.
We will show that the estimated utility is close to the true expectation by showing that is the case for each of the terms of the sum. We begin with the terms that only require DKW bound, which restate here: Let N, at time E [2']. the result from Massart, 1990, provides that, for a E [0, 1]:
In (2) 2t
Vk E [K].P
sup [E(0,1]
(F Fa(t))
a
(19)
We can therefore get that with probability 1 -Ko:
K
K
I FK-ita(t)dt
K
FR FK-i-1
Σ
Σ
i(b; b1t1)c S Ke
(20)
bit1
b
t=1
Similarly, with probability 1 Ka:
K
K Σ (b. bx41) Fx-1+1(b)) S i=1
K
(b. b,-1) FK 1 Σ
Σ
ilb: b1t1)e Ke (21)
i=1
Note that
20 and 21 are also valid when taking the supremum over b B.
We now move to bounding the last difference needed. We first provide the required tools.
Usual concentration incquality for the CDF can be obtained by considering the family of indicator functions x 1 {X S x). In order to obtain tighter concentration bounds, we will use results on uniform convergence results on multiclass learnability from Shalev-Shward and Ben- Ben-David, 2014 to bound all the terms simultaneously.
First notice that for any B E B, the family of events (13x-; > bi+1 2 3x-i+1 )ςę(K] U ((b, 2 8 > b are disjoint for any E B. We will consider the multiclass clas- sification functions associated with these events for b E B, and denote Hy this family classifi- cation functions. We also denote f the function which maps an element of to the corresponding multiclassifier.
We begin by bounding the Natarajan dimension of HB. generalisation of VC dimension. For reminder of the definition, see Shalev-Shwartz and Ben-David 2014 section 29.1.
Notice that amongst the events, there are interval indicator functions for each coordinate of the vector B.. Therefore, we can use the same argument as for obtaining the VC dimension of the family of functions 1 {X E [a, b)). The main difference being that we require 2K + 2 element of B in order have least three different values amongst one coordinate, than observing that one cannot obtain labels [1,0 0, 1] in the corresponding class yields the following upper bound on the Natarajan dimension A of the family multiclassifier at hand:
N (HB) < 2K +
(22)
24

---

Then, using the Multiclass Fundamental Theorem Shalev-Shward and Ben-Dave 2014 Theorem 29.3 yields the following concentration inequality, with probability a
Σ ((b) E
sup E
s
(23)
T
BDD
/C
2K (o)
Where there is universal constant C such that e"
We can therefore use this bound in order to obtain the following with probability at least az
sup B
E
(1 (Sk- bit1 2 8K 8k-++1) + (b, 2 8x-it1 > b5+13)
Σ
Djj
bi+1
7=1
K
(1 [3kk-- bit1 2 BK-1-1 + +1 1bb 2 8x- > b(11)
Σ
Uj
bi+1
1=1
< Ke
(24)
With this equation, we can now bound the error of the expected utility using (00). (21) and (24). with
probability least 1
sup
à (b()
[u(b, 3)] s 3KE
(25)
BEB
BND
which concludes the proof.
We restate the theorem providing upper bounds on the regret in the full-information feedback
Theorem 1. Under full-information feedback, Algorithm / achieves a regret Rı Ô K (KVT) for both the discriminatory and the uniform price auction.
Proof. Lemma yields the following concentration inequality:
P
(b)
E B~D
[u(b, B)] Ke 21 Ka
(26)
Let's denote the optimal bid b* == argmax
E [u(b, 3)]. Since b' is the maximum of at, we
BND
known that á' (b*) S (b')... Applying the previous concentration inequality both b" and b' and leveraging the optimality of b' gives us with probability Ka:
E [u(b', [)] Z E [u(b' [3]] + 6Ke
(27)
B~D
B
Choosing a 77 and summing over E [T]. then yields the desired regret bounds Rr δ (KVT).
B.2 Bandits Feedback
We provide in this section the details necessary in order to obtain the guarantees for the algorithms 2 and 3 This subsection is therefore only focused on the uniform price auction, which has the most expressive bandit feedback of the two auction formats.
Let us recall that in this setting, the bidder only observes the outcome of the auctions the end of each time step. Formally at time with 3² the bid of the adversary and b' its own bid, the bidder observes r(3 b') and p( bt). Lemma provides alternative representation, while Remark points out how it relates to indicator functions used for CDFs empirical estimates.
We recall the formula of the estimates of the marginal CDFs for & E [K]
E 1 far E (b/r42 bx+1111]] 1 1 < x}
Va [0, 11, P. (x)
(28)
Σ/=1 1l {xr E 22 D x
25

---

B.2.1 Explore then commit algorithm
We restate the theorem providing upper bounds on the regret in the bandit setting for the uniform auction.
Theorem 2.
The estimate then commit algorithms, with the exploration time Tespt K2/3722/3 achieves a regret bound of (K55/372/3)
Proof. In order to prove the regret the algorithm, we provide a two-part bound which matches the two-phase behavior of the algorithm. Indeed, we use the following regret decomposition between exploration regret and commitment regret:
RT Re + RT
(29)
Where we define the exploration regret as
Toupl
RT
Tezpt sup bEB
I' BDD
[u(b)
(((b,Bil
Σ
E
Jubb,,)")
(30)
B'DD
t=1
and the commitment regret
RT (T
Tempt)
sup bEB
E BaD
[u(b, (u(b,
Σ t=Tesp
E g'DD
[u(b',
(31)
We begin by opper-bounding the exploration regret by noticing that the utility is upper-bounded by K. This leads to
Reap S KT KTeppl
(32)
Notice that during the exploration phase, the bidder ensures that for every & E [K] it has at least observed [Texpt/K] K] samples of fg.
Notice that during the exploration phase, for every k [K]. the bidder has observed at least [Teapt/ KJ samples of Sg. This follows directly from applying Lemma to the bids exploration phase. This ensures our CDFS estimates F are valid on the whole domain and that we can create concentration bands.
We will concentration results the empirical CDF to show that estimate of the expected utility is close to the actual one. We begin by stating the concentration results that we will use
We can use Massart, 1990 to show that for all [K]:
Vk [K]PP P
sup zE(0.1]
FR Teant (x) Fa(x)) S
2 Tecpl
In
2 21-a
(33)
We will need another concentration result. It is well known that the family of indicator functions of intervals has VC dimensions 2, therefore, it follows from section 12.5 of Boucheron al., 2013 that for any l E [
Texp' (b) - Fx Teapt (a) - Fb(b) + Fa(a)
Fk
PP
sup (0.,))E
< /Kja)
21-a -aa
(b - Ps(a)
(34)
Where eTT, a)) 122 (
T
To upper bound supsen
(b,3) Teop (b)). (Fe) we will use the following formulation of the BND
expected utility into terms well suited for showing uniform convergence.
26

---

K Σ
B [l(b, 3]] = Σ F
ibst1 (FR-141(b(41) FR-1(bs+1))
[=1 1=1
abbt1 (Fk-i+1(b;) Fk Fk-241(b(41))
(35)
K 100--bih bi+1) PK-
FK-i+1(tddt - Σ 1bb
but1
Notice first that we can obtain the two following equations as in the proof of Lemma 8 we can use obtain similar bounds in (20) and
3
21
K
K
be
K
PK- P
Σ
FTeeet
<
i(b; bit1)e S Ke (36)
bi+1
i=1
bett
1=
K
K
K
Σ
i (b:
b FK-i+i (b:)
Σ
i (b: b(t1)
Fr kiiti(bb) (bs)
5
i(b; bi+1)e S Ke (37)
==1
can also get the following bound:
(Kx-41(0)) - FRant (bi)) us
S Ke
(38)
only remains to get concentration bounds for the following term:
K
Σ
ibbt 1 Fk-i(bit1) FK-i+1(b)) (b:))
(39)
-ibi41 (2Fk- (2Fx-44(((411) Fb-r(b)+1) FK-4+1(bi)
We start by the following computations:
K
K Σ
ibbt1 (Fx-iti(bi+1)
Fx (bb++1)))
ibbt (bx+i+((b+1))
i=1
K
(i - 1)6; (Fx-it1(b.)
2=
K
bi (Fx-11)(b++1))
Σ - (..fii-)((xxxt((b1))) - Fx-)-1(b;))
1=2
K+1
(i - (PF-) Kbx+1
Adding the other terms in of (39) yields:
K
2b,41 (2Fg-1+1(btt)) Fb-1(bi41) Fk-141(b.))
Σ i=1
b (Fx-)))(bor1))
b (2i 1) (Fx-1+1(b+11) FK-4t1(bi)
K+1
- (i-1)(b; -b:t1 (Fx-s++(bb) Kbx+1
(40)
27

---

Naturally, å can be written the same way, we will therefore bound 39 by bounding the error on each sum independently. By upper bounding using both (33) and as follows, with probability 2ka:
we can upper bound the last terms
sup BEB
ibit1 (:F=-i41(b++)) Fk-i(bi+1) PR (xxi+1((:))
(41)
1b;+1 (2Fk-st((bLt))) FR-I(be+1)= FK FK-i+1 (bi)) S Ke+ K Ke
Combining equations therefore yields with probability 1 2Ka
sup B
E (b, - -Texni (b) s <6K3/2
(42)
BDD
Where 2 1n( [eoggelTTena/// [
Then notice from Algorithm 2 that for all & Teept, all the bids b' the same (because they are the solution of the same maximization problem). By optimality we get ifexp! (bTerp!) 2 Tf'erpl (b*). Combining with (42) then yields for all 2 Teaps with probability 2Ko:
IV [u(b", [)] E [u(b',,)) S 6K
(43)
By summing over Teapt S T and recognizing the formula of 19 we get, with probability 1 - 2Ka:
RTmh < 12K
V Vin
2
KJ).
(44)
Since Texpt K2/372/3
And from 322
we get:
R
K5/332/3
(45)
Choosing + and summing Reom and R7 yields the desired regret bounds.
B.2.2 Improved bandit algorithm
We now move the improved bandit algorithm, which can allow for better regret bound when the instance it faces makes possible.
We restate the theorem providing upper bounds the regret in the bandit setting, including the instance-dependent bounds. Before providing the proof, we introduce several instance-dependent quantities which relevant for the instance-depeddett bounds and the proofs.
Theorem 4. Algorithm guarantee regret of ((K5/3T2/3) in general and, when A 0, instance- dependen regret bounds of Ö(K.T).
Proof. For the analysis, we will consider two cases, one that we call the worst-case, and one that is the good instance. We talk about good instances if during the first phase of the algorithm for some t*, A is positive, and if not, it is a worst-case instance.
Worst-case Let us first analyse what happens in worst-case instances Vt E [Ternt], A' < 0. As for the proof Theorem decompose the regret into exploration and regret.
Ry R +
R
(46)
We can, by noticing the utility is positive and smaller than K, upper bound the exploration regret by KT expt which yields
Repdl 5/3/2//3
(47)
28

---

In order to provide a similar analysis of the regret of the second phase as for Algorithm 2 we need to show that after the exploration phase, the bidder has effectively observed enough samples of each component of B ~ 'D on the right intervals (because observation is no longer guaranteed on [0, 1)).
We recall the formula of the marginal CDF estimators for &s E [K]:
Ve [0, Pc) Ej= 1 f & E (bx 2- k. 6/ n.] 1 18g S x}
(48)
Ej=1 1 fxr E ( -1
suffices to notice that during the exploration phase, at time t. when he := t K [t/K]] + 1, the interval corresponding to F that reads 1 {o E (b b strictly contains I UT and by monotonicity of the intervals, contains I U UI/++1 for any 1' 2 We therefore write: For any t E [T], for any k E [K]. V E I UI K+D Ej= fxr (k.+) 2 min(L L K])-
Notice from 15 that for 1' 2 1, for b E [LLEIK] IK. FK- is only evaluated I UTZ The previous statement is therefore sufficient for the concentration results of Theorem 2 to be reproduced.
The only modification needed is to notice that we can only guarantee that the optimal bid b* remains in the [ Z with probability Ka at each time. The probability of the bad event "the best bids are out of our confidence intervals" is at most KaT
We can therefore obtain that with probability 1 2KaT:
RT < 1/K5/3 In (2) + In(elTTeppt/ KJ).
(49)
Choosing a 1 and summing R and Reep yields the desired worst-case regret bounds of 2
75
Instance dependent In this section of the proofs, we examine the case where for some 1* E [Terpt]. we have A" > 0. First note that because intervals are shrinking, this implies that for all f 2 t², A
As for the previous case, we focus our attention on how samples that allow us to estimate the marginal
CDFs collected. The same proof in the previous section holds show that, for times t < t", least [/K] samples of each 3K- are observed, on the relevent intervals: I U
We now focus on the behavior of the samples in the else statement, i.c. when 2 t". Let t E [T]
such that A >> O and denote K = 2K 1 /
and k2 [K/2]. Then notice that if k is
even I C (bf, - -1 10 [ and if Ky is odd I C (bg by [ Therefore, after one round (i.e.
M
2K steps) the bidder observes at least one sample of 3 on I U
We can therefore write the two following concentration inequalities as in the proof of Algorithm 2 here specific intervals, and in any time variant. For any t E [T'] and E [K]
The first from Massart, 1990
In (2)
Wk [K].P
sup =EZUUZ
F Fk-k+1(z) Fx x-
S
2[t/2K]
21-a
(50)
The second:
Fx F k41 (b) - Fk (k) Fx-R+1 (b)+ Fx (x))+1(a)
<c((t/2K]a)
sup (a (ANNEEE
2 21
v Fa((b) - (r.(a)
(51)
Where e(t, a) = 122 In -oop(e))
This leads, using the same procedure as in Theorem 2 to with probability 1 - 2Ka
sup be][.e[k]
E [)] ab(b) < 3/2
(52)
Z
BND
29

---

12 Where = 1/2 1m [ KJ) [
Using the optimality of mann and the fact that long 52 is true, b remains in Hia[K] I ensures that, for 2 with proba -KKx:
E
(u(b,, 2 E
[u(b", ,8]
1/K
(53)
B-D
3ND
The cumulative regret therefore follows by summing and choosing a
7
12
RT S Kt + Σ 12K S Kt
Σ 12K
(54)
t
All that is left is to show that We introduce these quantities here: we denote B C the set of maximizers of the expected util- ity and the optimal intervals I C R. the smallest closed intervals such that 8 C II Ig We also introduce the interval gap A == mi..e(2.....K)) (minZ; max Ix and the util- 13 ((b) and og == E [u(b", ity gaps: o == [u[(b", []] ba.t.by Smin -2/2
upper bound ta' based on some instance-dependees quantity.
E [u ()b)
bs.t.bx 2mxx bg A/2
Notice from equation (2 that necessarily, as soon as 12K3/2 S min(( +, 6% )eE(K]).frr all E []]. the intervals I are at most A/2 wider than Ig and therefore A Therefore,
12K
min( )<c((()
With these quantities, we can now write the following regret bound, which completes the proof:
Rr S 20 0(min
k5/372/3
12K
2
+K xx2VT)
(55)
mín + ( DEIKK max
C
Regret lower bouds
This section contains the proofs of the main regret lower bounds for the discriminatory (first price) and uniform price auctions, namely [emma Theorem 3 We construct hard instances and use ieformationntheorettee arguments to establish fundamental limits on the achievable regret in these settings. The techniques used here are inspired by and extend prior work, as referenced in the main text. The difficult instance that we consider is significantly more straightforward to describe for the proof of Lemma We therefore begin with this one, as it should make understanding both proofs easier.
C.1 Lower bound for the first price auction
Let us restate the lemma before providing the proof. Lemma 3. Any algorithms for bidding in repeated first price auctions with known valuation must incur regret of Q (T2/3)
Proof. The first-price auction is special case of the discriminatory auction when only one item is available. The utility simply writes: u(b, /) (b > 3) (v b). Notably, when / has random distribution of Cumulative Distribution Function E (b, 8)] F(b) (w b).
Throughout this proof, we will use these notations, with the bid of the bidder b E [0, 1] and the opposing bid 3 E [0, 1].
To prove a lower bound on the regret of learning in the repeated first price auction, we use techniques similar to those in Cesa-Bianchi Bianchi al., 2024 (ie, we show that in this problem we can embed 1/3 "bandit arms" into our continuous actions space).
30

---

Outline of the proof We devise a base probability distribution of 3, the adversary's bid, which is described by its CDF F. This distribution is such that the utility of the bidder is constant on wide range of bids (ie, [0. with a constant). From this base probability, we derive family of (F.), multiple slightly perturbed versions of F. The main characteristic of the perturbation is that it leaves the CDF of F unchanged outside of an interval of width ~ T We provide O (TI/3) of such perturbation. The instance we consider is bidder such that the distribution of the opposing bids is drawn uniformly at random amongst the perturbed distribution. Quantifying the distance between the feedback distribution generated by each perturbed distribution allows us to prove the lower bound.
The base distribution D is characterized by its CDF F' that we define to be:
1 3(1 b)
36 1b<3 + 4 1 2
F(b)
b
b2 3
(56)
It is easy to check that EADD [u(:,3) is constant on [0, }). and is decreasing on [3: 1].
We define the intervals (I')) (iE (rr[a)/ on which the 2th perturbation takes place as follows:
If" = T 1/3 1/1-3/33111133
Let's then define the corresponding perturbations ef [0, - R: -
<T] = F (i+ (1+1) F(b)) 1 (bb
(57)
We can now define F. := F + eT" the 7th perturbed CDF, and DJ' the corresponding distribution. It is straightforward to see that F. and F coincide outside of I,". It is also clear, since F?" is constant on Z that the utility is maximized in /7-1/33
We can now describe the instance faced by the bidder Let T E N, the difficult instance is follows:
An index i E [[3TT/3]] [] is drawn uniformly at random.
For in [T]:
- The bidder picks a bid b' based on the past feedback Zi,..., Zz-1
The adversaries bid f is drawn according to D.." the distribution with CDF F..
The bidder receives the feedback Z, 1 1( > 3*). and the utility us (v (o-66) 2 }
From here onward, focus on determining the minimum regret any algorithm must incur when facing the previously described instance of the first-price auction. We also restrict our analysis to sensible algorithms, that is, whose bids are always in [0, 41- These assumptions are relaxed at the end of the proof.
We denote p.0 the probability measure over B when its drawn according to D and Ift the probability measure of 3 conditionally on the value of i (ie when its drawn according to DF)). The notation extends naturally to expectations E. and EE' as well as regret R2. and Ri..
Some Notations:
For t E [T], we denote Y; [0. 1] - f0, 1} such that (((b) = 1(b 2 3t). And Z, is the feedback received at time t, is random variable and depends on the bid played by the algorithm A at time f. For now, we restrict ourselves to deterministic algorithms, which allows us to write b² : {0, 1} r - [0, 1] the function which maps the feedback received up to time t to the bid played by the algorithm A at time f. With these notation, notice that Z, Yi (Z1, ..., 2-1)).
With these in mind, the following lemma constitutes the core of the proof. We postpone its proofs just after the end of this proof, essentially, one uses the fact that distributions of feedbacks Z, are too close to be distinguished.
Lemma 9. For all S [33-1/37 and any deterministic algorithm A, denoting Nr NT(1) the number of times algorithm A produces a bid in IF_, we have:
9
E [Nr Ea [NT(1) N
2/3
E (1)
(58)
40
31

---

We now use the fact that we know that in the hard instance, i is drawn uniformly at random.
Averaging for < [3T we get:
/3T//11 E' [Nr(1
1=
/37//1
E
[Nr(1i]
+
T2/3
1371/9
E
(i)
(59)
1/3
/3T1/31
40
//3
T
9
72/3
T
(60)
/
40
//21/3
[3T1/31
1
RT
rEE [T NT)
(61)
1/71/3
T
T
minr;
T
T/2
(62)
1
[3T /37
40
|/T
T
ms
T
T223
(63)
37'133
40
37'/3
3v3
minr; r
T
72/3
T
(64)
40
Where r; is the sub-optimality of not playing interval when it is optimal.
(1- 1
T1
3 3 -
1 T-1/3
1/3
2 27
T-1/3 1/3
9
3 3
1417 T-13)
Reinjecting this lower bound on yields the desired lower bound of S 2T2/3). This bound is valid for any algorithm which issues bids in j0, }1 Lemma 11 generalises to any deterministic bid. The lower bound generalizes to random algorithms by Yao's minimax principle.
C.1.1 Technical lemma
Lemma 9. For all S [/T--1/3] and any deterministic algorithm A, denoting NT the number of times algorithm A produces bid in IT have
9
E (Nr(1) E. (N+( S 22/3 Ed [T))
(58)
40
Proof. We want to upper bound the following quantity
T
E [Nr(1) - E (N) =
Σ Fd (Z,, 2,-1) E I7- - -P0 [b' (Z,,.,,Z,-i) e I!] (65)
We will upper each term of the sum independently. The algorithm can be anything deterministic; therefore, (c) can be any function, which is why we bound the previous quantity as follows:
32

---

pat [69 (Z1.... Z...,,Z-11) E ] - po
[b' p
(Z1,.,,Z-11 E It]
(66)
1 P Pizuni 1) P
-P Pa ullz
(67)
KL (Pi2 PD (Zim
(68)
2
KL KL (P2 :P2)
+
KL (Ii
(69)
2
j=2
Where P (2,,...-11) is the push-forward probability of (Z1, ... Z(-1).
Since we focus on deterministic algorithms, (2 Zj-1 1) conditionally on Zi,.,, Ze-1 is fixed.
Pd [ = Z1, Z
KI. (T2 2,, P22, 21 21... = E0
In
p0 [2g = 0 Z,, Z1-1]
Pi Iz = 0 Z ... 2j
(70)
pd 12, = 2, .., 4
pd [[ = 1 Z Zz 1
P
Z = 1 2 z
(71)
o01
[Y,(6b] 0]
E
In
pO [X,(0)) -0]
(72)
1.N (b) =
P. [2, = 12100
p0 (xx((6)) = 11 16 EI!
In
P
(b))
(73)
(F)) ('()) S (1- TO (b [ IT)
(74)
Where {b E } appears because for other values of b2, the logarithmic terms are 0.
We obtain 744 from the fact that the KL between two Bernoulli P, Q of parameters p.g q is
KL(P, Q) < (p-9)²
(1-0))
Since F is non-decreasing and Fi(b)) E [3 21. by concavity of x + x(1 z) on this interval.
(B) - F'(()))²
KL (P&, 2....,,-1" : ;12 2211,,2....
<
p0 p0 EI!)
(75)
2
9
1 - 1o' (it ((+tr-=))) pD (b'
i
po
E
2
9
(76)
We can then use Lemma 10 in combination with (69
and (76) to obtain:
9
Pp [b' (Z1, Ze-1) =
p0 [b' (Z) .., Z EI| < T-13/
E0 [N)( 1/3 /
(77)
40
We can therefore re-inject in 66 to get:
T
E [Nr(i)]
E [Nr(1)
9
T
1/3
E
[N(11]
< T/3 (E9(NT(1)
(78)
40
40
[=1
33

---

Lemma 10. For < [3T /37, we have the following inequality:
F i T-11/3
Fo 1 TT13// 1/3)
-73
(79)
400
Proof.
1.0
(11-118) - [ 9
Fo (+ )) 2 =
2
(80)
3 (11 5 3T-3/33
3 (1 14 T-1/3
9
1
1
(81)
1/3
9 (i + 1) 7-13
3T31/3 1/3
(82)
99 iT 1/33
(9 (i 1)
97-2/3
(83)
400
Where we get (33) from the fact that é I 1/3 (given T but thats always the case)
(9-
-9- iT 1/3) (9 +++ 1) > 20,
Lemma 11. Let A be any algorithm for the first price auction, their exists an algorithm A achieving lower regret that only plays bids in [0, 2)
Proof. For any algorithm A. if at time / the algorithms picks bid D outside of [0, }). replace b by J' 2. ignore the feedback received from the auction and provide a simulated feedback drawn according to (F(b)) to A. Because the feedback we provide follows the same distribution, and both drawn independently from any other randomness (namely other 5²)), on expectation, the algorithm behaves identically for the following time steps, and utility-wise the cumulative reward receive by the algorithms has strietly increased, since u(ō²)= 2 ubb)..
C.2 Lower bound for the uniform price auction
This section is dedicated to showing the lower bound on the rate of learning in uniform price auctions. The lower bounds is valid when the learner is willing to acquire at least 3 items (ie 23 0, and K 2 3).
We restate the theorem:
Theorem In the uniform price auction, any algorithms must incur a regret of (T2/3) for learning bid with known valuations, when valuations are such that U/ 0.
Proof. For simplicity, we prove the lower bounds in the uniform 3-item auction. The lower bound naturally extends to K > 3 by considering adversary bid distribution where for all & < K 3, P(A: = 1) = 1. The proof revolves around constructing hard instance of the learning to bid problem, and then showing one cannot avoid regret, which grows T2/3 in this instance.
The hard instance In the instance of the problem, we focus the bidder who has the following valuations 01, 222 V3 = 1, 3.33 3.2 As before, B = (31, 32, 83) is the adversary's 's bid and for & e also denote fg the corresponding density. Since the quantity that
(1, F& is the CDF of Dk. matters in our problems are the marginals CDFs (Lemma 1.. we first define our hard instance by the densities and marginals (checking then that there indeed exists distribution with these is then enough).
The overview of the hard instance is as follows: we characterize (via the marginals) distribution D (called base instance) adversary bids such that there exists an interval C [0, 1] such that the set of maximizers of the expected utility can be written 01, y, y for y E I. We then build a family of 1/3) distributions based perturbed versions of D (via additive perturbation of the marginals)
34

---

for which there exists a single expected utility maximizer. The hard instance then consists in selecting uniformly at random one of the perturbed distributions when 0.
The densities the base instance are as follows:
101
if [0 900
y E 900
fa(y)
3(va-M)
if E 61 3.
03
if E (3 if E [0, y E ( 900 if E ( 61
21
f2(v)
3(12-w)
if (3.1]
if [0, 5 900
if E 900
fi(y)
3(v2
if E 61
01
if (3.)
Where a1, Q2,, 0g are normalisation constant. The values of are not important because they define the density above U2 and U3. ie in regions of the bid space B that we know are suboptimal from Lemma 7
This results in the following CDFs for y E (0, U2]:
101y
y E (0, 5
900
Pa(y)
+ Fil)
if E 500
5
G
if E (
21y
if E [o. 5
5 900 500
P2(1)
Pi(y)
y E
F.(
if
3
if y E
[0,
900
Fv(
[In (U2
In (U2 (i
y) + 900
y E
900
900 6 if 6
As before, the opponents' bids follow a distribution, & ~ D. Given sample of this random variable (B1, B2, B2) the utility of the learner is the following function
ub(b,, 62, b3)
1 (6, 2 83 2 b2) (vi - 8z)
+ 1 (3, 2 b2 2 {3} (m - b2)
+ (b2 2 82 2 b1] (v) + + 282)
+ 1 [31 b 2 32) [a] + - -2b3)
+1 (b. 2 81) + 03 331)
For & [K), PE. [0. 1] + J0, 1) the CDF of the 4 element of the vector B. And we denote the corresponding density fx. The expected utility then writes:
E (us(b1, b2, ba)l 11 (Fs(b1) Fo((2)) 1 vfa(v)dy
b2
(bb(22) - Fb(b2) (v1 -b2)
1 pzz
+ + + v2) (F2(be) F2(61)) -
yfz(y)dd
b.s
+ [Fa(ba) - (bbba) ) (u1 + 222 - -2ba)
+ (vi v2 v3) F (ba)a - 3 yfi (2)
35

---

We can hence compute partial derivatives:
① E (u,(bi, b (wi - bi) fa(bi)
(84)
rb BND
E
(ug(bi, b2, bb]] = F2(b2) 1b((2)) + (02 b2) f2(b2)
(85)
Bb2 SDD
0
IE
Lua(bI, b2, b3]] = 2 F2(6s)) (ez b3) fb
(86)
bbg
BND
We can therefore write the partial derivative explicitly:
101y
if y E [0
① E [ug(b (2,,
5 900
(2, bs)l
if y 900
(87)
0b BND
if y E 6:3
21y
if E
[0, 900
5
E
[ug b2 bb)l
+
if y E
(88)
bbg BDD
if
88 and (87) that the maximum is attained for all b2, by E 1900 e such that b2 = by. Furthermore, there exist c E IR such that for all b2, by 300
Recall, that b B
b2 by. it should be clear form 5
5
8] if b2 + by the utility at least c(b2 by) sub-optimal.
Let O, for ls [o. [.Il we denote 1sth == ( (o0 + ke, 900 + (k+ + e). We will use these intervals to define local perturbations of the CDFs. Note that with these notation, 1 and 22k-1 are respectively the first and second half 1
For the purpose of the lower bound, we only need to introduce a perturbation of F2. We therefore define 2,e as follows:
F2(1) + (y - ke)
if E 12t
F (v)
F2(1) +e (y -ke)
if 1 12 otherwise
(89)
F2(1)
With the following density
fe(1) +1
i E 12k
(v)
f2(U) -1 if
(90)
f2(y)
otherwise
We therefore define D. P (10. (1).11"). distribution such that if (31. Bs) Dd then the corresponding CDFs 31, B2, B3 are Fi, P/..: Fg.
We have now defined what we need define the hard instance. It is defined by the following process:
Given T, set
Draw l uniformly at random in [o, +.]
For t in [T]:
The bidder picks bids 6f bb, by based on the past feedbacks Zz, Zt-1.
The adversaries bids are drawn :33 ~ Di
The bidder receives the utility ug (b) bb, bb) and the feedback 2: Z(,3, b()
36

---

Note that e depends on T, intuitively, it should behave as T 3. The exact dependency required is determined later in the proof.
Because in this instance, the only thing a bidder can learn is 2, or equivalently which dis- tribution D. it faces, we will discard in the analysis the part of the feedback which doesn't provide information about the second marginal distribution. Reducing to Zz == 2 bb) = (1 & b3 { E (by, b2 [ > b2)) (this is directly implied by Lemma 2p. To pro- vide a simpler analysis, it is convenient to work with a one dimesional feedback, notice that the previously described feedback equivalent (one can define bijection) with 2(33', bb) max (1 {3g E (b3, 62] 333 { 623), this is the formulation we use in the following proofs. We also only consider algorithms that, at all times t, bid bj = v1. This is without loss of generality, as not doing so would only add additional regret and provide additional useful feedback.
We also only consider deterministic algorithms, the lower bound then generalizes randomized algorithms by Yao's minimax principle.
Our final reduction is the following: consider in the following analysis only algorithms such that Eh by b/ = o(T2/3). This without loss of generality: since the optimal bids bž and bg are always equal and belong to It The expression of the derivatives (87 and (88) ensures that for all bids with by and by in the interval [5/ [5/900, 8 the algorithms incurs a regret which scales with b2 by. Furthermore, if either b2 or by is not in [5/900, z. the algorithms incur additional regret term of constant size. Therefore any algorithms such that we do not have T b/ by = ( incurs a regret which scales as ((T2/3) in this instance.
Some Notations: We denote p0 a probability measure over B when the CDFs are respectively Fi, F2, F3 and Tp probability measure over (3 conditionally on the value of l (ie when its distributed according to D.... The notation extends naturally to expectations E and E
Lemma 12. For all S [/T and any deterministic algorithm A. denoting Nr (i) the number of times algorithm A produces bid such that (b'y, bb] iI! # 0. we have
E' [Nr( - E. (i) S 10eT E
(91)
Averaging for < J.]. we get:
E. [1)
[ L E
[P (0)
+ 10e7
(92)
Litel
T
T
+ 10eT
(93)
Let us denote (i) the number of times algorithm A produces bid such that (b/. bb] n I + 0. and i is the smallest such index. We can recover for this one that E Ea NT(ii) = Notice that because we focus on algorithms such that ΣT by - bj = o(72/3), the difference (2//)) We continue the computation without this
Σ E [i) E" (Nr
additional term of size
72/3
as is clear the bound remains unchanged from this addition (it
would only add to term of order
22/3 in the right hand side of the inequality).
Rr 2
B [
Nr(1)
(94)
7e
[=1
T
T
> min:;
T
10eT
(95)
I
7c
7t
37

---

Where r; is the sub-optimality of not playing bids in interval i when it is optimal. Using 87 and
88
we obtain
6
2
12
Choosing 700
T/3 yields the desired lower bound of ! (T2/3)
C.2.1 Technical lemma
Lemma 12. For all - [3T=1/31 and any deterministic algorithm A, denoting NT (i) the number of times algorithm A produces bid such that (bgy, bb] ni! + 0, we have:
E'' (N) [Nr] 10eT EN
(1))
Proof. For convenience and to have shorter expression, we denote (bg, bb](-) = (6)())65()))
We want to upper bound the following quantity:
Ee [Nr 15 [Nr(1]] = Σ F (bbs by] (Z ... Zz- I!! + 0
(96)
ns (6)) bbg (Zi..., -1-1) n I + 0]
We will upper each term of the sum independently. The algorithm can be anything deterministic, therefore (bg. b6](.) can be any function, which is why we bound the previous quantity as follows
Pd [bb, [5] [Z,..,, Ze-1 nIt + 0 pO
[bbg bbl Zo-1) # #0]
(97)
pp (2mm.,)111) p0
(98)
$ V KI (TRi
(Pizzmi s)i PO
(Brmi 1))
(99)
KL (P2, P2,)
+ Σ
KI
Ppi 2,12.... 1:
Po 2/12 .)
(100)
j=2
Where Piz, 2.1) is the push-forward probability of (Zi,.., Zz-1).
Since we focus on deterministic algorithms, (Zi,,.., Zz-1) conditionally on Z1, ... Zj-1 is fixed. We can therefore write the following equation bound terms the square root of (T0).
p0 Iz Z Z,-1]
KL (F'Z, (P.,, 1i ;2,,,, 2 =
E
In
Fa [Z, = 0 Z1, Zz-1l
P I2 = 0 Z1, Zz-1]
(101)
p" Z, = u E1,.. 23-11
In
p. [2, =u Zi..., Zy-1l du
p² [Z, = u Z1 Z
0
(102)
p0 12, = Zi,.., Zy-1]
+ ln
pd 12 = 1 2 ... Zj
P [2 Z1, Zz
(103)
Note that this can be written as such because 2, takes values and 0 with positive probability, it can also take values in byg b9 and its distribution admits density because the distribution of 33 admits
38

---

density. We continue forward in our calculation, using the fact that the distribution of 32 and hence Zj between Pet and Ie only differs on Tz
po Iz =0 Zz, ..... 2
KL (22,,12 P2,, Z2 2/...7511) = E0
In
PO [2, =0 Zi.., ...... 2)-1]
is [2, 0 21, 2z
(104)
p [Z, = =u/ 21, .. 7
In
p0 [2, Zi..,, ..... Zz- 1 du
pt [Z, = u Z1, Z
k=
12
(105)
P0 1Z, Z .., 2--1
ln
p0 [Z, = 1 Z .., 2
IP' 123
Ei,.. 1
(106)
po 1Z, 0 Zn, ... Zn-1
E0
In
Fm [2] = 0 Z1..,,
P 12, = 0 1,,,, 2
(107)
10 1Z, = a ,,, 3
In
p" [²[ = u Zz, Zj-1] du
p² 12, = n Z Zz-1]
11
(108)
p0 12, = 21 Zj-1]
+ In
Pd 1=I = 1 Z Z5-1]
Ppd [2, Z1, .., z
(109)
IPD
12, = 0
Z1
2
E0
In
pD [2, p=I = 0 Z1,.., 2n-1]
(110)
P [2 0 2
Zz-1]
pu IZj 1 2
2j 1|
P0 [Zj = 1 3,,-, 23-1) { 12 n bg) * #0}
In
P [Z3
,,,,, Zz-1
(111)
pa 12, = u Z,,.. 2--1] 1
10 12 = -ul E1,.., dul L n 1b/, bg] + 0)
+
In
1:
D² 12 Z1,.,
Zz
(112)
Let us denote Y, (b²) is the function which has values when 3/ S b2 and value 0 when B > bg. And let us use the inequality between the KI. divergence and x² distance.
12D [Y, = 0] 1O [Y,(6))= =0]
KL 1P2,,22...2211111 2....Zz-1) S <EO
Im
P. [Y,(6)] = 0
TPO [V, =
Ps [Yg(W)) -1] 11 100 (Y)((()= =11) 1 ( n 1b 62) #0}
+ In
(Ja(M) - (2)( 2
(1) dul (1t n (bS, 6b] + #0]
(F8(x)- - -x)())² 2
max well Fb(()) (1 - -F((x)) + +602 Fd0 (r (1, #0)
< 2 (81 + p) (Té (1/s 1/) +
(113)
We can now use 100) and (133) to get:
Pi [1g, [6] (7,, 2--1 nI
+ 0
poo
[1g b5] (Z,, 7--1) # S 10 / E (N)
(114)
39

---

Reinjecting in 96 allows us to recover:
E' [Nr(1)) EE" [NT 107 1 E (i)
(115)
D Instance specific proofs
Here, we present proofs and results that are specific to certain instances the auction problem, such as A-separated distributions and the i.i.d. unit-demand adversary setting. These specialized analyses provide further insight into the behavior learning algorithms under specific structural assumptions.
We begin by providing the proof of Lemma 4 which we first restate for convenience.
Lemma 4. Learning discrininatory or uniform auction when the adversary' distribution is A 2K can be achieved with respectively regret of ((T2/33 and O(VT).
separated, with A
Proof. We first provide the proof of the lower bound in the discriminatory auction. We begin by providing the necessary tools for the reader to understand the reduction the case of A-separated distribution with A S 2K- Our first remark is the following: while the proof of Lemma makes use of an adversary distribution whose support is [0, 1]. one can easily provide another difficult instance for adversary bids on [0, } Indeed, consider, with the notations used in the proof, F(b) = max(1, F(26)), and valuation scaled down on [0, 5), and the lower bound holds.
2. Then the bidder faces problem identical to the original one,
1
All that is left to show for the lower bound to extend to A sepearted distribution is that there exists such instances that reduces to the above scaled down difficult instance.
With this mind, consider the multi-unit discriminatory auction, when the bids of the adversary such that 3 := (1, 2K ..... 1 K-2 b) where b follows the distribution corresponding to the scaled down first price auction mentioned above. Note that this constitutes A A-separated distribution for A < 2K Let us consider the case when the bidders value E B is such that V1 S }. It straightforward when writing the utility function that for any bidder such that Vı S 2. it is strategy dominant only emit bids smaller or equal to Therefore, from the bidder's perspective, this reduces to first-price auction problem, with opposing distribution F(b) and valuation vn. The lower bound of 2/33 Lemma therefore extends to this setting for the discriminatory auction.
We now move to providing an upper bound for the uniform price auction.
We begin by showing that if the opposing bids follow A separated distribution, then there exists a utility maximizing bid b' e B such that values are only 0 and/or 1. Let 'D be a A separated distribution. For convenience, let rewrite the utility:
u(b,
Σ d=1
1 (b. 34-411 bet1]
Σ
nl
3x-itt
1=1
(116)
K 1 [ik-1 bit1 2 3x-1t17
Σ Uj - b
1=1
Since D A separated distribution, given any b B, there is most one E [K] such that P(b: 2 8K-441 b(41) and/or P(3x-i bit BK-141) can be nonzero. Furthermore, notice
40

---

that given E [K], we always have
E
(be 8k-it1 > lit1
Σ
Us - 8i-
5=1
+ [3 bs+1 2 Bx-s+t}
Σ
bi+1
(117)
/=1
i Σ
S E
U/
BK BK-it1
The previous equation obtained by noticing that (3x-; > bi+1 2 (x-i+1} and {b. 2 3K-i+1 b are disjoint and the second indicator includes the condition b,+1 8K-
Therefore, by defining i* argmax;e(K] E
EE=r3 U5 -3k-et3- We ensure that for any b B,
we have E [u(b, 3)1 S Σj j=1 Uy 3x 3
Now, by definition of 4k- if b E such that Ix- S (bx+11, ber then [u(b,3)] Σ -- U/ 51--++1 which the maximum utility the learner can achieve. Notably, this means that one can always construct optimal bid b B that consists only of Os and 1s.
We further notice from the formula of (Fx)xe(K) in (??) that if D is A separated the empirical distribution described by (Fx (F))x((K] is also separated.
Let us now suppose that, in Algorithm 3 when there is a tie between several maximizers, the algorithm chooses, if possible, bids with values 0 or 1.
With this in mind and the fact that the estimates built for the algorithm (F&) necessarily correspond to a A separated distribution, it should be clear that, at any time t, the algorithm only plays bids composed of and 1. Because there are only K such bids, the bidder essentially plays K-armed bandit problem.
Furthermore, the concentration bounds developed in the proof of Theorem 4eensure with probability 1 2Ka
sup b
E (b. B) ūi((b) s 6//3/2
(118)
It
B-D
E 0, BK 8K-041]
And therefore. if we denote
A
=
min.e[K],i44* E
K Uy
3x- 3x- as soon as 6/3 A the bidder only plays the optimal arm.
The regret therefore scales Ö(VT) in instance dependent fashion (depending A)).
now move to providing the postponed proofs for the unit-demand symmetric case. We begin by proving our concentration result Lenttleemmma 5 Lemma S. Let 1, N, and let Xo [1]. E [k] i.i.d. samples from a distribution with cdf F. With probability 1 a
(z) - S Fx
(z) + aR
(8)
In(
Where e
and au is constant which only depends on k. k and N.
21
41

---

Proof. Let k. E [K]2, and t E [T] such that one has observed X ( X (k), the hh ordered
statistic t times. We can apply the DKW inequality from Massart, 1990 bound the distance from its empirical CDF to its actual CDFs denoted F(x) and P(a). This yields the following
in (2) 2
P
sup xE|0,1]
FF() (x) - F(o)(E)) V/
2 21-a
(119)
We denote
Using 7 one has that for F the CDF corresponding to P, P&(F)) F(x).
where Ps is the polynomial defined by 77. This polynomial is strictly increasing on (0, 1), we can therefore get the following inequalities with probability
a, Vx [0, 1]:
P (F() (2)) + +) s F(x) S P3- (P(z) (x) ++)
(120)
Using 7 once again allows to get with probability a, Vx [0, 1]:
Per (PF² (F())()) s)) & ((r)(1) < Per (P=² (x)
(121)
We can then obtain concentration inequality in the usual formulation, with probability az
Per (PE) (F())=))) Par)()) S Eo0,,*'
(122)
Where oR only depends on the upper bound of the derivatives of both Pe and PT on (0.1).
With this, we now have the necessary tools to prove the Theorem 5] Let us first restate the theorem Theorem When facing i.i.d. adversaries the uniform auction with bundit feedback, [Agorithm guarantees the regret is upper bounded by Ô (VT).
Proof. As noted in Lemma 7 it is known advance that bidding such that b, = v, is optimal. Since this is compatible with our Algorithm 5 we assume that amongst the maximizers of ūt the algorithm always chooses one such that b1 = 01- Let t E [T). recall that a') =: Ua.( [ and E [u,b, 3)] = U.. (ex(())))))))))>>> Notice that the observations formalized in Lemma ensure
B~DD
that for any x E [0, v1 at time t, there exists k such that (*)) 2 t/ K. We can therefore leverage Lemma 5 to obtain the following for l E [K] with probability a:
sup 0000.
Ff(x) [x) < E
(123)
In (2) 21/K
Where 7 max;, Ok. and c¹
Note that we can ensure the bound is true across all ls E [K] with probability 1- Ka
Reinjecting directly and using the formula from
15 one gets the following with probability - Ka
sup
ū (b)
E BND
(b,
Bi]
s $3K2d
(124)
b =01
In
Where 7 = maxj, 0,, and
21/K
Using the optimality of be with respect to wf (b). we get that with probability - Ka:
E
[u(bb,,3)
[u(b", B)] 6K-
(125)
AND
BND
Summing over & E [7' and taking A yields the desired regret bound.
We finally provide the reduction necessary to obtain the lower bound of Lemma which we restate first:
42

---

When facing i.i.d. adversaries in the uniform auction with bandit feedback, any learning algorithm must incur at least regret of (2 ())T)).
Lemma 6.
Proof. We focus showing that can build reduction one of the hard instances used in the proof of the full-information feedback lower bound in Brânzei et al., 2023 We focus on the 2 item auction.
Let p 3.2 if we sample two independant binomial random variable X,, X2 with probability p
multiply them by I and denote that / := ( 1,,, m. X2)) then with probability
5. 3 = (0,0), 0), with probability 5. 3 = (g. 0) and with probability 5. f = 3)) First notice that having with probability 9. , (0, 0) does not change the best strategy (since the utility function w(:, (0, 0)) is constant). Then notice that the probability of 3 ( 0) and β = ( have derivatives in p of opposing signs which ensures
create perturbations of size 5 in opposing direction by small changes in These are sufficient to ensure one can reproduce the same proofs as in Brânzei et al., 2023 Theorem 4 and lower bound the regret this setting by ((vT).
43


Reviews:
[{"review_id": "TD5CoSzfaM", "reviewer": "Reviewer_Wq2f", "summary": "The paper compares two common multi-unit auction formats—uniform-price and discriminatory auctions—from the perspective of a bidder using online learning to optimize strategies against stochastic adversaries. It analyzes regret bounds under full-information and bandit feedback settings, highlighting both worst-case and instance-dependent learning difficulties.", "questions": "NA", "limitations": "NA", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n1. This paper provides concrete and thorough theoretical proof, showing the regret bounds for uniform and discriminatory multi-unit auctions with various formats.\n2. The paper is well-written and properly organized.\n3. It is interesting to consider the so-called \"instance-independent\" regret, providing insights how the algorithms can be improved beyond worse-case.\n\nWeaknesses:\n1. The comparison results in some sense are not surprising.\n2. The assumption that the bids of the adversary are drown from fixed distribution is kind of strong.", "was_revised": true, "final_justification": "I shall keep my score.", "rebuttal": "Thank you for the review. \n\nIn the absence of questions, we will address the two weaknesses mentioned in the review. \n\n1. We believe our results are non-trivial and several aspects are surprising. For instance, the degeneracy of achievable regret rates in the uniform price auction, depending on whether the learner has unit, two-unit, or more than two-unit values (cf Table 1) is, in our opinion, rather surprising. We also consider it surprising that, under bandit feedback, when opposing bids are order statistics, uniform price and discriminatory auction exhibit regret rates which scale differently with $T$ (respectively $\\Theta \\left ( \\sqrt{T} \\right)$ and  $\\Theta \\left ( T^{2/3} \\right)$). Nevertheless, we understand your comment since some results intuitively make sense, such as the fact that regret in both auction formats scales identically under full-information (as $\\theta \\left ( K \\sqrt{T} \\right )$).\n\n2. It is true that for practical applications, such an assumption might be considered strong. On the other hand, considering that opposing bids are fully adversarial is also not realistic. We believe a realistic middle ground is to consider a contextual version of the problem: opposing bids would be i.i.d. conditionally on a context, which the bidder would observe before participating in each auction. In this work, to keep the modeling aspect straightforward, we do not consider that contextual aspect. \n\nWe also want to point out the fact that the lower bounds derived in the paper are also valid for adversarial opposing bids. In that sense, only the upper bounds results in the paper are \"limited\" in their scope to stochastic opposing bids.  \n\nFurthermore, technically, this assumption has two main upsides. First, it makes the analysis of the algorithms more tractable as we can use a deterministic algorithm. \nSecond, it enables us to derive instance-dependent bounds; these types of bounds, which characterize regret beyond worst-case, are not classically obtained for adversarial settings in the bandit literature [1]. \n\n\n[1] Lattimore, T.,  Szepesvári, C. (2020). Bandit algorithms. Cambridge University Press."}, {"review_id": "YFvKZyuV9B", "reviewer": "Reviewer_4GPy", "summary": "The authors study multi-unit uniform price and discriminatory price auctions from an online learning perspective. At each time step $t$, the learner participates in either a uniform (respectively, discriminatory) auction with the goal of winning up to $K$ identical items by submitting a vector of bids $(b_1^t, …, b_K^t)$. It is assumed that the learner’s utility is additive and that the utility associated with winning the $k$-th item for any $k \\in [K]$ is known and fixed over time.\nThe learner’s bids compete with the top $K$ bids submitted by other participants. The learner wins exactly $k$ items if precisely $k$ of their bids are among the $K$ highest overall. The payment scheme is as follows: in uniform price auctions, the learner pays $k \\cdot p$, where $p$ is the value of the first rejected bid; in discriminatory price auctions, the learner pays the sum of their $k$ winning bids.\nThe feedback model can be either full-information—where the learner observes all the top $K$ competing bids—or bandit feedback, where the learner only observes the number of items won and the corresponding price. The competing bids are modeled as independent and identically distributed (i.i.d.) random variables.\nThe learner’s objective is to minimize regret with respect to a benchmark bidder who knows the distribution of the competing bids and bids optimally to maximize expected reward.\nAs far as I can tell (despite several typos in the paper that make this somewhat unclear) these appear to be the authors’ main contributions:\n1.\tFull-feedback: The authors claim to improve the previously known upper bound for uniform price auctions by a $\\sqrt{K}$  factor. However, I believe there may be a typo here. In the related work section, they state that Branzei et al. achieve a regret rate of $O(K \\sqrt{T})$, which is exactly the rate the authors obtain in this paper. \nIt is unclear whether the authors provide any additional improvements for the full-feedback setting. They state: \"We show that both auction formats admit tight worst-case regret rates of $\\tilde{O}(K\\sqrt{T}))$ under the full-information setting (improving the best known rates for uniform price auctions by a factor of $\\sqrt{K}$).\" This wording suggests they also contribute something for discriminatory price auctions, but I did not manage to find any explicit contribution in this sense, leaving the reader uncertain about what has actually been improved.\n2.\tBandit Feedback – Upper and Lower Bounds: For the bandit feedback setting, the authors claim: \"Our analysis also yields regret rates of $\\tilde{O}(K^{5/3} T^{2/3})$ for uniform price auctions, and we show a matching lower bound.\"\nHowever, this seems problematic. Based on the context, this result should only hold in the stochastic i.i.d. setting. Furthermore, the authors reference Potfer et al., who achieve a regret rate of $\\tilde{O}(K^{4/3} T^{2/3})$, which seems actually better than the upper bound presented in this paper. If Potfer et al.'s result is correct, it would contradict the claim that the authors' lower bound is tight. In fact, I could only find a $\\Omega(T^{2/3})$ lower bound in the paper, not the $\\Omega(K^{5/3} T^{2/3})$ bound they seem to suggest with the phrasing above. Overall, this part of the contribution is unclear.\n3.\tInstance-Dependent Rates: The authors also claim to provide improved instance-dependent regret rates for the uniform price auction, specifically for one-unit and two-unit demand cases, along with matching lower bounds in the time horizon.", "questions": "Could you please clarify what are the contributions relative to the literature answering to the point raised in the summary?\nAlso, the summary table 1 should report also the dependences on K, not just on T.\nFinally, a \"techniques and challenges\" section would be beneficial for the reader to understand better what are the non-standard technical contributions with respect to the existing literature.\n\nTypo: line 123, diplayed formula: extra ]\n\nI am willing to reconsider my score depending on the authors response.", "limitations": "Yes", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 1, "significance": 3, "originality": 2, "strengths_and_weaknesses": "I believe that understanding the regret rates in stochastic i.i.d. uniform and discriminatory is an interesting contribution.\nHowever, as already pointed out in the summary above, the related work and contribution section left me perplexed about how to contextualize the contributions provided by this paper.", "was_revised": true, "final_justification": "I still believe that the paper is slightly below the acceptance threshold: in the light of the further discussion about the related work provided by the authors in the rebuttal, I believe that the actual contributions are in fact incremental (e.g., their proposed algorithm provides worst-guarantees wrt existing algorithms and only improves in distribution-dependent guarantees, and the lower bounds are not tight in $k$).", "rebuttal": "Thank you for the review.\n\nWe take note that the exposition of the literature and of the contribution could be clearer and will improve the issues you raised.\nWe first provide clarification regarding the issue raised in the summary and then answer the remaining questions.\n\n\n\n## Typo in the literature review\nThere is indeed a typo here. In the uniform price auction, under full-information feedback, Branzei et al, provided an upper bound which grows as $\\tilde{\\mathcal{O}} \\left ( K^{3/2} \\sqrt{T} \\right )$, leaving a gap with the lower bound of $\\Omega \\left ( K \\sqrt{T} \\right )$. In this work, we provide an algorithm that guarantees a regret upper bounded by $\\tilde{\\mathcal{O}} \\left ( K \\sqrt{T} \\right )$. In light of the previously mentioned lower bound, this algorithm's regret upper bound is optimal, fully characterizing the regret rates of this problem as $\\Theta \\left ( K \\sqrt{T} \\right )  $. We apologize for this particularly confusing typo. \n\n##  Contribution bandit feedback\n - Under bandit feedback, for the uniform price auction, the main contribution of our work is the lower bound of order $\\Omega \\left (T^{2/3} \\right )$ provided by Theorem 3. In the literature, the best lower bound available for the uniform price auction was the one in the full-information setting of $\\Omega \\left (K \\sqrt{T} \\right )$ by Branzei et al. This lower bound matches the rates in $T$ of the upper bounds provided by Potfer et al., therefore fully characterizing how regret scales in $T$ in this setting. \nWe will ensure to better highlight that this lower bound is tight in $T$, not in $K$.\n- As you mentioned, the worst-case bound we obtained for Algorithm 3 is worse by a factor $K^{1/3}$ in comparison to Potfer et al.. The main novelty of this algorithm is that it is able to adapt, guaranteeing $\\tilde{\\mathcal{O}} \\left ( K \\sqrt{T} \\right )$ in the bandit setting when facing \"easy\" instances. The worst-case guarantees of $\\tilde{\\mathcal{O}} \\left ( K^{5/3} T^{2/3} \\right )$ ensure that, while able to leverage favorable instances, this algorithm still guarantees reasonable regret in other instances.  \n\n##  Techniques and challenges\nWe understand the need to provide more information on how our work differs from previous ones (Potfer et al., Branzei et al., Galgana et al.) in the techniques we used for algorithm design and analysis. We will include a \"techniques and challenges\" subsection. \nWe will emphasize the fact that since we focus on stochastic opposing bids, our algorithms are fundamentally different from the ones used in previous work. Namely, while the previous approaches relied on discretizing the bid space $B$ (defined on line 109) and using randomized bandit algorithms, we neither need to discretize nor use randomized algorithms. Our algorithms mainly leverage statistical CDF estimation techniques. A key advantage of this approach is that it allows for a more straightforward analysis. \n\n\n\n\n##  Table 1\n We did not specify the dependence in $K$ in Table 1 to improve readability. We were able to obtain upper and lower bounds on the regret that match in their dependence on the time horizon $T$. Yet, the dependence on the number of items, $K$, is not tight. To represent these results accurately, we would need to present upper and lower bounds separately, using $\\tilde{\\mathcal{O}}$ and $\\Omega$ instead of $\\Theta$. \nWe emphasized the differences in scaling with respect to $T$, as we believe this is the most interesting aspect of the contribution.\nTo ensure that the notation is clear and represents the bounds fairly, we propose to mention that $\\tilde{\\Theta}$ hides factors that depend on $K$. \nWould these improvements be satisfying?\n\n\n[1] Potfer, M., Baudry, D., Richard, H., Perchet, V., & Wan, C. (2024). Improved learning rates in multi-unit uniform price auctions. Advances in Neural Information Processing Systems, 37, 130237-130264.\n\n[2] Brânzei, S., Derakhshan, M., Golrezaei, N., & Han, Y. (2023). Learning and collusion in multi-unit auctions. Advances in Neural Information Processing Systems, 36, 22191-22225.\n\n[3] Galgana, R., & Golrezaei, N. (2025). Learning in repeated multiunit pay-as-bid auctions. Manufacturing & Service Operations Management, 27(1), 200-229."}, {"review_id": "or78FaToPI", "reviewer": "Reviewer_AAkx", "summary": "The paper studies multi-unit auctions (MUAs), where several identical items are sold in each round. It focuses on two common formats: uniform-price and discriminatory-price auctions. While both allocate items to the highest bidders, they differ in how winning bidders are charged. The central question explored is how a single bidder, participating in repeated instances of such auctions, can learn to optimize their strategy when the aggregated bids of their opponents follow a known probability distribution.\n\nThe analysis is framed through the lens of regret minimization, evaluating the bidder’s ability to learn over time. Two feedback settings are considered: full information and bandit feedback. In the full information setting, both auction types pose similar learning challenges. However, under bandit feedback, the paper shows that uniform-price auctions allow for a smaller instance-dependent regret than discriminatory auctions, making them more favorable for learning in practice. While most of the novel theoretical results concern uniform-price auctions, the key contribution of the paper lies in the comparative perspective on the learning complexity in the two auction formats.", "questions": "Can you comment on the dependence of the regret on specific parameters of the instance for the instance-dependent bound ?", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 4, "strengths_and_weaknesses": "**Strengths :** The motivation is clear and straightforward. The topic itself is timely and interesting, addressing a well-established yet practically significant problem in auction theory. The paper is well-written, with a coherent structure and precise explanations that guide the reader through many different instances of the problem.. The results presented are thorough and cover a wide range of scenarios. Moreover, the contributions are not only substantial in number but also of high quality.\n\n**Weaknesses :** While the paper is strong, there are a few weaknesses that could be improved. Some parts of the general setting are not entirely clear. For example, it is not stated whether the bids $\\beta_1^t, \\ldots, \\beta_n^t$ are ordered in increasing value, which can affect the interpretation. The issue of non-truthfulness is also not discussed in depth. This is important because, in single-unit auctions, uniform-price formats are known to be truthful. The special case where K=1 is not clearly separated from the general case, which makes the analysis feel less complete. For the instance-dependent regret results, it would have been helpful to study how the regret depends on specific parameters of the instance, to better understand which situations are easier or harder. Finally, there are no experiments included in the paper, but this is acceptable given the theoretical nature of the contributions.", "was_revised": true, "final_justification": "After having read responses to my review and others', I still have a positive opinion of the contributions, though maybe some light edits/clarifications would be beneficial to the paper.", "rebuttal": "Thank you for the review. \n\n## Question\nWe characterize how the regret scales differently according to the number of positive valuations of the items (unit demand, two-unit demand, and more ). This is shown in Table 1 under the \"worst case\" column.\nWhile we did investigate further how specific parameters of the instance change the instance-dependent bound, our analysis only yielded conditions on the expected utility function. We were not able to derive explicit conditions on parameters of the instance (distribution, valuations, etc.).  \n\n## Non-truthfullness\nThe two auction formats we consider are non-truthful. It is not clear to us how we could discuss further the non-truthful aspect of these auction formats, as the paper looks into how to learn online the best bids, which wouldn't be needed if the auction were truthful.\nWe nevertheless included Lemma 7 in the Appendices, which describes how the uniform price auction is truthful for the first value/bid. We will consider making this aspect clearer in the main paper.\n\n## Single unit auction\n Regarding the K=1 special case (for which our comparison reduces to a first-price versus second-price auction), it is indeed not addressed on its own. Nevertheless, it is a special case of the \\textit{unit demand} setting for which some results are mentioned (lines 285-288). Indeed, if K=1, then the bidder only has $v_1>0$ \n\n## Opposing bids\n You are right, $\\beta^t_1, ..., \\beta^t_K$ are indeed in non-increasing order. This is expressed in the paper by the fact that they belong to $B$, defined on lines 107-109 as the subset of $[0,1]^K$ composed of the non-increasing sequences. We note that this is somewhat implicit and will try to highlight it more explicitly."}, {"review_id": "yBYXAmDKcc", "reviewer": "Reviewer_mhSS", "summary": "The authors study a \"learning to bid\" problem in a repeated auction of several identical units of an indivisible item. They study two possible welfare-maximizing auctions that differ in their payment rules: uniform price and discriminatory price. This problem, and the derivation of regret rates for learning to bid, has been studied recently by Branzei et al. and Galgana and Golrezaei. The key conceptual contribution of the present work is to consider a stochastic model of utilities, where the bidder of interest evaluates her utilities in a Bayesian fashion over the draw of the other competing bids. Regret is also evaluated with respect to the stochasticity in the other bids. This allows the authors to transfer over many of the previous regret rates. They also show the existence of settings where learning to bid in uniform price auctions is easier than in discriminatory price auctions.", "questions": "Line 15: Perhaps that claim would have stronger support if the authors included a reference that is more recent than 2009.\n\nLines 61-71: regret rates are presented with dependence on K, but K has not once been defined before that.\n\nLine 99: I think you should explicitly state immediately that the K items are K identical copies of the same indivisible item. \n\nLine 104: If the \\\\(v_{\\ell}\\\\) are marginal valuations, is there an assumption that \\\\(v_1\\ge v_2\\ge\\cdots\\ge v_K\\\\)? In Line 110, are the beta's also drawn from a distribution such that the beta's have decreasing marginal utilities?\n\nLine 119: I believe that the decreasing marginal returns assumption above is required for this to be the correct allocation function that implements the efficient/welfare-maximizing allocation. The authors should make that clear. Also, it might help to (i) use the words \"efficient\" or \"welfare-maximizing\" instead of \"standard\" (line 118), and (ii) include a one line explanation why the allocation function has that particular form. \n\nLines 124-126: \"(the bid that won its emitter this item)\" I don't understand what this means. Based on eqn (3), the discriminatory price auction sets the price of the kth item to b_k (the bidder's marginal value for the kth unit), regardless of who wins. Is that correct? I guess the b_k's for k >= x(b, beta) don't impact the bidder's utility.\n\nRemark 1: is this well-known? If so, include a citation/reference. Otherwise a few lines of intuition would be good. I don't think the authors should include precise claims without proof.\n\nSection 5: I was a bit confused as to how this is \"beyond worst-case\" as opposed to the previous section. My understanding is that this section is the same bandit-feedback setting as Section 4, and the authors are just proposing and analyzing a better algorithm (basically doing a more refined CDF estimation). (OK, I see now that the main application is for instance-dependent bounds. It would help if you included a formal discussion of the benefits instance-dependent bounds provide. I know that it's a standard thing in this literature, but putting things into context would help.)\n\nDid Branzei et al. and Galgana+Golrezaei study separations in learning complexity between the two auction formats?", "limitations": "Yes.", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths\n---\n\nMulti-unit auctions are prevalent in the real world, and learning to bid in these repeated auctions is an important problem that has received study in recent years. The authors contribute to that literature with a model of stochastic adversaries, showing that many of the regret bounds transfer over to their setting, and derive improved results in some cases.\n\nThe standalone improvement (Lemma 3) to the regret lower bound of Galgana+Golrezaei is nice, and the setting showing that learning to bid in uniform price auctions is strictly easier (O(T^{1/2}) vs. Omega(T^{2/3})) than in discriminatory price auctions, is fairly interesting.\n\nWeaknesses\n---\n\nI found it difficult to assess the contribution over the prior works of Branzei et al. and Galgana and Golrezaei. The authors should improve the presentation to emphasize the main differences---both conceptual and technical. From what I could gather, the model is identical to those two papers, and the only difference is in how the other competing bidders are treated. In the present work, the competing bidders are treated as stochastic, and the main bidder's objective is to maximize her expected utility over the draw of the competing bids. The main techniques appeal to standard CDF estimation concentration bounds. Here, some differentiation over the techniques from prior work would help the reader substantially. Also, as  I mention below in the comments section, some further exposition clarifying the purpose of instance-dependent guarantees (and what exactly they mean mathematically) would be helpful.\n\nThe proof sketch that involves multiclass classification/Natarajan dimension sounds quite interesting to me and I would have liked to see a slightly more-expanded intuitive explanation in the main body. Where/why does multiclass classification come into the picture?", "was_revised": true, "final_justification": "I will maintain my score as borderline as I am not entirely able to see a sufficient conceptual advancement over prior works--the main contribution appears to be a modified setting that allows the two formats to be studied in a unified sense.", "rebuttal": "Thank you for the review. \n\n## Comparison with prior work\nWe begin by clarifying how our work differs from previous ones (Potfer et al., Branzei et al. and Galgana et al.).\n\n### Comparing auction formats\n All these previous works focused primarily on developing learning algorithms for one auction format at a time and studied the case of adversarial opposing bids. This work studies and compares learning in both the auction formats and focuses on stochastic opposing bids. \nGalgana et al. provide some numerical experiments comparing both formats in how quickly the bids converge and regarding the equilibrium achieved, in the appendix without theoretical analysis. \n\n### Technical differences\n We will make sure to better highlight the technical differences with prior work. Since we focus on stochastic bids, our algorithms are fundamentally different in the techniques they leverage. While other work relied on discretizing the bidding space $B$ (defined in line 109)  and applying a randomized algorithm, our algorithm works directly on $B$ and does not need randomization. As you mentioned, we mainly rely on statistical CDF estimation techniques. Besides the fact that this approach is technically different, it allows for a simpler and more tractable analysis, which is the basis allowing us to compare both auction formats under a common framework. \n\n\n\n## Natarajan dimensions intuition\nRegarding the Natarajan/multiclass classification, we believe a good intuition for its usefulness in our special case is the following: in multiclass classification, given a context, you want to evaluate the probabilities of the sample belonging to each available class; because the classes are mutually exclusive, the probabilities must sum to one. Furthermore, when observing the true class of one sample, the indicator function corresponding to the true class takes the value 1 and the others take the value 0. \nIn our problem, a very similar structure appears when, given a bid profile $\\mathbf{b}$, we make estimates of the probabilities of obtaining $1,2, ... $ or $K$ items. This is similar to the multiclass setting in the sense that both probabilities and indicator functions of the events must also sum up to 1 here. \nThis is the property that we mention as \"strong negative correlation\" on line 174. \n\n\n## Line-by-line comments\n\n\n- Line 15: \n You are right, adding a more recent reference will strengthen the argument. We will add the following reference :\nKhezr, Peyman, and Anne Cumpston. \"A review of multiunit auctions with homogeneous goods.\" Journal of Economic Surveys 36.4 (2022): 1225-1247\n\n- Line 61-71:\n This can indeed be unclear; we will ensure to mention $K$ is the number of items available at auction before using the notation. \n\n- Line 99:\n We will note right away that items are indivisible and identical to ensure the setting is clear. \n\n- Line 104:\n The $(\\beta_k)_{k\\in [K]}$ are indeed non-increasing (they belong to $B$, which is defined on line 109 as the non-increasing sequences of $[0,1]^K$). It is indeed also common to assume the marginal valuations $v_1,...,v_K$ are non-increasing. This question was also raised by another reviewer, we will make this more explicit in the final version. \n\n\n\n- Line 119:\nWe used the term \"standard\" instead of \"efficient\" or \"welfare maximizing\" as these two types of auctions have been studied and shown to be inefficient by De Keijzer, Bart, et al. and they are called \"standard auction\" in this work (cf [1] end of this response).\n We nevertheless acknowledge that the term \"standard\" might not be the most transparent and will prefer a descriptive approach explaining the rationale behind the allocation, highlighting the fact that it would be optimal if bidders were to bid truthfully (bidding $b_i=v_i$).\n\n\n\n\n- Line 124-126:\nYour understanding is mostly correct. In the discriminatory auction, the price of the $k^{th}$ item \\textit{allocated to the bidder} is set as $b_k$. Be aware that the bid $b_k$ is not necessarily the bidder's marginal valuation $v_k$. Since these auction formats are non-truthful, it is not optimal to bid $b_i=v_i$.  \nYou are correct in your understanding that the $b_k$ for $k > x(\\mathbf{b},\\beta)$ do not change the bidder utility. \n\n\n## Remark 1\n We understand the need for a more detailed argument. As it is not the main focus of the paper, and to adhere to space constraints, we did not provide too much detail.\nThe main arguments to show the complexity of the maximization are the following : \n- $\\hat{u}^t (\\mathbf{b})$ is written as a function of $\\mathbf{b}$ and $\\hat{F}_k^t$ (equations (13) and (14)) and it is separable into functions of neighbouring pairs of components of $\\mathbf{b}$. \n- Each of these functions is piecewise linear with pieces joining at the past observed $\\beta_k^t$. \n\nGiven these two points, one can prove the complexity bounds by using Theorem 1 in Branzei et al., which shows that the maximization problem is equivalent to a shortest path problem in a Directed Acyclic Graph. \n\n\n\n## Section 5 \n This section indeed focuses on Bandit feedback. The main point of this section is the following: in general, we cannot say one auction or the other is easier to learn; yet if we restrict the possible distributions (or the valuation of the bidder), then some results showing that both auctions are not always equivalent can be obtained. This section focuses on showcasing some of these cases and providing the corresponding analysis.\n\n## Instance Dependent bounds\nThe strength of instance-dependent bounds is that they represent how the regret can be lower for certain instances. In short, they allow us to characterize what parameters make the learning problem easier or harder and how much our algorithms can leverage them. In our case, that can be having only unit-demand (or two-unit demand) or having an opposing bids distribution that is well-behaved. It is the focus of section 5 to understand what these parameters are for our auction settings and how they might differ depending on the auction format. \nWe will make sure to more clearly explain why it is beyond worst case and highlight the interest of these bounds in the paper. \n\n\n\n\n\n[1] De Keijzer, Bart, et al. \"Inefficiency of standard multi-unit auctions.\" European Symposium on Algorithms. Berlin, Heidelberg: Springer Berlin Heidelberg, 2013.\n\n[2] Potfer, M., Baudry, D., Richard, H., Perchet, V., & Wan, C. (2024). Improved learning rates in multi-unit uniform price auctions. Advances in Neural Information Processing Systems, 37, 130237-130264.\n\n[3] Brânzei, S., Derakhshan, M., Golrezaei, N., & Han, Y. (2023). Learning and collusion in multi-unit auctions. Advances in Neural Information Processing Systems, 36, 22191-22225.\n\n[4] Galgana, R., & Golrezaei, N. (2025). Learning in repeated multiunit pay-as-bid auctions. Manufacturing & Service Operations Management, 27(1), 200-229."}]

Author rebuttal:

Meta-review: The paper provides a theoretical comparison of uniform-price and discriminatory multi-unit auctions, a timely and well-motivated topic. Positive aspects included the thoroughness of the analysis and the novelty of considering instance-dependent regret. There was one major issue, raised by multiple reviewers, about the lack of clarity regarding the paper's novel contributions compared to a significant body of existing work. The authors' rebuttal did address this to a reasonable extent, and I tend to discount the concerns of the some of the reviewers who did not engage further on this topic. I'm recommending the paper as an accept, but I strongly encourage the authors to carefully incorporate the feedback about clarifying the relationship to Branzei et al, Galgana et al, etc.
Decision: Accept (poster)