Improved learning rates in multi-unit uniform price auctions
Authors: Marius Potfer
Dorian Baudry
Hugo Richard
Vianney Perchet
Cheng Wan
Venue: NeurIPS 2024 poster (2024)
Keywords: Online Learning
Auctions
Bandits
Primary area: bandits
TL;DR: We improve known regret rates in repeated uniform multi-unit auctions under bandit feedback, and introduce a novel partial feedback specific to the auctions.

Abstract: Motivated by the strategic participation of electricity producers in electricity day-ahead market, we study the problem of online learning in repeated multi-unit uniform price auctions focusing on the adversarial opposing bid setting. The main contribution of this paper is the introduction of a new modeling of the bid space. Indeed, we prove that a learning algorithm leveraging the structure of this problem achieves a regret of $\tilde{O}(K^{4/3}T^{2/3})$ under bandit feedback, improving over the bound of $\tilde{O}(K^{7/4}T^{3/4})$ previously obtained in the literature. This improved regret rate is tight up to logarithmic terms. %by deducing a lower bound of $\Omega (T^{2/3})$ from the dynamic pricing literature, proving the optimality in $T$ of our algorithm up to log factors. 
Inspired by electricity reserve markets, we further introduce a different feedback model under which all winning bids are revealed. This feedback interpolates between the full-information and bandit scenarios depending on the auctions' results. We prove that, under this feedback, the algorithm that we propose achieves regret $\tilde{O}(K^{5/2}\sqrt{T})$.

