Robust Auction Design in the Auto-bidding World
Authors: Santiago Balseiro
Yuan Deng
Jieming Mao
Vahab Mirrokni
Song Zuo
Venue: NeurIPS 2021 Poster (2021)
Keywords: auto-bidding
auction design
reserve pricing

Abstract: In classic auction theory, reserve prices are known to be effective for improving revenue for the auctioneer against quasi-linear utility maximizing bidders. The introduction of reserve prices, however, usually do not help improve total welfare of the auctioneer and the bidders. In this paper, we focus on value maximizing bidders with return on spend constraints---a paradigm that has drawn considerable attention recently as more advertisers adopt auto-bidding algorithms in advertising platforms---and show that the introduction of reserve prices has a novel impact on the market. Namely, by choosing reserve prices appropriately the auctioneer can improve not only the total revenue but also the total welfare. Our results also demonstrate that reserve prices are robust to bidder types, i.e., reserve prices work well for different bidder types, such as value maximizers and utility maximizers, without using bidder type information. We generalize these results for a variety of auction mechanisms such as VCG, GSP, and first-price auctions. Moreover, we show how to combine these results with additive boosts to improve the welfare of the outcomes of the auction further. Finally, we complement our theoretical observations with an empirical study confirming the effectiveness of these ideas using data from online advertising auctions. 

Robust Auction Design in the Auto-bidding World
Santiago Balseiro
Yuan Deng Google dengyuan@google.c. com
Jieming Mao
Columbia University and Google srb21554columbit edu
Google
mao jmggoogleee.coom com
Vahab Mirrokni Google mirrrokni@googe.coo com
Song Zuo
Google
szuo0google.com
Abstract
In classic auction theory, reserve prices known be effective for improving revenue for the auctioneer against quasi-linear utility maximizing bidders. The introduction of reserve prices, however, usually do not help improve total welfare of the auctioneer and the bidders. In this paper, we focus on value maximizing bidders with return on spend constraints a paradigm that has drawn considerable attention recently as more advertisers adopt auto- budo-nidding algorithms in advertising platforms and show that the introduction of reserve prices has a novel impact on the market. Namely, by choosing reserve prices appropriately the auctioneer can improve not only the total revenue but also the total welfare. Our results also demonstrate that reserve prices are robust to bidder types, i.e., reserve prices work well for different bidder types, such as value maximizers and utility maximizers, without using bidder type information. We generalize these results for a variety of auction mechanisms such as VCG, GSP, and first-price auctions. Moreover, we show how to combine these results with additive boosts to improve the welfare the outcomes of the auction further. Finally, we complement our theoretical observations with empirical study confirming the effectiveness of these ideas using data from online advertising auctions.
Introduction
As auto-bidding-thee practice of using optimization algorithms to procure advertising slots slots-is becoming the prevalent option in online advertising. growing body of work is revisiting auction
theory from the lens of the auto-bidding world [Aggarwal et al. 2019 Babaioff et al. 2021 Balseiro al. 2021a a Deng et al. 2021b Golrezaci et al. [202c]]. A benefit of auto-bidding that simplifies advertisers' bidding process by asking advertisers for their high-level goals and then bidding on behalf of the advertisers The main difference with classic auction theory stems from the model adopted for agent behavior. Unlike the classic utility maximization model, where each agent aims to maximize its own -insi- utility given by the difference between value and payment, the behavior of an auto-bidding agent is determined by its underlying optimization algorithm. In particular, the prevalent adopted model for the behavior of auto-bidding agents is that of value maximization, where each agent aims to maximize total values subject to an ROS (return on spend) constraint on the average spend per opportunity. For example, two common auto-bidding strategies are target CPA (cost per acquisition) and target ROAS (return on ad spend) auto-bidding, in which an algorithm optimizes the
'See hwtp::/supportt.ttcpo/ wow.pppppp..ooooooooopoooooooo.e peceters/value-oiimmizaooio with-roas bidding and Aggarwal et al. 2019 Balseiro et al. 202 a
and http::/wwww.faccbookk www..k/c////osune///oooeee
Deng el al.
2021b for more background introductions.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

total value (e.g,, the number of conversions) subject to an ROS constraint specified by the advertiser (e.g,, the average spend for each conversion should not exceed a pre-specified target).
One surprising observation when agents are value maximizers is that the Vickrey- Clarke-Groved (VCG) auction, which is truthful and efficient for utility maximizers, is no longer truthful nor efficient. Value maximizers have incentives to strategize their bids and, moreover, there exist auction instances where the social welfare equilibria under the VCG auction is only 1/2 of the optimal social welfare [Agaraal et al. 2019 Deng et al. 2021b] This is because the ratio between bids and values can be very different for each value- value- maximizing agent, and an agent with a low value may end up outbidding other bidders with high values in some auctions, creating allocation inefficiency. While there have been recent work addressing this problem, most previous studies have several shortcomings, e.g., they reduce such efficiency loss by introducing boosts that explicitly or implicitly rely on the accurate knowledge of the advertiser values (Deng et al., 2021b), or they aim to optimize for either value-maximizing buyers or utility maximizing buyers (and not a mixture of auto-bidders) [Balseiro
et al. 2021a], or they aim to optimize only welfare and not revenue (Deng et al.. 2021b].
In this paper, we aim to address the above shortcomings and propose simple auctions taking inaccurate value signals additional inputs and we prove that the auctions have robust approximation guarantees in terms of both social welfare and revenue. Such inaccurate value signals could be the outcomes of some machine learning models that have bounded multiplicative errors on advertiser values Our key theoretical result is a generic lemma that transfers the accuracy of the value signals into approximation guarantees on both welfare and revenue for various auctions. Moreover, our main theorems not only work in the pure auto-bidding world, but also in mixed environments in which both value maximizers and utility maximizers coexist. Furthermore, the approximation guarantees apply to very general set of market outcomes, i.e., they hold as long as no bidder is using a bidding profile that is always dominated under any competing bids. Such a broad solution concept includes classical notions such as complete-information Nash equilibrium our empirical results, additionally provides guarantees that hold along the convergence path when agents individually optimize their strategies using simple update rules.
refinements and, as we discuss in
Our auctions are based on VCG or generalized second-price auctions (GSP) and use the inaccurate signals as reserve prices and/or as (additive) boosts. Reserve prices are minimum prices the agents should clear to win the auction. Boosts are additive transformations on top of bids, i.e., agents are ranked based on the sum of their bids and boosts. Moreover, boosts are subtracted from standard payments to maintain incentive compatibility for utility maximizers. Intuitively, adding properly chosen boosts can push the auction to more efficient outcome (Deng et al., 2021b]. On the other hand, in contrast to the classic utility maximization setup in which reserve prices usually do not help improve social welfare, modest reserve prices in fact may improve social welfare when there are value-maximizing agents in the market. The key difference is that in truthful auctions like the VCG auction, iillit-maximizeer never react to reserve prices, but maximizers do react to reserve prices to satisfy their ROS constraints. It turns out that, with properly chosen reserve prices, one can climinate bad bidding strategies by reducing the set of bidding strategies that could be best responses to other bidders' strategies. As a result, the remaining good bidding strategies lead to an outcome with better social welfare guarantees.
1.1 Our results
We propose set of simple auctions and prove approximation guarantees both in terms of social welfare and revenue. In particular, these approximation guarantees for the proposed auctions are all tight except for the social welfare approximation for GSP with reserve (Appendix D.. The conclusions are robust against: i) signal inaccuracy. ii) agent behavior models (value/utility maximization or intermediate), iii) system status beyond equilibrium. The following Table I summarizes most of our approximation results, where E [0, 1] describes the approximation accuracy of the signals and X E [o, 1] indicates a hybrid behavior model between pure value maximization and pure utility maximization (c.g., x = 0 for pure value maximization and À = 1 for pure utility maximization). All formal definitions will be given later Section 2
'The learning task of the signals can a complex problem given the potential interaction with advertiser incentives. In this paper. we are agnostic about how the signals are learned and hence the learning problem is out of the scope. Nevertheless, the line of work on incentive- aware learning [Epasto et al. 2018 Golrezaei et al. 10 could be relevant to avoid or mitigate inappropriate incentives.

