Learning Safe Strategies for Value Maximizing Buyers in Uniform Price Auctions
Authors: Negin Golrezaei
Sourav Sahoo
Venue: ICML 2025 poster (2025)
Keywords: multi-unit auctions
value maximizers
bidding strategies
online learning
Primary area: general_machine_learning->online_learning_active_learning_and_bandits
TL;DR: We propose a class of bidding strategies for value maximizing buyers in uniform price auctions that are easy to characterise, efficiently learnable and robust against significantly stronger benchmarks.

Abstract: We study the bidding problem in repeated uniform price multi-unit auctions from the perspective of a single *value-maximizing* buyer who aims to maximize their cumulative value over $T$ rounds while adhering to return-on-investment (RoI) constraints in each round. Buyers adopt $m$-*uniform bidding* format, where they submit $m$ bid-quantity pairs $(b_i, q_i)$ to demand $q_i$ units at bid $b_i$. We introduce *safe* bidding strategies as those that satisfy RoI constraints in every auction, regardless of competing bids. We show that these strategies depend only on the bidder’s valuation curve, and the bidder can focus on a finite subset of this class without loss of generality. While the number of strategies in this subset is exponential in $m$, we develop a polynomial-time algorithm to learn the optimal safe strategy that achieves sublinear regret in the online setting, where regret is measured against a clairvoyant benchmark that knows the competing bids *a priori* and selects a fixed hindsight optimal safe strategy. We then evaluate the performance of safe strategies against a clairvoyant that selects the optimal strategy from a richer class of strategies in the online setting. In this scenario, we compute the *richness ratio*, $\alpha\in(0, 1]$ for the class of strategies chosen by the clairvoyant and show that our algorithm, designed to learn safe strategies, achieves $\alpha$-approximate sublinear regret against these stronger benchmarks. Experiments on semi-synthetic data from real-world auctions show that safe strategies substantially outperform the derived theoretical bounds, making them quite appealing in practice.

Learning Safe Strategies for Value Maximizing Buyers in Uniform Price Auctions
Negin Golrezaei'
Souray Sahoo!
Abstract
multiple units, with the per-unit price set the Kth highest bid. These auctions are widely used to allocate scarce re- sources in critical markets such as emissions permits, energy markets, and Treasury auctions. To succeed in these mar- kets, bidders must develop effective bidding strategies that balance long-term value maximization with financial risk management, all while operating under limited information, uncertainty in competing bids and strategic (or adversarial) behavior of other bidders, among other challenges.
We study the bidding problem in repeated uni- form price multi-unit auctions from the perspec- tive of single maxximiing buyer who aims to maximize their cumulative value over T rounds while adhering to return-on-in -nneeetennn (Rol) con- straints in each round. Buyers adopt m-umiform bidding format, where they submit m bid-quantity pairs (be, 4)) to demand di units at bid b;- We in- troduce safe bidding strategies as those that sat- isfy Rol constraints in every auction, regardless of competing bids. We show that these strategies depend only on the bidder's valuation curve, and the bidder can focus without loss of generality. While the number of strategies in this subset is exponential in m, we develop a polynomial-tie time algorithm to learn the optimal safe strategy that achieves sublinear re- gret in the online setting, where regret is measured against clairvoyant benchmark that knows the competing bids priori and selects fixed hind- sight optimal safe strategy. We then evaluate the performance of safe strategies against a clairvoy- ant that selects the optimal strategy from a richer class of strategies in the online setting. In this see- nario, we compute the richness ratio, a E (0, 1] for the class of strategies chosen by the clairvoy- ant and show that our algorithm, designed to learn safe strategies, achieves a- a-approximate sublinear regret against these stronger benchmarks. Exper- iments on semi-synthetic data from real-world auctions show that safe strategies substantially outperform the derived theoretical bounds, mak- ing them quite appealing in practice.
In this paper, we model the bidders value-maximizing agent with per-round ceturn-on-investinne (Rol) constraints. This model reflects real-world decision-making in industries where managing financial risks is as critical as maximizing value. Unlike traditional mechanism design, which assumes bidders with quasilinear utility (i.c., utility decreases linearly with payments), many practical settings involve bidders who optimize total value while adhering to financial constraints such as Rol or budgets. These scenarios frequently arise in industries where agents or algorithms bid on behalf of clients, optimizing for high-level objectives within strict con- straints context akin to the principal-agent framework (Fadaei & Bichler, 2016; Aggarwal et al., 2024). Examples include autobidders in online advertising, where advertis- ers seek to maximize clicks while keeping the average cost per click below a threshold (Lucier et al., 2024; Balseiro et al., 2021a; Deng et al., 2023b), and consultants bidding for small firms in emission permit auctions (EEX, 2024).
finite subset of this class
Building on this, we study the bidding problem in repeated uniform price auctions over T rounds, from the perspective of a single bidder who seeks to maximize cumulative value while adhering to per-round Rol constraints that is, ensur- ing that the value obtained in each round is at least fixed multiple of the corresponding payment (see Eq. (2)).
To address practical bidding interfaces, we assume bidders adopt m-uniform bidding format, a generalization of the uniform bidding format (De Keijzer et al., 2013; Birmpas et al., 2019) for some E N. In m-uniform strategy b = ((bi, (r)..,................ (bm, {m))), )), bidders bid bj for the first gi units, by for the next 4 units and so on (see Definition 1).
1. Introduction
In uniform price multi-unit auction, the auctioneer sells K identical units of single good to buyers who may demand
'Massachusetts Institute of Technology, Cambridge, USA. Cor- respondence to: Sourav Sahoo Esourav99@mit.cduu.
1.1. Our Contributions
Proceedings of the nnnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
Safe Bidding Strategies (Section 3). To ensure that the bidder satisfies the Rol constraint without knowing the com-

---

Learning Safe Strategies for Value Maximizing Buyers in Uniform Price Auctions
peting bids, we introduce the concept of safe bidding strate- gies. These strategies guarantee that the Rol constraint is met regardless of how the other participants bid. We then identify the class of m-uniform safe undominated bidding strategies, denoted by 8,, (Theorem 3.2), and demonstrate that the strategies within this class depend solely on the bidder's valuation vector [u),..., vK] and exhibit a "nested" structure (illustrated in Fig. 1).
dence on T in the regret bound improves from T vT implying that it is easier learn safe strategies for value maximizers compared to bidding strategies for quasilinear utility maximizers.
Richer Classes of Strategies for the Clairvoyant (Sec- tion 5), A key novel aspect of our work is to evaluate the performance of safe bidding strategies with most m bid-quantity pairs and the online learning algorithm from Section 4 against a clairvoyant that selects the optimal strat- egy from richer class of strategies. In this case, the bid- der (learnr)) achieves a-approximate sublinear regret (same as Theorem 4.3) for a parameter a E (0, 1] deefined as the richness ratio- setio-thereby demonstrating the robustness of the safe bidding strategies against a broad range of bench- marks (Corollary 5.2). One of our main contributions is to compute the richness ratio, a, for various classes of bidding strategies. Specifically, when the clairvoyant selects the optimal bidding from the class of
1/2
2/8
21o
aha
W7
Figure 1. Nested structure of the bidding strategies in Sg. Consider the strategy ((w3, 3), (w7,4), (wa, 2)} E 83. where we note that Q1 = 3. Q2 = 3 ++ 4 = 7 and Q2 = 3 + 4 + 2 = 9. The 1th highest bid (i.e., by) is the average of the first Q3 entries of the valuation vector, i.e., by- = wa,, where wi- = } Eegs ve.
(a) strategies that are Rol-feasible, not necessarily safe and have at most m bid-quantity pairs, we get a = 2. notably independent of m (Theorem 5.3).
Learning Safe Bidding Strategies (Section 4). Designing an algorithm to learn the optimal safe strategy with at most m bid-quantity pairs poses significant challenges due to the exponential size of the decision space in m. So, we first con- sider an offline setting where the competing bids are known in advance. In this setting, we construct polynomial-sizer directed acyelic graph (DAG) with carefully assigned edge weights and show that determining the maximum weight path in the DAG is equivalent to computing the optimal safe strategy with at most m bid-quantity pairs (Theorem 4.2).
(b) safe strategies with most mn' bid-quantity pairs, where m' 2 m, we obtain
m/ (Theorem 5.4).
(c) strategies that are Rol-feasible, not necessarily safe and have at most m' bid-quantity pairs, where m' 2 m, we get that a = m 2m
(Theorem 5.5).
Computing a involves two key challenges: (a) deriving an upper bound on the ratio between the value obtained by the clairvoyant's 's optimal strategy and that of the optimal safe strategy in the worst case (see Definition 4 for details), and (b) proving that this upper bound is tight. The key ideas for deriving the upper bound are outlined in Section 5. The construction of problem instances, each tailored to specific strategy class, is non-trivin toivialvial due to their exponential size in m and the need for a careful choice of competing bids and the valuation vector, detailed in Appendices D. to D.4. Simulations using semi-synthetic data show that the empir- ical richness ratios in practical scenarios are significantly better than the theoretical bounds, making safe strategies highly appealing in practice (Section 5.3).
Building on this, we develop an online learning algorithm when the competing bids are unknown.' Our algorithm runs in polynomial time and achieves regret of Õ(M VmTT) in a full-information setting and (m 3/2 V2V regret in a bandit setting, where the clairvoyant selects the fixed hind- sight optimal safe strategy (Theorem 4.3). Additionally, we establish a regret lower bound of ((M (Theorem 4.4).
The problem of learning to bid in multi-unit uniform price and pay-as-bid auctions has been explored recently by Brânzei et al. (2023); Galgana& & Golrezaei (2024); Pot- fer et al. (2024), assuming the bidders are quasilinear utility maximizers. Our work differs from them in two key ways: (a) we consider value-maxinn maximizing buyers with Rol con- straints, fundamentally different behavioral model, and (b) from technical perspective, unlike prior works that require bid spaces to be discretized, our approach does not, due to the structure of safe strategies. Consequently, the time complexity becomes independent of T in both online and offline settings 2, and under bandit feedback, the depen-
1.2. Related Work
Value Maximizers and RoI Constraints. The concept of agents as value maximizers within financial constraints is a well-established notion in microeconomic theory (Mas- Colell et al., 1995). In mechanism design literature, one of the earliest explorations of aalue-maximizing agents was conducted by Wilkens et al. (2016). Their work primar-
I 'For detailed discussion on leveraging offline algorithms for no-regret learning, we refer readers to Roughgarden & Wang (2019); Niazadeh et al. (2022); Brânzei et al. (2023).
as that in the online setting. In the online setting, time complexity refers to per-round running time.
2 AAssuming the discretization level in the offline setting same
2

---