Improved learning rates in multi-unit uniform price auctions
Marius Potfer
1,2
Dorian Baudry²
Hugo Richard'
Vianney Perchet
Cheng Wan
1 Joint team Fairplay, ENSAE, and Criteo AI LAB
2 EDF R&D
3 Department of Statisties, University of Oxford
Abstract
Motivated by the strategic participation of electricity producers in electricity day- ahead market, we study the problem of online learning in repeated multi-unit uni- form price auctions focusing on the adversarial opposing bid setting. The main contribution of this paper is the introduction of new modeling of the bid space. Indeed, we prove that a learning algorithm leveraging the structure of this prob- lem achieves a regret of ( under bandit feedback, improving over the bound O(KT/$13/4) previously obtained in the literature. This improved re- gret rate is tight up to logarithmic terms. Inspired by electricity reserve markets, we further introduce a different feedback model under which all winning bids are revealed. This feedback interpolates between the full-information and bandit sce- narios depending on the auctions' results. We prove that, under this feedback, the algorithm that we propose achieves regret 5/25/2
1 Introduction
The short-term electricity market, based on a wholesale market, is organized as auction that de- termines the quantity each electricity producer needs to produce and the price at which electricity sold. They participate, in this market by submitting prices for each kilowatt-hour they can produce. They have the opportunity to participate strategically, submitting prices that can deviate from their actual production cost. While several regulatory and practical constraints apply, this market is essen- tially a multi-unit auction of identical items (Willems & Yu, 2022). These auctions are extensively studied and utilized for resource allocation. Several pricing rules can be applied, the most common being discriminatory pricing, uniform pricing (Ausubel et al., 2014), and Vickrey-Clarke Clarr---lark--rrvvess Groves (VCG) auctions (Sessa al.. (017). Although the VCG auction is known for its truthful bidding property, is seldom implemented due to its complexity. Instead, uniform or discriminatory pricing often preferred, particularly in treasury auctions (Khezr & Cumpston, 2022) and their procure- ment variations in electricity reserve markets (Viehmann et al., 2021
The wholesale electricity market is held every day and, structurally, the electricity producers who participate in the mechanism remain same for multiple years. This represents an opportunity to study how producers be strategic in the way they adapt to other's bidding strategies. We there- fore focus on the problem of online bidding in a repeated multi-unit auction. This setting allows us to model how agent participating multiple times to auction with the same other partici- pants can leverage the information he has obtained during past auctions. This family of settings, of which review is available in (Nedelec al., (022), was first investigated for learning from the point of view of the auctioneer and was then applied to bidders learning how to bid optimally.
potiie fr
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Auction rules A decision-make maker (i.e., the bidder) repeatedly bids in uniform pricing K-umit auction. The single-shot version of the auction, from the perspective of any participant whose Online learning in multi-unit auctions with uniform pricing (every object is sold at the same price independently of the winner) is studied in (Branzei et al.. 2024) while the case of discriminatory pricing is studied in Galgana and Golrezaei, 2023 When the bids of all bidders are revealed after each auction (full-information),, known regret rates for uniform and discriminatory pricing are the same order (vT) (Branzei al., 2024 Galgana & Golrezaei, 2023) where the time horizon. When bidders only observe the number of items they win and the price (bandit feedback) the regret upper bounds given in Galgana and Golrezaei, 2023 and Branzei et al., 2024 are of order ((T2/3) (for discriminatory pricing) and (TT3/4 (for uniform pricing) suggesting that bidding multi-unit auctions with uniform pricing is strictly harder than with discriminatory pricing. Our study shows that this is not the case as we present an algorithm achieving regret ((T2/3) with uniform pricing therefore closing the gap between the two settings.
value obtaining a kth -item is denoted by Vi E [0, 1], proceeds as follows.
1. Each participant submits bid profile (br,)) E B, where
B = {(bx (E(K)) such that 1 2 b1 2 b2 2 .... 2 bx 2 20}
We call B the action space and we denote by b-; the bids from other participants.
2. The price per item p (b;, b-1) is set either
the th highest bid (Last Accepted Bid (LABB pricing rule),
the (K + 1)th highest bid (First Rejected Bid (FRB) pricing rule).
3. The participant receives the items they won and pays p (b., b-c) for each item. Since items are identical, we call allocation E [K] == (1,2, ..., K) the number of items participant receives, formally defined as follows:
11 E [K] s.t. bi, 2 p (b,, b-:) for the LAB rule
34 (b,, b-:)
(1)
[ik E [K] s.t. by,k > p (b, b-:)
| for the FRB rule
The focus is to design efficient learning algorithms for the decision-maker i.e. one specific par- ticipant i; we can therefore aggregate bids from other participants as the bid of a single adversary G b-; and omit the index i of the learner denoting b == b, This setup gives rise the quasi-
linear utility u(b,3) 3) = Σi (b.,9) [ur p(b. 3)].
In the remainder of this paper, we adopt the LAB pricing rule. The techniques and theoretical proofs can be adapted from one setup to the other with little change. In the absence of specific mention of pricing rule, our results can be applied to both auction types.
Repeated setting As mentioned above, this auction is not played just once, but repeated many times (say, each day). We shall then denote a time horizon T, and assume a different auction is run at each time step t [T' and the objective of the bidder is to maximize their cumulative utility. Quite naturally, the bidder should adjust their bids to the adversary's 's behavior, learned from the outcomes of the previous iterations. On the other hand, we assume that the bidder does not need to learn their own values, i.., the valuations (Vx (U*)KE[K] are known to the bidder and do not change over time.
We denote by (b') (b") and (B8), respectively the sequences of bids of the player and of the adversary, and by p² : p (b', and x' := x (b',3") the price and allocation time The utility of the bidder after the auction E [T] is then defined as u(b', Σn' (ur 10--pt p²). As standard in online learning, we evaluate the performance of a learning (bidding) strategy through its regret, defined as follows
T
RT sup B
ub. 3")
E Σ (b ,4)
where the expectation is taken over the randomness of the algorithm generating the bids b'. Maxi- mizing the utility of the bidder is equivalent to minimizing the regret.

---

Feedback The bidders can improve their strategy using the information they receive after each iteration of the auction. The type of feedback they receive represents their knowledge about the bids of the adversary. In the literature, two common types of feedback are considered (Cesa-Bianchi et al., 2023).
1. the bandit feedback where the bidder's allocation Ty is revealed and the price pt is only revealed if 24 0, and
2. the full information feedhack where all the bids emitted by all participants are revealed.
Inspired by the terms of commodity electricity markets in several European countries including Germany and France, similarly to Karaca et al., 22020, we shall introduce and study third partial feedback specific to multi-unit auctions,
3. the all-winner feedback: the allocation, the price, and all the winning bids are revealed to the bidder.
Remark 1. With a uniform discretization of the bidding space B, learning to bid in multi-unit uniform auctions can be recast special instance of combinatorial bandit problem. In the latter, the decision maker sequentially selects multiple arms out of N available, i.e., picking at each stage an action in some admissible subset of {0,1) Using off-the-shelf combinatorial bandit algorithms, that do not leverage the relevant structure of repeated auctions, would end up in highly inefficient and sub-optimal procedure (see Section 2) Our approach is different; in essence, we reduce the complex combinatorial problem by expressing the utility objective as a polynomial (in K and T sum of simpler functions.
Related Work Multiple-unit auctions of indivisible identical items have been extensively studied in their static settings. In particular, how the pricing rules (discriminatory, uniform, VCG) influence revenue (Ausubel et al., 2014), social welfare (Birmpas et al., 2019 De Keijzer et al., 20033), or price stability (Anderson & Holmberg, 2018). Their use in the context of electricity markets is common and similar questions are being studied with this specific application in mind (Akbari-Dibare) et al.,
2020 Cramton & Stoft. 2006) Fabra et al., 2006; Son et al., 2004))
The repeated setting of auctions, and specifically the use of online learning procedure inspired by Multi Armed Bandits has received lots of attention in the last decade. First studied from the point of view of the auctioneer: Blum al., 2004 studied maximizing auction revenue, Cesa- Besa-Bianchi al., 2014 and Kanoria and Nazerzadeh, 2014 specifically focused on learning reserve prices. Learning to bid, the bidder's problem, was considered later on, initially in single-item auctions. Second price auctions facing either adversarial or stochastic highest opposing bids were studied in Weed et al., 2016 and contextual, budget-constrained setting by Flajolet and Jaillet, 2017. Balseiro et al., 2019 considered the first price auction with adversarial opposing bids leading optimal regret rates of (TT233 in the known valuation and contextual setting.
First mentioned in Feng et al., 2018 for unit demand, multiple unit auctions as online learning problems only recently started to be considered as their own topic of interest. Discriminatory pricing and uniform pricing respectively studied Galgana and Golrezaei, 2023 and Branzei et al., 2024 can be learned with Ö(VT) in the full-information setting. Under bandit feedback, the former achieves ((KT2/3) regret rates in discriminatory pricing and the latter ((K7/478/4) regret rates with uniform pricing. Compared to single unit auctions, the combinatorial nature of the action space in K-unit auctions makes it a harder learning problem. Branzei et al., 2024 makes use of a cautiously designed equivalent action space represented as a Directed Acyelic Graph (DAG) to address the combinatorial limitation and to design an algorithm guaranteeing the aforementioned regret bounds.
The effects of specific feedback on the ability to achieve lower regret rates have also raised some interest. Feng et al., 2018 studied the effects of "Win Only" feedback in more general auction set- ting. More recently, Cesa-Bianchi et al., 2023 focused on feedback transparency. They characterize gaps in the regret rates that can be achieved depending on the amount of feedback received, getting three separate rates O(VT), ( and Q(T)) depending on the feedback considered. The work of Karaca al., 2020, similarly to the all-winner feedback, studied partial feedback, which lie in between bandit and fullinnformation motivated by electricity market auctions.
3

---

Contribution We introduce a novel representation of the action space that overeomes the com- binatorial complexity introduced by the multiplicity of the bids in K K-unit auction. Inspired by the properties of the equivalent action space used by Branzei et al., 2024, we introduce bid-gaps, to further decompose the utility into a sum of independent functions. This decomposition leads to im- proved regret rates of (KK4/37//3 under bandit feedback, compared to the known upper bound of Ö(K7/178/1). These improved bounds match, in terms of T, the rates Ō(KT2/3) achievable in discriminatory pricing. We notice a reduction to simpler auctions which bear an (TT2/5) lower bound on the regret, answering the open question of the optimal rates dependency in 7 in the bandit setting. Motivated by the terms bid revelation electricity reserve markets in several European countries including Germany and France, novel feedback structure is considered, which lies in between bandit feedback and full information. This feedback, which we call all-winner, reveals all the winning bids of the action. We propose algorithm that achieves O(K ((T)) regret, almost matching the regret rates under full information up factor K, while the lower bound of S VT) proved by Branzei et al., 2024 for the full aol-iifformatio feedback, naturally extend to this setting. We summarize our results in Table below.
Feedback
Literature
This work
Lower bound
Full information
Ö(K3/VVT)
O(K3/2 O(K3/VVT O(K4/ST2/3)
Q(KVT) ((KVT) Q(T2/S1
All winner
Bandit
0(K7/978/4)
Table 1: Regret Rates in multi-uni unit uniform price auction. holds in the LAB pricing rule setting
2
Action space
We first motivate the new cautiously designed action space, and provide intuitions on how it is constructed and its main properties. We then formalize its definition.
Motivation for an alternative representation Usual techniques such as uniform discretization of the action space as in (Feng et al., 2018) might lead to consider the subset of iicceincea sequences on this discretization, denoted by B. C {0,e, e, .... (1+) - 1)e, [ > Without loss of generality, we shall assume in the following that 1/e is an integer. The main downside of this representation is that the size of B, exponential and thus, without any further properties of the
problem leveraged, this would lead to arbitrarily bad regret rates Ö(T in bandit setting, Even though we can restrict the available action to reasonable ones (ie undominated strategies 6) this isn't enough to achieve improved rates in general.
Branzei et al.. 2024 proposed a Directed Acyelic Graph (DAG) equivalent of the action space B. to overcome this combinatorial limitation. They use the decomposition of the utility into a sum of independent functions, depending only on pairs of consecutive bids (the edges in their graphs), to reduce the combinatorial complexity to only 2 (instead of K), and thus achieved an ((K7/4T8/4) regret bound under bandit feedback. Motivated by the breakthrough enabled by such representa- tion of the action space, we consider a new equivalent action space He, introduced in Eqquttoo 5) This new action space allows to leverage more precisely the regularity of the utility with respect to the bidder's choice of bids, which in turn leads to improved regret bounds under bandit feedback, presented in Theorem [
2.1 Action space tailored to the outcomes
We now provide intuitions on the utility regularity that will be leveraged. We start by observing that, for given auction, the price is either set by one of the bidder's bid or by bid from the adversary.
Assume that the bidder bids (b1..., bx) B., and that the price by for some k E [K]. Then, we claim that many bid profiles would have led to the same outcome. Indeed, any bid profile (from the bidder) with the same 1tth bid by. leads to the same outcome. In the alternative case, where the adversary sets the price, if the bidder wins & items (i.e., the K k adversary's bid 3 sets the price), then any bid profile satisfying by 2 8k- x 2 but1 leads to the same outcome.

---

Notice that in the two aforementioned cases of regularities of the utility, all bids b E B, which would lead the same outcome share one of the following properties: for specific and j.
in the first case hy = je, in the second case by 2 (j + 1)e - je 2 ba+1-
For simplicity, we shall assume that the bids the decision-make belong to the e-discretization, i.e. (b1,..,,kk) E B, while the bids of the adversary do not belong to it, in order to avoid tie We denote this set Be, the set of non- non-increasing sequences of [0, 1]k without values in [
We, introduce alternative description of the bidding space B, whose structure closely matches the aforementioned regularities' in order to improve the bidder's strategy. It leverages new binary variables indicating which of the aforementioned properties bid b E Bg has, they are defined as follows: for any & E [K] and j E [H].
heg (b) = 1 (4x = je} h /e+ (b) = 1 fbx 2 (j + 1)e je 2 bu+1).
(3)
and J.= [2]. For any b E Be, we define the pseudo-bid ha to be the list of these binary variable hi.j with k,j E K. x J, such that ha.j(b) = 1, ordered in lexicographic order, increasingly in k and decreasingly in j. We naturally define H, the pseudo-bid space generated by the bid space B.:
Let IC = (1, 1--1,11111 "
H. (bblbe E Be}
(5)
For each pseudo-bid h E Ho, there exists unique b E B, such that h = hh. This therefore defines a bijective mapping between He and Be.
Lemma 1.
Proof. From the expression of H. in (5), it clear that the mapping b + ha is surjective.
Let E H., there exists b = {bi,... ...,, 5x E B, such that h2 Let ju J. such that by = jec, for all l E [K], we have he.j. E h. If there exists another bid b = (b,,... bx) E B. such that
h = h2. for all & E [K]. he.j. (b) = L.Therefore (3) yields by = -asc by for all l [K]. This proves unicity and therefore that the mapping is bijective.
The following characterization of the pseudo-bid space directly follows from Lemma 1
Corollary 1. Given a bid b- = (be)sE(K) E B, and the pseudo-bid hy E He, we have the following: for all j,j E [K] x Je,
by je = hRj hp
by 2 (j + 1)c > je 2 be+1 N E hb
(7)
To provide further intuition, Figure Ta and Figure Tb
show how two corresponding bids might be represented in B, and H., The bids 6 represented by circles, while the bid-gaps (7) are ellipses.
2.2 Utility decomposition
Leveraging the new action space, we define the utility, price, and allocation function on H, resulting from the bijective map with B,. Let E H. and B, the unique element of B, such that hb- For all 3 Bye, we define the utility as u (h,, 3) = u(b, f), the price xn (hn. 3) = x(b, () and the allocation PH (hs, B) = p(b, 3)
The following additional set notation, which matches a binary variable h& its corresponding price range, allows for unified descriptions:
(je) Phhhs)) (je, ( + 1)6)
if k: is integer if k is half integer,
We now explicitly show how the pseudo-bid space is well suited to capture the regularity of the outcomes of the auction (and therefore of the utility) mentioned above. To be more precise, the
"This assumption comes without loss of generality, since e.g. adding uniform noise with extremely small variance to the bidder's bid prevent ties a.s. see Lemma 8 in /uubecctionn A.3
5

---

2
b
b2
bx
h1,5
h1
$ h1
h2
2 2/,,22
(a) Bids in B.
(b) Bids and corresponding hid-gaps in (PP)))
Figure 1: Graph representation of action spaces B, (Branzei et al., 2024) and ((P.) (this paper)
following Lemma 2 states that within pseudo-bid profile h, a pseudo-bid he.j can be credited for the outcome: any other pseudo-bid profile containing this pseudo bid would have lead to the same outcome.
Lemma 2. Let B Biee and (k. E K. To. There exists C {0, 1}. such that for all h E He with hy.5 E h,
(p B) Pe(haa)) n (an (h, [ C and ifC pH (h, () is also constant on (h H. has E h}
Proof. Let b E B. such that ha.j E hT- If k is integer, then Corollary yields by je, hence we
get 1 (pn (h, (3) =jc {IH (h, 3) k] [
je bk > 3K- [K-k+1) which only depends
on k.j and B. If l: is half-integer, then Corollary 1 yields be+1 < je < (j + 1)c < by. hence we
Yj 1 [[je < BK < (j + 1)e} which also only depends on j and B. is straightforward to see that when the indicator function takes value one,
get [/ (h, () = Pe (hk n (r
price constant with value je for the integer case and 3K
the half integer case.
Lemma 2 allows us to exhibit key property of the utility on the pseudo-bid space: it can be decom- posed into sum of sub-utilities (defined in Eqqution I1), each of which only depends on one of the components of h.
Lemma 3. Let h E H. and B E By The utility of the bidder rewrites sum of sub-utilities:
3)
Σ
w(ha,53)) B), with
(10)
hh.chh
U [K]}} >
who,. :) (1pp(h,
(u - PH (),
(1I)
Proof of Lemma x (h, (h, 3) 0 implies that u as defined Equation 10 is zero, as expected. For
the case where x (h > 0. we use that the indicator functions in Equation I1 correspond to disjoint
events. Thus, there exists unique pair (k, IC x Je such that w(h,, 3) 0, furthermore, this sub-utility w(hu,,, matches the utility u(h, 33. This concludes the proof.
While the expression these indicators Equation involves the full action h, Lemma 2 shows that they only depend either the associated bid hagj- Furthermore, notice that within given E He, the events corresponding each lg. E are disjoints and therefore only one can be realized. As result there is at most one h h with positive sub-utility, denote it h, (h, (3).

---

3 Learning algorithms and guarantees
We first present two algorithms and estimators of the utility corresponding to the different feedback settings. We then state the regret rate achieved by these algorithms when used with the introduced estimator, depending on the setting considered, as well as a lower bound on the regret in the bandit setting. To simplify notations, we shall further introduce F/y (.) un 3¹) and w.) w(,,3')
3.1 Algorithm for online learning in K-unit uniform auction The regret minimizing algorithm combines two separate procedures,
An exponential weight update, detailed in Algorithm 1 which creates and updates the weights for each bid and bid-gap each time step, akin to an EXP3 type algorithm (but normaalzal (Cesa-Bianchi and Lugosi, 2
Lattimore and Szepesvári, 2020)).
A sampling procedure, tailored to our action space, described Algorithm 2 that re- normalizes the weights into probability distribution by using weight-pushing method, and uses an efficient procedure to sample an action. (Takimoto and Warmuth, 2002).
Because of the combinatorial structure of the problem, using directly the exponential weight algo- rithm would be highly inefficient, with a complexity of order O(2k to store weights and compute probabilities directly on the action space. The second auxiliary sampling algorithm gets rid off this complexity burden.
Algorithm S pseudo-code details the exponential weight algorithm used building block of the no-regret procedure. It computes weights for each pseudo-bid hased on the corresponding sub- utilities, or their estimated values. These weights are used sample pseudo-bid sequence h H..
Algorithm 1:
Component based exponential weighting
Input: time horizon T, parameters ε > and v Output: actions for each time step (h², h2 ,..... h h²" E (H.)².
Initialize: for (k,j) E K. x Te, set Q"(he.)) =1 for f 1.2........ do
Sample h' using the sampling procedure of Algorithm 2 with input parameters Q'-1; Receive the utility ut u(h', ,²)) and the feedback. Based on this feedback, define
wh = w(,,B') in the full oulliinformttin feedback, see [T]
ve Update the weights based on the weights v²: for (b. E K. Te do
vh
with bandit feedback, see (T9)
with all wllner feedback, see 20
('(bes) = Q'- exp (nu'(he.)
(12)
Algorithm 2 is sampling procedure and uses weight-pushing technique (Takimoto and Warmuth, 2002) to efficienlly sample pseudo-bids and compute weights and probabilities on H., is exploit- ing the lexicographical ordering of the pseudo bid (increasingly in & and decreasingly in j) which creates a graph-like structure, as illustrated in Figure Tb is indeed possible to sample an element of H, by repeatedly sampling the next binary variable conditionally on the previous one. To ex- plicit this graph-like structure, we define s(.) the successor function, which given a pseudo-bid hx. provides the set of possible next element of action. For k [K- 1]. E J. \ {0).
s shb+11/25) (1441/2.5-1, hxt1s)
(13)
s(hu,) = 11
(14)
s(hx,o) == {/x+1.0}
(15)
As well the following, which serves the stopping condition of the sampling:
Vj Te. s(hk,))
(16)
7

---

Algorithm 2: Selection of the bids by weight-pushing algorithm
Input: Weights Q for every bids bid-gap ((E_))(A))EE)))
Output: bid vector h E He;
Initialize : f- K 2' For all j E Je, ((hk)) t-
while 2 do
for j Je do [( Ehea(he,)) (h))((h)
k 2 To - - ((hi))
Sample according to the probabilities:
vj E Je, h h1t) (h1,,) T(h
To
h < {k}
while (h) j do
sample h+ E sh),, the next element of the sequence h, with probability:
P(h = Ih) = Q(h')
r(A) for all h E s(h); T(a
h - h (h+}:
h h4i
The combination of Algorithm 1 and Algorithm 2 leads to the following probabilities, typical of an exponential weight algorithm, on H., For h E He.
exp (En nu (u)(
F P'hh-
(17)
Engh, exp nu7
as shown in Appendix B in Equation 29
Estimators With partial feedback (either bandits all-winner), the bidder does gather enough information to compute all of the sub-utilities, and it can only do it for a subset of pseudo-bids. They must therefore resort, as is standard multi-armee bandit literature, to estimators that should leverage all the information available. Under bandit feedback, only sub-utilities of binary variables which belong to the action played time can be computed.- On the other hand, under all-winner feedback, the richer feedback allows to compute sub-utilities for bigger set of binary variables h, we denote A and define it in Lemma 4
Lemma 4. With the all-winner feedback, the bidder can compute from its feedback the sub-utilities of any pseudo bid in A(h', (²), defined as:
A(h', B²) = {hs.s (b. E K. x Jel s.I. (k l x'} or {ks x'and je 2 p²}}
(18)
Where x² = (h", 33) and = p 1²).
The formal proof of Lemma 4 in Appendix C
As noted above, within given pseudo-bid h, only one sub-utility can be non-zero. We there- fore also define the set of binary variables with non-zero sub-utilities A, (h', ( == (haa
A(h', ,tt) [w/,,,, 0}.
We can now formally introduce the estimators used by the no-regret procedure. Definition 3.1 (Estimators). Let h' H. be the action played by the learner, and 3 B the bids of the adversary at time t.. For any bid or sid-gap h, we define the sub-utility estimators:
Bandit feedback vi (h) (1 k.)) w (h) K
(19)
Pe(h)
w (h) - K
All-winner feedback wi (h) (h At(h'))
(20)
P (h A!(P)))
ft P

---

where ht, := : h. (h', 3 is the sub/pseudo-bic played at time t that has non-zero sub-utility, B is the probability distribution on H, as (17) and F (h) := -henthhh (h)
Naturally, estimation of the utility of any action h He is done with simple summation, over E h, of these estimates.
3.2 Regret Analysis
we recover the regret guarantees obtained by (Branzei al., 2024 Theorem 2) in the same setting for the full-information feedback. We provide a formal statement and proof of this result in the [Appendix B] in Theorem 3 We now analyze the performance of the learning procedure for the two other types of feedback.
Combining Jadd the sampling Algorithm 2
Theorem 1. In the repeated K-unit auction with uniform pricing guarantees and under bandit feedback, Algorithm / incurs a regret of at most O (K4/872//3 log (T)) For any time horizon T, with the choices of = ( (K)
1/3 and 17 1 -K11//-2//3 / //0g
Proof sketch. The aforementioned regret bounds are proved by using similar analysis the one in Lattimore and Szepesvári, 2220 to obtain regret bounds of EXP3 algorithm in the adversarial bandits case. We apply this analysis to the discretized action space H, and bound the additional cost of using a discretization separately. Then we choose a discretization size to minimize the total regret.
The improvement over known regret bounds in Branzei et al., results from the decomposition of the utility into sub-utilities. Since these sub-utilities only depend on one bid or bid-gap. the variance of the estimators (cf Lemma 99 only depend on the possible number of bids or bid-gaps of order 2) not the number of bid profiles of order ,k This is akin to why combinatorial bandits under band-b feedback (Audibert et al., 2014) achieve better regret than under
O
Theorem 2. For any time horizon T, using Algorithm in the repeated K K-unit auction with uniform pricing guarantees, under all-winner feedbuck, a regret of at most K3//2 (1//2/TTog(() with rj = K-1 1/2 and e = 1/22
Proof sketch. The proof of these bounds in the all-winner feedback follows closely the analysis used for the bandit feedback. Better bounds are achieved in comparison to the bandit's feedback thanks to the lower variance of the estimator defined in (10), proved in Lemma [0] Intuitively, this comes from the ability to observe the realized utility more often, allowed by the richer feedback. We exhibit this by using tools used in bandits with graph feedback (Alon al., 2017).
Regret lower bound We provide matching lower bound on the regret of any online learning algorithm (Lemma 55) in the bandit feedback setting, by extending a result from (Balseiro et al., 2019) in the context of single price auctions. This partially answers an open question raised by Branzei et al., regardig the achievable learning rate in the bandit setting for the problem that we consider.
Lemma 5. Any online learning procedure must incur (T2/33) regret in multi-unit uniform auction with the Last Accepted Bid rule under bandit feedback Bid pricing rule.
This stems from the fact that against an adversary that only plays bids with value 1 except for its last bid, the auction is essentially first-price auction.
Proof. We extend the lower bound on the regret of the first price auction in Balseiro et al., 2019 At time t. let Ø = {1, ..., 1, h²y be the bid of the adversary, let the valuation of the learner be 01., 0) and denote by (bf...., b()
B the learner's bid. We only consider sensible bids, such that bf > 0 - = 1, because they are dominating strategies. The learner's 's utility is uh,, (3)
(bf h1) ), and the bandits feedback, (x', 1 fo" 0) p²) is : (1 [b] > h/), 1 {b] > h2) b)) which coincides with both the utility and the bandits feedback of the first price auction with value 1.
This specific instance of the repeated K-unit auction therefore coincides with the repeated first price auction with opposing bid ht at time i, which can be any instance of the first price auction. Therefore

---

if no learning algorithm can guarantee better regret than ((T2/3) in the latter problem, no algorithm can guarantee better regret than (TT2/5) in the former.
Conclusion
We provided the first no-regret algorithm achieving optimal rates in T for the K-unit uniform auc- tion under bandit, full information, and all winner feedback. The techniques and theoretical tools presented can be applied to obtain similar regret guarantees in the adversarial bid setting with ran- dom valuation, under the assumption that the valuation and opposing bids are independent. An interesting open question whether similar rates can be achieved in contextual setting (when val- uations changing at each round are observed before each play). The obtained regret rates match the ones obtained in the discriminatory price auction, commonly compared auction mechanism, up to factor O (K*)). This raises the question of whether this gap can be closed or if lower bound showing a separation in achievable regret rates exists.
Acknowledgements
Dorian Baudry thanks the support of the French National Research Agency: ANR-19-CHIA-02 SCAL,
Ocean, and ANR-23-CE23-0000 Doom. Dorian Baudry was also par- tially funded by UK Research and Innovation (UKRI) under the UK government's 's Horizon Europe funding guarantee [grant number EP/Y028333/1).
This research was supported in part by the French National Research Agency (ANR) in the frame- work of the PEPR IA FOUNDRY project -AN--23-PEIA-0003) and through the grant DOOM ANR-23-CE23-0000 It was also funded by the European Union (ERC, Ocean, (01071601) Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council Executive Agency. Neither the European Union nor the granting authority can be held responsible for them.
References
Akbari-Dibave A., Mohammadi-Ivatlon B., & Zare, K. (2020). Electricity market pricing: Uni- form pricing vs. pay-as-bid pricing. Electricity Markets: New Players and Pricing Uncer- tainties, 19-35.
Alon, N., Cesa- Besa-Bianchh, N., Gentile, C., Mannor, S., Mansour, Y., Shamir, O. (2017). Non- stochastic multi-armed bandits with graph-structured feedback. SIAM Journal Com- puting, 46(6), 1785-1826. httpp::/doi.org/ 10. Anderson, E., & Holmberg, P. (2018). Price instability in multi-unit auctions. Journal of Economic Theory, 175, 311-341.
Audibert, J.. Bubeck. S., & Lugosi, G. (2014). Regret in online combinatorial optimization. Math-
ematics of Operations Research, 39(1), 31-45.
Ausubel, L. M.. Cramton, P., Pycia, M., Rostek, M., & Weretka, M. (2014). Demand Reduction and Inefficiency Multi- Auctions. The Review of Economic Studies, 8/(4), 1366-1400. https://doi.org/I1 10. [093/restud//du([]]
Balseiro, S., Golrezaei, N., Mahdian, M., Mirrokni, V., & Schneider, J. (2019). Contextual bandits with cross-learning. Advances in Neural Information Processing Systems, 32,
Birmpas, G., Markakis, E., Telelis, O., & Tsikiridis, A. (2019). Tight welfare guarantees for pure nash equilibria of the uniform price auction. Theory of Computing Systems, 63, 1451-1469. Blum, A., Kumar, V., Rudra, A., & Wu, F. (2004). Online learning in online auctions. Theoretical Computer Science, 324(2-3). 137-146.
Branzei, S., Derakhshan, M., Golrezaci, N., & Han, Y. (2024). Learning and collusion in multi-unit
auctions, Advances in Neural Information Processing Systems, 36.
Cesa-Bianchi, N., Cesari, T., Colomboni, R., Fusco, F., & Leonardi, S. (2023). The role of transparency in repeated first-price auctions with unknown valuations. arXiv preprint 1.X0::2307.09478.
Cesa-Bianchi, N., Gentile, C., & Mansour, Y. (2014). Regret minimization for reserve prices in second-price auctions. IEEE Transactions Information Theory, 61(1), 549-564. Cesa-Bianchi, N., Lugosi, G. (2006). Prediction, learning, and games. Cambridge university press.
10

---

Cramton, P., & Stoft, S. (2006). Uniform-price auctions in electricity markets. Elsevier Science. De Keijzer, B., Markakis, E., Schäfer, G., & Telelis, O. (2013). Inefficiency of standard multi-unit auctions. European Symposium on Algorithms, 385-396.
Fabra, N., von der Fehr, N.-H., & Harbord, D. (2006). Designing electricity auctions. The RAND
Journal of Economics, 37) 23-46.
Feng, Z., Podimata, C., & Syrgkanis, V. (2018). Learning to bid without knowing your value. Pro- ceedings of the 2018 ACM Conference Economics and Computation, 505-522, https: 1963322996663321200
//doi.org/ 10. Aoooi.org//.1.
Flajolet, A., & Jaillet, P. (2017). Real-time bidding with side information. Neural Information Pro- cessing Systems.
Galgana, R., & Golrezaei, N. (2023). Learning in repeated multi-umit pay-as-bid auctions. arXiv
preprint arXiv:2307. 1933.
Kanoria, Y., & Nazerzadeh, H. (2014). Dynamic reserve prices for repeated auctions: Learning from
bids. Web and Internet Economics: 10th International Conference, WINE 2014, Beijing,
China, December 14-17, 2014. Proceedings 10, 232-232.
Karaca, O., Sessa, P. G., Leidi, A., & Kamgarpour, M. (2020). No-regret learning from partially observed data in repeated auctions. JTAA-PPpersOnLinee 53(2), 14-19.
Khezr, P., & Cumpston, A. (2022). A review of multiunit auctions with homogeneous goods. Journal of Economic Surveys. 36(4), 1225-1247.
Lattimore, T., & Szepesvári, C. (2020). Bandit algorithms. Cambridge University Press. 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.
Sessa, P. G., Walton, N., & Kamgarpour, M. (2017). Exploring the vickrey-clarke-gun grooves mechanism for electricity markets. PPAC-PapersOnt.img 50(1), 189-194.
Son, S., Baldick, R., Lee, K.-H., & Siddiqi, S. (2004). Short-term electricity market auction game analysis: Uniform and pay-as-bid pricing. IEEE Transactions Power Systems, 19(4), 1990-1998.
Takimoto, E., & Warmuth, M. K. (2002). Path kernlls and multiplicative updates. International Conference on Computational Learning Theory, 74-89.
Viehmann, J., Lorenezik, S., & Malischek, R. (2021). Multi-unit multiple bid auctions in balancing markets: An agent- q g-learning approach. Energy economics, 93, 105035. Weed, J., Perchet, V., & Rigollet, P. (2016). Online learning in repeated auctions. Conference Learning Theory, 1562-1583.
Willems, B., & Yu, Y. (2022). Bidding and investment in wholesale electricity markets: Pay-as- bid versus uniform-pric -rrice auctions. Tilburg University, Toulouse School of Economics and CERRE.

---

A Problem-specific simplifications
This section focuses on characterizing undominated strategies and showing that when learner plays on an e-discretization of the bid interval [o, 1] assuming ties never occur is without loss of generality.
A.1 Dominated strategies
Since the scale of the bid space is deciding factor in the rates of regret we obtain, it is useful to analyze the utility functions of the learner. Indeed, for the learning procedure, it can be useful, to restrict ourselves from the start to bids which can potentially be optimal. We show next that, under certain condition on the values of the learner, we can restrict the bid space B.
Lemma 6. Let {ui, 02,-- v be the valuations of the learner. Then for any bids b (bi,... bx) B such that there exists E [K].be > Vs. there exists b a non-increasing sequence of [0, v2l x [0, 02) x x [0, uk] such that
BB B, Bb, 2 ub,,8)
Proof. Let {1r, "2, J J be the valuations of the learner. Let b = {bi, b0b,..,,b' bx} E B a bid such that there exists i E [K],b; > Up. We define as follows:
Vi E [K], b, min(u;; by)
Let B E B be the bids of the adversary. As max, p(.) is increasing in its arguments hence pbb 3) S ().
(21)
There are possible cases Either the allocation remains the same x(b, () s<(b, B), it decreases xbb, (3 S x<b, 33) (decreasing bids cannot result in a increased allocation).
If the allocation remains the same, then (1 implies u(b, 3) ulb
If the allocation decreases, the items obtained when bidding b but not obtained when bidding b necessarily corresponds to bids which have been lowered (other bids remain higher than the price). Let j E [K] such that by is of these bids, since the item used to be won by 2 p(b, Since it is not won by the learner playing b, we have b, S p(b, .3). Hence b2 S p(b,3).
Since this is the case for all items j won under b and not under bidding p(b, (3, w(b, 3) 2 ubb B).
is therefore always the case that
ubb,3) 2 u(b, B)
(22)
Since it is true for all B B, this concludes the proof.
A consequence of Lemma i that of [0, vi] x [0, U2] X ... X [0, ug].
restrict our learning procedure to non- non-increasing sequence
In the following of the paper for simplicity we use B as the bidding space. This covers the worst case which corresponds to the case when for all E [K]. v2 =
A.2 Discretization error
To use online learning techniques in our instance of multi-unit uniform price auction, discretization B, of the bid space B which is continuous. We bound here the added regret incurred because of this discretization, that is the additional regret suffered when comparing the best action in hindsight of B, to the best of B.
Definition A.1 (Discretized regret). Let (b'),e(T) E BT be the action played at time E [T],
against the opposing bids (g)) ( B". The discretized regret is defined as follows:
RT, max BEB,
ua 3')
Σ u(b', 3¹)
(23)
We bound the cost of this discretization follows
12

---

Lemma 7. Let (b')E)(T E B.. be the action played at time t E [T), against the opposing bids
(3')em E B With Ry the dicretized regret and Ry the regret, we have the following inequal-
ity:
Rr S Rr. + KTe.
Proof of Lemma 7 Let (8*) KEmT E (10, the adversary bids played to time T.
Let (E) E Be.
RT sup bEB
((b E Σ u(b 13)
sup beB
u(,, 3¹)
sup B. t=1
u(b, 3¹) + sup
Σ
((b,)') E Σ u( (bb 8')
be Be
sup bEB
ub, 3r)
max be B
u(b, Bd) + RT.
Let 0, there exists bapt E B such that Σ u u(Doptr Bt) + u2 sup Σ 3(b,
beB
We define its closest discretized bid from above
Dopt,t (
if bopt.t E N if bope,i > [t]e
Dopt,e =
(24)
6
else
xE[K]
Since max(.) cannot increase more than its arguments and Vi [K], bopt,e,t S bope,s + e,
vt [T], p p(bopt.e: 3*) pl p(bopt, ,¹)
(25)
and since Vi [K], bept,e, 2 bopt.i-
VI [T], x ((oppt.,, 2 x xboopt, 3¹)
(26)
therefore,
a Dopt,e: 3²) 2
u bopt, 3²) KTe 2 sup Σ bEB t=1
u(b
KTe μ.
Hence
T
PT
u(b,B')
max
u( u(b,3') RT,
bEB
1=1
sup
u(b, B*)
u(bopt,er 3*) + RT,
bEB t=1
KTE # RiT
Since the previous inequality is true for any 0, we get
Ry & KTc Rr.e-
13

---

A.3 Avoiding ties
the latter analysis, we assume that ties never occur. We show here how this assumption, for our regret analysis, is equivalent to using small perturbation of the bids of the learner. Let (0, c) and ~ 24 8] the random perturbation of the bids of the learne. We define B the set of non- increasing sequences of (X, c X, 2c x..., c x}*, the set in which the perturbed bids of learners take value.
This perturbation of the discretized set we use as bid space for the learner comes at no costs in terms of added regrets. The previous Lemma can straightforwardly be applied to the perturbed set B& as the key reason for the additional regret is the discretization step e, which remains unchanged here.
Lemma 8. Let B B" be the bid of the adversary up time T, for any bid sequence of the learner b" E XX there is almost surely never a tie.
Proof. Let 3" E B" and for all E T denote 3 = 18f,--..kkk For any bid sequence bad E BXXT, a necessary condition for ties to occur is that there exists (t,j) E [T] x [K] such that 3 E fc+ X,2c X..., 2 to belong to finite set.
X}. This is almost surely never the case, is the probability
Remark For the sake of regret bounds, since we almost surely don't have any tie, the assumption that the adversury plays bids in Beg is without loss of generality.
B Appendix: Regret analysis
B.1 Full-information regret rates
Theorem 3. the full information feedback setting, Algorithm 7 coincides with the Hedge algo-
rithm with parameter n on H It ensures a regret of at most O (VK3Tlog (T)) by taking = v K
log( () 2KT
and 1j
Proof of Theorem In order to leverage classical results on the exponential weight algorithm in the expert setting, we aim to show that the combination of our algorithms leads to probability update rule of the form:
1pt-1(h) (h) exp (174² (h))
('hh) Ejen. P)- (j)
(27)
Let h be bid profile in H., denote h, its 7th element (ith element of the sequence) and len(h) the length of the sequence h. Given the sampling Algorithm 2 we have by telescoping and the product of conditional probabilities
Psd (h)
TPt (P((h(14:11) (E(1,lcn(b)]
II
('(ha))
II [E(],len(h)]
('(b,)
((
[Ise(1
Q'(hss
rg [L((1)
(h₂) Q²=1(h,) exp (h,))
exp (h))
mt- (hg-1)
II
pe-1(h, (hilhi-)
rb
1 1 1(+))
[E[])een(h)]
r
(hh)
exp
(nu (h)) p(-1(h)
(28)
Tb
where we used the probability update rule
12
14

---

We can prove that ro EnCH.
II (h())). An induction on
maxlen (h) heff
where we
ve[1.len(hi]
denote h the k first component of the sequence h:
ro
Σ
II
Q'(hs) I (t,(hi(
[
This is true for & 1 from the definition
2 of To
For 1.
Ho Σ
II
Q'(Na)
hacheH,
Σ
II
Q'(ha)
Σ (1()
hychEH
hEa(he)
Σ
II L
Q'(ha)
ha
where used the fact that the function successor s(.) provides all possible next element of sequence
h.
rf-1
We then simplify
0
ro
Σ
II
Q'(h,)
he H, lenlh))
Σ
II
(hi) exp (mpr(hs)
he H. ke(h)))
1 (h.
-E hel
exp (nj)
II Pr-1(h,(b, (E[1)Jen(bb]
(t-1(h))
exp (nul) (h)) (h)
0
heH.
We can therefore write
ppt-1 (h) exp (n7u' (h))
(h((h) = Σien, (P) exp vpu
(29)
This is the update rule of the Hedge algorithm on the action space H.- Therefore using Theorem 2.2 of Desa-Bianchi and Lugosi, 2006 restated in the Appendix 4 leads the following regret bound:
log (lB.)) + T2K²
RT,
(30)
log (1/c*)
+ nTK²
8
where, bound log (lB.)) in (30). used the fact that the action space H. in bijection with the original discretized bid space: K non-increasing elements of (1,2,..., [+J]. which cardinal is trivially smaller than ..
Taking 7 = log( RT
we obtain
9 Rr. <
TK3 log (
8
15

---

Finally, using lemma] 7
Rr S RT. + KTe
9
TK (
+ KTE
8
9
T V
VTK3
log
+1
8
K
with c=v /
B.2
Partial feedback regret rates
B.2.1
Bandit feedback
To prove the regret rates in the bandit feedback settings, we use Lemma 9 which bounds the neces- sary quantity for the standard EXP3 analysis.
Lemma (Bandit feedback estimator). The estimator a' (h) defined by 19) has the following prop- erties:
The estimator (h) has a fixed bias - K:
E a' [b) = u uh) K.
The square the estimator be upper bounded as follows:
Ph) (b) & 4K max k2? !
Σ
hEH.
Since the estimator has a constant bias for every action, one can use it the problem similarly to an unbiased estimator.
Proof of Lemma 9
Let h be a bid or a bid-gap, then
E [h))
Σ
P
(h')
Σ i w'(h)
hiEH.
heh
wh)) - K
Σ P(h')
1(h = =1h))))) PP(l))
h'eH.
heh
F ('')) w (h(()) K
Σ
1hh (h) h2)
(h((h))
h'EH,
w/ (h(()) - K
Σ p'(h")
(h())( (h))en
= (h)((h) - -K K.
16

---

Σ [(LEE =
Σ
F' (h)a'(n))
(31)
heH,
heH,
w (h(hh(h) K
Σ
P'hh")
Σ P'(h)
1( = M.)
(32)
P((h)
h'ell
hell
(w'))) K
Σ h'ell.
P'(h')
Σ PP'(h)
(33)
Po((h.)
he hEH, ch
(w'(h)) K)²
= E
P'hh')
(34)
P'(h4)
h'EH.
EnerRAMe P(hh') (t(ht)
I K
Σ
(35)
MEE
K2 Σ
(36)
Mo
$ (K)
(37)
where
h m.
There only remains upper bound |0*).
For any E [0, 1] we denote for this proof j(p) = [.., which the value j such that E [je,je+e) Let h He, notice that h (h, ,²) E (b.,(h, ()) (h, ((((t,a)))))))) which directly results from the decomposition formula 10 To upper bound |O*) we will therefore upper bound the different values the pair (Ire
(a), p( (
()) can take.
Since the learner plays bids in H. (or equivalently BD), P(), can only take either the value of one of the components in or one of the bids of its first argument. Because 3 is a vector of size K we can write that: (p(h,,'').
H.) s K + L
Furthermore, because units either attributed to the player the adversary, we can write K K > Pe( ,,,") 2 x.(.. 2 K [( 2 pe(., p The two cardinals can only differ if the price is set by an adversary bid because the no ties assumption implies almost surely for all i E [K] & [+].
Therefore each possible value of pe( ,3") only correspond to one value of æf( ,,)), except for the K values set by the adversary, where æ, (,) can at most take K values.
Therefore
1 > 2
K2 +
h H.Jl 2 2 ((. 3',, (,( h H.).
(38)
(39)
> 10y1
(40)
which leads to the needed upper bounds
We now restate Theorem I and then provide proof of the corresponding regret guarantees. Theorem I In the repeated K K-unit auction with uniform pricing guarantees and under bandit
feedback, Algorithm incurs a regret of most O (K 44/3///33 log (T))- For any time horizon T.
with the choices of = K 1/3 and K-1/3T-2/3 2/3
1og
17

---

Proof of Theorem 7 For T N,, we denote (h') (h') E H. generated by Algorithm[] 1 We can first notice that, by conducting the same analysis as in B.1 up Equation 29
the actions played at each time-steps,
we obtain:
('(h) Pr- (h) exp (17ū (h))
(41)
Eien. Pt-1 exp mp
which by simple induction allows us obtain:
cxp E m (h)
P'(h)
(42)
ΣISH. exp
EE= nid (1)
We can now proceed to the regret analysis. For any action h E He, we define:
T RT. Σ (b) E
Σ (ht)
which is the expected regret relative to playing all the rounds.
We have, because Lemma
ΣT= a (h) = Et w'(h") KT
and E,1 (h')) = ΣneB (h)u' (h) = EnEB TPt E1) [a (h)) + K. Therefore
RT. E
Σ at (h(
E
(())a(()))
(43)
!=1 heH.
We denote W,, = EnEH, cxp(1 Ei= (hh)).
Then we have for any h E He.
exp Σ (h) S Σ
exp(1
W a' Wy Wo II
W.,,
hE
1=1
t=1
We can then upper bound the terms of the product as follows
Σ ('(h)
exp
W
exp (nii (h))
W
W
bEH,
<
Σ (h) exp (nū'(h)
heR.
where the second inequality comes from We can then further bound this term using the inequalities
V < 1, exp(x) < 1++++0 x² and Va E R, S exp(x).
This gives
W. W,
< 51+1 Σ (hhha((h) +1² Σ (h)
(44)
hell
hel.
" Σ (h)att (h) + + Σ P())at()))
< exp
(45)
heR.
hen.
18

---

This in turn yields
exp
1 (b)
Wo
II exp
Σ hel!
P
(h) + +
Σ pd (h))a'())²
(46)
exp
(h)a +1
Σ
Σ
P' (b))
(47)
(=1 beM.
1=1 helf
where by applying the log, simplifying, and taking the expectation we get
log(Wo)
Σ (h) Σ
Σ
P (h)
I
n
(h)
(48)
7
t= bEB
heH,
T
T
(oo( 1
T
E
à' (h)
Σ
Σ
P' (b)a'(h)
+ +n
Σ
Σ
('))a(())
(49)
1=1 1=1 heHfe
he
lo)(W)
R
+ tyR
Σ
('h)a
(50)
7
heB
We recognize the expression of the regret from (43
Because it is true for all h E He, we can take
the maximum and notice Rr, maXbeH, RT.h- Noticing that Wo HH, s (t) K and using
Lemma Lanmaa/oocclude the bound on the discritzed regret as follows:
log Hel
RI,
P (h))[[((()
(51)
"
t=1 helf.
log (2)
< K
+ nAKTT
(52)
7
KT
5K
V
log
(53)
with = V KT log (t)
Then using Lemma 7 we can bound the regret:
RT Rr KTe
(54)
T log (2) + KTe
5K3/22
(55)
T
5K1/372/3
1+ log
(56)
K
with the specific choice of e = (K) 1/3
B.2.2 All-winner feedbbck
As in the bandit feedback, to prove the regret rates, we use Lemma 10 which bounds the necessary quantity for the standard EXP3 analysis.
Lemma 10. The estimator a' (h), defined by 20 has the following properties:
The estimator ū' (h) has a fixed bias K:
E [b) u' (h) K.
(57)
The square of the estimator verifies:
Σ
Ph) (h)² < 8K log(2).
(58)
heh.
19

---

Proof of Lemma
10
This proof is mostly based on the following careful computations.
E
(h)]
Σ
Pd
(h²)
Σ
(0(h)
hEEB
heh
w'(h)) K
Σ h'eH.
(h()")
1 E A((h')) E
(59)
IP (h E A!(1))
Ee
PwB
w' (he (h)) -K 1(1,(h) E A,(''))
Σ h'el,
Fst (h")
P (h)(h) E (A((19)
PaB
w² (h) - K
E
P'(h')
P (ki(h) E AA)(
PaB
(h) K (h) K.
Σ PTL)E((()) = Σ (')))'(())?
heH.
LheH.
(h)( -K K
Σ
(P((h) Σ P'(h')
1(1(()) E At("))
P 1':N3.
(hg E A2(11))
hEH,
hi
(h)) - K IP
Σ (p)
E
P'((h))
(h((h) E AL((1))
he
(u'(h( (h)) K)² FaBt (hī(h) E A{)1
Σ Te (h)
hEH.
('(h))
K Σ
P
(h)(h) E At(I))
heHl P
P(().)
< k
P
(h) E A1(1
EO PoB
< K
(60)
EnEO:AEEAL(a) (a(a
M EEO
< K28K log
22
< <KK log
Taking a +
Where to bound (60) we use lemma II from Alon et al., 2017 restated the Appendix.
We define a graph over the elements of O', such that each element 0, has an incoming edge from the other elements 02 such that 01 (o2). This graph matches (60) to the expression lemma allows to bound.
It only remains to determine the independence number of this graph. First notice that, for each value of l: + 2 only one bid-gaps with this first index can belong to O Indeed, otherwise, since there exists a bid-profile h such that both belong to it, h² (h) would have two values, which impossible because only one bid or bid-gap per bid profile can have non-zero sub-utility.
Then notice that for two bids Oc, with the same first index l an integer values, the observed set of the lowest one necessarily contains the other. This naturally arises from the definition of A'.
20

---

These two observations ensure that, in an independent set of this graph, there is at most one element having each index & {1. 3. most 2K. Which using the lemma 11 from Alon et al., 2017 completes the proof.
2......... 2... 2k-1 J. This ensures the independence number of this is at
We restate the regret guarantees in the all-winner feedback before the proof.
Theorem 2 For any time horizon T, using Algorithm in the repeated K-unit auction with uniform pricing guarantees, under all-winner feedback, a regret of at most O [K / (oll))) with 1j K- 'T''--111 1/2 and 122
Proof of Theorem 2 The proof of this theorem is identical to the one of theorem with only the
need to replace ot by u² up the point where we bound the regret in equation The proof completes follows. The discretized regret can be bounded as in B.2.1
log [Hll
RT dise
P' 1 (h)
(61)
11
hEH,
log (2)
K
+ n/8KTTlog
(62)
KK5/2
8log(2) + +log
(63)
with 7
KVT
Then using Lemma] 7 we can bound the regret:
RT RT. dise + KTe
(64)
< K3/2 (8lg((2) + 9logg )1) + KTe
(65)
9
T
< k2// VT (1+8log() + log
(66)
K3
with < /
Ka
C Proof of technical lemmas
Lemma 4. With the all-winner feedback, the bidder can compute from its feedback the sub-utilities of any pseudo bid in A(h', B²)) defined as:
A(h', (B)))') = {hE,, (), K x Je|.st s.t. [T > x') or [k = r'and jc 2 2'}}}
(18)
Where xf = x (h', B²) and p² = P
Proof of Lemma 4 Let L [T], h' and I be the action of the player and the adversary time t. Let b' be the corresponding bid to the pseudo-bid h². Under the all-winner feedback, all winning bids are revealed, hence the feedback reveals to the learner the K - x<b', 3 biggest bids of the adversary: (Bi)ss (B))sck=a(bb.e)) Furthermore, since the price known, the learner can deduce from the rules of the auction that for all 2 K r'b',3'):
B S pb'', ,
(67)
For any value j.j E KC x J. such that he E A(h, B), let's show that we can evaluate the corre- sponding sub-utilities.
We first look at the ability of the learner to evaluate the indicator functions the sub-utilities defined
in Lemma 3 for ha, A(h',
For the integer values of k we can rewrite the indicator function of the sub-utilities, as follows
1 (p B) je} {zH B3) k} 1{3K-N je > 8K-K+1). When K - k +
21

---

K - (K-x(b',3)) this can be evaluated for any value of j. because the adversary bids are known. When K - k= K z(b', 3¹), ), the indicator function can still be evaluated if je > p(b', 33) using 667
For the half-integer values of k. follows: : [p (h, 33 E (jc, (j + ( (h, () = k 1/2] = { < 8x-k+1/2 < ( (c)).
rewrite the indicator function of the sub-utilities Lemma 2 as
Therefore, when K k + 1/2 < K - rrbb,, , this indicator function can be evaluated. Hence when & 2 x + 1/2, and that regardless of the value j.
Therefore, it is always possible for the learner to evaluate the indicator function.
Evaluating the remaining term of the sub-utilities Σ Pir(h, 33) is more straightforward since only needs to done when the indicator function takes value
For the integer values of k, the indicator function takes value 1, then pH (h, 3) je, therefore the remaining term is known.
For the half-integer values k, if the transformed indicator function takes value 1, then the price set by 3x - therefore, the remaining term is also known.
This concludes the proof as the full sub-utilities can always be evaluated on A(h,
D Restated results from the literature
D.1 Exponential weight forecaster
In this problem of learning under expert advice, they are N expert and each time E [N]. the learner chooses probability to play each expert (u/)EEN E y and nature reveals the losses (1))E111 [0, LJN.
N
R
min N
Σ 1
Theorem (Theorem 2.2 Cesa-Bianchh and Lugosi, 2006). Assume that the losses take values in [0, L). For any nu and > 0, and for all 91,.... Un E V. the regret of the exponentially weighted average forecaster satisfies
log N
mL²n
R,
1
In particular, with / In N/n, the upper bound becomes (n/2) In..
This theorem, besides the changes in notations, is slight variation from the original formulation as it allows for losses greater than 1. The resulting 1,2 term in the upper bound is well known extension and the steps to prove this extension scaled losses are provided in the original work by Cesa-Bianchi and Lugosi. 2006
D.2 Lemma graph feedback
The following lemma is restated from Alon et al., 2017
Lemma 11. Ler G (V,E) E) be directed graph with |V| K, in which each node i E V is assigned positive weight wi Assume that Eiev w, S 1, and that w; 2 e for all i E V for some
constant ( <6 Then
Σ iEV
Wi
S 4ax 4K
W.
EjENi(A)
Wi
ac
where a a(G) is the independence number of G.
D.3 First price auction lower bound
We restate Theorem 10 from (Balseiro et al., 2019):
Theorem (Lower Bound for Learning to Bid). Any algorithm must incur 2/(2233) regret for the learning bid in first-price auctions problem, even if the value of the bidder is fixed (i.e., there only one context).
22

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The main claims made in the abstract are presented in the paper, specifically as the two main Theorem T and Theorem and Lemma
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
fine to include aspirational goals as motivation as long as it 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: The paper discuss and introduces the assumptions made order for the stated results to hold, most of which are stated in the Introduction I
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 separate' "Limitations" section in their paper.
The paper should point out 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 au- thors should reflect on how these assumptions might be violated 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 on a few datasets or with a few runs. general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the ap- proach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-ter system might not be used reliably to provide closed captions for online lectures because fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to ad- dress problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best 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 complete (and correct) proof?
23

---

Answer: [Yes]
Justification: While the full set of assumption presented as part of the problem setting in the Introduction [ proofs of the theorems provided in the appendix B
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 theo- rems.
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 a short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be comple- mented 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 experimental results of the paper to the extent that it affects the main claims and/or conclu- sions 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 be 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 a dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can accomplished various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way accomplish this, but reproducibility detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of model checkpoint, other means that are appropriate to the research performed.
also be provided via
While NeurIPS does not require releasing code, the conference does require all sub- missions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or a way re- produce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which thors are welcome to describe 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 (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
24

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
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 NeurlPS code and data submission guidelines htttss:/nniss.c//puble///
guides/CooeSabmmssiinoiiii
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: http:ppblccccuuueeeeoooeeouubbbs
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. only a subset of experiments are reproducible, they should state which ones 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 to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to 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 in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
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 appropri- ate 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 accompanied by error bars, confi- dence intervals, or statistical significance tests, at 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 to a library function, bootstrap, etc.)
25

---

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 emror of the mean.
is OK to report I-sigma error bars, but should state it. The authors should prefer- ably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in 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 reproduce the experiments?
Question:
Answer: [NA].
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not 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 of compute required for each of the individual experimental rums as well as 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 or failed experiments that didn't t make it 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 http:://eeeunp..ccoobbiiehhcccet
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This is a theoretical paper, its result are not tied specific field. While it might be the basis for further research into applying learning in auction, which would allow for participant in auction better adapt to others strategies, is unclear what societal impact this might have and how fit for practical use the techniques develloped here are.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
26

---

Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact spe- cific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that 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 out 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 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 unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitiga- tion strategies (e.g., gated release of models, providing defenses in addition to 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 deseribe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses no such risks.
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 re- quiring that users adhere to usage guidelines restrictions 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 is 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
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?
Question:
Answer: [NA]
Justification:
The paper does not use 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 dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g.. CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, age should be provided. For popular datasets, paperswithcode. wtw.oodwd..o/dddaaatt..oea.a has cu- rated licenses for some datasets. Their licensing guide can help determine the license of dataset.
license, copyright information, and terms of use the pack-
27

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and the documenta- tion 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 new assets.
Researchers should communicate the details the dataset/code/mmodll as part 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 is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
For crowdsourcing experiments and research with human subjects, does the pa- per include the full text instructions given to participants and screenshots, applicable, well as details about compensation (if any)?
Question:
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
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 contri- bution of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code Ethics, workers involved in data collection, cura- tion, 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 equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
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 equiva- lent) 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 to 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 as the institution conducting the review.
28


Reviews:
[{"review_id": "O75Kau5Svc", "reviewer": "Reviewer_eotr", "summary": "The paper analyzes repeated multi-unit uniform price auctions through the lens of online learning. At each time step, a bidder submits a sequence of bids $(b_1,\\dots,b_K)$ to win up to $K$ identical items for which the bidder holds known valuations that depends only on the number of won items and are the same from one round to the other. Other bidders participate to these multi-unit uniform price auctions and the first $K$ higher bids are the one that get the items, paying the $K$-th highest price or the $K+1$-th highest price, depending on the model.\nThis setting was already studied by Branzei et al. (2024), but they obtained suboptimal learning rates for this problem.\nIn this paper, the authors close the gap in the regret rate and they further analyze and characterize the learning rates arising from a different type of feedback that was not previously considered.", "questions": "1) I see that there's still a mismatching rate when it comes to the other parameter $K$. Do you think that this is an artifact of the proof or we need better algorithms / better lower bounds to close this gap?\n2) What if also the other bidders learn? I think that in this case we probably need a different definition of the regret. Do you have in mind any way to tackle this problem?\n3) What kind of dynamic could arise if also the other bidders utilize the algorithm you proposed? Does the dynamic converge somewhere?", "limitations": "The authors correctly state the assumptions under which the theorem they proved hold.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper provides interesting insights on how to tackle repeated multi-unit uniform price auctions and this understanding translates into improved (and matching in the time horizon) learning rate with respect to the SOTA.\nThe paper also provides a model for a new type of feedback that could be of interest in concrete applications and also characterize (in the time horizon) the learning rate of this problem.\nOverall, the paper provides a valid contribution to the development of online learning in auctions.", "weaknesses": "Though this is quite common in this literature, the paper does not explore what can be done in strategic settings where also the other bidders learn, and what kind of dynamic might arise in this case. It would be interesting to model other bidders not as an oblivious environment, but rather as other learning agents.\n\nTypo. Line 41. \"suggesting that bidding multi-unit auctions with uniform pricing is strictly harder than with uniform pricing.\" I assume that the second should be discriminatory pricing.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review.\n\nQ1. Indeed our upper and lower bound do not match for the parameter K. We believe the lower bound in the bandit setting is not tight with respect to its dependency in $K$, we expect the tight bound to depend on the scale of the utility $K$.  Regarding upper bounds, we do not see any obvious way to improve them. We therefore leave the question of closing the gap to future work and in particular the task to show whether the all-winner feedback is strictly harder than the full information feedback.\n\nQ2. If the other bidders learn, we need to move from an oblivious adversary to an adaptive one. The notion of regret we should use remains the same : comparing the average utility to the best strategy in hindsight, but we need to allow the opposing bids at time $t$, $\\boldsymbol{\\beta}^t$ to depend on the history up to time $t-1$.\nOur algorithm is a variation of EXP3 for which the regret bounds can be generalized to an adaptive (or $\\textit{reactive}$ ) adversary, as discussed in [3] notes 11.5, point 4, this can be done without any change in the analysis. We are confident that the regret bounds therefore also hold in this setting. \n\nQ3.The dynamics of play that arise when players use no-regret algorithms in a game is an active field of research. The multi-unit uniform auction is a game with continuous action space. However, even in finite games the dynamics are not fully characterized. In finite games, if all players play EXP3, the average play converges to a Coarse Correlated Equilibrium or Hannan set (see chapter 7.4 of [1]). The convergence of iterates towards a Nash equilibrium is only shown for finite potential games [2] which does not fit multi-unit uniform auctions. The current theory is therefore not sufficient to characterize the dynamics of play in our framework.\n\n[1] Cesa-Bianchi, Nicolo, and Gábor Lugosi. Prediction, learning, and games. Cambridge university press, 2006.\n\n[2] Heliou, Amélie, Johanne Cohen, and Panayotis Mertikopoulos. \"Learning with bandit feedback in potential games.\" Advances in Neural Information Processing Systems 30 (2017).\n\n\n[3] Lattimore, Tor, and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Z2xoeV0KMp", "reviewer": "Reviewer_Ep16", "summary": "The paper studies no-regret bidding algorithms in multi-unit uniform-price auctions with adversarial competing bids.  In this problem, the bidder has diminishing marginal values for units of the item, and submits one bid for each unit.  The top K bids win, and the payment is uniformly the lowest winning bid for each unit of the item.  The authors present an algorithm that (1) under bandit feedback, achieves regret $\\tilde{O}(T^{2/3})$, and (2) in a slightly more informative model where all winning bids are revealed, achieves regret $\\tilde{O}(T^{1/2})$.  Both bounds are almost optimal.", "questions": "(also including detailed comments)\n\nLine 9: \"this feedback interpolate ...\"\n\nLine 27: \"this represent ...\"\n\nLine 28: \"... others bidding strategies\"\n\nLine 41, \"... with uniform pricing is strictly harder than with uniform pricing\": the latter \"uniform\" should be \"discriminatory\"?  Also I wouldn't say they \"suggest the former *is* strictly harder\".  Something like \"the former *might be* strictly harder\" sounds more accurate.\n\n\"Auction rules\" paragraph: it might help to quickly motivate diminishing marginal values here.  I imagine someone unfamiliar with auctions / microeconomics may not immediately see why this makes sense.\n\nLine 59: competing bids being adversarial (and not stochastic) seems like an important modeling choice, and I'd mention this upfront (e.g., in the abstract or earlier in the introduction).\n\nLine 137: the gaps here seems to be $K^{3/2}$ instead of $K$?\n\nLine 183, eq (4): brackets don't match.", "limitations": "No concerns.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "The paper makes concrete improvement and presents almost optimal bounds for a meaningful problem that has received considerable attention.  The techniques appear nontrivial.", "weaknesses": "The paper is somewhat hard to navigate.  For example, I was lost a few times when new concepts / definitions / constructions are introduced while it's not clear at the moment what purposes they serve.  Some explanatory text would help.  I'd also appreciate more motivation for the problem setup (e.g., diminishing marginal values).  The paper could also use some polishing (there are many more small issues in addition to the ones listed below in detailed comments).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review. Thank you for noticing the typos and for suggesting some improvements in the presentation of our approach. We will clarify this part and make the necessary correction in the revision.  \n\nLine 41: Indeed you are right, we will reformulate according to your suggestion.\n\n\n“Auction rule paragraph”: The non-increasing assumption on the values $v_1,v_2,...,v_K$ results from the law of diminishing returns, a standard assumption in microeconomics see [2] chapter 2. It is also a standard assumption in multi-units uniform auction and is studied in [1] in the non repeated setting. We will add these comments just after line 61.\n\nLine 59: We agree and will add that competing bids are adversarial in the abstract\n\nLine 137: The gap with the lower bound is indeed a multiplicative factor of $K^{3/2}$. In that sentence we meant to highlight that under all winner feedback our algorithms upper bound is only worse of a factor $K$ compared to the full-information upper bounds ( $\\mathcal{O}(K^{5/2} \\sqrt{T})$ versus $\\mathcal{O}(K^{3/2} \\sqrt{T})$ ). We take note that it can be ambiguous and will reformulate it. \n\nLine 183: Thank you for noticing, it should be $h_{k+\\frac{1}{2},j} (\\mathbf{b})  = \\mathbb{1} \\left \\\\{ \\exists \\boldsymbol{\\beta} \\in  B_{ \\setminus \\epsilon},  \\\\{x(\\mathbf{b},\\boldsymbol{\\beta})=k \\\\} \\cap \\\\{ (j+1)\\epsilon > p(\\mathbf{b},\\boldsymbol{\\beta}) > j\\epsilon \\\\} \\right \\\\}$ \n\n\n\n\n[1] Ausubel, Lawrence M., Peter Cramton, Marek Pycia, Marzena Rostek, and Marek Weretka. “Demand Reduction and Inefficiency in Multi-Unit Auctions.” The Review of Economic Studies 81, no. 4 (289) (2014): 1366–1400.\n\n[2] Greenlaw, Steven A., et al. Principles of Microeconomics 2e. United States, OpenStax, 2017.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "OBxGg506wG", "reviewer": "Reviewer_VAEZ", "summary": "This work studies the problem of multi-unit uniform price auctions. By introducing a new modeling of the action space, the paper improves the regret of the online learning problem to $\\tilde{O}(K^{4/3}T^{2/3})$ under bandit feedback, and $\\Omega(T^{2/3})$ is a regret lower bound under this feedback model. Under the all-winner (partial feedback), the algorithm achieves a regret of $\\tilde{O}(K^{5/2} \\sqrt{T})$.", "questions": "1. Could the authors provide more intuitions and details on the method of Branzei et al., 2024?\n2. Could the authors provide some intuitions on Algorithm 2, the weight-pushing sampling? In my sense, this algorithm makes a sequential sampling of all $h$'s in $\\mathbf{h}$. Please correct me if I am wrong. \n3. In bandit and all-winner feedback models, why do you need to subtract $K$ in the numerator of the estimator? Could you please provide some intuition on this by comparing it with your treatment in the full feedback model where you do not do this step?", "limitations": "The authors have addressed the limitations of their work.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The main strength of this work is to provide a new modelling of the action space to largely improve the regret of the considered problem. This new finding, together with the improvement, if correct, already makes a solid contribution in my view.", "weaknesses": "The manuscript has the following weaknesses in my view: \n1. Although the all-winner feedback model could be first raised in the multi-unit auctions, other similar partial feedback models have already been introduced in different settings, e.g., Chen et al., 2024. \n2. The paper's method is an improvement over the method of Branzei et al., 2024, as claimed. Yet, the authors do not provide details on their DAG equivalence method, which makes it a bit hard to appreciate all the details of the newly proposed method. \n3. The authors could provide more intuitions on some technical details; see Questions. \n4. There seems to be an extra \"}\" in Equation (4); And should Equation (6) be $b_k \\geq (j + 1) \\epsilon \\geq j \\epsilon \\geq b_{k + 1}$?\n\n[Ref]  \nChen et al., Dynamic Budget Throttling in Repeated Second-Price Auctions, AAAI 2024.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review.\n\nW1. The all-winner feedback model is indeed a particular case of partial feedback that is widely studied. However, it has never been studied in multi-unit auctions which is the focus of our study. We will clarify this in the related work section. \n\nW2/Q1. The key idea in [1] is the decomposition of the utility in a sum of terms where each term only depends on two consecutive bids. They therefore associate to every set of bids a path and the utility is seen as the sum over the utility of each edge. In contrast, we are able to decompose the utility as a sum of terms that can be estimated individually (without any need for a dependency in previous terms) and therefore obtain improved guarantees.\n\nW4.  Indeed equation (4) has an extra “}“ and equation (6) should be $b_k \\geq (j+1) \\epsilon >  j \\epsilon \\geq b_{k+1}$.\n\nQ2. Your understanding is correct. Algorithm 2 indeed performs a sequential sampling of the $h$’s in $\\mathbf{h}$, this allows for both a more efficient sampling and the use of specific weights for each $h$, see [3] for a more complete overview.  One could also directly sample $\\mathbf{h}$, ensuring the weights of each $\\mathbf{h}$ are the sum of all the weights of their components $h$’s. Intuitively this would have a higher complexity cost as it would sample in the product space instead of successively in each space. (for $N,M$ integers computing weights and sampling once in $[N]^M$ is exponentially less efficient than computing weights and sampling $M$ times an element of $[N]$).\n\nQ3. Subtracting $K$ in the numerator is a technical detail which ensures that the value the estimator $\\hat{u}^t(\\mathbf{h})$ takes can be upper bounded which is necessary for the analysis of EXP3.\nIn the full-information feedback, we directly use the utility (and not an estimator) $u^t(\\mathbf{h})$, which is already upper bounded by $K$. The difference between Hedge and Exp3 is discussed in [2] notes 11.5 remark 3.\n\n\n[1] Brânzei, Simina, et al. \"Learning and collusion in multi-unit auctions.\" Advances in Neural Information Processing Systems 36 (2024).\n\n[2] Lattimore, Tor, and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.\n\n[3] TAKIMOTO, Eiji et WARMUTH, Manfred K. Path kernels and multiplicative updates. In : International Conference on Computational Learning Theory. Berlin, Heidelberg : Springer Berlin Heidelberg, 2002. p. 74-89.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "fHyYDpuhK0", "reviewer": "Reviewer_XwZ3", "summary": "This paper considers online learning in repeated multi-unit uniform price auctions, motivated by the strategic participation of electricity producers in the electricity day-ahead market. By introducing a new modeling of the action space to EXP3, the authors propose an algorithm that achieves $\\tilde{O}(K^{3/2}\\sqrt{T})$, $\\tilde{O}(K^{5/2}\\sqrt{T})$, and $\\tilde{O}(K^{4/3}T^{2/3})$ regret bounds for full information, all-winner, and bandit feedback, respectively. They also provide lower bounds for each case.", "questions": "1. Could you provide a motivating example to justify the allocation policy in setting (1)? According to (1), it seems that multiple players may receive the same item, which may not be convincing to me.\n\n2. According to the paper, the valuation $v_l$ is known to the bidder. What is the motivating example?", "limitations": "The authors have addressed some of the open problems in the conclusion.", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. They provide regret bounds for various feedback settings: full feedback, partial feedback, and bandit feedback.\n2. The proposed algorithm improves the regret bound by using a new model of the action space.", "weaknesses": "1. I think that the setting is not clearly written and seems to differ from previous work [1] without justification. In more detail, for the allocation described in (1), for player $i$, any items with a value larger than a price are allocated. However, in [1], the auctioneer allocates the $j$-th unit to the player who submitted the $j$-th highest bid. Additionally, the role of the valuation $v_l$ is not clearly described. \n\n2. The motivation for the allocation policy in this setting may not be well described.\n\n\n[1]Brânzei, Simina, et al. \"Learning and collusion in multi-unit auctions.\" Advances in Neural Information Processing Systems 36 (2024).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review. \n\nW1/Q1 It is inexact to say that our setting is not the same as in [1]. While the way our allocation policy is described indeed differs from the description in [1] it results in the same allocations as allocating the $j^{th}$ items to the $j^{th}$ highest bid. \nIndeed, since all items are identical, it is sufficient to keep count of how many bids from player $i$ are above the price (and hence amongst the $K$ highest). Therefore  strictly allocating the $j^{th}$ items to the $j^{th}$ highest bid and allocating one item for each bid in the $K$ highest gives the same allocation (as permuting identical items does not change the allocation).\nWhile it is possible for two players $i,k$ to have the same allocation $x_i(\\mathbf{b})=x_k(\\mathbf{b})$ this only means they get allocated the same number of items. \nWe take note that this might not be straighforward and will ensure to make it clearer. \n\nW2. Multi-unit auctions with uniform pricing and the associated allocation rule [1] used in this paper is a natural model for the short-term electricity market. We give some references l99.\n\n\nQ2.  From both a motivation and technical point of view, it is reasonable to assume some knowledge of the valuations :\n- The value is a quantity that represents how useful each item will be to the bidder. In that sense, any bidder trying to acquire items should have some knowledge of the valuation of this item $\\textit{for them}$. \n- We are studying the adversarial opposing bid setting, yet, as pointed out in [2] without any assumption on the valuation (ie adversarial valuation that can vary across auctions) no non-trivial regret guarantees can be obtained. Since their setting ( first price single item auction with valuation observed before each round ) is strictly easier this impossibility result also applies to multi-unit uniform auctions.\n\nWe chose to focus on known valuation as it allows for a more concise and understandable analysis. Another possible model would be to assume that valuations are unknown but constant across auctions and that a noisy version of the valuation is observed whenever an item is won. Adapting our algorithm to this setting would require to use estimates of valuations instead of the real values. We leave this adaptation to future work as we believe the main ideas of our work are easier to get in the setting we consider.\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n[1] Brânzei, Simina, et al. \"Learning and collusion in multi-unit auctions.\" Advances in Neural Information Processing Systems 36 (2024).\n\n[2] Balseiro, S., Golrezaei, N., Mahdian, M., Mirrokni, V., & Schneider, J. (2019). Contextual bandits with cross-learning. Advances in Neural Information Processing Systems, 32.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This manuscript studies the problem of online learning in repeated multi-unit uniform price auctions, an important auction format in the electricity market. The main contribution is the improvements over the regret bounds in [Branzei et al. 2024], mainly an improvement from $O(T^{3/4})$ to $O(T^{2/3})$ in the upper bound, and an improvement from $\Omega(T^{1/2})$ to $\Omega(T^{2/3})$ in the lower bound, both under the bandit feedback. The improved upper bound uses a clever and novel representation of the action space, together with a decomposition of the utility into a sum of functions of independent actions, rather than the action pairs in [Branzei et al. 2024]. The lower bound uses a simple reduction to first-price auctions with binary feedback when the LAB pricing rule is used; no improvement for the FRB pricing rule is available though. The reviewers unanimously appreciate the new action representation and utility decomposition, and I would also like to join the reviewers and recommend acceptance.
Decision: Accept (poster)