---

Table 1: Social welfare and revenue approximation guarantees for different auctions with ?-
approximate value signals (y E [0, 1). For boosts we need: signal E b V value, value) with 2 1; for reserves we need: signal E (y value, value).
Auction
Behavior model'
Social welfare?
Revenue
Theorem
VCG with reserve
E 0.
1/(2-1 -7)
7
Corollary
VCG with boost
X
E
0,
1/(2 -7)
Corollary
VCG with reserve and boost
E
00,
(1+
Y
Corollary 4.4
GSP with reserve
A E
[0,
7
Corollary 4.8
GSP with reserve and boost
== 0
(1+7)/22
7
Corollary 4.6
À = 0: value maximization; À == 1: utility maximization; E (0, 1): intermediate models (see Program
For < < 1, (1 2)/2 > 1/(2 - >%
Observe that in a world with value maximizers only (i.e., À = 0), if all the value maximizers can hit their targets (see Program ( the revenue equals to the social welfare. In such environment, social welfare guarantees can directly imply the same revenue guarantees under the condition that value maximizers all hit their targets.
provide a general framework for proving approximation results the presence of value maxi- mizers through novel technical lemma (Lemma 3.T). In fact, our approximation results are mostly derived from this lemma. Finally, we conduct empirical analyses with eemi-synthetic data and validate theoretical findings for the performance of our mechanisms in VCG auctions.
1.2
Related Work
As central topic in economic study, since the seminal work of Vickrey-Clarke-Giee
(VCG)
auctions [Clarke 1971 Groves 1973 Vickrey [96T] and Myerson's auction [Myerson] 1981], auction design has been successfully deployed in many different fields. Examples includes combinatorial auctions for reallocating radio frequencies [Cramton et al. 2006 and generalized second-price price
auctions well dynamic auctions for online advertising Aggarwal et al. 2006 Edelman et al.
2007 Mirrokni et al. 2020 Varian 2007].
In contrast to works assuming maxiiiziaxii agents, a growing body of work has recently focused on nuto-bidders such as target CPA bidders and target ROAS bidders. Aggarwal et al. [2019] find the optimal bidding strategies for a general class of auto-bidding objectives and prove the existence of sure-strategy equilibrium. Deng et al. Tb) show how boosts can be used to improve the efficiency guarantees when target CPA and target ROAS auto-bidders coexist. Balseiro al. 2021a] characterize the revenue-optimal single-stage auctions with either value-maximizers or Miility-maximizerr with ROS constraints under various information structure. Golrezaci al. 2021cc study the auction design for utility-maximizerr maximizers with ROI constraints, where the behavior model iS equivalent to the special case of ours with À 1/(1 + minimal ROI). Besides the model of constrained optimization, there is another generalization of the utility models with ROI constraints adopted by |Babaioff al. [2021] Goel et al. 2014 2019]. In particular, the negative payment term in the utility function replaced by a general cost, which is often a convex function of the payment.
Independent of the above, the term of value-maximizer has been used in some other works but with quite different mathematical models |adaei and Bichler (2016), Wilkens et al. (2016] 2017). The main distinction is that in these models, the target ROS constraints are imposed on a single auction rather than across a set of auctions, hence the bidders become insensitive to the marginal tradeoff between values and payments, leading to different behavior patterns.
Prior to these works, the simplest auto-bidding model budget optimization with utility- maximizers [Borgs et al. [007]. Pai and Vohra [0144] characterize the revenue- auction of utility-mm maximizin bidders with budget constraints. For applications in online advertising, [Balseiro and Gur (2019) develop budget management strategies that are no-regret in long run, which is extended in more complex settings [Avadhanula et al. 2021 Balseiro et al. 2020b 202 Celli et
2021] Balseiro et al. 2017 2020a provide a thorough study to compare different commonly used
budget management strategies practice. Conitzer et al. (017 2018 study pacing algorithms for budget constraints in both first price auctions and second price auctions.
3

---

The techniques of reserve prices and additive boosts have been widely studied in the literature
Amin al. 2013 Deng et al., 202 la Golrezaei al. 2021b Lavi al. 2003 Paes Leme al., 2016
Sandholm and L Likhodedov] 2015]. Among these works, Deng et al. [ improve the welfare
approximation ratio to (c + ()/(c+ ( 2) using boosted auctions with accurate signals about bidders'
values in the environment with value maximizers only. Our results are more robust and more general from several aspects: We allow inaccurate signals that approximate bidders' values; Our results hold for mixture of behavior models in auctions with reserves and/or boosts; We provide guarantees on revenue performance addition to welfare performance.
Some of our results rely on the assumption that the auto-bidders adopt uniform bidding strategies when the underlying auction is not commpttlle for maximi-ma bidders. practice, it is usually hard for bidders to adopt and optimize non non-uniform bidding strategies, and moreover, uniform bidding has been shown to perform well against optimal non-uniform bidding strategies in ad auctions [Balseiro and Gur 2019 Bateni et al. 2014 Deng et al., 2020 Feldman and Muthukrishnan 2008 Feldman et al. 2007
Preliminaries
Position Auctions. We consider setting with bidders bidding simultaneously in position auctions [Lahaie et al. 2007 Varian 2007]. In each position auction j, we have sy slots which can be allocated to sj different bidders. For each bidder i [n)). we use Vi, to denote the base value of auction j for bidder i, and the value of the k-th slot in auction j is Vi,j p,S Here pos,. J.& E R+ the position normalizer of the k-th slot in auction j which does not depend on i. Without loss of generality, we assume posj.a is decreasing in k. For notation convenience, we ,05,,,,+1 0 for the non-exisie non-existing slot. We use I (n, m, } fu]s,. {pos) p.ke to denote a problem instance and - to denote the bidders other than bidder i. The optimal welfare of the problem instance is defined as
(cP(
pos k k-th highest value of (U1,j, Ungj).
We use b. p. x to denote bidders' bids, payments and allocations. More particularly, busj is bidder i's bid auction. &i.j is if bidder gets the k-th slot of auction j and 0 otherwise. Pt.j is the price paid by the bidder i in auction The welfare and revenue of an allocation x and payments p defined as
Wel(x.p)
Ti.jh Ui.j p,
and Rev
Pij-
For notation convenience, we will use (x,, = Σラ= E Tag.A k Miy -pos,, and Rev;(x,p) p) Σラ= Pi,j to represent each bidder's contribution to welfare and revenue.
In this paper, we mainly focus on three auction formats used in position auctions: the Vick- Clarke--rrovee auction (VCG), the generalized second-price auction (GSP), and the first-price auction (FPA). Their allocation rules are the same: rank bidders by their bids (tie-breaking by bidder indices) and allocate the k-thh slot to the bidder with the k--th highest bid. In the VCG auction each agent pays the externality it imposes on the other the agents, in the GSP auction each agent who is allocated pays the bid of the next highest bidder, and in the FPA each agent who is allocated pays their bid. For notation convenience, we denote by bR., the k-th highest bid for & E [sy] in auction Assuming bidder i wins slot l in auction its payment Pig in the three auction formats are: (1) VCG: Pi,j = Ene++ b (pos, - pos, pos,,x). ). (2) GSP: Pt.j b pos and (3) FPA: Pt.j = bi, poss,.. k. not hard to see that, with the same bids, the payments from these three auctions is ranked in an increasing order as VCG, GSP, FPA.
Reserve Prices and Boosts. We further consider three auction formats with reserve prices and boosts. We denote by rt,j the reserve price and by 2i.j the boost for bidder i in auction j. When we have boosts, bidders are ranked by their score bi.j Zi.j and we use bR.j to denote the k-th highest score for k E [s,] auction j. For ease of presentation, we consider lazy reserves such that the slot not allocated to a bidder if her bid without boosts does not clear her reserve, i.c., bis Ta our results

---

continue to hold for eager reserves Paes Leme et al., 2016]. With reserve prices and boosts, the prices of VCG, GSP and FPA when bidder gets slot in auction j become:
VCG: Pi.j = Ex=k+1 max(bas - Zi,j. Ti.j) (posj, j,os
GSP: Pt.j max - Zijo rig) 3,5
FPA: Pt.j (b.r (n,)) 3,
It is worth highlighting that boosts and reserves are fairly different components in auctions. Reserves filter out the candidates whose bids are lower than their reserves and then the remaining candidates are ranked uccording to their original bids. In contrast, boosts are added to the candidates ranking scores, and therefore, the candidates are ranked according to their original bids plus their boosts.
Inaccurate signals. Our auctions take inaccurate value signals as input and use them as reserve prices and/or boosts. In particular, for y [0, 1]:
When the signals are used as boosts, we allow multiplicative errors in both directions and we say boosts are 7-approx, for any E [n]. E [m/, 2i, ІI Us.g. V- Me,,u-0,, o..). and μ = y v;
When the signals are used as reserve prices, we allow multiplicative underestimation errors and say reserve prices are "-approx, if for any i E [n], E [m], ri,j [y Vijj vt.).
Note that we require a one-direction error for reserve signals. One can always convert signals with bounded errors both directions into signals with only underestimation errors by scaling them down once multiplicative overestimation errors have finite upper bound.
Bidders. We focus two types of bidders: utility maximizers and value maximizers. A utility maximizer bidder maximizes (zl, p) - Rev;(z, . p). In contrast, a value maximizer maximizes Wel, p) subject generality to assume the target ratio between return (el, p) and spend Rev;(r,)) p) is 1.
return spend constraint Wel, (z. p) 2 [ev; p). Here, it is without loss of
These two types of bidders can be summarized by bidders optimizing the following program
max
Wel, (z. p) - X; (z,,))
S.I. Wel, (x. 2 Re,
Here X; = corresponds to a value maximizer and X; corresponds to a utility maximizer. Our results apply for bidders with X; E [0, 1J. We allow X; to be different for each bidder and they are unknown to the auctioneer. Here, utility maximizers can be modeled with = 1 because all the auctions we consider are individual rational. As result, the optimal solution of the objective in is always non-negative, and therefore, the constraint would be irrelevant for utility maximizers.
Solution Concept. We consider solution concept called indominated bids which includes the sup- port of Nash equilibrium bids as a subset. Because our results apply to the larger set of undominated bids, they readily hold for refinements such as Nash equilibria, in which our results give price of anarchy bounds |Papadimitriou 2001]. Following the standard definition of (weak) dominance, for problem instance and an auction format, we say bid vector by (bs,1.... ..., di.m) is (weakly) dominated by another bid vector by (b'.1...,, ....... b/.m). ). if the following two requirements are satisfied:
Let ar p be the allocation and prices induced by by, V_ and x', pp' be the allocation and prices induced by 6/, 6' ;- Then for any other bidders' bids 6',,- 6/ is at least good as b, i.c.
both violate constraints: Wel, p) < Revi p) and Wel: ,') < Revi ,p) dy violates constraints while by does not: Wel,(x, < (ev;(x,p) and (el:(x',pp) 2
Rev,(a', p/)
neither violates constraints, and by yields no worse objective: Wel, Rev: (z. p) and Wel:(x', ,p) 2 Rev.(x',z) ,/) and Wel,(a', -/)->; > Rev. (x',''))))))))) ,/) 2 Wel; p) X Rev, (z)
There exits b'_, such that 1/ strictly better than by i.e.
dy violates constraints while by does not: Wel,(x,p) < (ev;(x,p) and Wel:(x',p') 2 Rev,(x',
5

---

or neither violates constraints, and by yields strictly better objective: Wxl, 2 (2, and (al, p²) 2 Rev, (2', p') and Wel, p²) x, (ev,(2''p') p/) (c,, X
We omit the word "weak" for convenience for the rest of the paper. We say b; is undominated if there no bj dominates bç. Denote the set of all bidders' bids b = (bj,..,,b,, ba) by in which each 6; is undominated for i E [ni] and each bidder is paying at most its welfare.
As uniform bidding is widely adopted in automated bidding strategies, we also consider solution concept related to it. We say b; is a uniform bidding for bidder i, if b.,- = Vs ó; for all j E [m]. We use i. to denote the set of all bidders' bids b = (bi,..., b,)) such that each b, is uniform bidding and is not dominated by any other uniform bidding and each bidder is paying at most its welfare.
3 Main Technical Lemma
We first show lemma which will be used the major technical building block for our results. This lemma provides a general framework for proving approximation results on revenue and welfare. Informally, this lemma says that once we can guarantee lower bounds on bidders' bids and apply reserve prices and/or boosts, these immediately lead to lower bound guarantees on revenue and welfare in terms of the optimal welfare. Notice that this lemma continues hold when apply reserve prices only (i.e., = v = 0) or boosts only (i.e., 3 = 0). For a better understanding of the lemma statement, conditions number and hold by the definition of the model and conditions number 3 and 4 will be proved hold when using this lemma.
Lemma 3.1. Consider running m position auctions with allocation and pricing rule A. Assuming A together with bidders' bids b satisfy the following conditions for parameters a, B, pu, v 2 0:
For each bidder i and each auction j. the reserve satisfies Ts.j 2 B v.j and the boost satisfies μ. Us. S Zi. < V. V2.5-
In each position auction, bidders are ranked by their scores bug + 25, and the k-th highest score wins the k-th slot b 2 Ti.j-
If bidder i's value vi, ranks in top-s, in auction j. bidder bids at least a times its base value, iee. bug 2 Vs.g-
If bidder wins slot k in auction j. bidder i pays at least the VCG price, i.e. Pis 2 E j pos,,x) -max(bas - 24.g.Ta..)
For each bidder, her total payment is at most her total value.
We have Rev(A(b)) 2 min
[a+t B+v (BB+0
.)) Wel(OPT) and Wel(A(b)) 2
a I-max(voo+p-)) Wel(OPT).
We give a high-level proof sketch of this lemma. The detailed proof can be found in Appendix
Proof Sketch. Informally, the first step of the proof is to fractionally partition the auction slots into two parts so that (1) In part A, A(b) and OPT agree in allocation; (2) In part B, A(b) and OPT disagree in allocation. We then lower bound the welfare and the revenue of A(b) in these two parts separately with different arguments.
In part A, A(b) and OPT have the same allocation. The welfare of A(b) is by definition the same as the welfare of OPT. Moreover, the revenue of A(b) can be lower bounded by / times the welfare of ОРT, via conditions on reserve prices (the first bullet point of the lemma statement).
In part B. A(b) and OPT have different allocations as allocated bidders of OPT are not allocated in A(b.. Since we have lower bounds on bids (the third bullet point of the lemma statement), these bidders' bids would give lower bound the revenue of A(bb) via VCG pricing. The additional boost 2 (in the first bullet point of the lemma statement) would escalate this effect and give a lower bound on a linear combination of the welfare and the revenue of A(b).
By putting these lower bounds together with the condition that (el()A()) > Rev(A(b) (in the fifth bullet point of the lemma statement), can obtain lower bounds on Wel(AA(b) and Rev(A(()).

---

Applications in Auctions
4.1 VCG Auctions
In this section, we consider VCG with reserves and boosts. We first show the following lemma about the set of undominated bids O. Its proof can be found Appendix B
Lemma 4.1. For any problem instance let @ be the set of undominated bids for VCG with reserve
r and boost z. Assume reserve r satisfies that Ti.j < Vi.j Vi E [n],] E [mm] and boost & satisfies that Zijj E Uu.j. U4.)) for some
S 1 for all E [m].J E [m]] For any O have big 2 Vij. if bidder i's value Vi ranks in top-8; in auction j.
With Lemma we are ready to state our results on VCG with reserves and boosts. The following three corollaries are the results we get when we apply (1) only reserve prices (2) only boosts (3) reserve prices and boosts together.
Combining Lemma 4.1 with Lemma 3.1 using a = 1. 3 = % and μ === 0:
Corollary 4.2. On any problem instance I, VCG with y-approx reserve, denoted by VCG,, satisfies
(b)( 2 2-7
Wel(OPr) and Rev(VCG?(b) 2 Wel(OPT).
for bids b from the undominated bids set O.
Combining Lemma with Lemma 3.1 using a 3 0, μ 7/(1 (1-1)),, and 1/(1 - 7)):
Corollary 4.3. On any problem instance I, VCG with y-approx boosts, denoted by VCG satisfies
1
(e)(VCG 2 Wel(OPT)
for bids b from the undominated bids set +.
Combining Lemma 4.1 with Lemma 3.1 using a 1, 14 7 and
Corollary 4.4. On any problem instance VCG with y-approx reserve and y-approx boost, denoted by VCG satisfies
7 7+ Wel(OPT) and Rev(VCG,, mg Wel(OPT).
Wel(VCG, (b))
2
for bids b from the undominated bids set θ.
4.2 Generalized Second-Price Auctions
For GSP, we are able show lemma similar Lemma assuming bidders all value maximizing (A; = 0 Vi E [ni) and they are uniform bidding. Its proof can be found in Appendix g
Lemma 4.5. For any problem instance I with X; = Vi E [n]. ler Ou be the set of undominated uniform bids for GSP with with reserve and boost z. Assume reserve satisfies that rt. < Us Vi [m].j E [m], and boost z satisfies that for some v - S 1, 21,j E [p Us.j. V. Va.s) ) E [n].] E [m]. For any b θ,.. we have bij 2 Vi.j. if bidder i's value Vi ranks top-s; in auction j.
we can obtain results similar to Corollary only state the strongest one with both boosts and reserve prices:
Combining Lemma with Lemma 3.1
We
Corollary 4.6. On any problem instance I with >; Vi [n]. GSP with 7-approx reserve and y-aaprox boost, denoted by GSP r.b satisfies
7 ++
WeI R.))
Wel(OPT) and Rev(GSP (bb))) 2 7 Wel(OPP),
2
for uniform bids b from the undominated uniform set O...
When there are no restrictions on bidders' bidding behavior, we can obtain the following weaker lemma for GSP with reserves. Its proof can be found in Appendix
7

---

Lemma 4.7. For any problem instance I, let θ be the set of undominated bids for GSP with y-approx reserve and no boosts. For any b E θ we have bú. 2 rt.j 2 ? Vv... vi E [n].j [m].
Combining Lemma 4.7 with Lemma 3.1
using a = 3 = 7, and μr = 0:
Corollary 4.8. On any problem instance I, GSP with appppx reserve. denoted by GSP?, satisfies Wel(GSP, 2 Wel(OPT) and Rev(GGP,(b)) 2 Wel(OP1),
for bids b from the undominated bids set O.
4.3 First-Price Auctions
For FPA, if we restrict that bidders are only value maximizers and they uniform bidding, we know from prior work that optimal welfare and revenue can be achieved without reserves and boosts. Its proof can be found in Appendix D
Theorem Deng et al. [2021b]. On any problem instance I with X; = 0 0 E [m], FPA has
(el(FPA(b)) = Rev(FPA(b) = Wel(OPT),
for uniform bids b from the undominated uniform set O..
When there are no restrictions on bidders, we get similar results GSP with the following lemma. Lemma 4.9. For any problem instance I, let Q be the set of undominated bids for FPA with y-approx reserve r and no boosts. For any b E θ we have bú, Z ri,j 2 Vi.j. Vi E [m], E [m].
Combining Lemma 4.9 with Lemma 3.1 using a 7, B 7, and μ = V
Corollary 4.10. On any problem instance 1, FPA with "appprox reserve (FPA?) has
(cl(FPAZ(b) 2 Wel(OPT) and Rev(FPA7(b) 27 Wel(OPT),
for bids b from the undominated bids set θ.
5 Experiments
In this section, we derive semi-synthetic data from real auction data of a major search engine to vali- date theoretical findings concerning VCG auctions. VCG auctions provide clean environment for us to validate our findings as uniform bidding is a best response for each value maximizer Aggarwal et al. 2019 while computing best response in GSP auctions is highly non-trivial task.
Observe that when the bidders are symmetric such that their valuation distributions are identically and independently distributed, both optimal efficiency and optimal revenue are achieved in any symmetric equilibrium, and thus, no efficiency or revenue improvement can be observed by applying real ad auction data for capturing variation across bidders. For
mechanisms. Therefore, the experimental purpose, we simulate VCG auctions with bids from value maximizers only, as utility maximizers do not respond to either boosts reserve prices in VCG mechanisms. Instead of using real return on ad spend targets for value maximizers, we generate artificial targets to exclude any practical noises from the real system. We emphasize that the main objective for empirical study is to validate our theoretical findings rather than investigating the efficiency and/or revenue potentials on real systems actually implemented in practice. Many practical aspects often need to be taken care of in the design of real systems, which would never he considered in theory.
Simulation Procedures. To properly evaluate the efficiency and revenue of a new mechanism, after the generation the dataset, we first pre-train the (uniform) bid multipliers ò for value maximizers in 25 iterations without reserve prices and boosts to obtain equilibrium simulate the response value maximizers by gradient descent on their bid multipliers in log space until convergence [Aggarwal et al. 2019 Nesterov 2013]. Formally, let d be the bid multiplier for value maximizer in iteration f. In addition, let Wel,, be value maximizer i's total received value in iteration t, and let Rev,, be her total payment in iteration t. Then, in iteration
starting point. We then
1, the value Wel. where maximizer i's bid multiplier is updated by log 8 = (1 - (1-7)) log dG, + 7tt log Rev..
m (0, 1) is properly chosen learning rate for t-th iteration. Intuitively, when Rev., < Wel,
8

---

value maximizer i's bid multiplier increases for the next iteration; otherwise, her bid multiplier decreases for the next iteration. After obtaining starting point, we simulate another 25 iterations for auctions with reserve prices and/or boosts. In this way, we can observe both the initial impact of adding reserve prices and/or boosts and how the impact changes over time during value maximizers' response until convergence.
Reserve Prices and Boosts. In addition to the baseline in which continue use auctions without reserve prices, we experiment with boosts and reserve prices using signals with different approximation factors 7. For each bidder in each auction j. we will set reserve prices or give boosts based on in different treatments. Here. let s/ be random variable independently sampled from Gaussian distribution with mean (1 + 7)/2 and standard error 0.01, truncated within (n: 1). In treatment reserve-y, we set the reserve price as s/ MM.jj- In treatment boost-y, we add an additive boost 1-7 s Vi,j as suggested. Finally, in treatment boost-reserve-7, we set the reserve price as $/ Us.j and additionally give an additive boost 1_ -5, Va.j- All metries we report are relative 1-7 to the gap between the baseline (i.e., without treatment) and the optimal solution. More precisely, let Kinit be the initial welfare (revenue) without reserve prices or boosts, Ki be the welfare (revenue) under treatment e, and x(OPT) be the optimal welfare (revenue). Then the reported percentage is computed by (Ke- Kinnt)/ (x((PT) Kinit).
5.1 Experimental Results
Figure reports the trend of welfare performance in VCG auctions under different treatments with one run of the experiment. Observe that both variants of reserve prices have neutral initial impact on welfare before value maximizers start respond. After the value maximizers start to respond, they adjust their bid multipliers towards a better allocation, resulting in a positive impact on welfare. As the reserve prices become more precise (i.e., when y is closer to 1), the welfare impact is larger, which confirms our theoretical results of Corollary 4.2 In contrast, both variants of boosts have positive initial impact welfare. However, as the value maximizers start respond, the welfare impact starts to decrease but the final impact after convergence is still positive, confirming our theoretical results of Corollary 4.3 Interestingly, when treatment reserve-ry and treatment boost-7 share the same their final impact on revenue after response are close to each other, as predicted by the same welfare bounds from Corollary 422 and Moreover, combination of boosts and reserve prices outperforms the treatments with either reserve prices only or boosts only, which validates Corollary 4.4 that enjoys a better bound than Corollary 4. and
boost-0.3 0.3
benst--eserve-00.3
reserve-0.3
boost-0.3
boost-weeerve-0..
reserve-03
boost-0.7
roserve-0.7
boost-0.
bonst--werre-00.7
reserve-0.7
2.6
0.5
2.4
2.2
2.0
1.6
0.1
1.4
15
20
25
10
15
20
25
(a) Trend of Welfare
(b) Trend of Average Bid Multiplier
Figure 1: Convergence during response per iteration.
Figure Ib dedonsssssstes the trend of average (uniform) bid multipliers for value maximizers under different treatments in VCG auctions with one run of the experiment. We observe that the average multiplier decreases during response for both treatments with reserve prices only, leading to better welfare performance post response as shown in Figure la Moreover, as the reserve prices become more precise, the average multiplier is lower after convergence. Intuitively, the welfare maximized when all the value maximizers adopt a bid multiplier 1 so that the auction results in ranking according to their values. Therefore, the bid multipliers getting close to after response the main driving factor behind the increase of welfare for treatments with reserve prices only. On the other

---

hand, the average multiplier increases during response for both treatments with boosts only, leading worse welfare performance post response as shown in Figure Ia A combination of reserve prices and boosts induces mild decrease of the average multiplier, resulting in rather stable welfare performance during value maximizers' response.
Signal
Reserve Only
Boost Only
Boost Reserve
7 0.3
37.4% 3.2%
23.0% 3.4%
55.4% + 3.3%
Welfare Lift
7 = 0.5
47.9% + 2.9%
33.6% + 3.2%
63.2% + 3.1%
7 0.7
58.6% 3.3%
3.2% 47.7%
67.6% + 3.2%
7 = 0.3
28.2%
1.7%
23.7%
2.2%
44.9% 1.9%
Revenue Lift
7 = 0.5
39.4% + 1.9%
35.3% + 2.5%
52.9% + 1.8%
? = 0.7
54.1%
1.8%
51.2%
3.0%
59.9% 2.2%
Table 2: Welfare and revenue lifts for different treatments after convergence.
We conduct 10 runs of repeated experiments and Table shows the welfare and revenue impact after convergence with 95% confidence intervals. First, notice that treatments with reserve prices only have better welfare and revenue lifts than treatments with boosts when they share the same y. Moreover, combination of boosts and reserve prices leads to further improvements in both revenue and welfare. For all variants, as the signals becomes more precise (i.e., Y is closer to 1), the impacts are larger. Note that in an environment with value maximizers only, if all value maximizers could always hit their target spends after convergence, the improved ratios for welfare and revenue should be the same. However, due to the discontinuity of the bidding landscape, there are value maximizers who cannot hit their targets in practice. As result, we witness difference between welfare improvement and revenue improvement even after convergence.
Conclusion
In this paper, provide both theoretical and empirical evidence demonstrate that introducing properly chosen reserve prices and/or boosts can improve both revenue and welfare in the auto- bidding world. Our results robust bidders' behavior models well inaccurate signals that approximate bidders' values. One limitation of our results is regarding the requirement of reserve prices not exceeding bidder values. Although one avoid this by scaling down the reserve prices, does require additional knowledge from the auction designer on an upper limit of the inaccurate signals. is intriguing question address such an issue in more robust way.
7 Acknowledgement
Thanks are due Mohammad Mahdian, Aranyak Mehta, Renato Paes Leme, and Ying Wang for helpful discussions, and for their comments and suggestions.
References
Gagan Aggarwal, Ashish Goel, and Rajeev Motwani. Truthful auctions for pricing search keywords. In Proceedings of the 7th ACM Conference on Electronic Commerce, pages 1-7, 2006.
Gagan Aggarwal, Ashwinkumar Badanidiyuru, and Aranyak Mehta. Autobidding with constraints. In International Conference on Web and Internet Economics, pages 17-30. Springer, 2019.
Kareem Amin, Afshin Rostamizadeh, and Umar Syed. Learning prices for repeated auctions with strategic buyers. In Advances in Neural Information Processing Systems, pages 1 1699
Vashist Avadhanula, Riceardo Colini Baldeschi, Stefano Leonardi, Karthik Abinav Sankararaman, and Okke Schrijvers. Stochastic bandits for multi plati-platform budget optimization in online advertising. In Proceedings of the Web Conference 2021, pages 2805 2817, 2021.
Moshe Babaioff, Richard Cole, Jason Hartline, Nicole Immorlica, and Brendan Lucier. Non-quasi- linear agents in quasi-linear mechanisms. Proceedings of 12th Innovations in Theoretical Computer Science, 2021.
10

---

Santiago Balseiro, Anthony Kim, Mohammad Mahdian, and Vahab Mirrokni. Budget management strategies in repeated auctions. In Proceedings of the 26th International Conference on World Wide Web, pages 15-23, 2017.
Santiago Balseiro, Anthony Kim, Mohammad Mahdian, and Vahab Mirrokni. Budget-constraine incentive compatibility for stationary mechanisms. In Proceedings of the 21st ACM Conference on Economics and Computation, pages 607-608, 2020a.
Santiago Balseiro, Haihao Lu, and Vahab Mirrokni. Dual mirror descent for online allocation problems. In Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 613-628, PMLR, 13-18 Jul 2020b.
Santiago Balseiro, Yuan Deng, Jieming Mao, Vahab Mirrokni, and Song Zuo. The landscape of auto- bidding auctions: Value versus utility maximization. In Proceedings of the 22nd ACM Conference on Economics and Computation, 2021a.
Santiago Balseiro, Haihao Lu, and Vahab Mirrokni. Regularized online allocation problems: Fairness and beyond. In Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 630-639. PMLR, 18-24 Jul 2021b.
Santiago R Balseiro and Yonatan Gur. Learning in repeated auctions with budgets: Regret minimiza- tion and equilibrium. Management Science, 65(9):3952-3968 2019.
MohammadHossein Bateni, Jon Feldman, Vahab Mirrokni, and Sam Chiu-wai Wong. Multiplicative bidding in online advertising. In Proceedings of the fifteenth ACM conference Economics and computation, pages 715-732, 2014.
Christian Borgs, Jennifer Chayes, Nicole Immorlica. Kamal Jain, Omid Etesami, and Mohammad Mahdian. Dynamics bid optimization in online advertisement auctions. In Proceedings of the 16th international conference on World Wide Web, pages 531-540, 2007.
Andrea Celli, Riccardo Colini-Baldeschi, Christian Kroer, and Eric Sodomka. The parity ray regularizer for pacing in auction markets. arXiv preprint arXiv:2106.0950. 2021.
Edward H Clarke. Multipart pricing of public goods. Public choice, 1(1):17-33, 1971.
Vincent Conitzer, Christian Kroer, Eric Sodomka, and Nicolas E Stier-Moses. Multiplicative pacing equilibria in auction markets. arXiv preprint 17X.::1706.07551, 2017.
Vincent Conitzer, Christian Kroer, Debmalya Panigrahi, Okke Schrijvers, Eric Sodomka, Nicolas Stier-Moses, and Chris Wilkens. Pacing equilibrium in first-price auction markets. arXiv preprint 1810v:1811.07766,6 2018
Peter Cramton, Yoav Shoham, and Richard Steinberg. Combinatorial Auctions. MIT Press, 2006.
Yuan Deng, Sébastien Lahaie, Vahab Mirrokni, and Song Zuo. A data-driven metric of incentive compatibility. In Proceedings of The Web Conference 2020, pages 1796-1806, 2020.
Yuan Deng, Sébastien Lahaie, Vahab Mirrokni, and Song Zuo. Revenue-incentive tradeoffs in reserve pricing. In International Conference on Machine Learning. PMLR, 2021a.
Yuan Deng, Jieming Mao, Vahab Mirrokni, and Song Zuo. Towards efficient auctions in an auto- bidding world. In Proceedings of The Web Conference 2021, 2021b.
Benjamin Edelman, Michael Ostrovsky, and Michael Schwarz. Internet advertising and the gener- alized second- -pice auction: Selling billions dollars worth of keywords. American Economic Review, 97(1):242-251 2007.
Alessandro Epasto, Mohammad Mahdian, Vahab Mirrokni, and Song Zuo. Incentive-aware learning for large markets. In Proceedings of the 2018 World Wide Web Conference, pages 1369-1378, 2018.
Salman Fadaei and Martin Bichler. Truthfulness and approximation with value-maximizing bidders. In International Symposium on Algorithmic Game Theory, pages 235-246. Springer, 2016.
11

---

Jon Feldman and S Muthukrishnan. Algorithmic methods for sponsored search advertising. In Performance Modeling and Engineering, pages 91-122. Springer, 2008
Jon Feldman, Shanmugavelayutham Muthukrishnan, Martin Pal, and Cliff Stein. Budget optimization in search-based advertising auctions. In Proceedings of the 8th ACM conference on Electronic commerce, pages 40 49, 2007.
Gagan Goel, Vahab Mirrokni, and Renato Paes Leme. Clinching auctions beyond hard budget constraints. In Proceedings of the fifteenth ACM conference on Economics and computation, pages 167-184, 2014.
Gagan Goel, Vahab Mirrokni, and Renato Paes Leme. Pareto efficient auctions with interest rates. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 1989-1995, 2019.
Negin Golrezaei, Adel Javanmard, and Vahab Mirrokni. Dynamic incentive-awer aware learning: Robust pricing in contextual auctions. Operations Research, (0(1)297-314, 2021a.
Negin Golrezaci, Max Lin, Vahab Mirrokni, and Hamid Nazerzadeh. Boosted second price auctions: Revenue optimization for heterogeneous bidders. In Proceedings of the 7th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, 2021b.
Negin Golrezaei, Ilan Lobel, and Renato Paes Leme. Auction design for roi-constrained buyers. Proceedings The Web Conference 2021. 2021c
Theodore Groves. Incentives in teams. Econometrica: Journal of the Econometric Society, pages 617-631, 1973.
Sébastien Lahaic, David M Pennock, Amin Saberi, and Rakesh V Vohra. Sponsored search auctions. Algorithmic game theory, pages 699-716, 2007.
Ron Lavi, Ahuva Mu' Alem, and Noam Nisan. Towards a characterization of truthful combina- torial auctions. In 44th Anmual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings., pages 574-583. IEEE, 2003.
Vahab Mirrokni, Renato Paes Leme, Pingzhong Tang, and Song Zuo. Non-clairvoyant dynamic mechanism design. Econometrica, 18(5):1939-196 2020.
Roger B Myerson. Optimal auction design. Mathematics of Operations Research, 6(1):58-73, 1981.
Yurii Nesterov. Introductory lectures on convex optimization: A basic course, volume 87. Springer Science & Business Media, 2013.
Renato Paes Leme, Martin Pál, and Sergei Vassilvitskii. A field guide personalized reserve prices. In Proceedings of the 25th international conference on world wide web, pages 1093-1102, 2016.
Mallesh M Pai and Rakesh Vohra. Optimal auctions with financially constrained buyers. Journal of Economic Theory, 150:383-425, 2014.
Christos Papadimitriou. Algorithms, games, and the internet. In Proceedings of the thirty-third annual ACM symposium Theory of computing, pages 749-753, 2001.
Tuomas Sandholm and Anton Likhodedov. Automated design of evvenue-mxiimizing combinatorial auctions. Operations Research, 6000- 2015.
Hal R Varian. Position auctions. International Journal of Industrial Organization, 2566):1163-1178, 2007.
William Vickrey. Counterspeculation, auctions, and competitive sealed tenders. The Journal of Finance, 16(1):8-3) 1961.
Christopher A Wilkens, Ruggiero Cavallo, Rad Niazadeh, and Samuel Taggart. Mechanism design for value maximizers. arXiv preprint arXiv: 2016.
Christopher A Wilkens, Ruggiero Cavallo, and Rad Niazadeh. Gsp: the cinderella of mechanism design. In Proceedings of the 26th International Conference on World Wide Web, pages 25-32, 2017.
12


Reviews:
[{"review_id": "N-jgiudllo", "reviewer": "Reviewer_C57R", "summary": "This paper studies auction design for advertising slots when the agents are using auto-bidding optimization algorithms.\n\nThe bidders: The focus is on “value-maximizing agents”: this type of agent aims to maximize the total value he gets from his allocation, subject to the constraint that his value is at least his price (as opposed to a utility-maximizing agent, who aims to maximize his value minus his price; the authors also study interpolations between value maximizers and utility maximizers). The authors write that this is the prevalent adopted model for the behavior of auto-bidding agents. There are $m$ position auctions and each agent $i$ has a fixed (i.e., not Bayesian) value $v_{i,j}$ for each auction $j \\in [m]$. Agent $i$’s value for the $k^{th}$ slot in auction $j$ is $v_{i,j}\\cdot pos_{j,k}$, where $pos_{j,k}$ is a position normalizer that doesn’t depend on $i$ and is common knowledge.\n\nThe auctions: The paper studies VCG, GSP, and first-price auctions with reserves and boosts, the latter of which means that each bidder’s bid $b_{i,j}$ is increased by some boost $z_{i,j}$. The reserves and boosts are set to be equal to some noisy signals about the values $v_{i,j}$ which the authors write could be obtained, for example, using a machine learning model. These signals are assumed to be accurate up to some multiplicative error. Also, the bids are assumed to be undominated (which includes the support of Nash equilibrium bids as a subset).\n\nThe results: The authors prove approximation guarantees showing that for each of these three auctions, the revenue and welfare are approximately optimal, where the approximation factor depends on the accuracy of the noisy value signals. They also provide experiments on semi-synthetic data that validate these theoretical findings. From my understanding, the buyers’ values are based on real-world ad auction data, but the signals and bids are synthetically generated.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "To start, I appreciate the relaxations this paper has made with respect to prior research, as summarized in lines 39-47. In particular, I like that the results require only noisy knowledge of the buyers’ values, which seems plausible. I also appreciate that the results hold for a mixture of value maximizers and utility maximizers, rather than one or the other.\n\nI did find some of the results a bit hard to interpret—in particular, Lemma 3.1, which is the first actual result of the paper. The lemma depends on quite a lot of conditions and parameters $\\alpha, \\beta, \\mu, \\eta$, so it was hard for me to wrap my head around if they were reasonable conditions. It would be helpful to remind the reader which conditions hold by definition of the model (e.g., the first condition, from my understanding) and which you will prove hold (e.g., the third condition).\n\nThere were also some aspects of the model I think could have used more explanation. For example, the authors write that it is common to assume the buyers are value maximizing in prior research on auto-bidding, but intuitively, why is this the case? Intuitively, why aren’t they utility maximizers?\n\nOther than these two confusions, I thought the paper was pretty well written, though I also have some more detailed comments:\n-\tLines 45-46: At first I was confused, thinking the signals were the only input to the auction. But it’s really signals together with actual bids, from my understanding.\n-\tLine 53: “As longs as” -> “as long as”\n-\tLine 114: “approximates” -> “approximate”\n-\tLine 145: I think this should be “wins slot k in auction j”\n-\tLine 154: This should be “the prices of”\n-\tLine 158: Why isn’t this $\\hat{b}$? The other prices are in terms of $\\hat{b}$ rather than $b$.\n-\tLine 165: “an one” -> “a one”\n-\tLines 184-197: The notations x, p, x’, and p’ are used repeatedly in lines 185-195 but only defined in lines 196-197—it would be good to move this definition earlier.\n-\tLines 306-307: What does “the dataset” consist of, the $v_{i,j}$s? Can you say a bit more about how it’s generated?\n-\tLine 307: $\\delta$ is used in line 201 when defining uniform bidding strategies, but here $\\alpha$ is used, so it would be good to make this notation consistent.\n-\tLines 314-315: What are “spend” and “target spend” in this inequality? Do you mean Wel and Rev?\n-\tLine 318: “overtime” -> “over time”\n-\tLine 321: I think you mean “experiment with boosts”\n-\tLine 342: Could you mean welfare instead of revenue? I don’t see anything about revenue in Figure 1a.\n-\tLine 374: “requirement” -> “require”", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I appreciate the limitations the authors describe in the final section---namely, that to set the reserve prices, it is necessary to know how noisy the signals are.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "E2sW9tqrH6G", "reviewer": "Reviewer_7XKj", "summary": "This paper focuses on value maximizing bidders with return on spend constraints—a paradigm that has drawn considerable attention recently as more advertisers adopt auto-bidding algorithms in advertising platforms, and show that the introduction of reserve prices has a novel impact on the market. Choosing reserve prices appropriately can improve not only the total revenue but also the total welfare. \nTheir results also demonstrate that reserve prices are robust to bidder types, i.e., reserve prices work well for different bidder types, such as value maximizers and utility maximizers, without using bidder type information. Then generalize these results for a variety of auction mechanisms such as VCG, GSP, and first-price auctions. Moreover, they show how to combine these results with additive boosts to improve the welfare of the outcomes of the auction further. Theoretical observations are complemented with an empirical study using data from online advertising auctions.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Task is new, and the work is a novel combination of well-known techniques. The related works are adequately cited, the comparison is clear..\nThe submission is technically sound. Methods are used appropriately and it’s a complete work. The authors are careful and honest about evaluating both the strengths and weaknesses of their work. \nLine 314, how this eta is chosen? Line 326 to 327, is there a redundant? \nThe submission is clearly written and well organized. It adequately inform the reader. \nThe results are important and advance the state of art. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"ethical_concerns": "No", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "DGDOUS2sgmg", "reviewer": "Reviewer_xr54", "summary": "This paper studies welfare and revenue outcomes in a position auction with boosting and personalized reserves, where bidders behave in a manner motivated by autobidding.  Specifically, each bidder is assumed to want to maximize a modified utility of the form (value - lambda * payment) where lambda lies in [0,1], subject to an ROI constraint that value is at least payment.  Lambda = 1 corresponds to standard quasi-linear utility while lambda = 0 corresponds to value maximization.  As a solution concept, the paper considers all profiles of undominated bids, which is a relaxation of equilibrium notions.  The underlying auction is either VCG or GSP.\n\nBoosting and personalized reserves aim to improve efficiency and welfare by leveraging information about an agent's true value and incorporating it into the auction rule.  This paper asks what happens when this information is noisy, which they model as having the reserve price and boosting parameters be within some constant factor of the agent's true value.  The authors show that when this holds, the welfare and revenue will be approximately optimal under arbitrary undominated bids.\n\nThe paper concludes with an experimental study of the proposed method on synthetic data based on historical bidding traces.  The study indeed shows that natural bidding behavior converges with the addition of approximate reserves and boosts, and that welfare and revenue improve.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Boosting and personalized reserves are common in modern advertising auctions, and evaluating the impact of noisy estimates in such systems is an interesting direction.  Prior work (e.g., Deng et al. 2021b) had shown that these approaches are consistent with non-quasi-linear objectives used in autobidding systems.  This work builds upon that line by showing that the conclusions extend to scenarios where different auction participants have different types (utility-maximizer vs value-maximizer), and to the broader space of undominated bid profiles.\n\nThe authors position the paper as focusing on the case with boosts and reserves coming from noisy signals, such as perhaps being learned imperfectly by the platform.  However, this is modeled as assuming a strict constraint on boost factors and reserve prices that relate them to a bidder's true value.  This doesn't feel like a perfect fit; I would have preferred to see the signals as part of the model, perhaps taken from a distribution that allows very incorrect estimates with low probability.  \n\nThe paper also avoids discussing incentive issues that arise from the use of such factors.  This is especially relevant in an autobidding world, where advertisers might rightly be concerned that the platform exploits the autobidding interface to learn information that can be used against the bidder's interests.  I would have liked to see at least a passing discussion of such issues.\n\nThe welfare and revenue bounds themselves are not particularly surprising, and follow using now-standard logic analyzing the impact of boosting and reserves.  What is nice about the paper is the generality of the model in which these bounds hold.  The experimental evaluations are a nice addition as well, especially for exploring convergence properties (a notable gap in the theory).\n\nOverall, I think this is a modest but helpful contribution to our understanding of the robustness of position auction tricks like boosting and personalized reserve tuning.  The modeling omits many important practical issues, but the theory presented here makes a reasonable start that could be fleshed out with further work.  The technical contribution itself shares much in common with recent prior work.  Overall I think the paper could be accepted to the conference if there is room.\n\n===\n\nPost Author Response: Thanks for the thoughtful response.  I agree that adding the citations and discussion mentioned would be helpful. Overall I'm still favorable about the paper.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "In my opinion, boosting and personalized reviews should be viewed with wary skepticism, as they essentially bend incentive properties to gain welfare and revenue.  There is a sense in which platforms exert monopoly power when using these tools, since they typically push the auction toward a platform-favorable market outcome.  This paper mostly ignores the way in which the platform learns information about buyer values, and hence sidesteps these issues.  Some acknowledgement and/or discussion about this would be helpful.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "3vyTQ7C-4oI", "reviewer": "Reviewer_m9PK", "summary": "This paper studies the auction design when the buyers are either utility or value maximizer with budget constraint. Under this setting the authors focus on three mechanisms VCG, GSP and First Price Auction. They have two main contributions compared to the previous literature:\n1. They show that introducing reserve prices might have a positive impact on social welfare.\n2. Also the authors try to model that the seller does not know the exact values of the bidders, meaning has only access to noisy signals.\n\nThen the authors assess their findings by running some simulations and running real experiments that confirm their findings.\n", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I like the paper and it is interesting. However, I have some conceptual questions related to the significance of the contribution compared to the previous literature.\n1. In Deng et al 2021, the authors have shown that boosting can make the auction more efficient in a similar setting. The present paper proposes reserve prices. By setting the boosting factor such that it matches the reserve price, especially in GPS and VCG, do the results of the boosting from the previous literature extend the results in the case when the seller knows the accurate values?\n2.Regarding the noisy signal, the authors indeed show that efficiency extends modulo some error. This is important since indeed in practice it does not hold the fact that the seller knows the exact signals. However I do find this result surprising, the paper would improve significantly if the authors show that these bounds are tight and robust to any uncertainty set and not only a multiplicative one that implicitly still assumes that the seller knows the bounds of the inaccuracy that depend on the try signal.\n\nA minor comment: it is great to have the table 1 summary, however it uses a lot of notation that is hard to grasp without the model. I would recommend either to move it after the model introduction or introduce with more details the notation.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "NA", "review_text": "", "extra_scores": {"ethical_concerns": "NA", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}]

Author rebuttal:

Meta-review: All the reviewers agreed that this paper studies a worthwhile topic, and are generally positively disposed towards the paper. At the same time, several reviewers felt that the technical contributions of the paper are somewhat marginal.

On a relatively minor note, I will also echo what one reviewer said about related work: there is significant work by several industry labs on autobidding, and especially budget constraints. The present paper seems somewhat heavily skewed towards citing work primarily from Google. While this is probably due to an accident of only hearing about those particular works, it does seem like something the authors should take care to fix, as it looks a bit odd.

A specific early work that I want to point out is the paper by Borgs et al. "Dynamics of bid optimization in online advertisement auctions." Proceedings of the 16th international conference on World Wide Web. 2007.

Decision: Accept (Poster)