Learning Safe Strategies for Value Maximizing Buyers in Uniform Price Auctions
ily delved into the single-parameter setting, characterizing truthful auctions for value maximizers. Similarly, Fadaei & Bichler (2016) and Lu et al. (2023) studied truthful (approx- imate) revenue- maximizinn mechanisms in combinatorial markets tailored for such agents.
that has diminishing marginal returns property, i.e., v1,1 2 1i,2 2 ... 2 vi.K which is standard in literature (Brânzei et al., 2023; Goldner et al., 2020). As we study optimal bidding strategies from the perspective of a single bidder, we drop the index i when the context is clear. The maximum total demand for bidder i, denoted by M E [K], is defined as min E [K 1] : Mj+1 = =0). If such an index does not exist, we set M as K. Hence, without loss of generality, we assume v E R.M. For each [e1,.... UM]. we define the average cumulative valuation vector as [w],.... Warl.
In recent years, there has been growing interest in Rol- constrained value maximizers, particularly in the context of autobidding and online advertising. One of the earliest works in this area is Golrezaei et al. (2021), which studied auction design for Rol-constrained buyers and validated the presence of such soft financial constraints using data from online ad auctions. Broadly, the literature in this space can be divided into two categories: (i) works that design opti- mal auctions under Rol constraints (Balseiro et al., 2021 la;b; 2022; Deng et al., 2021; 2023b), and (ii) works that char- acterize optimal bidding strategies and/or develop learning algorithms in repeated auction settings (Aggarwal et al., 2019; Deng et al., 2023a; Golrezaei et al., 2023; Castiglioni et al., 2024; Aggarwal et al., 2025; Lucier et al., 2024). Our work primarily aligns with the latter. We study value- maximizing buyers in uniform price auctions under Rol constraints and demonstrate that these buyers can employ safe bidding strategies that are efficiently learnable and ro- bust against variety of strong benchmarks.
1 Σ ve Vj E E
where w = j
(I)
As 0i 2 2...2 UM, we also have wi 2 2 WM.
2.1. Auction Format and Bidders' Behavior
Allocation and Payment Rule. In a uniform price auction, each bidder submits a sorted bid vector b using m-uniform bidding language (see Definition 1). The auctioneer collects the bids (entries of the bid vector) from all the bidders, sorts them in non-increasing order, and allocates units to the bidders with the top K bids (also termed as 'winning' bids), That is, if bidder has j bids in the top K positions, they are allocated j units. For ease of exposition, we assume there are no ties (or ties are always broken the favor of the bidder in consideration). See Appendix F for our discussion on handling ties. We assume the auction follows the last- accepted- bid payment rule (bidders pay the Ktth highest bid per unit) which is widely used for uniform price auctions in practice (Regulations, 2019; Garbade & Ingber, 2005).
Multi-unit Auctions. In this work, we focus on a subset of combinatorial auctions termed as multi-unit auctions in which multiple identical goods are sold to a group of buy- ers.² These auctions find widespread application in various practical scenarios, including Treasury auctions (Hortaçsu & McAdams, 2010), procurement auctions (Cramton & Ausubel, 2006), electricity markets (Tierney et al., 2008), and emissions permit auctions (Schmalensee & Stavins, 2017). While several works have focused on studying the equlibria properties in these auctions (Ausubel et al., 2014; 4;; Markakis & Telelis, 2015; De Keijzer et al., 2013), comput- ing equilibrium strategies is usually intractable in general valuations. As result, a growing body of work has emphasized on design- ing optimal bidding strategies in prior-free setting, i.e., without any assumptions of the competing bidders' bids or valuations (Galgana& & Golrezaei, 2024; Potfer et al., 2024; Brânzei et al., 2023). Our work contributes to this literature by learning optimal strategies for value- maximiinng buyers in repeated uniform price auctions.
Let B_ denote the bids submitted by all bidders except bid- der i and o (1) be the jth smallest among the top K compet- ing bids (i.e., bids from all bidders except bidder i). Suppose bidder i submits b, such that the bid profile is B (b: Let rr(3) and p(3) denote the number of units allocated to bidder and the clearing price (i.e., the per-unit price which is the Ttth highest submitted bid), respectively. The total value obtained by the bidder is V(3)- = Σj Uy while the total payment made is P(B) = p(B) I(3).
multi-unit auctions due to
Bidding Language. Multi-unit auctions allocate a large number of identical units, requiring efficient ways for the bidders to express preferences. A common approach is stan- dard bidding, where bidders submit a vector of bids, one for each unit (Brânzei et al., 2023; Galgana & Golrezaei, 2024; Babaioff et al., 2023; Birmpas et al., 2019; Potfer et al., 2024). Although expressive, this becomes computationally impractical when the number of units, K, is large, as in EU ETS emission permit auctions and Treasury auctions. To address this, we consider bidding language called m- uniform bidding, for any m E N. 4 In m-uniform bidding,
2. Model
Preliminaries. There are n buyers (bidders) indexed by i E [m), and K identical units of a single good. Each bidder i has a fixed, private valuation curve, denoted by V, E TRK
For comprehensive survey combinatorial auctions, we refer the readers to several excellent works by De Vries & Vohra (2003); Blumrosen & Nisan (2007); Palacios-Han Huerrta et al. (2022).
*This format generalizes the unifform bidding format (De Kei-
3

---

Learning Safe Strategies for Value Maximizing Buyers in Uniform Price Auctions
bidders submit m bid-quantity pairs (b;; qt). where b, is the bid value per unit and qi is the quantity demanded:
2.2. Learning to Bid in Repeated Settings
In practice, most multi-unit auctions, such as emission per- mit auctions and Treasury auctions, conducted in re- peated setting. Formally, the auction described in the previ- ous section takes place sequentially over T rounds indexed by L E [7'. We assume that the valuation vector v is fixed over the T rounds which is a standard assumption in the literature (Brânzei et al., 2023; Galgana & Golrezaei, 2024; Potfer al., 2024). Similarly, the target Rol is also assumed to be fixed over the T rounds.
Definition 1 (m-Unnffom Bidding). For a fixed m E N, m- uniform bidding strategy is characterized by m bid-quantity pairs, denoted as b == ((b1, q1),................. (bm. qm)),, where bj > b2 > > m > 0 and 4j > j. E [m]] This m-uniform bid can be equivalently expressed as a vector (similar to the standard bidding format) in which the first qi bids are bt. followed by 92 bids of b2, and
We define b[1 f = ((b1, ((b1,q1)... qI).... (be. qe)). for all l < m, to represent the first & bid-quantity pairs within a m- uniform bidding strategy b- = ((b1, q1)..... (bm. qm))). We further define Q; = -' ae for all j E [m]] as the total quantity demanded in the first j bid-quantity pairs, with Qo = 0, where we assume, without loss of generality that Qm S M. If M, the bidding format equivalent to standard bidding but in practice, bidders often submit only few bid-quantity pairs. For instance, in the 2023 EU ETS auctions, bidders submitted ~ 4.35 bid-quantity pairs per auction on average (EEX, 2023).
We now extend the notations from the previous section to the repeated setting. Formally, in this setting, 3 denotes the bids submitted by all bidders except bidder i in round and () 3-6²) is the 5th smallest among the top K competing bids in round I. In round 4, if bidder i submits a bid b', the bid profile is f := (b'; 3b) Let x(3²) and p(3*) denote the number of units allocated to bidder i and the clearing price, respectively, in round t. The total value obtained by the bidder is V(Ø*) = Ejsn(Br UJ, while the total payment made is P( = (113))x((B))
-
The bidders maximize their total value obtained while adhering to constraint that ensures the total value obtained in an auction is at least a constant multiple of the payment in that auction. This can be equivalently expressed as a return-on inveestenntt (RoI) constraint:
Bidders' Behavior.
RoI Constraints in Repeated Setting. In the repeated setting, we require the bidders to satisfy the Rol constraint described in Eq. (2) in every round. A bidding strategy is called feasible for sequence of competing bids (B=)<e()) if the Rol constraint is satisfied for every round t E [T]. Remark 2.1 (Rol Constraints). Our notion of Rol constraints in the repeated setting aligns with the definitions in Wilkens et al. (2016; 2017); Lv et al. (2023). Similar constraints are considered by Lucier et al. (2024) and Gaitonde et al. (2023), termed as marginal Rol (or value) and maximum bid constraints (up to scaling factors), respectively. Unlike the aggregate constraints over T rounds typically assumed in online ad auction literature (Deng et al., 2021; 2024; Feng et al., 2023; Deng al., 2023a), we enforce Rol constraints for each auction individually. This distinction reflects the fundamental differences between the two settings: ad auc- tions often occur simultaneously and frequently, with values in the order of cents, whereas Treasury and emission permit auctions occur sequentially over longer horizons, with units valued in millions. Hence, bidders in such auctions priori- tize profitability in each auction rather than waiting for an indefinite period, leading to per-round Rol constraints."
V(b: 2 (1+))
Here, y is defined as the target Rol which is private and fixed. Without loss of generality, equivalently the valuation curve v is scaled by _ for the rest of this work. For 7 0, the Rol constraint implies the value obtained in an auction is at least the payment. We illustrate how the auction operates in Example 1.
assume y = 0 (or
Example Consider an auction with n = 2 bidders, and K 5 identical units. The valuations are: Vi [6, 3, 1, and V22 = [5,3, 1, 1,0). Both the bidders are value maximizing buyers with target Rol, 7I = 72 O. Suppose m = 2 and the bids submitted by the bidders are b = ((, 2). (3.3) and by = {(4,2) 2), (2, 2))- The bid pro- file: 3 = 15, 5, 4, 4, 3. 3. 3, 2, 2] and top K = 5 winning bids are [5. 5, 4, 3). Bidder 1 allocated 3 units as they have 3 bids (underlined) in the winning bids, and bidder 2
gets the remaining 2 units. The clearing price p((3) 3,
(2( = 6 + 4 + 3- 13, (2) = 5 5 3 8, (13) = 3 3- = 9, and P2( = 2 3- = 6. The Rol constraint is
2.3. Objective and Performance Metric
We consider an online setting where a bidder seeks max- imize cumulative value while satisfying Rol constraints
satisfied both the bidders as 13* > 9 and 8 > 6.
jzer et al., 2013; Birmpas et al., 2019) and aligns with practical languages like those in product-mix auctions (Klemperer, 2009) and piecewise- linear bidding (Nisan, 2015).
'Although EU ETS emission permit auctions are scheduled to occur regularly, regulations stipulate that an auction may be canceled if the bidders' demand falls short of the supply of permits or if the clearing price of the auction does not meet the reserve price (Regulations, 2019). Hence, the bidders more likely ensure Rol feasibility each round.
'Suppose the bidder bids for, and wins more than M units. There is no additional value being allocated over M units, but the total payment increases (assuming the clearing price is positive), potentially violating the Rol constraint.
4

---

Learning Safe Strategies for Value Maximizing Buyers in Uniform Price Auctions
and managing uncertainty about competing bids. In this setting, bidders privately submit their bids, and the auction- eer allocates items and sets prices based on these bids. In round t, the learning algorithm maps the feedback informa- tion set from the first t - 1 rounds, denoted by Z to a bid b', where this mapping may be deterministic or ran- dom. Under full information feedback, the information set I'-1 ((*,, ..?...... .........)) which includes all bids from previous rounds. In the bandit setting, the information set I--1 = (V(3*), (V(3),,((3)) P((*),... V(3 P(3--1) includes only the value and price outcomes of the previous rounds.
3.1. Characterizing Safe Bidding Strategies
We begin by defining underbidding (overbidding) under the m-uniform bidding format in the given context. Recall that in single-item auction, if the value of the item is v, then bid b is an underbid (overbid) if b < v (b > v). Definition 3 (Underbid and Overbid). A m-uniform bidding strategy b = ((b1, qi),..., (bm, qmm) is an
(a) underbidding strategy if by S WQ,, Vj E [m]] and B e [m] such that by < wQ.-
(b) overbidding strategy if E6 [m]] such that by > wor-
We design learning algorithms to minimize regret, the dif- ference in the value obtained by a fixed mandsiiht-optimall strategy chosen by clairvoyant with a priori knowledge of competing bids and that by the learner over time. Formally,
Underbiddding
Overbidding
REG-
max BEB
V(b;
Σ ElV('';
(3)
where the expectation is with respect to any randomness in the learning algorithm. Here, B is the class of bidding strate- gies (formally characterized in Section 3). We require the bidding strategies B to be Rol feasible for the sequence of competing bids [ )ee(r)- In Section 4, we consider the case when the both the clairvoyant and the learner choose strategies from the same class and aim to obtain sublinear regret. Later, we consider more challenging settings where the clairvoyant can choose the optimal strategy from much richer classes of strategies compared to the learner. In these cases, we obtain sublinear a- a-approximate regret, where a (0, 1] is the richness ratio (see details in Section 5).
92
92
Q2
Figure 2. The solid line represents the average cumulative valua- tion curve, w, and the dotted line represents the valuation curve, v. The figure in the left (resp. right) illustrates underbidding (resp- overbidding) for a 2-uniform bidding strategy. Note that the no- tions of underbidding and overbidding in Detinition 3 are defined with respect to w and not v. Here, the plots of and w are shown to be linear for illustrative purposes only.
In other words, if 7 0, b = ((b, (1b1,9))..... (hm 9m)) is underbidding strategy if, for all E [m]]. the bid by is at most the average of the first Q2 entries of the valuation vector, denoted as wo,, and there exists & E [m]] where the inequality is strict. Recall that Q2- = =ess le denotes the maximum number of demanded units in the first j bid- quantity pairs. Similarly, b is an overbidding strategy if there exists some & [m]] such that be is strictly greater than the average of the first Qe entries of the valuation vector. Having defined the notions of overbidding and underbidding, we characterize the class of safe bidding strategies, Sm:
3. Safe Bidding Strategies
Recall that strategies chosen by the learner must be causal (mapping the history to a bidding strategy) while remaining Rol feasible for all rounds t E [T], even under adversarially generated competing bids. This creates an obvious chal- lenge: a bidding strategy that satisfies Rol feasibility in pre- vious rounds may become infeasible even under the slightest change in the competing bids e.g., if v J0.9, 0.5, 0.1], the bidding strategy (0.6,3 3) is Rol feasible for competing bids e = [0.61, 0.59, 0.59 but not for 3 = [0.59, 0.59, 0.59). To address this, we focus on safe bidding strategies that inherently guarantee Rol feasibility, regardless of the adver- sarial behavior of competing bids:
Theorem 3.1. For any m E N, no overbidding is allowed in S.n. So, the collection of all m-uniform safe strategies is
8. = ={b= (bb (bms 9m)) be S &wq Vl [ml]
where w is defined in Eq. (1).
Definition 2 (Safe Strategies). A m-uniform bidding strat- egy, b- = ((b,, g1)..., , (bm; {m)), is called a safe strategy if it is feasible irrespective of the competing bids, i.c.,
The proofs of this section are presented in Appendix A. Since there are infinitely many safe strategies in Sn, we
V(b;B_) 2/12/ P_b vB_
"In Definition 3 (and throughout the paper), we assume 7 = 0 without loss of generality for case of exposition. Fig. 2 illustrates how different values of y impacts the results. Specifically, for any y 2 O underbidding and overbidding defined with respect the scaled average cumulative valuation curve, w
The class of all m-uniform safe bidding strategies is denoted as Sm. The union of classes of safe bidding strategies with at most m bid-quantity pairs is denoted as Um = Uke[m) 8k-
14.7
5

---

Learning Safe Strategies for Value Maximizing Buyers in Uniform Price Auctions
focus on the subset of safe undominated strategies, Sm. ob- tained by removing very weakly dominated strategies. A safe strategy b is said to be very weakly dominated if there exists another safe strategy b' such that, for any compet- ing bid _3_. V(b, S V(b', (Shoham & Lyyton- Brown, 2008, pp. 79). Keeping these strategies does not improve the bidder's performance, but removing them yields finite strategy class (as shown below), which significantly simplifies the design of online learning algorithms. We now present the main result of this section:
be decomposed across the bid-quantity pairs. Formally, Lemma 4.1. Problem (OFFLINE) can be formulated as
R
T
Q2
ΣΣ 5=1 k=
2k I Leq 2 3
max max [E[m] Q1....Q
1+1
The proofs of this section are presented in Appendix B. Building on the decomposition in Lemma 4.1, we now con- struct an edge-weighted DAG (V, E) as proposed earlier.
Vertices. The DAG has a 'layered' structure with source node (s), destination node (d) and m intermediate layers. The thh intermediate layer contains M M+1-4 nodes, denoted by (f.j) where & E [m].] E {f, E + 1......... M) as shown in Fig. 3. For convenience, we set 8 = (0, 0).
Theorem 3.2. The class of m-uniform safe undominated bidding strategies, Sm is given as follows:
S = -{D- ((bI,))))..... (bm qm)) = u- 6 [ml] [ml}
The union of classes of safe undominated strategies with at most m bid-quantity pairs is denoted by U = Uke(m! S%-
Edges and Edge Weights. A directed edge exists from vertex y under the following conditions:
Observe that S is a finite class of bidding strategies that depend only the valuation curve and is independent of the competing bids. The strategies in St, exhibit "nested" structure, referred to as nested m-uniform bidding strate- gies hereafter, where the jth highest bid (by) is the average of the first Q3 = Σ'=1 qe entries of the valuation curve (illustrated in Fig. 1). Importantly, fixing 2j's 's uniquely determines the bidding strategy, as bj wq, for strategies in S; which will be crucial in learning the optimal safe bidding strategy, as discussed in the following section.
(i) (e - 1, and y (e,j"), Ae [m]] and j < j'. This edge connects consecutive layers in the graph, and its weight is given by:
T
w(e) = Σ
Uk . I wy 2 2-(
(4)
k=j+1
(ii) x = (4.J) and y = d, ve E [m].j E [M. This edge
connects the current layer to the destination node d, and its weight w(e) 0.
4. Learning Safe Bidding Strategies
Layer 1: Q.
Layer 2: Q2
(1.1)
Here, the clairvoyant and the learner choose strategies from the class of safe bidding strategies with at most m bid- quantity pairs, U Thus, the regret defined in Eq. (3)
(1.
(2,2)
d
T
Σv(b; - Σ B 1=1
REG- = max BE U.
(1.3)
(2,3)
To design learning algorithms, we first consider the offline setting, where we aim to solve the following problem given the bid history, [ kem
Figure 3. In this DAG, M = 3, m 2. The red path refers to b ((w), 1), (w3, 2)} E UG. The values in red are the corresponding Q 's. Similarly, the blue path refers to b = (w3, 3) UZ.
max bEU
Σ V(b: 3
(OFFLINE)
Theorem 4.2. * TThrre exists a bijective mapping between the s-d paths in GVV E) and bidding strategies in W i.e. the path s - (1, -
(ki 2x) - d for k E [m] refers to the strategy b ((b,, 91), ... (bk, 9k)) where
Since Ut contains O(M")) strategies, evaluating each strat- egy individually is intractable. To overcome this, we reduce the offline problem to finding the maximum weight path in a carefully constructed edge-weighted directed acyclic graph (DAG), which allows for the computation of the optimal offline bidding strategy in poly(m, M) time.
b = w= and q8 = 22 21-1, [k]. where wne is defined as per Eq. (1), V2 E [k]. Conversely, the strategy b- (wWQ, ((wQ) 91),...,. ... (wQ.. 9k)) maps the path + (1, - .....- -k, Qx) + d.
The value obtained by bidding strategy is the weight of the corresponding s-d path. Thus, the Problem (OFFLInE) is equivalent to finding the maximum weight s-d path in G(V, F.) which can be computed in poly(m, M) time.
4.1. Offline Problem
Fix a bid history. H. = [ lretry and consider (OFFLINE).
The following lemma shows that the objective function can
6

---

Learning Safe Strategies for Value Maximizing Buyers in Uniform Price Auctions
4.2. Online Setting
Theorem 4.3. Algorithm runs in poly(m, M) time per round and achieves REG O(M / log M) under full information feedback, and REG I O(M² /m log M) in the bandit setting.
In the online setting, in each round & E [2], the learner submits strategy b' E Ut and receives feedback from the auction. We consider two feedback models: (a) full informa- tion setting and (b) bandit setting, with the latter discussed in Appendix B. Leveraging the DAG formulation, we design an online learning algorithm such that REG = o(T). Without loss of generaity, assume V/ E [0, 1], Vj E [M]]
Algorithm 2 Update Edge Probabilities
Require: For 2 1, G (V, F.). For t 2 2, additionally require 7) (e) and w/ (e), Ve F.
1: tf
In every round 4, DAG GV, E) is constructed as de- scribed earlier. After receiving feedback at the end of the round, in the full information setting,
- Initialize the edge probability of each edge e = I - as
4 (e) 1/Nval where N₂ is the set of out-neighbors of z.
2: 1r 2
Sct (n- (d) = and recursively compute in bottom-to-top
(f) = - 1. and y = (e,j") with & E [m] and j < <',
fashion for every node u in (V, E):
1 (u) = Σ
(v) .p (e) (xxp(//('(e)))
w'(c) = Σ Uk I wy 2 B [10] [K)
I/w
(5)
k=j+1
- For edge e= u g (V, F), update edge probability:
(ii) If (e,5) and d. then w' ((()) = 0, E [m],j E [M].
('(e) x-) exp()exxppw (w)
(()
The online algorithm in Algorithm consists of three main steps: (1) UPDATE, (2) SAMPLE, and (3) MAP. In the first two steps, the algorithm maintains and updates the probabilities over the edges in the constructed DAG and selects s-d path in the DAG by sampling from these proba- bilities. These steps implement exponential weight updates using the weight-pushing method proposed by Takimoto & Warmuth (2003). Naively implementing exponential weight updates by treating each 5-d path (safe strategy) as an expert intractable as there are ((Mr)) such experts. However, following the decomposition in Lemma 4. Algorithm only needs to maintain weights for individual edges and then sample path based on these weights, avoiding the need to track weights for each path separately. The MAP step is the key component of the algorithm that maps the sampled path to a safe strategy (by Theorem 4.2).
We prove Theorem 4.3 by showing that Algorithm is an ef- ficient (polynomial time) and equivalent implementation of the exponential weight updates algorithm. We complement Theorem 4.3 by establishing the following lower bound.
Theorem 4.4. Suppose M 2 and m 1. Then, there ex- ist competing bids, 1 (e such that, under any learning algorithm, the expected regret [B[RE]] = (2MVT) in both full information and bandit settings.
5. Competing Against Richer Classes of Bidding Strategies
In previous sections, we characterized the class of safe bid- ding strategies and proposed a learning algorithm that obtain sublinear regret, where the regret is computed against a clair- voyant that also selects the optimal safe bidding strategy. In this section, we consider the cases where the clairvoyant can choose the optimal strategy from richer bidding classes, which we will describe shortly. We show that under Algo- rithm 1, the class of safe bidding strategies achieves sub- linear (approximate) regret when competing against these stronger benchmarks. Here, the performance metric is
Algorithm 1 Learning Safe Bidding Strategies (Full Info.)
Require: valuation curve v. time horizon T, learning rate 7) >> 1: for t = 1, ........ T do
2: Construct (VVV Æ) similar to G(V F)) without weights
3: UPDATE: Obtain edge probabilities ())) by Algorithm 2. SAMPLE: Define initial node
and path p¹ s.
4: while لf cl do
5: Sample with probability sp (u v).
T V(b;BL) Σ E(V(b'BL))
6: Append v to the path p": set u + V.
a- REREG max BEB
7: end while
8: MAP: If = +
- 21) some & [m]] submit b' ((b1.q), qq). (be: 4k)) where
+ (k, 24) d for
Here, B, is the class of bidding strategies from which the clairvoyant (which serves as our benchmark) chooses the optimal bidding strategy whereas the bidder (learner) sub- mits bids, b' UC in each round unless stated otherwise and E (0, 1] is defined as the richness ratio.
6 Was and 9
11 AÊ E [k].
where Way is defined as per Eq. (1) for all f E [k]] 9: The bidder observes 3i and sets w' (c) as per Eq. (5).
10: end for
Remark 5.1 (Richness Ratio a). In prior works on approxi- mate regret, a typically measures the hardness of the offline
7

---

Learning Safe Strategies for Value Maximizing Buyers in Uniform Price Auctions
problem, such as maxber. Ei=1 V(b; B²2 (see Streeter & Golovin (2008); Niazadeh et al. (2022)). In contrast, our richness ratio, capturing the relative
5.1. Richness Ratio of m-uniform Non-Safe Strategies
Here, we consider the clairvoyant class Be be the class of bidding strategies containing at most m bid-quantity pairs, which are feasible only for the given bid history H-, rather than for every possible sequence of competing bids as in the case of safe strategies. The following theorem characterizes the richness ratio of this class, denoted as Fm
work reinterprets richness of the clairvoyant's 's strategy class compared to the learner's. Specifically, it quantifies how closely the value achieved by the optimal strategy in U approximates that by the optimal strategy in Be. If B, = U then a = 1 (see Section 4). By considering a richer class of strategies for the clairvoyant, we aim to quantify the robustness and per- formance of safe strategies against stronger benchmarks.
Theorem 5.3. For any m E N, A Aoth 21 S 2. Further-
more, there exist a bid history and valuation curve such that for any 8 E (0, 2) A -n- -1 (H-, v) 2 22 2 8. Thus, the richness ratio of the class 3 is 1/2.
Our main contribution in this section is to compute the richness ratio a for different classes of bidding strategies. To this end, for any Be, define:
Theorem 5.3 implies that restricting the learner to safe bid- ding strategies has a bounded cost and does not lead to an arbitrary loss in the obtained value as the upper bound is independent of m. Building on this, Corollary 5.2 shows that Algorithm I results in - -approximate sublinear regret in the online setting when the safe strategies compete against -th Additionally, the factor-of-two loss represents a worst- case scenario. occurring in a highly non non-trivial setting (see Appendix D.2). In practice, we expect these strategies to perform near-optimally. a claim further supported by the numerical simulations presented in Section 5.3.
uy, = max AB,, ue (H-, v), where v.H-
AB., Uo (H-,V)= m Σts V(b; 33))
max E B2)
for H- = 118-1eetr) In words, As_ is the maximum ratio of the value obtained by the optimal bidding strategy in B, and that by the optimal strategy in Un over all valuation curves and bid histories in offline setting. We drop the argument v from 2rg (H-,V v) when the context is clear.
Definition 4 (Richness Ratio). Suppose the clairvoyant chooses the optimal strategy from B. (which may depend on the bid history, H-) such that AB,, S X, and the bound is tight, i.., there exist a bid history H_. a valuation curve v, and 8 >> such that B,, (H-,v) v) 2 A 5 for any 8 E (0, 8) Then, the richness ratio of B. is a = 1/x.
Proof Sketch of Theorem 5.3 (Upper Bound). We now present the central ideas to prove the upper bound, which are also used to show the subsequent theorems, albeit with changes specific to each case. Fixing bid history, H.,, we consider the expression in Eq. (6). Maximizing over all bid histories and valuation curves, we get the desired result.
The key idea is that if, in the worst-case scenario for the offline problem, the optimal safe strategy achieves no more than a f-fraction of the value obtained by the optimal bid- ding strategy in B., then the learner can achieve at most a x -frcction of that value in the online setting as well. In the subsequent sections,
Firstly, we bridge the we bridge the gap between the bidding strategies of the clairvoyant and the learner by construct- ing a restricted class of safe strategies, Unn (H.) S U This restricted class is exponentially smaller in size and is derived based on the optimal strategy selected by the clairvoyant (see exact characterization in Eq. (17) for Theo- rem 5.3 and Algorithm 3 for Theorem 5.4). We demonstrate that considering this restricted class of safe strategies is sufficient to derive tight upper bounds.
consider different classes of bid- ding strategies for the clairvoyant and compute its richness ratio a. An immediate corollary of Definition 4 is:
Corollary 5.2. Suppose the clairvoyant chooses the optimal strategy from the class B, such that NB., < X and this bound is tight. Then, Algorithm I obtains R- I O(M /mll M) under full information feedback and x REGa, < <O(M2 2 mm log M) under bundit feedback.
Second, as a crucial step, we show that for any m-uniform safe bidding strategy ([wQ, (IIQ,,91)...... .I)...., (wq... : 9m)).
Vbb 3_) = max V( Q));B_)
fE(m)
Proof. As As SAA
for all competing bids 3_, where, Q: = Σド Qj- Thus, the value obtained by any m-uniform safe strategy can be determined by knowing the value obtained by the strategies in Ui allowing us to focus solely on l-uniform strategies.
T
T [V(
A REGss A b
1 max
Σ V(b:
Σ
T Σ
S max bE
BlV
REG
As the third key idea, we partition the T rounds into sets Tj. based on the least winning bid of the optimal bidding strategy chosen by the clairvoyant (see details in Eq. (15)) and derive lower bounds on the value obtained by 1-uniform
1m
By Theorem 4.3, we get the stated regret upper bound.
8

---

Learning Safe Strategies for Value Maximizing Buyers in Uniform Price Auctions
strategies in (H-) in terms of the value obtained by optimal strategy chosen by the clairvoyant in each partition T3. With these three key ideas, we bound the ratio in Eq. (6). The detailed proof is presented in Appendix C.I.
5.3. Estimating The Richness Ratio: A Case Study
In this section, we estimate the richness ratio (equivalently As,, for the discussed classes of bidding strategies by experiments using EU ETS emission permit auction data from 2022 and 2023. Detailed methods are provided in Appendix E, and the results are shown in Fig. 4.
Proof Sketch of Theorem 5.3 (Tight Lower Bound). For any 8 E (0, 1]. we construct a tight lower-bound instance for any m E N by considering an offline problem where M- T = 2 and K M + I, with N = ( We set = [1, r,... ........1) w] E RM, where v = (6)). The sequence of T auctions is divided into 2m partitions of ex- ponentially varying sizes, each with an identical competing bid profile. In each bid profile, there are two types of bids: "big' and 'small'. All 'big' bids are set to C >>>> 1, while the "small" bids remain identical within a partition. The parti- tion sizes, the number of 'small' competing bids, and the exact values of these bids are carefully chosen to ensure that (H=:v)= 2 2 - ā (see Appendices D.1 to D.2). A 2 u.
120
-20
15
113
2115
1.0
100
170
Figure 4. The left (resp. right) figure refers to (the upper bound (H-) (resp. Aug, (H-)) a function of on) 5m Min
Estimating Ay .uc (H-). The left plot of Fig. 4 shows
5.2. Richness Ratio of m'nunfrm Strategies
that (the upper bound for) A A , (H-) is significantly better than the theoretical bound of 2. The decaying trend of the plot with increasing m can be attributed to the fact that are computing an upper bound for the value achieved by the optimal bidding strategy in F which is independent of m, rather than the exact value (see Appendix E.2). For 2 4, even the upper bound of Aym .ug. (H-) 1.05 indicating that the safe bidding strategies are near-optimal.
We first consider the case when the clairvoyant selects the optimal strategy from the class of safe bidding strategies with at most m' bid-quantity pairs where m' 2 m..
Theorem 5.4. For any m, m' E such that m' 2 m, m Additionally, there exist H- and v such
Au a Uin S m". that for any 5 E (0. 21 Auc,, Me, (H..v) 2 m² -. 6. Thus, the richness ratio of the class U is a = m/m'.
m
Suppose the clairvoyant can now select the optimal strategy from -th the class of bidding strategies with at most m' bid-quantity pairs (m' 2 m) that are feasible for the bid history H- [ (e but not necessarily safe. Then, Theorem 5.5. For any m, m.m' E N such that m' 2 m, I 22'' Moreover, there exist H- and v such
Estimating Au;,.u; uu; ). From the right plot of Fig. 4, we observe that the empirical values of Aus, uG (H-) is signifi- cantly better than the worst-case bound m (Theorem 5.4). In fact, the gain obtained by increasing the number of bid- quantity pairs plateaus after m 4 and even for m 10, the ratio of the value obtained by the optimal bidding strat- egy with at most 10 bid-quantity pairs to that by optimal l-uniform bidding strategy is ~ 1.25.
A 9%h Mu
that for any 8 E (0, 2). A
(H-.v) 2 2m 8. Thus, -" 21
the richness ratio of the class 5 R- is a- m m/'m'
Both plots show that the richness ratio is significantly better in practice than the theoretical bounds, suggesting that safe strategies with small are near-optimal in practice.
By Corollary 5.2, for m' 2 m, Algorithm obtains m. my"
approximate (resp. m -pprroxiimtte sublinear regret in the online setting when the clairvoyant draws the optimal strategy from the class of safe (resp. feasible but not neces- sarily safe) strategies with at most m' bid-quantity pairs.
6. Conclusion and Open Problems
We studied bidding in repeated uniform price auctions for a value maximizing buyer with per-round Rol constraints and characterized safe bidding strategies that can be efficiently learnt and are robust against various strong benchmarks. This study suggests several interesting future research di- rections: (I) analyzing bidding strategies in discriminatory- price ("pay-as-bice bidd""" auctions; (2) modeling bidders with time-varying valuations and cumulative Rol constraints; (3) incorporating both RoI and budget constraints for a more realistic model of bidder behavior; and (4) extending the analysis to the more complex setting of combinatorial auc- tions with non -nnidentiaal items.
The richness ratio in Theorem 5.4 and Theorem 5.5 can theo- retically become arbitrarily small as m for a fixed m. However, the bidder has the flexibility choose m; increas- ing m, though, incurs higher space and time complexity for Algorithm 1. Moreover, for any given pair (m,m'). m'), the bound is tight under a highly non-trivial setting (see details in Appendices D.3 to D.4). In practice, as shown in Sec- tion 5.3, the observed richness ratios are substantially better than the theoretical bounds, suggesting that the worst-case scenarios are unlikely to arise in real-world applications.

---

Learning Safe Strategies for Value Maximizing Buyers in Uniform Price Auctions
Impact Statement
133, 2021b.
Balseiro, S., Deng, Y., Mao, J., Mirrokni, V., and Zuo, S. Optimal mechanisms for value maximizers with bud- get constraints via target clipping. Available at SSRN 4081457, 2022.
This is primarily a theoretical work that discusses a class of bidding strategies in multi-unit auctions. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Birmpas, G., Markakis, E., Telelis, O., and Tsikiridis, A.
Tight welfare guarantees for pure nash equilibria of the uniform price auction. Theory of Computing Systems, 63: 1451-1469, 2019.
Acknowledgements
N.G. and S.S. are partially supported by the MIT Junior Fac- ulty Research Assistance Grant and the Young Investigator Award from the Office of Naval Research (ONR), Award No. N00014-21-1-277. We thank the anonymous review- ers whose comments greatly improved the presentation of this manuscript.
Blumrosen, L. and Nisan, N. Combinatorial auctions. Algo-
rithmic game theory, 267:300, 2007.
Brânzei, S., Derakhshan, M., Golrezaci, N., and Han, Y.
Learning and collusion in multi-unit auctions. In Thirty- seventh Conference on Neural Information Processing Systems, 2023.
References
Castiglioni, M., Celli, A., and Kroer, C. Online learning under budget and roi constraints via weak adaptivity. In Proceedings of the 41st International Conference on Ma- chine Learning, 2024.
Aggarwal, G., Badanidiyuru, A., and Mehta, A. Autobid- ding with constraints. In Web and Internet Economics: 15th International Conference, WINE 2019, New York, NY. USA, December 10-12, 2019, Proceedings 15, pp. 17-30. Springer, 2019.
Cramton, P. and Ausubel, L.. M. Dynamic auctions in pro- curement. Handbook of Procurement, pp. 1-21, 2006.
Aggarwal, G., Badanidiyuru, A., Balseiro, S. R., Bhawalkar, K., Deng, Y., Feng. Z.. Goel, G., Liaw, C., Lu, H., Mah- dian, M., Mao, J., Mehta, A., Mirrokni, V., Leme, R. P., Perlroth, A., Piliouras, G., Schneider, J., Schvartzman, A., Sivan, B., Spendlove, K., Teng, Y., Wang, D., Zhang, H., Zhao, M., Zhu, W., and Zuo, S. Auto-bidding and auctions in online advertising: A survey. SIGecom Exch., 22(1):199183, 2024. doi: 10. 445/3699822.3699888
De Keijzer, B., Markakis, E., Schäfer, G., and Telelis, O. Inefficiency of standard multi-unit auctions. In European Symposium on Algorithmss pp. 385-396. Springer, 2013. De Vries, S. and Vohra, R. V. Combinatorial auctions: survey, INFORMS Journal on computing, 15(3):284-309, 2003.
Deng, Y., Mao, J., Mirrokni, V., and Zuo, S. Towards effi- cient auctions in an auto-bidding world. In Proceedings of the Web Conference 2021, pp.
Aggarwal, G., Fikioris, G., and Zhao, M. No-regret al- gorithms in non-truthful auctions with budget and roi constraints. In Proceedings of the ACM on Web Confer- ence 2025, WWW '25, pp. USA, 2025. URL httpt:ttp///ccc. /oi. wrg/10../000 /trg/1..115//// 3696410. 3714881.
2021.
Deng, Y., Golrezaei, N., Jaillet, P., Liang, J. C. N., and Mirrokmi, Multi-channel autobidding with budget and roi constraints. In International Conference on Machine Learning, pp. 7617-7644. PMLR, 2023a.
New York, NY,
Deng, Y., Mao, J., Mirrokni, V., Zhang, H., and Zuo, S. Autobidding auctions in the presence of user costs. In Proceedings of the ACM Web Conference 2023, pp. 3428- 3435, 2023b.
Ausubel, L. M., Cramton, P., Pycia, M., Rostek, M., and Weretka, M. Demand reduction and inefficiency in multi- unit auctions. The Review of Economic Studies, 81(4): 1366-1400, 2014.
Deng, Y., Golrezaei, N., Jaillet, P., Liang, J. C. N., and Mir- rokni, V. Individual welfare guarantees in the autobidding world with machine-learned advice. In Proceedings of the ACM on Web Conference 2024, pp. 267-275, 2024.
Babaioff, M., Immorlica, N., Li, Y., and Lucier, B. Making auctions robust to aftermarkets. In 14th Innovations in
Theoretical Computer Science Conference (ITCS 2023).
Schloss Dagstuhl-Leeinizz--a
für Informatik, 2023.
EEX. 2023.
Ecx eua primary auction spot download, com/en/ sha-primary-aucte on- oad.
Balseiro, S. Deng, Y., Mao, J., Mirrokni, V., and Zuo, S.
URL htt.r//atttteeiiooeeeetetaaa-aaa
Robust auction design in the auto-bidding world. Ad- vances in Neural Information Processing Systems, 34: 17777-17788, 2021a.
Accessed on January 17, 2024.
Balseiro, S., Deng, Y., Mao, J., Mirrokni, V. S., and Zuo, S. The landscape of auto-bidding auctions: Value versus utility maximization. In Proceedings of the 22nd ACM Conference on Economics and Computation, pp. 132-
EEX. URL
Auctions participation report, August 2024.
com/ fileadmin/
BBt./aaccess/aaavrrrmtttttaaaaad htr.r//emoonnntaaaaaaaaatteee/// Emissi onssiios__Aie httsssoooos.cuctooo/222220000000
10

---

Learning Safe Strategies for Value Maximizing Buyers in Uniform Price Auctions
pertiicipation_smin_Fir 2024-08-01.
Accessed:
International Conference on Web and Internet Economics, pp. 474-491, 2023.
Fadaei, S. and Bichler, M. Truthfulness and approxima- tion with value- maximizng bidders. In International Symposium on Algorithmic Game Theory, pp. 235-246. Springer, 2016.
Lucier, B., Pattathil, S., Slivkins, A., and Zhang. M. Auto- bidders with budget and roi constraints: Efficiency, regret, and pacing dynamics. In Proceedings of Thirty Seventh Conference on Learning Theory. pp. 3642-3643. PMLR, 2024.
Feng, Z., Padmanabhan, S., and Wang, D. Online bidding algorithms for return-on-spend constrained advertisers. In Proceedings of the ACM Web Conference 2023, pp- 3550-3560 2023.
Lv, H., Zhang, Z., Zheng, Z., Liu, J., Yu, C., Liu, L., Cui, L., and Wu, F. Utility maximizer value maximizer: mechanism design for mixed bidders in online advertis- ing. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pp. 5789-5796, 2023.
Freund, Y. and Schapire, R. E. A theooretc general- ization of on-line learning and an application to boosting. Journal of computer and system sciences, 55(1): 1997.
Markakis, E. and Telelis, O. Uniform price auctions: Equi- libria and efficiency. Theory of Computing Systems, 57: 549-575, 2015.
Gaitonde, J., Li, Y., Light, B., Lucier, B., and Slivkins, A. Budget pacing in repeated auctions: Regret and efficiency without convergence. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023), volume 251, pp. 52, 2023.
Mas-Colell, A., Whinston, M. D., Green, J. R., al. Mi- croeconomic theory, volume 1. Oxford university press New York, 1995.
Niazadeh, R., Golrezaei, N., Wang, J., Susan, F., and Badani- diyuru, A. Online learning via offline greedy algorithms: Applications in market design and optimization. Manage- ment Science, 2022.
Galgana, R. and Golrezaei, N. Learning in repeated multiu- nit pay-as-bid auctions. Manufacturing Service Opera- tions Management, 2024.
Garbade, K. and Ingber, J. The treasury auction process: Ob- jectives, structure, and recent adaptations. Current Issues
Nisan, N. Algorithmic mechanism design: of multiunit auctions. In Handbook of Game Theory with Economic Applications, volume 4, pp. 477-515. Elsevier, 2015.
Through the lens
in Economics and Finance, 2005. URL https: / // /www. newyorkfed.cm wwtp///eaiaaaabbaara/eee.tt
Palacios-Huerte I., Parkes, D. C.,, and Steinberg, R. Combi- natorial auctions in practice. Available at SSRN 3844338, 2022.
Goldner, K., Immorlica, N., and Lucier, B. Reducing ineffi- ciency in carbon auctions with imperfect competition. In 11th Innovations Theoretical Computer Science Con- ference (ITCS 2020). Schloss für Informatik, 2020.
Potfer, M., Baudry, D., Richard, H., Perchet, V., and Wan, C. Improved learning rates in multi-unit uniform price auc- tions. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024. URL https: / / /popereviiee ewwriweww.. www.ee.ww/eeeee.eeee...ee......e
Golrezaei, N., Lobel, I., and Paes Leme, R. Auction design for roi-constrained buyers. In Proceedings of the Web Conference 2021, pp. 3941-3952, 2021.
Regulations, E. E. A. Eu ets auction regulations, 2019. URL. https: / wtw.//ereeeeee.ppp.....aeeee eu/
Golrezaei, N., Jaillet, P., Liang, J. C. N., and Mirrokni, V. Pricing against a budget and roi constrained buyer. In International Conference on Artificial Intelligence and Statistics, pp. 9282-9307. PMLR, 2023.
legal-contenn wwwoonntttttlnnccoeee /EN Cttii//ENNTTTTT/TETE Ttt//TXT/PDDDD 02010R1031-2019111 /TWKTT/DD///r/// /orri-CELE- 2024.
Accessed on January 19,
Hortaçsu, A. and McAdams, D. Mechanism choice and strategic bidding in divisible good auctions: An empirical analysis of the turkish treasury auction market. Journal of Political Economy, 11855):833-865, 2010.
Roughgarden, T. and Wang, J. R. Minimizing regret with multiple reserves. ACM Transactions on Economics and Computation (TEAC), 7(3):1-18, 2019.
Schmalensee, R. and Stavins, R. N. Lessons learned from three decades of experience with cap and trade. Review of Environmental Economics and Policy, 2017.
Klemperer, P. A new auction for substitutes: Central- bank liquidity auctions, 'toiic asset' auctions, and variable product-mix auctions. Journal of the European Economic Association, Forthcoming, 2009.
Shoham, Y. and Leyton-Brown, K. Multiagent systems: Al- gorithmic, game-theoretic, and logical foundations. Cam- bridge University Press, 2008
Lattimore, T. and Szepesvári, C. Bandit algorithms. Cam- bridge University Press, 2020.
Streeter, M. and Golovin, D. An online algorithm for maxi- mizing submodular functions. Advances in Neural Infor- mation Processing Systems, 21, 2008
Lu, P., Xu, C., and Zhang, R. Auction design for value max- imizers with budget and return-on on-seend constraints. In

---

Learning Safe Strategies for Value Maximizing Buyers in Uniform Price Auctions
Takimoto, E. and Warmuth, M. K. Path kernels and mul- tiplicative updates. The Journal of Machine Learning Research, 4:773-818, 2003.
Tierney, S. F., Schatzki, T., and Mukerji, R. Uniform-pricing versus pay-as-bid in wholesale electricity markets: does make difference? New York ISO, 2008.
Tsybakov, A. B. Introduction to Nonparametric Estimation. Springer Series in Statistics. Springer, New York, 1st edition, 2009. ISBN 978-0-387-790551-0 doi: 10.1007/ b13794.
Wilkens, C. A., Cavallo, R., Niazadeh, R., and Taggart, S.
Mechanism design for value maximizers, arXiv preprint arXiv: 1607.0436,, 2016.
Wilkens, C. A., Cavallo, R., and Niazadeh, R. Gsp: the cinderella of mechanism design. In Proceedings of the 26th International Conference on World Wide Web, pp.
25-32, 2017.
Williamson, D. P. and Shmoys, D. B. The design of approx- imation algorithms. Cambridge university press, 2011.
12

---

Learning Safe Strategies for Value Maximizing Buyers in Uniform Price Auctions
Contents
Omitted Proofs from Section
14
A.1 Proof of Theorem 3.1
14
A.2 Proof of Theorem 3.2
15
Omitted Proofs From Section 4
15
B.1 Proof of Lemma 4.1
15
B.2 Proof of Theorem 4.2
15
B.3 Proof of Theorem 4.3
16
B.4 Proof of Theorem 4.4
19
C Omitted Proofs from Section 5
20
Proof of Theorem 5.3
20
C.2 Proof of Lemma C.I
23
C33 Proof of Lemma C.2
24
C.4 Proof of Theorem 5.4
26
C,5 Proof of Theorem
29
D Tight Lower Bounds for Results in Section 5
29
D.I Tight Lower Bound for Theorem 5.3 (For m
29
D.2 Tight Lower Bound for Theorem 5.3 (For m 2 2)
30
D.3 Tight Lower Bound for Theorem 5.4
33
D.4 Tight Lower Bound for Theorem 5.5
35
Simulation Details
36
E.1
Reconstructing Individual Bid Data
36
E.2 An Uniform Upper Bound for /OPT (H-).
36
Resolving Ties
36
13

---

Learning Safe Strategies for Value Maximizing Buyers in Uniform Price Auctions
A. Omitted Proofs from Section 3
A.1. Proof of Theorem 3.1
Before proving Theorem 3.1, we present the following lemma about the bidder's per unit payments, which we will also use to prove several other results.
Lemma A.1 (Per-unit Payments), Suppose the bidder bids b (1).:.4)....... qm)). Recall that Qj Et= 9e, Vj
[m] Recall that, B_,( is the jth smallest winning bid in the absence of bids from bidder for round I. Ifj = 0, 3- () = and j > K, 3_ = oo. Then, the per-unit payments by the bidder in round
if (x(()) =0 i < x1(3)) < <QE- if xf(" Qe
p(B")
be. min B ()tt)))
(7)
Define the following class of no-overbidding (NOB) strategies with m bid-quantity pairs: ((b). gi)................... (bms qm)) by S ui vl E [m]]]
SNOB
:= (
m
We first show that Sm S SNOB and then complete the proof by showing NOB C Sm.
Proof of 8m C SNOB
Observation 1. Overbidding is not safe bidding strategy. To see this, let b ((b1 ......... (be, gc).... (6ms 9m)) be an overbid such that by > WQr. Now, consider an auction in which the competing bids are:
B (
if if Qi <j S
261,
where by. Submitting b gets allocated Qe units and from Lemma A.I, conclude that the clearing price of auction is by. As by > wQ, by assumption, the Rol constraint is violated.
As overbidding is not safe strategy, every safe bidding strategy is a NOB strategy, i.c., 8, C SNOB
Proof of &NOB S We now prove that the converse is also true, i.e. every NOB strategy also a safe strategy. To show this, fix any competing bid, B_, and consider any b ((b,, 91)....... (0m: 9m)) E 8 8NOB Suppose bidding b wins x(3) units. So, from Lemma 1, if 2 = O, trivially, P(0)
V(8). If Q < xx3) Qe, for some é [m].
P( = (()) (() < (3) be < (z) wQ. & xB) (F) V(
The first inequality holds true because bidders' per-unit payment is at most their least winning bid (individual rationality of the auction format), the second is true by definition, and the third is true because the wy is non-decreasing in j and xx3) S Qe. As the choice of competing bids and bidding strategy b was arbitrary, we conclude that every strategy in SNOB m
safe, i.e., gNOB C Sm, which completes the proof.
A.1.1. I. PROOF OF LEMMA A.I
Consider the following three cases:
(1) If a (((') 0, trivially, p(3t) O.
(2) Let Q < x(B)) < Qr. Let & be the last accepted bid after including b, i.e., the smallest bid in , = -bb,B"). Then
be b.
(a) holds true because bidder allocated at least one unit for bid by and
II. (b) correct because they do not acquire at least one unit for bid be. Hence, p(B²) = be-
(3) Suppose x(3²)= Qc. be > (-Q++1)) then p(,3) = -3_(0+ However, by S (3 -((3)) -bg- So. p( = min (br, (Qc+!))
14

---

Learning Safe Strategies for Value Maximizing Buyers in Uniform Price Auctions
A.2. Proof of Theorem 3.2
We show that for any m E N, most safe bidding strategies are very weakly dominated for which they can removed from Sm. resulting in Sn- We begin by establishing general result regarding the monotonocity of feasible bid vectors (not necessarily m-uniform strategies) for value maximizing bidders. As the result holds for any bid vector, it is also true for m-uniform bidding strategies.
Lemma A.2 (Monotonocity of feasible bids), Consider two sorted bid vectors: b = [b1, be...., by) and [b/ ./.... b/g such that bj 2 b/, Vi E [k]. Suppose b is Rol feasible for some competing bid, 3_. Then, b' is also feasible for B_ and
(bb 3_) 2 :3b.:
Suppose b- = ((b1. 91) ..... (bm, 9m)) is an underbidding strategy per Definition 3. Consider b' ((b1, ((b)))))... .i............................ (Kmm Lm)) such that of = q and bV = "a,, Vj [m]. By Theorem 3.1, we establish that b, b' 8m. Invoking Lemma A.2 gives us that the underbidding strategy is very weakly dominated, and hence be removed from Sn, obtain Sm.
A.2.1. PROOF OF LEMMA A.2
Let 3 = (_. and 3 (b',3.) ). We first prove that b' is also feasible for 3_ Contrary to our claim, suppose b' is infeasible, i.c., the value obtained by b' when the competing bids are B_ is strictly less than the payment. Suppose b' is allocated r' units with clearing price p(,3)) such that the Rol constraint violated:
p(B')= Wy,.
(8)
Suppose b is allocated r units when the competing bids are B_. By definition of allocation and payment rule, the units allocated and the clearing price in an auction are weakly increasing in bids, so r' S r and p(33' S p(3). As is feasible,
p(3) S wr.
Combining Equations (8) and (9), we have
(a) p(3) S wr up < p(3') = p(3) < r(B'),
which is a contradiction. Here (a) is true as wy is non non-increasing in j and r' S r. So, b' is feasible.
By definition of the allocation rule, the value obtained in auction is weakly increasing in the bids submitted. As and b' both feasible, V(b; (_) 2
B. Omitted Proofs From Section 4
B.1. Proof of Lemma 4.1
By Theorem 3.2, a strategy = ((b1, ((b1,41),- Qi),..., (br, gr)) E Ut, for some é E [m]] can be uniquely identified by (Qi,..., Q+} where 2 = =Ess 9 because b, = we, for all j E [e]. Let the bid history H. = [ kerr. Then, for any round t,
i Σ
Uk I ww 2 6 (k)
V(b;
j=1
Q3
1+1
Hence, the problem (OFFLINE) can be equivalently expressed as
T
Q2 Σ
V(b: = max
ΣΣ
Uk Iww
[Q 2 233
max belly I
max
EE|m Q Q
j=1 Am
Qj 1+1
B.2. Proof of Theorem 4.2
GV, E) is a DAG. For convenience, let d = (m + 1,0). In the constructed graph, any node (f.j) where E [m]] has edges edges either to the next layer, i.c. nodes of the form (E + 1.j') where j' > j or to the destination node (m + 1,0). Hence, the directed graph has topological sorting of the nodes implying that gVV, F)) is DAG.
15

---

Learning Safe Strategies for Value Maximizing Buyers in Uniform Price Auctions
Bijection between s-d paths and strategies in Un Consider a path
p = s + (1, + ... + (m,, 2m) + d.
By construction of GVV E), edges - (1,21) and (m, 2m) - d always exist. For any E [m 1], the edge (f, zt) + (e+ 21-1) exists if 24 21+1- With this path p, associate the strategy
b = ((b), .1)............................. (bm: 9m)) where by = was and qe = 22 - 21-1.V E [m]
where = 0. By definition, Q3 = Ete1 qe 2j and bj- = Wx = wQ, Vj E [ma]. Hence, b E U
Conversely, consider any safe strategy = ((b), (1)..... (bm: with by way With this strategy, we associate the s-d path p' + (1) + .... (m, Qm) d where Qj = Σ'= 9c, Vj [m]] We claim that p' is valid path, i.e., all the edges exist, because by definition = (1, Q1) and (m, Qm) + d always exist. Furthermore, for any É E [m- 1]. the edge (f, Q:) + (e + 1, Qe+1) also exists as Qe+1 - Qe = qe+1 > 0.
Weight of s-d paths. By assumption, s = (0, 0) and 2μ = 0. The weight of p = s - (1,21) 7 ... - (m, 2m) + is:
((p)
Σ ((e) = Σ
w(( - 1, - (f. zx)
cEp
E=1
m
26
2k 1 Wes 2 2 [1)]
1=
T 1
ΣΣΣ Uk 11 Use 2 (1)
which is the value obtained by the safe strategy b ((b1.q1)... (bmss 1m)) E U where by = Wz,, Ve E [m].
Computing maximum weight path. As G(V E) is DAG, the edge weights can be negated and the maximum (resp. minimum) weight path problem in the original (resp. 'negated') DAG be solved in space and time complexity of O(VV+ + [ (m.22) which is polynomial in the parameters of the problem.
B.3. Proof of Theorem 4.3
We begin by observing that there is bijective mapping between s-d paths in the DAG (V, E) and bidding strategies b Ur, (see proof of Theorem 4.2). The core idea of the proof is to show that Algorithm is an equivalent and efficient implementation of the Hedge algorithm (Freund & Schapire, 1997) where every s-d path is treated as an individual expert. Similar ideas have been utilized in Brânzei et al. (2023); Potfer et al. (2024); Galgana & Golrezaei (2024). For the sake of completeness, we provide the details below.
In Algorithm 1, (u ++-) denotes the probability distribution over the outgoing neighbors of node By the recursive sampling of nodes (Line 4-7 of Algorithm 1), we get that the probability of selecting s-d path p is
Pt (p)
II (e),,
(10)
and for any edge + in G (V, E), the edge probabilities, (c(), are updated as
I' (v)
x = (c)= (e) (1
(11)
where (d) and
I [+) computed recursively in bottom-to-top fashion for every node in (VV, as follows:
(w) = Σ (')
((o)))---10 1 -) cxp(1x'- + +)).
(12)
'Here, we assume the path has m + edges without loss of generality. The same argument follows if = -- (1,21)
(ks 24) + with & edges for some E [m]] is considered instead.
16

---

Learning Safe Strategies for Value Maximizing Buyers in Uniform Price Auctions
Now, consider naive implementation of the Hedge algorithm with learning rate yj in which each s-d path is treated as an individual expert. For i 1, define Pl HEDGE (p) Ieep (e). For t 2 2, the probability of selecting path p in round is
HEDEE (p) exp(n Ceep w w-))
pt
HEDGE (p)
Σp HAnDAS (p') exp(1) EeEr' w(-1(e))
Now, we show that for any path p and E PT), = P mecen (p). To this end, we first present the following result:
Claim B.1. For any node in the graph, let PP)) be the set of paths starting at and terminating at d. Then,
(u) = E II
(e) exp(1w -oww--1p (e))
pEP(() PEP
Proof. We prove the result by induction in bottom-to-top order. For the base case, u = d, (d) = 1. Suppose the result true for all the nodes in layer& ++1 1 for some 0 S l S m. By the recursion in Eq. (12), for any node u in layer l,
(w)
Σ
(v)
( (u - v) exp((nn''(( + v))
FE-TEEE
Σ
II
(e)= (e))) 00 u) exp((n"" u))
PEP(F)EED
Σ
II
exp(px' (e)
PET(u) cEp
where the first equality follows from induction hypothesis.
We will show by induction on t [T] that for any path p, I (p) PRDDE (p). For t 1 and any path p, Pl HEDGE (p)
Neep o0 (e) = (p). Here, the second equality holds by Eq. (10). Suppose the result holds for round t - i.e.
pt-1 (p) = PheDe (p) Πeep (e). For round 1,
1 Plrtee (p) exp (1 /wEw>
(d)
Pt (p)
II cEP
0 (e) (exp(nn-1(00
(e))
w (e))
T
[)-1(8)
cEP
where the last equality follows by telescoping product and invoking the induction hypothesis. By definition, I" By Claim B.I,
(s)
III
(E) exp(mw"-1(c)) = Σ pl (p')
exp
17
Σ w
P'
eEp'
"EP'
Substituting the values gives Fst (p)
ptt
REDGE (p) implying Algorithm is correct implementation of the Hedge algorithm.
B.3.1. BANDIT FEEDBACK MODEL
In the bandit setting, the bidder learns about their own allocation only for which w'(e) can not be exactly computed for all the edges. Hence, we use an unbiased estimator, (c()), of w'(e) as follows:
w/ (e) = w(e) w(e) w' Ife E pp] where (e(e) = Σ P'(p..
(e()
P:CEP
Here, p' (e) is the probability of selecting edge in round t, I't is the distribution over all s-d paths in Observe
that w (e) is well defined as pe()) > 0, Ve E, Vt e [T]. Here, w(e) is an lige-deeendent upper bound the edge weight w (e). Formally, for & E [m]]
ife = (1-1, (l.j") if = (f.j) d.
w(e)
0,
17

---

Learning Safe Strategies for Value Maximizing Buyers in Uniform Price Auctions
The algorithm followed by the bidder in the bandit setting is identical Algorithm I, with each instance of w w'(e) replaced by (e), Vt [T], Ve E E. Clearly, R[W((e) w'(e). The unbiased estimator W is different from the natural estimator w'(e) Ieee E p*] for technical reasons (similar to Lattimore & Szepesvári (2020, Eq. 11.6))
pi(c)
which we will clarify shortly.
B.3.2. REGRET UPPER BOUND
Full Information Setting. Having shown that Algorithm is equivalent to the Hedge algorithm, we now recall its regret bound from Brânzei et al. (2023, Corollary 1) which states that for learning rate rf.
1 REG
1/T
max log log((o((((g))) (p)) (p))
7
P
Observe that (p) 2 Mm which implies,
mog M T22
REG S
Setting 77
V
8m log T
we get REG S OM /mf log M).
Bandit Setting. Using the standard analysis for EXP3 algorithm (see Lattimore & Szepesvári (2020, Chapter I1)), we get
T
REG = max (og((')) (p)) +
1
log
Σ P
ps (D)e
Σ ('()))(())
17
where w'(p) = Ceep (e)). Note that w'(p) = Ceep (e) S Ecep w(e) S M and P (p) 2 -m For 17 S 1
M
mlog M
REG
(pp))((((pp3} (p)
m log M
T
+ mm
P'
(p) (c)
t=1
9EP
where in the first inequality, we used ex < 1 + + x² for x < 1 and log(1 +x) S for 2 0 and the second inequality follows from Cauchy-Schwarz. Schwarz. Observe that
Σ
(P)PP) Σ E B (e) Σ (e) p.eE
P'(p) = Σ r (c)
where the last equality holds as (²())= E Epeeep 1sd (p))
[x(+ ((e))) (w(e) w(e) (e) 2 (e))
(((e)
[M( - (c()) Σ w(e)?
Observe that E. w(e)2 < 1 S mM. Hence,
m log M
T
REG
pd (p) Σ (e)(
t=1
cEP
m log M
mT 2
Setting 17 372
1
log M ml
we get REG & O(M2 / m 3 log M)
18

---

Learning Safe Strategies for Value Maximizing Buyers in Uniform Price Auctions
B.3.3. TIME COMPLEXITY
In the full information setting, the running time bottleneck is Eq. (12). Thus, Algorithm runs in | (mmM²) time per round. The bottleneck of rumning Algorithm I under the bandit feedback is the efficient computation of the marginal distribution, p' (e). We claim that this can be done in O (M [i) ((mM3) time per-round.
We compute the marginal probabilities in a recursive manner over the topological sorting of the nodes in the DAG as follows:
for any edge starting at the source, e = + u. p²(( (e) = (e). For any other edge of the form + v, using law of total probabilities
v)
Σ P[(u P((u-v)l(2 + u]] p' + u) xEN
Σ 4'(u p' + u)) JEN
where Nit is the set of in-neighbors of node and (l + w) - u)] is the conditional probability of selecting edge + v once the edge z u is chosen. The final equality holds because by Algorithm we get that at any node, edges are chosen in a Markovian manner implying P((u (xr + u)] = s'(u + v). Observe that probabilities p' + u) for any E N are known while computing p'(u v) as the edge æ + u precedes u - v in the topological sort. So, the total run time is
(
( = O(MIE) = O(mM*)
max :uV:
Here, we exclude the destination node d while maximizing over the nodes as d has no outgoing edges.
B.4. Proof of Theorem 4.4
For m = 1, let K M be an even integer. Let v [1, ....., ...,, v). Here, the first entries are and the remaining entries are v. Let e = 1 - 5. Define 8' = 2M Consider two scenarios:
2
Scenario In this scenario, for every 1 [7). the competing bids B are:
8 ......
8%
w.p. 2 + 6,
8²_ 1tv 8' ..... 1
87) w.p. 2 8,
Scenario 2. In this scenario, for every t E [T], the competing bids B are:
[1 8' ,'....................
8%)
w.p. 1 8, 2
1+ 8' . 14
8'). w.p. + 6,
for some& E (0, 1/4) that would be determined shortly. Assume the randomness used in different rounds are independent.
Let P and Q be the distribution of (e(T) for scenario and 2 respectively. Then, for E (0, 1).
1 + 28
8752
KL(PIIQ) T (L + 8) BERN((.. 8)) 275 log
< 1 28
S 1678²
1 - 28
where the first inequality follows from log( (
<
2x I-r
By Tsybakov (2009, Lemma 2.6),
- TVTV(P,Q) 2 exp (- KL((P)))) 2 2 exp (-16762).
2
Consider the class of 1-uniform safe strategies. We first show that we need to consider only two strategies out of the M possible strategies. Recall that any strategy in this class of the form (wyy q)-
Case 1. 1 15 v/ Here, Wy 1, Vg. So, (1, M weakly dominates all the strategies of the form (1.q) for S < M
Case 2. +1 < M: In this interval, the highest bid value is for q = M due to diminishing marginal returns property. Note that,
2
M 1 8
8
8
W M
M +1
M
+
M
< 8'
19

---

Learning Safe Strategies for Value Maximizing Buyers in Uniform Price Auctions
Hence, no strategy of form (w.g q) for g 2 + 1 is allocated any unit in when the competing bids 8¹ ,...., 8)) The smallest bid value for M (M) = (1 - 2 M) is allocated all the units when the competing bids are _ - 8', _ 5'] and, by definition, weakly dominates all the strategies of the form (wis q) for M
2 + - q S M for q = M. Note that, WM = 1+ -+ 8'. Hence, (WM, M)
2
2 + 1. Hence, we have two undominated (for the constructed competing bids) strategies: b (1, ) and b = (1 - M).
Now, we compute the expected value obtained by b1 and by for scenarios P and Q.
= M
Ep [p]V(b;; = Eq ( (b;; (b;;
2
1+e
M 1
M
Sp2V(b2; = .
8)
8
(2 8) <
2
2
2
2
1
1 1++ 2
M
1
M
E2 (b2; = M
+
8
(2
8)
>
2
2
2
2
So, by (resp. b2) is optimal for scenario P (resp. scenario Q). Now, consider the distribution
P+Q
i.e., (ER.(
2
M 2
and E Ecto [V [Vbbg; M
1
M
E E [Vbii
3r 3²]]]
s 2
M 2
E betl;
max
reg ((bbB2))
(13)
Hence, for any be Ui, and any round E [T),
max Ep(V(b"; (²)) - Vb; (b);((]]]+ breli
max BolV(b"; - V(b; br
2 max (b(V(b"; + max
[b(V(b"; 3²) - max E r+g (V(b'; 33-)]]
brEui
brEu;
b'
= -Ep[V(bi 31] + (52[V(22;')) 2
max br
Eeis [V(b";
(3) M
M- 1
M
M
36
5M6
(2 5) -)
2 =
82
2
2 2
2
2
2
8
where the last inequality follows as 8 E (0, 4). Hence, any strategy b E Ut incurs a total regret of 5MT6 under Q. By two-point method from Tsybakov (2009, Thcorem 2.2),
either under P or
16
5MT8 (1-1) (L-TV(P,.0) Q)) >
5MT6
E E44 |EG
exp (-16T5²)
16
32
Setting 8 = 4/27' We get Ep
|REG]
MVT Hence, Erio REG] 2(MVT). 36
C. Omitted Proofs from Section
C.1. Proof of Theorem 5.3
To prove that A J.m .11 bid history, H- = 1. -B=
2 for any m E N. recall from the proof sketch that we first defined the following metric for any
ΣT, 1= V(b; 32)
max beg N maxbell, Et=1 V(b;
A F 11 (H-)=
(14)
Let OPT (H-) = ((bī, vi.................. .., (Dm- 4m where DOPT (H-) = argmax beatt Σ ((b Deffne Qi Ejse 17- Suppose DPTT (H-) is allocated ri units in round l. For any j E [m], let T3 be the set of rounds in which the
We assumed D (H-) = ((bi, qi).................. gin)) without loss of generality. The proof also follows if we considered OPT (H-) = ((bi (i,.g.................... (bi: 4h)) for some & [m] instead.
20

---

Learning Safe Strategies for Value Maximizing Buyers in Uniform Price Auctions
least winning bid is bz. i.e.
T =
< 03}
(15)
For any j E [mm], partition 7 into T3.0 and 7211 such that 7,,0 is the set rounds where the bidder gets strictly less than Qj units and T3, is the set rounds when they get exactly Q3 units:
T3,0 { EE :r : < 0z}.
T3 te 03}
(16)
For any j E [m]], let
Q = max :E T3o),
if T + if TT 0.
In other words, 23 is the 2nd highest number of units allocated to b (H-) over the rounds in Tý (or the highest if Too = 0 or 7,,1 0).
Step 1. Constructing a Restricted Class of Safe Bidding Strategies. Here, as crucial part of the proof, we construct a restricted class of safe bidding strategies, denoted by U (H-), where U Um (H-) C Um This construction serves two purposes. First, reduces the search space for the optimal safe bidding strategy. Second, and more importantly, it enables us to establish connection between the optimal safe bidding strategy and b (H-).
In defining the restricted class, we use the quantities, {Ộ,, Qj}jemm as follows:
u (H-) = bb= ((bi,9))...... (bmn; 9m)) be wQ Qr Q7), ve E
(17)
Recall that any strategy in U, with m bid- bud-quuttity pairs takes the form of b = ((b1, qi).... (bm pm))) 3) : be = wQr 4e E [m]. The strategies in Ue (H-) also have the same structure but as an important difference, for any & EE [m], we enforce Qi E (Qr, ). Observe that for any l E [m - 11.
Qe Qi Qi < Q+1 S Qu++
where the first and third inequalities follow directly from the definition of Qe and the second one follows from the definition of Q.+1. So, Qr's are distinet and ordered. Further observe that the number of bidding strategies in U (H-) is 0(2"); significantly smaller than the number of strategies in U which is O(MT).
With the definition of the restricted class of safe bidding strategies, we have
bES max n- Σt V(b: 3*)
bES N Σt V(b:BL)
ma Ei V(b:LL) Ay* H ur (H-)
(18)
1i= VLb
max (H-)
Step Value Decomposition for m-uniform Strategies. Let Vj be the time-average value obtained by OPPT (H.)) in the set of rounds in T (as defined in Eq. (16)). Formally, Vj E [m], k E {0, 1).
Vy
V(b (H-),3*).
T
TET
Define Wi = Ug. Note that V₁,1 Wo; because for any E Tj.1, have rē Q7- For any b E U, (H-), where b ((b::1),.... (bm,, gm)) by wQ.. and Q+ (Q7, Qe) for any l [m]. define N N C [m] as follows:
N = (j Q = 2j E [m]} and Ñ= (j: Q; = Q, < <j.J E [m]]
We now present a crucial result that expresses the value obtained by a m--niformm bidding strategy as a function of the value obtained by m 1 1-uniform strategies.
21

---

Learning Safe Strategies for Value Maximizing Buyers in Uniform Price Auctions
Lemma C.I. Let b ((wQ.:91)......... ......... (wQ.. bm)) be m-uniform safe bidding strategy for some E N. Then, for any competing bids B_,
V(b;
max V((wge) Qr); FE(m]
where we recall that Qi - Oj AA [m].
key consequence of Lemma C.1 that knowing the value obtained by the strategies in Ui is sufficient compute the value obtained any m-uniform safe bidding strategy. By Lemma C.I, for any round L Tj. and b E Um (H-), ) get
3(b; max V ((wer Q²): 2 V((wo,, Q));B=), FE(m)
(19)
V(b;
Σ Σ IET)
V((wa:=00)::B)) 0+);8()+ + Σ Σ
V(( Qz);
(20)
JEÑ EET)
Step 3. Allocation Lower Bounds for 1-uniform Strategies. For any j E [m], we invoke the following lemma establish lower bound on Eier V((Q,, Qz);B().
Lemma C.2. Let b Un (H.-), where b ((b1, .1)........................ (bm qm)) b, wa, and Q2 103 0, e [m]] Then, for any j E [m].
(a) iQQ, =,-- < Q3 (ie., j Ñ), we have
Σ
(1):8() 2 VgolT,ol + Wa, TTal
(21)
ET
(b) IfQ, = Q2 (i.e., j j N*), we have
V((wa, Q1);B1)) 2 Wo; IT,11-
(22)
Note that the right hand side of Eq. (20) depends only on the choice of the partitions N and Ñ. Substituting the lower bound from Lemma C.2 in Eq. (20), we establish that,
* T Σt 3L
(18) max DET
(H-)-
2 21
maxbeus (H-) Et_ (b;
bey Et 3Lb:
max
(23)
max (N., EjEN- (Wo;1Tall) + EzER (VgolT;.ol Wa (Ta1))
Let No) = argmax,x. .) { EjEN- (WazlZinl)) EJER (VrolT3.0l + Wa, [ Then,
I
T
Σ V(b; = ΣΣ Viel
max
beg 1=1
(=l
8=0
Σ
ViooTT.ol + (oo;1T:1) +
Σ jeNo
(ViolTT.ol + Wo;1TTal)-
(24)
JEN;
Consider partition of [m] that differs from the maximizing partition (N₂, NN),No) by exactly element, i.c., for any e No. consider the following partition: (Ng (a), No \ {a)). By definition,
Σ JEN;
Wo + Σ (VoolT,oo= + W2y (T 2
Σ jENjU(a)
(Waz +
E
(KolTTaol + W (T,l))
NE
jENoifa)
22

---

Learning Safe Strategies for Value Maximizing Buyers in Uniform Price Auctions
Va.oTTa Wa [Ta,1 Waa1Ta.1-
(25)
Now, for any b E No: consider the following partition: (No \ (b), No (b)). By definition,
Σ
( Wor[TTal)
Σ
(VoolT,ol + Wa, (Tal) 2 Σ (WarITaal) +
Σ
(VolTT,ol + Wa (Tial)
JEN;
JENo
JENg
JENGU(6)
Wo;17b.11 - Wg, |T,, 2 Vo.0 Ta,l--
(26)
Plugging in the values,
ΣJENS VSolTTool + We; Tral) + +ISeño (ViolTRol + Waz]TTaal
(24)
Ag An _u
(H-) S
ΣSENE (War (Tal)) + +ESENO (VooTTuul + -Wo, (Taal)
ΣJENz (VooTTioo+ + Wo; T2.l) + +IJEN. (2V2o1T3.ol (2,ol WW,, [T,.1]
ΣjeN; (Wa; (Taal) +ZjER (ViolT3.ol +Wo, (T,11)
(26) ΣSENS (2Wo117: [7,11 We, (Ta1l) +EJENO (2V Txal WW, [2,1)
ΣjENs Ki.l) + -ESERo (VrolTT.ol + W6, (ial)
2 Σ EIEN; 13a1 + ESEÑo (Vi.oTT3.0l + (Tal)) Σラ= W3, |T,al
ΣjENs T3al) + EjENo (VrolT + W2,17:11
= 2 22 Oz
where
E/=1 W [Ta1l
0 < 0H
EjEN; (W;; [Taal) + Dooño
(VulTToll Wa, TTal)
(3)
Σj=1 W3, Tya1
ΣyeN; (We; + EyeN, (Wa:ITa.l)
- Wo, [T,1| (0)
Q 1
max
= Wo; [,,1
JE(m]
Wo;
and (a) follows from Fact 1. Finally,
A x ur. max A y uu (H-) < 2 min ON =: 2 0,
where 0= min On (0, 1].
Fact 1 (Willammson & Shmoys (2011, pp. 25)). For positive numbers 01 .1...., am and bi...., bm.
Σー Uj < max aj
Σm bj
5E[m] by
C.2. Proof of Lemma C.1
We state and prove a stronger version of the result in Lemma C.I. Formally, Lemma C.3. For any N and competing bid B_, let b ((b), 91), ..., (bm: gm)) be feasible (not necessarily safe) m-uniform strategy for B_ Then,
V(b = max V((be, (2); 8E(m)
where we recall that Qi = E Gj, Vl E [m].
Lemma C.3 states a similar result as Lemma C. except a key difference that the bidding strategies are not necessarily safe.
23

---

Learning Safe Strategies for Value Maximizing Buyers in Uniform Price Auctions
C.2.1. PROOF OF LEMMA C.3
We prove the lemma via induction on m. The base case m for which the result is trivially true. Now assume that the result holds for any m-uniform bidding strategy for any competing bid B_.. We now show that the result holds for any (m + -umuifform bidding strategy which is feasible for B_
Consider any m + 1-uniform bidding strategy b = ((b1 91)...... (bmr 9m), (bm+1, bm+1)) feasible for 3_. Then,
Claim C.4. The bid-quantity pair (1m+1, Qm+1) is feasible for B_ and (_b 2 (((m+11, Qm+ 2m++)); B_).
Proof. By assumption, is feasible, the total demand of and (bm+11 Qm+1) are equal and b(z) 2 bm+1, Vj E [1m+1] where b(y) denotes the bid value in jihh position in the sorted bid vector. So, by Lemma A.2, (bm+1, 2m+1) is feasible and ((b:BB) V((m++1, Qm+1),
Suppose that by bidding b, the bidder is allocated r units. There are two cases: (a) r S Qm and (b) r > Qm.
Case I. r Qm In this case, have
(27)
Hence, by Claim C.4 and Eq. (27),
((b:3_) max V(bl1: m]] (((mm+1, Qm+1):B_)}
(28)
Case II. r > Qm Asr > Qms bm+11 is the least winning bid which implics 6m+1 2 (r), where we recall that (3(()) is the th smallest competing bid in B_. So, (bm41, Qm+1) 1) allocated at least units which implies V ((bm+1: Qm+1), 3_) z V(bb B_). By Claim C.4, we also have V(b; __ 2 V ((bm+1, Qm+1).B_) Hence,
V(b: = ((Im+11 1m+1):
(29)
As r > Qm. (bm+1, (m+1),Qm-)) is allocated at least Qm + units, whereas b(1 : m] has demand for (hence, can be allocated) at most Qm units. So,
33b 2 V(b[1 ml;
V(b: max [[([[ ml: (...V.(( (0+))))m++1):8))
(30)
For both Case and Case 11, we get the same result (cf. (28) and (30)). Hence,
V(b; )- max
[b[l m]: (_), V ((bm+1, (attes11.0m1/imm Qm+1);
(a) max
max V(be, Qr); V((m41,, (((0m41,mm41):::: 1_))); FE(m)
max dE [][++]]
V(bb,, Q.):
Here, (a) holds as b[1 : m] is feasible for 3_ allowing us to apply the induction hypothesis for m.
C.3. Proof of Lemma C.2
To prove this result, we use the following key lemma that measures the value obtained by OPT (H-) in terms of 1-uniform safe bidding strategies.
m
Lemma C.S. Let OPT (H-) = ((bi, ......., (bin )m))). Suppose Qi = Eres Te Vj E [m]] and OPT (H-) is allocated
Tē units in any round t E [T]. Then,
For any 1 (T) and q S rt, (Wgs () gets exactly q units.
24

---

Learning Safe Strategies for Value Maximizing Buyers in Uniform Price Auctions
For any j E [mm) let T [T] be the rounds in which by is the least winning bid, i.e.,
T== = {t [T] Q--1 < S Q7}-
Suppose that 3t T such that rf 23. Then in any round t' T in which byp (H-) is allocated at most r units, i.e. rh S rt ( ( is allocated at least rp units.
With this lemma, we are ready to prove Lemma C.2.
Case I: Q; = 2 < .j For any E T3 invoking Lemma C.5 (1) with Qj. we conclude that (wa, Qi) is allocated exactly 2 units. Summing over all rounds in T3
Σ TET,
((Iw,,:Q)):P)) = W, 17,11-
(31)
As Q3 < < -2aaan and Q, 2 r for any E Tj So, for any T3,0, invoking Lemma C.5 (2) with r = Q,, we conclude that (,g, Q2) is allocated at least r units. Hence, summing over all rounds, (wzy Q3) gets at least the value obtained by OPT (H.) over the rounds in Tz.0 So.
Σ rET).0
(b OPT (H-), = ViJolT,ool
(32)
T
Combining Eq. (31) and (32), for Qj = Q
Σ
V((wq,, 0;); 2 Vi + Wa, 17,l-
(33)
EE,
Case II: Qj Qj. So, for any 6 E 1, using Lemma C.5 (1) with q = Qj. we get that (wgq Q7) is allocated exactly Qj units, which is the same as the allocation for OPT (H-). Summing over all rounds in T3,,
Σ IET,
v(( ()):²²)) TTall
(34)
For the rounds in T3 trivially,
Σ
2 0.
(35)
1ET,o0
Combining Eq. (34) and (35), for Q, Q2,
V( 01);0() 2 Wo; TTal-
(36)
ET
C.3.1. PROOF OF LEMMA C.5
(1) First we show that for any t [T] and S rf, the 1-uniform bid (Wy. q) is allocated exactly q units.
As (Wy. 9) E Ut it safe strategy. By assumption, bOPT (H-) is allocated rf units in round Let e (boPT (H)),BL). Recall that, م- is the jth smallest winning bid in the absence of bids from bidder i for round t. If rī 0, the result is vacuously true. Suppose rř > 0, then
B 4
S p(3)) S Wr: S Wig
where the first inequality holds by definition of 3 and our assumption that q S rī- For the second inequality, suppose Qi < r S Q for some & [m] which by definition implies that by is the least winning bid. By Lemma A.1,
25

---

Learning Safe Strategies for Value Maximizing Buyers in Uniform Price Auctions
1. p(3)) = bj. we have p(3)) 2 (( as by is the least winning bid.
(r2)
() 2. If p(3") =B_ (9:-11 we have r = Q2 and by definition of B B_ p((3)= = -3- 2 3 (r:)
The third inequality is true as Rol constraint is satisfied by b (H-_ for round t, and the fourth is true wy is a non-decreasing function of j and S rf. From the first and last expressions, B²(()) allocated at least q units in round Moreover, (wgs q) can be allocated at most q units. Hence, the 1-uniform bid (wgs q) allocated exactly q units.
(g) < w which implies that (wy. q) is
(2) For any j E [mm] let T3 S [T]. defined in Eq. (15), be the rounds in which by is the least winning bid. Suppose that Et T such that r? < Q7. We show that in any round t' E T in which b (H-) allocated most ry units, i.e. r S rf. the I-uniform strategy (Wez rt) is allocated at least rī. units.
O, the result is trivially true. Hence, suppose rī 0 and consider the set of rounds in 73 for any E [m]. As r Qÿ. by Lemma A.I, p(39) bj. So, for any l' E T such that r S ri.
Observe that (wrz,rt) rf) U1 it is safe strategy. If rī
e (r2))
S bj S Wy:
Here, the first inequality holds as bj is the least winning bid for round t' E T and the second one holds as the Rol constraint is true for b OPT (H-) for round f. Hence, (W.z. r?) is allocated at least rp units in round t'.
C.4. Proof of Theorem 5.4
We state and prove stronger result which recovers the upper bound in Theorem 5.4 corollary and is also crucial to prove the upper bound in Theorem 5.5. Let 3.th be the class of bidding strategies with most m bid-quantity pairs that are feasible for the bid history H [ Then,
Theorem C.6. For any m, m' such that m' 2 m,
Ay n- F 4
m
Proof. For H_ 113 we define
Σt V(b'
max b' b'er*t H-
Ay 2 m² . (H-)
E 3Lb:
max bef
Then, maximizing over all bid histories, we get the desired result.
Let OPT (H-) = argmax "e ΣT V(b: 32). I definition, OPT (H-) E - implying A Ag* nhh (H-) 1 m
(H-) is a k-uniform bidding strategy where & S m I m', by
m
Without loss of generality, let the optimal bidding strategy in JH m be OPT (H.- = ((6). ai)....,. (b P. and Qi = Ejsejj of for all E [m²]. !l Let be the number of units allocated to OPT (H-) in round t. Recall that T3 is the set of rounds when b7 is the least winning bid when DPPT (H-) is submitted (see Eq. (15)). So,
T
my
VODOPT ml
OPT (H-): = Σ Σ
V(b
OPT ml
(HL);
Observe that, for any t T
OPT ((b OPT (H = 1000=v[0 OPT (H-)
[1: 31: max V ((b2, (2):
EEGi
"A similar analysis also follows if b OPT (H-) is a k-uniform strategy where m S k S m'.
26

---

Learning Safe Strategies for Value Maximizing Buyers in Uniform Price Auctions
where recall that b[1 j] represents the first j bid-quantity pairs and the last equality holds due Lemma C.3. For any t Tj. r -- So, A4 < j. V(b (K=); V( Q;): 3'') as the demand of the strategy (bg Qi) is strictly
less than the number of units obtained by bop (H-) that round. Hence, for any Tj
OPT Vi m'
- (10,,
Σ
V(D OPT m
(H-): - Σ E
(37)
j=1IET,
Let 9m _ t be the class of feasible strategies for H that contain exactly m. bid-quantity pairs. Then,
g² T (H-) (37) Ej=1 EiET, V((j.. 03):
Σ Cien, V((). 9)):3))
(38)
N- Ei= (L)
bEgm H- Σ V(b;3L)
max. beT
max
Constructing the class of bidding strategies, GH We now construct class of m-uniform bidding strategies, HH using DOPT (H-) as 'parent' bidding strategy, in Algorithm 3.
Algorithm 3 Constructing 9m
Require: OPT (H-) ((b), vi)...... (b )) The collection, C, of subsets S S [mre]] such that [S] m. Initialize 9h
I: for S E e do
2: Suppose S = fli...., , km J such that h < l2 < ... < km.
3: Construct m-uniform bidding strategy b ((b1, ) ...,, (bm 9m)) where
bj = bbg and Øj = Qk, Qiy-1: Vj E [m].
(39)
4: 9 9m (b)
5: end
Return: The class of bidding strategies, 5%
For example: suppose m' 4 and OPPT (H-) ((w3. 3), (w7, (ws, 1), (win, 2)). Let m and S (2,4). Then, b = ((w7, 7), (W),,3)).
Lemma C.7. Let bi) be the jth entry when DOPT (H.-) ) expressed as bid vector. Similarly. for any b E 9th let b be the jth entry when b is expressed as a bid vector. Then, for any j E [Qkm. I by) S buy Thus, by Lemma A.2, b is also feasible for H and b was chosen arbitrarily, we conclude that HH C S
Proof. Let S contain kn ... < km and b be constructed per Algorithm 3. Then, for any E [m] and any entry ê 17,11
Bie 2 b(qi,) bb, b(e)>
where the first inequality follows because entries in bid vector are in non increasing order, the first equality follows as bie.) by for all e [me]] and second equality follows from Eq. (39), As j and were picked arbitrarily, we get that for all j E [Qum.. J. bú) bby-
By Lemma C.7,
ΣT' EIET, (()))
Σj EIET, ((1))))): be Σr V(b;
(38) A Ny -hh (-L) <
(40)
beg Σr V(b;
max
max
Consider any b E 9t obtained from the set S = (ki,.... ......,,, km) C [m']. As b is feasible for H.,, invoking Lemma C.3 for any round t [T]. we get:
V(b; = max V(
3L)) max V(b, Q7):²))
(41)
EE(m)
EES
27

---

Learning Safe Strategies for Value Maximizing Buyers in Uniform Price Auctions
because for any l E [m], by b and Qe
Qi - Qi
Recall that Tis, the set of rounds which bj is the least winning bid, form a partition of [T]. So,
m
Σ V(b;
V(b:
ΣΣ Σ
E E Je(m"]/SCET
v(b;
ΣΣ
V(b:3")
(42)
EET
JES
JES IET,
For any j E S, consider any round E Tj:
V(b; max ((6)) 07);0() (166,0))00
= Σ
V(b;gL) N Σ
Q3)3))))))
(43)
EES
TE?)
tET
which implies,
Σ
(42) g(b;
N
B2)
(43)
N
ΣΣ
(44)
JESIETy
JESIET)
Note that bidding strategy b E 9m is uniquely determined by the set S S [mm]] that generates b. Hence,
max beg 1=1
Σ
((b:
max
Σ V(b
S[(m"): =m 1=1
(44)
max
v((3, Q));BL)
SCSm =m
jESIET) TET;
m
Q((0,,
(45)
m
j= IET
Hence,
Σ EIET, V((b). 37): (45) m
A AyR
m² Im x (H-)
<
- E V(b; BL)
max bEgm
Maximizing over all bid histories, we get that A Ay
m!
m²
m
Now, we prove that the result also holds for safe bidding strategies. Formally, we show that for m, m' and m' 2 m, ma.
Aur
2r, uy, m To this end, consider the quantity Aur, ug, (H-) analogous to A th g. k- (H.), upper bound it and g
maximize over all bid histories to get the desired result.
For any bid history, H_ [B' [B" lre(r), let SSAFE (H.)) == argmaxb'eur Σt V(b':BL). Without loss of generality, let DSAFE (H-)- (wwQ,, vi) ..... (wo,,, )). The proof to bound Aur, u4 (H-) is similar to that of Theorem C.6 till Eq. (38), where we have
Aus Aus, (H-) Ej' Exer, ( 31);33)
maxbes., Σt V(b: 3t))
Recall that S, is the class of m-uniform safe bidding strategies. Suppose Sm (H.) ) be the class that is constructed analogous to the class g.t. obtained Algorithm 3. We now show that 8mm (H- S 8m.
Lemma C.8. For any subset C [m'] such that |S| = m, suppose is the bidding strategy obtained from Then, b is a safe bidding strategy. As S was chosen arbitrarily, 8,, (H-) C 8m
28

---

Learning Safe Strategies for Value Maximizing Buyers in Uniform Price Auctions
Proof. Let S contain b < kim and b be constructed per Algorithm 3. Then, for any j E [m],
bj = bi, wais' and Qj- = =Q
Thus, a safe bidding strategy.
The rest of the proof follows similar to that of Theorem C.6 which gives the desired result.
C.5. Proof of Theorem 5.5
We need to establish upper bounds on A m² .
From Theorem C.6 and Theorem 5.3, we have:
max
D'Ey
r= 8Lb
T
A gg M- 11 mn
maxbeu
1= V(b:
b'Eg N
V(b';BL)
max EE "- Et=1 3(b";
El 3(
maxbelt, U E V(b: BL)
max
b"ETm
2m''
= =A AAg H- Jn- un!
Fm
m
D. Tight Lower Bounds for Results in Section 5
D.I. Tight Lower Bound for Theorem 5.3 (For m =
In this section, we construct bid history. H-_ and valuation curve v (equivalently the Ui,) for which the upper bound on Ay " -u presented in Theorem 5.3, is tight. Recall that for any choice of H-, - .ug. (HL-) I 2 64_ where O2. < maxje]m] ( ブ5 /Wa)) To minimize 0x_ we choose a valuation curve that very weakly decreasing. We then set the competing bids such that Q, < Q2 for all E [m]] Finally, we determine the values of [Ti,ol and |T,,|| for which the upper bound tight. See the definition of these quantities in Appendix C.I, where the first part of the theorem proven.
We present the when the cases are the same, for 2 the construction is more involved, and hence presented separately. Formally, for any ő E (0, 1/2), we design a bid history, H.,, and valuation vector, v for which A g #- ,1; (H v) 2 2 - 8.
1 below. The case for m > is deferred Appendix D.2. Although the main idea for both
Let M = 2 [2] Suppose v = [1, v,.,,... ............................... w| E R M target Rol = 0 and v = 4e where c = 7(1-1/M) that (0, 1/8) as 5 < 1/2. Let T = M and K = M 1. The bid history is defined as:
8-1/M 5 Observe
1 C,
ift < M - and j =
B (
if S M and S j S K
c,
ift M and 1 1 K
where >> W1. The bid history presented in Table I.
Table 1. Bid history for tight lower bound for m = 1. Here. C > 1 and c is a small real number.
t =
t t=
t =
1 t= M
C
C
C
C
C
C
1 1-c 1-c
1 1-e
Notice that the constructed H_ contains M rounds with high competition (where the bidder can acquire at most 1 unit), while there is one round with minimal competition, allowing the bidder to obtain any desired number of units. The
29

---

Learning Safe Strategies for Value Maximizing Buyers in Uniform Price Auctions
I-uniform safe bidding strategies of the form (Mgg q) do not perform well universally all rounds because with increase in y. despite the increasing demand (i.e., Q). the bid value Wy decreases, thereby reducing the likelihood of acquiring any units.
Notations. For a given bid history H recall that for any m E N, D (H-) = argmax DET" Σ V(b; (L)) We
define VOPT (H-) = Ei= V(b OPT :H the value obtained by b (H-) over the bid history H... Similarly, b,AA (H.-) = ar,m Ei= ((b: (3) and V-AAFE (H-) = = V(b,, (
Computing the optimal strategy in - We observe that no bidding strategy in - can obtain more than 1 unit the first . rounds and M units in the final round.
We claim that bPPT (H-) = (1, M). Observe that D (H-) is allocated I unit in each of the first M - rounds and M units in the final round. Hence, it is allocated the maximum number of units possible. To verify that bPPT (H-) ) is feasible for the bid history, notice that for Vt E [M - 1(36) = I wi = 1. For round = M, as > M,
p(3)) =
WM = μ 1 (1 - . 46), where = M
implying that Rol constraint is satisfied by PPPT (H-) in round / T. So, VOPT (H-) = M r(M -1).
Computing the optimal strategy in U. Here, argue that the optimal strategy in 21 is (w1, 1) (1, 1). Observe that the strategy (1, is allocated unit in each round. Hence, it obtains total value of M.
As 3- (1) = -1-c>
w2, for -,,,..., .M 1, bidding (Mig 9) for q 2 2 does not get any value in the first M rounds. Bidding (w.,. q) gets exactly y units in round M as wy > e for any q 2. So, for 2 S q M, the total value obtained by bidding (wiq q) is 1 + (q 1) q. Hence, V/SAFE (H-) M, which is the value obtained by the safe
strategy (w1, = (1, 1). So,
V/OT (HL) V,SAFE (H-)
M + vMM 1)
2M 4eeM - 1) 2-
-h an (H-.v)
M
M
D.2. Tight Lower Bound for Theorem 5.3 (For m 2 2)
In this section, we design bid history H_ and valuation vector, v such that for any E 10, By definition, for any H._ and m 2 2.
A Agm - uu
(H-, v) 2 2-
VOPT (H.). VSAFE (H-)
VOPT (H-).
- 21
v)
SVFEFFE (H-)*
(46)
where the second inequality follows because Aus 21 I m (by Theorem 5.4). So, instead of computing SAFE (H-) directly which requires solving a DP, we obtain V,ŠÄFE )) and show that the bound is tight.
1.2.1. CONSTRUCTION OF H...
We first decide all the parameters.
Fix m 2 2 and any integer N 2 2[7
Let M = 22m-1 Consider T = =N22m1 rounds and K = 222m-1 + units in each auction.
L't = mm6[2m--)) I/N
2(1-1/N)
<
2 7.
$ <
1. Set e such that e' = e (N2m-1 (
Consider valuation vector v [1, ........ U] such that = 1 2e', and target Rol 70 0. Partition the 2/ rounds into 2m partitions such that the first partition has I round and the jth partition has N N rounds for 2 < j < 2m. Each partition has identical competing bid profile submitted by other bidders. In particular,
1. The first partition (containing one round) has all the bids submitted by others as Wyym 141 +
30

---

Learning Safe Strategies for Value Maximizing Buyers in Uniform Price Auctions
2. i and is odd, for the j partition (of size N N2-2), the smallest N2m-j + winning competing bids are 10 1+1 and the remaining bids are C > W1.
3. j and j is even, for the juh partition (of size N 22-2), the smallest N2m-J winning competing bids are pmm 1+1 + and the remaining bids are C > w1.
We present an example for such a bid history in Table 2.
Table Bid history achieving tight lower bound for 2. Each round in the same partition has identical competing bid profile. Total number of units in each auction is K = No + 1.
Partition 1
Partition 2
Partition 3
Partition 4 t [N2 + 1, N:
t=1
t [2
t [N + 1,
bids are
N N² + bids are C
N3 N bids are
N bids are C 1 bid w2 +
N + 1 bids are WN441 +
2 bids are Wx241 + c
N + bids are WN+1 +
D.2.2. COMPUTING DOPT (H-)-
We make the following claim about the optimal m-uniform bidding strategy for the constructed H...
Lemma D.I. For the aforementioned H.,, OPP (H-) ((b1,q1),-... ...,, (Dms qm)) where
(L, (bj,q)) 9:) (WN9y-2,N221 - i ssijmm m..
=j=1
(47)
Furthermore,
VOPT (H-) 22m-1 + (2m 1) N2m-2
Proof. We begin by a crucial observation that the bid history does not allow obtaining more than N2m-j units in the jth partition while satisfying the Rol constraint, irrespective of the number of bids submitted by the bidder. To verify this, note that, the maximum number of units that can be allocated to any bidding strategy in the jth partition either 22m or 22m-j (depending on if j is even or odd). Suppose contrary our claim, the bidder is allocated 2/ + 1 units in the some round l. in the jth partition by bidding some b. Let G (b, 3 be the complete bid profile. So, p(B* 2 Wx2m-141 + but x33)) = 2m
indicating that the Rol constraint is violated, which verifies claim.
So, the total number of units, Nownt that can be obtained by the bidder over all the rounds is:
2m
Nistal & 22m-1
2m Caam-jj(Ni 1(Ni-1 N = 2mm22m-1111 (2m - 1)N2m-2 == Niaxx-
Now, we compute the the number of units obtained by bidding OP (H-) and show that it is allocated Nmax units for the constructed bid history, demonstrating that it is the optimal bidding strategy.
Consider any auction in the jth partition. The lowest winning bid in the bid profile is Wxzm-141 + e. Note that the unique bid values (ignoring the quantity for the sake of brevity) in 1,OPT (H-) are b = (1, WN.,.... W2 We claim that the m
winning bid values of OOPT (H-) in the jth partition are b = {1, WNz,.... Wyzm+zl-1/21 This is true because the least bid value in b is greater than wym i41 + E, i.c.
ymm RL 5/2] (WNam-141 + c) 2 WNam-) (WN2m-141 +
1-
2e.22m 2 -c
N2m N22-j +
-c=
2 (pm--((N2)) (N2m-) + 1)
Let N, denote the number of units allocated to OPT (HL) each auction in the jth partition. There are two cases:
31

---

Learning Safe Strategies for Value Maximizing Buyers in Uniform Price Auctions
for j odd, recall that for the j partition (of size N 2 the smallest N2m-j + winning competing bids 22 341 + and the remaining bids are C > w1. Then,
N₂ N +
(N -N N2m-j.
(b) For j even, recall that for the jth partition (of size N - 2 the smallest N2m-) winning competing bids are WNam--54 + e and the remaining bids are C' > W1.
m+1-
(N2 (N2--1-Ne -N22-39 } min mninNNm--j, N2m-mtt) = N2m-j_
N = min N2m-3,N+ N
Σ 2=
Here, the minimum is taken over two quantities where the first quantity is the number of competing bids less than C in any round in the j partition and the second quantity represents the total demand of the winning bids in bOPT (H-) for that round. So, the total number of units obtained across rounds
2m Σ
N2m
N2m-J ( - - 2mm.2m-11 - (2m 1)N2m-2
As this is the maximum number of units that can be obtained by the bidder, OPT (H-) ) is optimal. The total value obtained by bidding DOTT (H-) is
2m
OPT (H.-) 1+ (N2m-1 1)0
(N2m-J 1)u) -
1=2
= -2 + (2m - 1)(N2 -
D.2.3. COMPUTING SASAEE (H.-)
Recall that we compute V/SAFE (H-) and invoke the bounds on Aus., ug. instead of directly evaluating V-SAFE (H-).
Lemma D.2. For the aforementioned H-, DSAFE (HL = (1, 1) and V/SAFE (HL- = 2-m-11
Proof. The basic idea to enumerate the total units (value) that can be obtained by bidding (my q) for E [N and then finding the maximum of those values. As q can be exponential in m, we exploit the structure of the bid history to compute the objective in an efficient manner.
Suppose g 1. The maximum number of units (value) that can be obtained by bidding (1,1) is trivially 22m-1, S, (1, 1) obtains total value 22m-1
Suppose 2 2. Furthermore, assume 22m < S. 22mm-++1, for some 2 5 < 2m. Consider any bid of the form
(wgg q). Bidding (Wg, q) does not obtain any units the partitions indexed by j.j + 1...., 2m as wg is strictly less than the least winning competing bids in those partitions, i.e., Wgg S Wyam-s-1 < Wymm-ee + e, for any 8 E (i. I,..., 2m),
So, 22m-3 < S N2m--+t s+1 (W)g. !) gets no units
2m
N
N 2m - auctions.
In the remaining N auctions it can win at most y units. So, the maximum value obtained by (w,, 4) for any q is N 2 + (q - 1)u) < 2 + (22m-1tt 1)v) = N 2 + 222m-1 N5-2)u < 22m-1
where the last inequality holds as w < 1. Hence, DSAFE (H-) = (1, and SAAAFE (H-) N2m-1
32

---

Learning Safe Strategies for Value Maximizing Buyers in Uniform Price Auctions
Hence, from Lemma D.I, Lemma D.2 and Eq. (46)
VOPT (H--) v)
N2m-1 (2m 1) N2m-22j
3m 2m
m mVSSAFE (H-)
=
m.
2mN22-11 - (2m 1)N2m-2 26' - 1)( -N22m N2m-2
M222m
= 2 2m 1-7-11
+ 26 22((1 ))
m
N
= 2 - 8,
where the last step follows by substituting the value of é' and thus concludes the proof.
D.3. Tight Lower Bound for Theorem 5.4
In this section, we construct bid history H... and valuation vector, v such that for any E (0, }1, Aur (H_,v) ie., the upper bound is tight for m' 2 m + (If m = m, Au u = 1 implying the bound is tight). Recall that Theorem 5.4 states that Aug, un S m for any m 2 So,
2 m²
8,
m
SAFE (H-)
V-AFFE (H--
Au- my U. (H_
-Au uu; (H-, v).
(48)
VSAFE (H-)
m SAFE (HL-) 171
We now establish a lower bound on Auc (H.. v).
D. CONSTRUCTION OF H... We first decide all the parameters.
Fix m 2 2 and any integer N
> m'
Let .M Nm' Consider T Nmm rounds and K -Nm'=1 units in each auction.
Let
m6/(m' - 11-1/N
2( 1j I. Set such that e' N 1N 10mm-11 + 1).
2(1 1/N)
Let the valuation vector be v 1, u) such that = 1 - 2e', and target Rol, 7 0. Partition the N rounds into m' partitions such that the first partition has 1 round and the jth partition has N No-2 rounds for 2 s S m'. Each partition has identical competing bid profile submitted by the other bidders. In particular,
1. The first partition (containing one round) has all the competing bids to be wym'-141 + C.
2. For 2 S j S m', the jth partition (of size NO-1 - ND-2); the smallest Nm' + 1 competing winning bids are Wm1-1441 + and the remaining bids are C' >> W1.
We present an example for such a bid history in Table
Table 3, Bid history attaining tight lower bound for m' = 4 (and m = 1). Each round in the same partition has identical competing bid profile. Total number of units each auction = 3
Partition 1
Partition 2
Partition 3
Partition 4
1=1
1 E [2,
/ E [N 1, N2)
L L [2 + 1, N:3
bids are C N bids are wxa41
N3 N2 bids are
N bids are
N3 2 bids are bids are w2 + c
2 + bids are WN241 +
N 1 bids are WN+1 +
33

---

Learning Safe Strategies for Value Maximizing Buyers in Uniform Price Auctions
D.3.2. COMPUTING b,AF (H-)
We make the following claim about the optimal m' m'-unfoorm safe bidding strategy for H.. Lemma D.3. For the aforementioned H_,, b (H-) ((b1,11) (1:.).).................. (v pm)) where
(1,1),
ifj =
(bj. 91) N 2)
(49)
if2 S S ml
Furthermore,
SAFE (H.) Nmm + (m' 1)(Am' N Nm''220
Proof. We begin by a crucial observation that the bid history does not allow obtaining more than Nw units in the jth partition, while satisfying the Rol constraint, irrespective of the number of bids submitted by the bidder. To verify this, suppose contrary to our claim, that the bidder is allocated N -j + units in the some round t in the 5th partition by bidding some b. Let 3 = (b, 3² be the complete bid profile. Hence, p(3') Z W W 2 + but x(B) N -J + indicating that the Rol constraint is violated which verifies our claim.
So, the total number of units, No that can be obtained by the bidder across all the rounds is:
m
Nootal S Nm +
Nm -SN--1 -N--2) m m'N''=1- (m' 1)N'' 22: Nmax.
Now, we compute the number of units obtained by bidding b (H-) and show that it is allocated Nmax units across all the auctions, implying that it is the optimal bidding strategy.
To show SSAF (H-) is optimal, consider any auction in the 5tt partition. The lowest winning competing bid is WN='-141 tc. Note that the unique bid values (ignoring the quantity for the sake of brevity) in b (H-), provided in Eq. (49), b {1, uN,,...... W J. We claim that the winning bid values of bSAFE (H-) in the jth partition are b {1, WN....... ......... xm }. Again recall that for 2 I j S m', for the jth partition (of size N -N--2), the smallest N -1 competing winning bids are w 4 + and the remaining bids are C W1. And here, the least bid value in b is greater than w N'' -wm'-141 -44 i.c.
1-v
2cN' -1 +1) -
W (W +6) Nm (N''- +
Nm''J(N'''3+1)
Moreover, observe that the bidder is allocated the maximum number of units demanded for each of the bid value in b. So, the number of units in each auction in the 5th partition by bidding bSAFE (H-) is
m f+1
N
1+
Σ
(N--1_Ne = NJ
2=2
Hence, the total number of units obtained across all rounds is
m
Nm
pm''-((N--- 1an--sNii-N---- = m''N m''''-11 (m' 1) Nmaax
2=2
As this is the maximum number of units that can be obtained by the bidder, bSAFE (H-) is optimal. The total value obtained by bidding bSAFE (H-) is given by
m 1 23- + (N'''5 -1)u)
SAFAE m!!
(HL =1 (N 1)v +
1=2
= (m'
1)(N"
Nm'
34

---

Learning Safe Strategies for Value Maximizing Buyers in Uniform Price Auctions
D.3.3. COMPUTING bSAF (H-)
In this section, we compute the optimal I-uniform safe bidding strategy for the bid history, H... Lemma D.4. For the constructed H.,, A (H-) (1, and ViSAFE (H-) N
Proof. The proof is similar that of Lemma D.2 in the sense that it involves enumerating the total units obtaining by submitting (wgy 9) for all [N in efficient manner by leveraging the structure in the bid history.
Substituting values from Lemma D.3, Lemma D.4 and Eq. (48)
ucz uC (HL_, v) 2 Auu ug ()- = VSAFE (H--)
1
Aue
mn
m MVSSAFE (H.-)
Nm (m' 1)(Nm' Nm0
mNN
m (m' - 1)N'' 26 - 1) -Nm'-2
mNN'-1
m'
(m' -1) (1 +26
)) )
171
m
m
8,
77
where the last step follows by substituting the value of é' and thus concludes the proof. Corollary D.5. As U 3 for all m E N, the upper bound in Theorem C.6 also tight, i.e,, for any m' m and ô E (0, $1 there exists a bid history H and valuation curve v such that A ggth -m (H-, v) 2 m
au
D.4. Tight Lower Bound for Theorem 5.5
In this section, we present a bid history H. and valuation vector, such that for any 5 E (0, 21, A Ag iee, the upper bound is tight for m 2 m.
(H. v)
2m' 5,
m .1c.
m
Recall that Theorem 5.4 states that Aur, u; S m for any m 2 1. So.
VOPT (HL)
VOPT (HL V/SSFFF (H-)
gx 10 (H-,v)=
(H,, v).
(50)
/SAFE (HL-)
3" 21
m
Recall that for showing tightness of the bound for Theorem 5.3 for any m 2 2. we computed a lower bound on Agx _u; (H_ (cf. Eq. (46)). Thus, we consider a valuation curve and a bid history that has a structure identical to the one presented in Appendix D.2 but with the following modified parameters,
Fix m² 2 and any integer 2 2 2m
Let M N2m' -1 Consider T N2m' rounds and K 212m' units in each auction.
Let
m2m 1/N1/N 2(11//M
2(2m² 1] Set such that e' e/22m' 112m''11p 11 ((22mm 1).
Consider valuation vector [1, v, u] such that 1 1-2e 2e', and target Rol 7 0. Substituting the values from Lemma D.1 and Lemma D.2,
1
22m' + (2m' 1) N2m' 22)
A 9" .1p. (H_,v)
v) 2 m
A
2 21 (H-,v)
m2Nm'
2mn' 22m/ (2ml 1) -2 2e 22'm 1)(N2m' -N2m'
M222m
2m'
(2m' - 1)
+ 26 (2(11 (1-14
N 1)
N
35

---

Learning Safe Strategies for Value Maximizing Buyers in Uniform Price Auctions
2m' 8, m
where the last step follows by substituting the value of c' and thus concludes the proof.
E. Simulation Details
In Section 5.3, we conducted numerical experiments to estimate the richness ratio (or equivalently uz,,u;) in practice for the classes of bidding strategies discussed earlier. We now discuss a few details regarding the same.
Dataset. We estimate the richness ratio for the EU ETS emission permit auction data for 2022 and 2023, However, only aggregate statistics of the submitted bids publicly available for privacy reasons. Hence, we synthesize individual level bid data from these available statistics. The exact procedure reconstruct the bid data is presented in Appendix E. We sample T Unif[100, 300] auctions and let
sample the values from the Unif(O, 1] distribution. In each simulation, M ~ Unif[10, 80]. We vary m to yn 10 and average over 100 simulations to obtain plots in Fig. 4. As computing VOPT (H._) (the value obtained by the optimal bidding strategy in F can be non-trivial, we obtain a uniform upper bound for VOPPT (H-) that is independent of m (see details in Appendix E.2).
E.1. Reconstructing Individual Bid Data
We obtained the publicly available auction data for Tmaxx 443 EU ETS emission permit auctions held in 2022 and 2023 (EEX, 2023). For each auction indexed by & [T [Tmux], we have the following relevant information: the minimum bid (bmin)) the maximum bid (bmax). the average of the bids (bwwg) the median of the bids (bmea), and the number of bid-quantity pairs submitted (wiab). We normalized the bids to be in [0, 1]. For all rounds I, Ding z b/med (linear regression yields coefficient 1.01 and intercept -0.008).
Upon further investigation, we observed that, except a few, a significant number of auctions had either 8mii z blvg < By /A (Type 1) or Mnii < blng Ri U/ax (Type II). As Ulngg Rs by Umed VI, we deduce that for Type I, most of the bids are concentrated the interval 16tin 26 by bruin whereas for Type II, most of the bids are in the interval [26 bymaae m
We posit that for Type I (resp. Type II) auctions, E (0, 1) fraction of the bids (n are in b 2b D Puin (resp. (26 - by byax ( and the 1 - S fraction of bids are in [26 (resp. Type II) auctions, 28 > byin + bymax (resp. 2g < bymi + bmax)) we assume that all the bids are uniformly present in the interval (minn be bmaax) With these assumptions, we generate individual bid data for each auction by sampling uniformly from these intervals.
1m ([ax (resp. 1 avg bmax)) If for Type I
After generating the individual bid data, we compute the metrics for the reconstructed bids (say Bivg) for each auction and reject those with a relative error of at least 8 (tolerance). For our simulations, we set 0.05. We perform grid search for to maximize the number of auctions where the metrics of the reconstructed data are within 5 relative error of the actual metrics, and obtain that f = 0.97. Following this pre-processing, we have reconstructed individual bid data for T = 341 auctions. The bids are normalized to be in [0, 1].
E.2. An Uniform Upper Bound for VOPT (H-).
For any bid history, H_ = [ suppose bOPT (H-) is allocated ra units in any round L. Then, by Lemma C.5 (1), we know that (Wey, rt) also obtains ra units in round f. So,
(b OPT (H-);B²)= = V ((w,, r(); S max V(b; be
T
T
VOPT (H-) = Σ
V(boP
OPT (H-): < Σ
max V(b; V(b:
m
beuf
1=1
F. Resolving Ties
We first emphasize that the effect of resolution of ties on the objective function under the value maximization behavioral model is fundamentally different from the quasilinear utility maximization model. To illustrate this, consider a single-item second price auction with two bidders each valuing the item equally at v. Assume that both the bidders bid v and there exists definitive tie breaking rule (either randomized or deterministic). If the bidders are considered quasilinear utility
36

---

Learning Safe Strategies for Value Maximizing Buyers in Uniform Price Auctions
maximizers, the objective function value (value obtained minus the payments) for both the bidders is O. However, under the value maximization model (assume 7 0 for both the bidders), the objective function value for the winning bidder is and O for the losing bidder." 12 Hence, we need to carefully analyze the key results of our work in the event of ties.
In the context of multi-umit auctions, we can classify ties into two informal types: (a) 'good ties -ties occurring at any bid other than the last accepted bid (LAB) and (b) 'bad ties', which are the ties occurring at the LAB. All the results in this work are unaffected case only 'good ties' occur. Thus, we focus on 'bad ties' for the rest this section. For this discussion, we consider a public, deterministic tie breaking rule under which ties are always broken favor of lower indexed bidder. In the presence of ties, the undominated class of safe bidding strategies is still the class of nested strategies (Theorem 3.2). The tie breaking rule is incorporated into the decomposition in Lemma 4.1 and computing the edge weights in the DAG in the offline and online settings in Section 4, ensuring that the maximum weight path in the DAG gives the optimal offline solution and Algorithm I achieves sublinear regret in the online setting.
Altthoug,, the total (liquid) welfare in both cases.
37


Reviews:
[{"review_id": "2RvJNyZYfi", "reviewer": "Reviewer_zN7V", "summary": "This paper focus on one buyer’s bidding strategy in repeated uniform price multi-unit auctions. The buyer aims to maximize value under RoI constraints in each round. The authors restrict the buyers to adopt an $m$-uniform bidding format and introduce the notion of safe bidding strategies, which ensure that RoI constraints satisfied regardless of other buyers’ bids. They characterize a class of safe strategies and show that computing the optimal m-uniform safe bidding strategy is equivalent to finding the maximum weight path in the directed acyclic graph, simplifying the computational problem significantly. Building on this, the authors propose two online algorithm, the one under full-information feedback and the other one under bandit feedback.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their encouraging feedback. We're glad the reduction to the maximum weight path in the directed acyclic graph and regret guarantees were clear and appreciated.\n\n**Regarding the comment that the paper might only interest a small group of researchers:** We believe that the paper appeals to both practitioners and theorists. The key motivation of this work is emission permit auctions which are becoming popular to curb industry emissions. We provide a simple class of strategies and a learning algorithm that is robust to much stronger benchmarks (Section 5) and pliable to more nuanced bidder behaviors (Section 6).  Moreover, several proof techniques, specifically in Section 5, are novel and might be of broader interest, as pointed out by Reviewer 9dTj.\n\n**Regarding the comment on the performance drop of safe strategies compared to a larger class of bidding strategies**, we would appreciate clarification on what is meant by the “larger class.” \n\n**Comparison to $m$-Uniform RoI-Feasible Non-Safe Strategies.** If the reviewer is referring to the class of $m$-uniform RoI-feasible bidding strategies that are not safe, the performance drop of safe strategies compared to this larger class of strategies (chosen by the clairvoyant) is natural and unavoidable: the bidder (learner) must ensure that RoI constraints are satisfied **without knowing the competing bids** and therefore resorts to safe strategies, while the clairvoyant can choose an optimal strategy with full knowledge of the competing bids.\n\n - **Performance Gap is Bounded.**  We would like to highlight that the performance gap, as stated in Theorem 5.3, is **bounded and independent of m**. Moreover, this bound is tight (please see Appendix F.1 and F.2) implying that it can not be theoretically improved.\n\n - **Empirical Performance Gap is Even Smaller.** Empirically, as illustrated in Figure 3 (left side), in practice, the optimal RoI feasible strategy that is not safe achieves at most 1.25x of the value obtained by the optimal safe strategy; significantly better than the theoretical bound of 2.\n\n**On the Gap Between $m$- and $m'$-Uniform Strategies.** We thank the reviewer for highlighting the potential performance gap when the bidder is restricted to $m$-uniform strategies, while the clairvoyant benchmark selects from a richer set of $m'$-uniform strategies with $m' > m$. **Below, we explain why this gap is expected, how our theoretical bounds characterize it tightly, and why it is unlikely to be a concern in practice.**\n\n  - **The Choice of $m$ is Flexible.** We would like to clarify that the choice of $m$ (i.e., the bid granularity) is made by the bidder and is not fixed. In other words, the bidder is not constrained to use a small value of $m$. While a larger $m$ offers the potential to improve performance, it also increases the size of the action space and the time it takes to learn the optimal $m$-uniform bidding strategy (the space/time complexity of the learning algorithm is $O(mM^2)$ as stated in Appendix C.3.3).\n\n - **Our Theoretical Bounds are Tight.** The upper bounds in Theorems 5.4 and 5.5 are tight, e.g., for Theorem 5.4, for any $\\delta \\in (0, 1]$, we construct a problem instance for which the ratio of the value obtained by the optimal safe bidding strategy with at most $m’$ bid-quantity pairs to the value obtained by the optimal safe strategy chosen with at most $m$ bid-quantity pairs is at least $\\frac{m'}{m} - \\delta.$ \n    \nPlease refer to Appendix D.5 and D.6 for the formal proofs and Appendix F.3 and F.4 for the construction of these instances. Thus, theoretically, it is not possible to improve this bound. In practice, bidders typically use small values of $m$, such as 4 or 5 (Line 173-175, right column), which we believe are reasonable trade-offs. \n\n  - **Theoretical Worst-Case is Rare in Practice.** As shown in Appendix F.3 and F.4, the problem instances that attain the worst-case upper bounds are highly nontrivial, and their constructions are quite intricate. For instance, the valuation vector must take the form $ \\mathbf{v} = [1, 1 - \\epsilon, \\ldots, 1 - \\epsilon]$ with $ \\epsilon = O(\\frac{m \\delta}{m'}),$ and parameters such as  $M = K = T = O(N^{m'})$ where $N = O(\\frac{m'}{\\delta}).$ The competing bids also need to be carefully designed across rounds. **This level of intricacy strongly suggests that such worst-case gaps are unlikely to arise in realistic settings.**\n\n  - **Empirical Gaps are Much Smaller.** Our experimental results corroborate this insight. In particular, Figure 3 (right) illustrates the empirical gap when fixing $m = 1$ and varying $m'$. While Theorem 5.4 provides an upper bound that grows linearly with $m'$, in practice, the observed gains plateau quickly. For instance, increasing $m'$ to 10 results in only a $\\sim$1.25x improvement—far below the 10x theoretical bound. This demonstrates that while the theoretical worst-case exists, it is rarely encountered in practical scenarios.", "claims_and_evidence": "I find all the claims clear and convincing.", "methods_and_evaluation_criteria": "The proposed methods and evaluation criteria look reasonable to me.", "theoretical_claims": "I did not check the proofs. But the theoretic results align with my understanding of the techniques used and many similar results appear in the literature.", "experimental_designs_or_analyses": "There is only one experiment, which looks convincing to me.", "relation_to_broader_scientific_literature": "The paper may only interest a small group of researchers (the mechanism design community and the bandit algorihtms community).", "essential_references_not_discussed": "All the necessary references are properly discussed.", "other_strengths_and_weaknesses": "Strengths:\n1. The paper characterized the minimal class of safe bidding strategies and show that the solution of the optimal safe bidding strategies is equivalent to finding the maximum weight path in the directed acyclic graph. This reduction simplifies the problem and provides a clear computational pathway for finding optimal strategies within this class.\n2. The paper proposed two online algorithms achieving sub-linear regret under full-information feedback and bandit feedback respectively.\n\nWeaknesses\nWhile the focus on safe bidding strategies provides valuable insights, the performance of the proposed strategies diminishes when considering a larger class of bidding strategies. In particular, Thm 5.4 and Thm 5.5 indicate that when $m’$ is significantly larger than $m$, the term $m’/m-\\sigma$ becomes very large. Thus, the performance of safe bidding strategy is worse comparing to a larger class of bidding strategies. Consequently, the effectiveness of the proposed algorithms may be limited when extended beyond the specific class of safe bidding strategies.", "other_comments_or_suggestions": "I do not have other comments.", "questions_for_authors": "Is it possible to solve the issue mentioned in the weaknesses above?", "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": "FUD2VMjLIl", "reviewer": "Reviewer_9dTJ", "summary": "This paper introduces the notion of safe bidding strategies for value-maximizing buyers in uniform price multi-unit auctions, ensuring return-on-investment (RoI) constraints are met. A value-maximizing buyer aims to maximize the received value, while only factors in the payment in the RoI constraint. In a uniform price multi-unit auction, the auctioneer sells $K$ identical units of a single good to buyers who may demand multiple units at decreasing marginal values, with the per-unit price set at the $K$-th highest bid. The private type for each buyer is then a vector of values describing the decreasing marginal value for the $k$-unit. To reduce the exponentially large bidding space, in practice, buyers adopt an $m$-uniform bidding format, where they submit $m$ bid-quantity pairs $(b_i, q_i)$ to demand $q_i$ units at bid $b_i$ instead of the vector of bids for each additional unit.\n\nThis work characterizes a finite class of safe strategies and develops a polynomial-time algorithm to learn the optimal safe strategy with sublinear regret. The paper also evaluates the performance of safe strategies against a clairvoyant with a richer class of strategies, computing the optimal richness ratio $\\alpha$.  Notably, when the clairvoyant selects the optimal bidding from the class of strategies that are RoI-feasible (not necessarily safe) and have at most $m$ bid-quantity pairs, the richness ratio $\\alpha$ is $1/2$, independent of $m$.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive feedback. We're glad the theoretical depth and effort came through. The changes suggested by the reviewer are easily manageable with the additional page allowed for the camera-ready version, and we believe they will improve the organization of the manuscript.\n\n**Regarding paper being dense:** The density of the presentation is partly due to the space constraints given the breadth of our results. We clarify the questions the reviewer has raised and present a plan to update the model section for better readability.\n\n**Regarding the notion of bids:** Each bidder submits a vector of bids $\\mathbf{b} \\in \\mathbb{R}^M$ using the $m$-uniform bidding format:  $$\\mathbf{b} = \\langle (b_1, q_1), \\dots, (b_m, q_m) \\rangle.$$\nThat is, the bidder bids $b_1$ for the first $q_1$ units (i.e., the first $q_1$ entries of the vector are $b_1$), $b_2$ for the next $q_2$ units (i.e., the next $q_2$ entries are $b_2$), and so on. This description is included in the introduction (Line 50-52, right side), and as the reviewer suggested, we will add further clarification in Section 2.1.\n\n**Regarding valuations:** In the repeated setting, the bidder's valuation curve remains fixed across rounds, which is standard in the literature on learning in multi-unit auctions (e.g., [1, 2, 3]). The bidder is allowed to submit different bidding strategies in each round to minimize (approximate) regret over time, which is ensured to be sublinear. We will make this assumption explicit in the camera-ready version.\n\n[1] Brânzei, S., et al. Learning and Collusion in Multi-Unit Auctions. NeurIPS, 2023.\n\n[2] Galgana, R. and Golrezaei, N. Learning in Repeated Multiunit Pay-as-Bid Auctions. MSOM, 2024.\n\n[3] Potfer, M., et al. Improved Learning Rates in Multi-Unit Uniform Price Auctions. NeurIPS, 2024.\n\n**Regarding the number of sold units and RoI constraints:**  The reviewer’s understanding is correct. In each round, $K$ units of the goods are sold independently (see Lines 143–147, right column), and the RoI constraint is imposed on a per-round basis (see Remark 2.1, Lines 165–187, left column, for a detailed discussion). \n\n**Regarding Section 2.1:** We thank the reviewer for the helpful suggestion. In the camera-ready version, we will restructure Section 2.1 into three subsections: (1) preliminaries, including notations and terminology; (2) the standalone multi-unit auction format, including allocation and payment rules, the $m$-uniform bidding language, and the per-round RoI constraints; and (3) the repeated setting, introducing the new notations and formally stating the learning-to-bid problem and performance metrics.", "claims_and_evidence": "The analysis and proof in this work is comprehensive and non-trivial.", "methods_and_evaluation_criteria": "The main results from this work are i) characterization of the safe bidding strategies, ii) poly-time learning to bid algorithms, and iii) various bounds proved on regret and richness ratios. Although there are some complementary empirical sections, the most technical part seems to be the theoretical ones.", "theoretical_claims": "I didn’t verify all the details, but the theoretical results look sound to me. The amount of work is really impressive (~25 pages of different proofs).", "experimental_designs_or_analyses": "I didn’t check carefully as this is mainly a theory paper.", "relation_to_broader_scientific_literature": "The proof of bounds might be of broader interests.", "essential_references_not_discussed": "I don’t know any.", "other_strengths_and_weaknesses": "The theoretical contribution of this work is non-trivial and the mount is pretty impressive. I see one main shortcoming of this work is that the paper seems to be too dense, and the presentation could be largely improved. For example, in the “Learning to Bid in Repeated Settings” paragraph in Section 2.1, the space of the bid is undefined, and only gets further discussed in “Bidding Language” on the next page. For the repeated setting, it remains unclear to me whether those values are identical across rounds or re-drawn at the beginning of each round. It is also confusing whether the $K$ unit of goods are sold within one round or spread across multiple rounds. It is also confusing whether the RoI constraint is imposed per round or across multiple rounds. If I understand correctly, both the $K$ unit of goods and the RoI constraints are well-defined within each round, and only the learning to bid algorithm needs to span over multiple rounds. If that is the case, it might be better to first describe the complete auction, including RoI constraints, etc. Only after the auction is completely defined, state the learning to bid problem on top of the underlying repeated uniform price auctions.\n\nI would have given a higher score if this work is better organized.", "other_comments_or_suggestions": "See above.", "questions_for_authors": "No further questions.", "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": "TSwSQUDGrT", "reviewer": "Reviewer_gJHK", "summary": "The authors study repeated uniform price auctions with respect to bidder behavior. They consider value maximizing buyer that has return of investment (RoI) constraint. The paper proposes safe bidding strategies that allow bidder to be sure that RoI will not be violated in the future rounds. The main contribution is learning algorithms that are efficient (they have sublinear regret in number of rounds T in both full-information and bandit settings). The work is enriched by considering setups with richer class of competing bidding strategies (non-safe) and relaxation of RoI constraints on each round. Finally, some claims are supported by synthetic experiments.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the encouraging feedback and are glad the theory and structure were clear and well-received. We believe the changes suggested in response to your thoughtful comments can be incorporated into the camera-ready version using the extra page.\n\n**Re the use of Unif[0,1]:** We tested other distributions (e.g., Laplace, truncated half-normal) and found similar trends with minor differences. We chose Unif[0,1] for consistency with prior theoretical [1] and experimental work (Galgana & Golrezaei, 2024). \n\n[1] Ausubel, LM., et al. Demand reduction and inefficiency in multi-unit auctions. The Rev. of Econ. Stud., 2014.\n\n**Re the presentation:** Given the length and technical depth of the manuscript, we chose to present the main contributions comprehensively in the introduction and provide a clear roadmap. As suggested, we will shorten the abstract and use the space to add more proof sketches—especially for Theorem 4.4 (regret lower bound) and the tight instances in Theorems 5.3–5.5, which we believe are novel and of independent interest.\n\n**Re the comment on missing terms/variables:** Could the reviewer clarify which terms or variables are unclear? As noted in our response to Reviewer 9dTj, we plan to add a notation subsection at the start of Section 2 to define all terms more clearly.\n\n**Re the term “bid”:** The term “bid” refers to a single number here. We imply this in the next line (Line 126):  *“… if bidder $i$ has $j$ bids in the top $K$ positions ...”*\n\nThe bidder submits a vector of bids $\\mathbf{b}\\in\\mathbb{R}^M$ using the $m$-uniform bidding format (the bidding language): $\\mathbf{b}=\\langle (b_1, q_1), \\dots, (b_m, q_m)\\rangle,$ where the bidder bids $b_1$ for the first $q_1$ units (i.e., the first $q_1$ entries of the vector are $b_1$), $b_2$ for the next $q_2$ units, and so on.\n\n**Re the  j-th smallest winning bid:** As mentioned earlier, the word “bid” refers to a single number. In a multi-unit auction with $K$ units, each bidder submits multiple such bids and the $K$ highest bids across all bidders win. Thus, the $j$-th smallest winning bid refers to the $(K - j + 1)$-th highest bid overall.\n\n**Re the notion of Clearing Price:** The clearing price (or per-unit price) refers to the $K$-th highest bid, which each bidder pays per unit they receive (see Line 133, right).\n\nWe use Example 1 (Lines 176–186) in the paper to illustrate each term:\nConsider an auction with $n=2$ bidders and $K=5$ identical units. There, $m=2$, and the submitted bids are: $\\mathbf{b}_1 = \\langle (5, 2), (3, 3) \\rangle = [5, 5, 3, 3, 3]$, $\\mathbf{b}_2 = \\langle (4, 2), (2, 2) \\rangle = [4, 4, 2, 2]$. Each entry in $\\mathbf{b}_1$ and $\\mathbf{b}_2$ corresponds to a single bid.\n\nThe sorted list of all bids is: $[5, 5, 4, 4, 3, 3, 3, 2, 2]$. The top $K = 5$ bids (i.e., the winning bids) are $[5, 5, 4, 4, 3]$. The clearing price (i.e., the $5$th highest bid) is $3$. Here, the 2nd smallest winning bid is $4$.\n\n**Re “removing weakly dominated strategies”:** By the definition in Line 256-257, If a safe strategy $\\mathbf{b}$ is weakly dominated by another safe strategy $\\mathbf{b}'$—that is, $\\mathbf{b}'$ yields at least as much value as $\\mathbf{b}$ for **every** competing bid profile, —then a RoI-constrained value-maximizing bidder can safely ignore $\\mathbf{b}$. Therefore, we remove such strategies from the class of safe bidding strategies. \nKeeping them does not improve the bidder’s performance, but removing them yields a **finite** strategy class, which significantly simplifies the design of online learning algorithms. \n\n**Re the unsafe and weakly dominant strategies:** To clarify: **unsafe strategies and weakly dominant strategies are conceptually unrelated** as stated below.\n\nPer Def 2 (Lines 243-251), a safe strategy satisfies the RoI constraint for **every** possible competing bid profile; otherwise, it is not safe (or as the reviewer described,  “unsafe”). Thus, safe and unsafe strategy classes are **disjoint**.\n\nWithin the **safe class**, we further refine the strategy space by removing weakly dominated strategies—those that are never better and sometimes worse than another safe strategy. The notion of weak dominance is therefore defined **only within the safe class**. Considering this, **an unsafe strategy cannot be weakly dominated or weakly dominant** based on our definition in Lines 253–255.\n\n**Re inputs and Outputs of Alg. 2:** The output of Alg. 2 is the updated value $\\varphi^t(e)$ for all edges $e$. \nThe inputs are: the structure of the DAG, for $t \\geq 2$, the values $\\Gamma^{t-1}(v)$, $\\varphi^{t-1}(e)$, and $\\mathsf{w}^{t-1}(e)$ for all nodes $v$ and edges $e$. For $t = 1$ (initialization), only the DAG structure is required.\n\n**Re $\\mathbf{w}$ in Thm 4.2 and Alg. 1:** $\\mathbf{w}\\in\\mathbb{R}^M$ is the average cumulative valuation vector where $w_j=\\frac{1}{j}\\sum_{k=1}^j v_k$, i.e., the $j$-th entry is average of the first $j$ entries of the valuation vector as defined earlier in Line 118.", "claims_and_evidence": "The submission is strongly supported by claims in the form of Theorems and Lemmas supplied with proofs. The main contribution of the work – theoretical results. So, the evidence is presented correctly. The work is supported by a large appendix, where all the statements are carefully proven.", "methods_and_evaluation_criteria": "The main contribution of the work – theoretical results. The main methods – proofs are made correctly and are presented in clear way.\n\nThere are some experimental synthetic results to support the claims. They are adequate (I have a minor question – see Q section)", "theoretical_claims": "I’ve not checked all the proofs in detailed way (checking each implication). However, checked all main blocks – they are OK (do not seem contradictory) + Checked carefully several proofs: for Lemma 4.1 and for Theorem 4.2. No issues found.", "experimental_designs_or_analyses": "I’ve read experimental design and analyses (both in the main part – Section 5.3 and Appendix G). \n\n\nLine  2024 “We sample the values from the Unif[0,1] distribution”. This assumption sounds very theoretical. Is it true that in real life (common case) the values are distributed uniformly?", "relation_to_broader_scientific_literature": "The key contributions are related to works:\n\n-\tBrˆanzei, S., Derakhshan, M., Golrezaei, N., and Han, Y. Learning and collusion in multi-unit auctions. In Thirtyseventh Conference on Neural Information Processing Systems, 2023.\n\n-\tGalgana, R. and Golrezaei, N. Learning in repeated multiunit pay-as-bid auctions. Manufacturing & Service Operations Management, 2024.\n\n-\tPotfer, M., Baudry, D., Richard, H., Perchet, V., and Wan, C. Improved learning rates in multi-unit uniform price auctions. In The \n\n\nThirty-eighth Annual Conference on Neural Information Processing Systems, 2024.\nThe main difference: That works assume that the bidders are quasilinear utility maximizers, while this paper study value-maximizing buyers with RoI constraints (which is drastically different setup).", "essential_references_not_discussed": "I’ve not found such", "other_strengths_and_weaknesses": "Strengths\n-\tSolid paper with clear theoretical contributions \n\n-\tVery nice storyline and claim support (decomposition in lemmas/theorems, proofs, structure overall)\n\n\nWeaknesses\n-\tpresentation: \n\no\ta) the story (and contributions) of the paper repeats 3 times with different level details: Abstract, Into, Main part (Sections 2-6). A few numbers of proof sketches\n\no\tb) several missed introduction of terms / variables in code", "other_comments_or_suggestions": "-\tI would suggest to reduce Abstract (~ 3 times) saving space (most content presents in Intro) and use this space to add more proof sketches", "questions_for_authors": "-\tLines 124-125, right part: What is “bid”? In this place of the paper this term is introduced, while not being defined. Is it 1 number, M numbers (per each good), or K numbers? Far-far from this place (page 4) there is the discussion about bidding language, however it does not help define the initial intention in Sec.2.1..\n\n-\tLines 141-142, right part: What is “the j-th smallest winning bid” formally? The questions refers to the previous one as the term bid is not defined earlier (is it 1 number per bidder, or M numbers.. etc). E.g., if a bid is not a single number, then how a comparison between them is organized.\n\n-\tLines 144-145, right part: “the clearing price” is not defined. What is it formally?\n\n-\tLine 255, left part: “removing weakly dominated strategies” I have not found discussion on what is happening with weakly dominant strategies, if keep them. Can it be clarified? I see an example in Lines 236-242 about infeasible strategies that forces to introduce “safe” strategies. Is it true that “unsafe strategy” = “weakly dominant”? If not what is the difference?\n\n-\tAlgorithm 2: Please, specify its inputs and outputs\n\n-\tDefinition of w: In Theorem 4.2 and Algorithm 1 there is usage of w (b_l = w_{z_l}) while it is not defined earlier (within the theorem and the algorithm). In Line 118 right side, I see some definition of w as a function of v (so, in fact, there is w = w(v)), but it is very far from the theorem statement and the pseudocode. I highly recommend to state how w is obtained in Theorem 4.2 and Algorithm 1", "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: The paper studies a value-maximizing, ROI-constrained buyer's bidding problem in repeated uniform price multi-unit auctions.  The reviewers all agreed that the paper is a valuable contribution, and the complaints were mostly about the presentation.  We encourage the authors to improve the paper accordingly based on the detailed suggestions and comments in the reviews.
Decision: Accept (poster)