Robust Auction Design in the Auto-bidding World
Year: 2021

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.

heading: 1 Introduction
text: As auto-bidding—the practice of using optimization algorithms to procure advertising slots—is becoming the prevalent option in online advertising, a 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 et al., 2021a, Deng et al., 2021b, Golrezaei et al., 2021c]. A benefit of auto-bidding is that it simplifies advertisers’ bidding process by asking advertisers for their high-level goals and then bidding on behalf of the advertisers.1 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 quasi-linear 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
1See https://support.google.com/google-ads/answer/6268637 and https://www.facebook.com/business/m/onesheeters/value-optimization-with-roas-bidding; and Aggarwal et al. [2019], Balseiro et al. [2021a], Deng et al. [2021b] for more background introductions.
35th Conference on Neural Information Processing Systems (NeurIPS 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-Groves (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 at equilibria under the VCG auction is only 1/2 of the optimal social welfare [Aggarwal et al., 2019, Deng et al., 2021b]. This is because the ratio between bids and values can be very different for each 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 as 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.2 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 a 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 as refinements and, as we discuss in our empirical results, additionally provides guarantees that hold along the convergence path when agents individually optimize their strategies using simple update rules.
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 a 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, utility-maximizers never react to reserve prices, but value-maximizers do react to reserve prices to satisfy their ROS constraints. It turns out that, with properly chosen reserve prices, one can eliminate 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.

heading: 1.1 Our results
text: We propose a 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 E). 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 1 summarizes most of our approximation results, where 2 [0, 1] describes the approximation accuracy of the signals and 2 [0, 1] indicates a hybrid behavior model between pure value maximization and pure utility maximization (e.g., = 0 for pure value maximization and = 1 for pure utility maximization). All formal definitions will be given later in Section 2.
2The learning task of the signals can be 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., 2021a] could be relevant to avoid or mitigate inappropriate incentives.
GSP with reserve and boost = 0 (1 + )/2 Corollary 4.6 1 = 0: value maximization; = 1: utility maximization; 2 (0, 1): intermediate models (see Program (1)). 2 For 0 < < 1, (1 + )/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 (1)), the revenue equals to the social welfare. In such an environment, our social welfare guarantees can directly imply the same revenue guarantees under the condition that value maximizers all hit their targets.
We provide a general framework for proving approximation results in the presence of value maximizers through a novel technical lemma (Lemma 3.1). In fact, our approximation results are mostly derived from this lemma. Finally, we conduct empirical analyses with semi-synthetic data and validate our theoretical findings for the performance of our mechanisms in VCG auctions.

heading: 1.2 Related Work
text: As a central topic in economic study, since the seminal work of Vickrey–Clarke–Groves (VCG) auctions [Clarke, 1971, Groves, 1973, Vickrey, 1961] 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 auctions as well as dynamic auctions for online advertising [Aggarwal et al., 2006, Edelman et al., 2007, Mirrokni et al., 2020, Varian, 2007].
In contrast to works assuming utility-maximizing agents, a growing body of work has recently focused on auto-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 pure-strategy equilibrium. Deng et al. [2021b] show how boosts can be used to improve the efficiency guarantees when target CPA and target ROAS auto-bidders coexist. Balseiro et al. [2021a] characterize the revenue-optimal single-stage auctions with either value-maximizers or utility-maximizers with ROS constraints under various information structure. Golrezaei et al. [2021c] study the auction design for utility-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 et al. [2021], Goel et al. [2014, 2019]. In particular, the negative payment term in the utility function is 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 Fadaei 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 is budget optimization with utilitymaximizers [Borgs et al., 2007]. Pai and Vohra [2014] characterize the revenue-optimal auction of utility-maximizing bidders with budget constraints. For applications in online advertising, Balseiro and Gur [2019] develop budget management strategies that are no-regret in a long run, which is extended in more complex settings [Avadhanula et al., 2021, Balseiro et al., 2020b, 2021b, Celli et al., 2021]. Balseiro et al. [2017, 2020a] provide a thorough study to compare different commonly used budget management strategies in practice. Conitzer et al. [2017, 2018] study pacing algorithms for budget constraints in both first price auctions and second price auctions.
The techniques of reserve prices and additive boosts have been widely studied in the literature [Amin et al., 2013, Deng et al., 2021a, Golrezaei et al., 2021b, Lavi et al., 2003, Paes Leme et al., 2016, Sandholm and Likhodedov, 2015]. Among these works, Deng et al. [2021b] improve the welfare approximation ratio to (c+ 1)/(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 a mixture of behavior models in auctions with reserves and/or boosts; We provide guarantees on revenue performance in 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 incentive-compatible for utility-maximizing bidders. In practice, it is usually hard for bidders to adopt and optimize 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].

heading: 2 Preliminaries
text: Position Auctions. We consider a setting with n bidders bidding simultaneously in m position auctions [Lahaie et al., 2007, Varian, 2007]. In each position auction j, we have sj slots which can be allocated to sj different bidders. For each bidder i 2 [n], we use vi,j 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 · posj,k. Here posj,k 2 R+ is the position normalizer of the k-th slot in auction j which does not depend on i. Without loss of generality, we assume posj,k is decreasing in k. For notation convenience, we set posj,sj+1 = 0 for the non-existing slot. We use I = (n,m, {s}j , {v}i,j , {pos}j,k) to denote a problem instance and i to denote the bidders other than bidder i. The optimal welfare of the problem instance is defined as
Wel(OPT) = mX
j=1
sjX
k=1
posj,k · k-th highest value of (v1,j , ..., vn,j).
We use b, p, x to denote bidders’ bids, payments and allocations. More particularly, bi,j is bidder i’s bid in auction j. xi,j,k is 1 if bidder i gets the k-th slot of auction j and 0 otherwise. pi,j is the price paid by the bidder i in auction j. The welfare and revenue of an allocation x and payments p are defined as
Wel(x, p) = nX
i=1
mX
j=1
sjX
k=1
xi,j,k · vi,j · posj,k, and Rev(x, p) = nX
i=1
mX
j=1
pi,j .
For notation convenience, we will use Weli(x, p) = Pm
j=1 Psj k=1 xi,j,k ·vi,j ·posj,k and Revi(x, p) =Pm
j=1 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 Vickrey–Clarke–Groves 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-th 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 b̂k,j the k-th highest bid for k 2 [sj ] in auction j. Assuming bidder i wins slot k in auction j, its payment pi,j in the three auction formats are: (1) VCG: pi,j = Psj =k+1 b̂,j · (posj, 1 posj,), (2) GSP: pi,j = b̂k+1,j · posj,k, and (3) FPA: pi,j = bi,j · posj,k. It is 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 ri,j the reserve price and by zi,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 b̂k,j to denote the k-th highest score for k 2 [sj ] in auction j. For ease of presentation, we consider lazy reserves such that the slot is not allocated to a bidder if her bid without boosts does not clear her reserve, i.e., bi,j < ri,j ; 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 i gets slot k in auction j become:
• VCG: pi,j = Psj =k+1 max(b̂,j zi,j , ri,j) · (posj, 1 posj,);
• GSP: pi,j = max(b̂k+1,j zi,j , ri,j) · posj,k;
• FPA: pi,j = (b̂i,j zi,j) · posj,k.
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 according 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 2 [0, 1]:
• When the signals are used as boosts, we allow multiplicative errors in both directions and we say boosts are -approx, if for any i 2 [n], j 2 [m], zi,j 2 [µ · vi,j , ⌫ · vi,j), and µ = · ⌫;
• When the signals are used as reserve prices, we allow multiplicative underestimation errors and say reserve prices are -approx, if for any i 2 [n], j 2 [m], ri,j 2 [ · vi,j , vi,j).
Note that we require a one-direction error for reserve signals. One can always convert signals with bounded errors in both directions into signals with only underestimation errors by scaling them down once multiplicative overestimation errors have a finite upper bound.
Bidders. We focus on two types of bidders: utility maximizers and value maximizers. A utility maximizer bidder i maximizes Weli(x, p) Revi(x, p). In contrast, a value maximizer maximizes Weli(x, p) subject to a return on spend constraint Weli(x, p) Revi(x, p). Here, it is without loss of generality to assume the target ratio between return Weli(x, p) and spend Revi(x, p) is 1.
These two types of bidders can be summarized by bidders optimizing the following program
max Weli(x, p) i · Revi(x, p) (1) s.t. Weli(x, p) Revi(x, p).
Here i = 0 corresponds to a value maximizer and i = 1 corresponds to a utility maximizer. Our results apply for bidders with i 2 [0, 1]. We allow i 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 a result, the optimal solution of the objective in (1) is always non-negative, and therefore, the constraint would be irrelevant for utility maximizers.
Solution Concept. We consider a solution concept called undominated bids which includes the support 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 a problem instance I and an auction format, we say a bid vector bi = (bi,1, ..., bi,m) is (weakly) dominated by another bid vector b0i = (b0i,1, ..., b0i,m), if the following two requirements are satisfied:
Let x, p be the allocation and prices induced by bi, b0 i, and x0, p0 be the allocation and prices induced by b0i, b0 i. Then for any other bidders’ bids b0 i, b0i is at least as good as bi, i.e.,
• both violate constraints: Weli(x, p) < Revi(x, p) and Weli(x0, p0) < Revi(x0, p0) • bi violates constraints while b0i does not: Weli(x, p) < Revi(x, p) and Weli(x0, p0)
Revi(x0, p0) • or neither violates constraints, and b0i yields no worse objective: Weli(x, p) Revi(x, p) and
Weli(x0, p0) Revi(x0, p0) and Weli(x0, p0) i ·Revi(x0, p0) Weli(x, p) i ·Revi(x, p)
There exits b0 i such that b0i is strictly better than bi, i.e.,
• bi violates constraints while b0i does not: Weli(x, p) < Revi(x, p) and Weli(x0, p0) Revi(x0, p0)
• or neither violates constraints, and b0i yields strictly better objective: Weli(x, p) Revi(x, p) and Weli(x0, p0) Revi(x0, p0) and Weli(x0, p0) i · Revi(x0, p0) > Weli(x, p) i · Revi(x, p)
We omit the word “weak” for convenience for the rest of the paper. We say bi is undominated if there is no b0i dominates bi. Denote the set of all bidders’ bids b = (b1, ..., bn) by ⇥ in which each bi is undominated for i 2 [n] and each bidder is paying at most its welfare. As uniform bidding is widely adopted in automated bidding strategies, we also consider a solution concept related to it. We say bi is a uniform bidding for bidder i, if bi,j = vi,j · i for all j 2 [m]. We use ⇥u to denote the set of all bidders’ bids b = (b1, ..., bn) such that each bi is a uniform bidding and is not dominated by any other uniform bidding and each bidder is paying at most its welfare.

heading: 3 Main Technical Lemma
text: We first show a lemma which will be used as 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 to hold when we apply reserve prices only (i.e., µ = ⌫ = 0) or boosts only (i.e., = 0). For a better understanding of the lemma statement, conditions number 1, 2 and 5 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 ↵, , µ, ⌫ 0:
• For each bidder i and each auction j, the reserve satisfies ri,j · vi,j and the boost satisfies µ · vi,j  zi,j < ⌫ · vi,j .
• In each position auction, bidders are ranked by their scores bi,j + zi,j and the k-th highest score wins the k-th slot if bi,j ri,j .
• If bidder i’s value vi,j ranks in top-sj in auction j, bidder i bids at least ↵ times its base value, i.e. bi,j ↵ · vi,j .
• If bidder i wins slot k in auction j, bidder i pays at least the VCG price, i.e. pi,j Psj =k+1(posj, 1 posj,) ·max(b̂,j zi,j , ri,j).
• For each bidder, her total payment is at most her total value.
We have Rev(A(b)) min ⇣
(↵+µ) +⌫ , ⌘ ·Wel(OPT) and Wel(A(b)) ↵+µ1+max(⌫,↵+µ ) ·Wel(OPT).
We give a high-level proof sketch of this lemma. The detailed proof can be found in Appendix A.
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 OPT, 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 a lower bound on the revenue of A(b) via VCG pricing. The additional boost z (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 Wel(A(b)) Rev(A(b)) (in the fifth bullet point of the lemma statement), we can obtain lower bounds on Wel(A(b)) and Rev(A(b)).

heading: 4 Applications in Auctions

heading: 4.1 VCG Auctions
text: In this section, we consider VCG with reserves and boosts. We first show the following lemma about the set of undominated bids ⇥. Its proof can be found in Appendix B. Lemma 4.1. For any problem instance I , let ⇥ be the set of undominated bids for VCG with reserve r and boost z. Assume reserve r satisfies that ri,j < vi,j 8i 2 [n], j 2 [m], and boost z satisfies that zi,j 2 [µ · vi,j , ⌫ · vi,j) for some ⌫ µ  1 for all i 2 [n], j 2 [m]. For any b 2 ⇥, we have bi,j vi,j , if bidder i’s value vi,j ranks in top-sj in auction j.
With Lemma 4.1, 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 ↵ = 1, = , and µ = ⌫ = 0: Corollary 4.2. On any problem instance I , VCG with -approx reserve, denoted by VCG r , satisfies
Wel(VCG r (b)) 1
2 · Wel(OPT) and Rev(VCG r (b)) · Wel(OPT),
for bids b from the undominated bids set ⇥.
Combining Lemma 4.1 with Lemma 3.1 using ↵ = 1, = 0, µ = /(1 ), and ⌫ = 1/(1 ): Corollary 4.3. On any problem instance I , VCG with -approx boosts, denoted by VCG b , satisfies
Wel(VCG b (b)) 1
2 · Wel(OPT)
for bids b from the undominated bids set ⇥.
Combining Lemma 4.1 with Lemma 3.1 using ↵ = 1, = , µ = , and ⌫ = 1: Corollary 4.4. On any problem instance I , VCG with -approx reserve and -approx boost, denoted by VCG
r,b, satisfies
Wel(VCG r,b(b)) + 1
2 · Wel(OPT) and Rev(VCG r,b(b)) · Wel(OPT),
for bids b from the undominated bids set ⇥.

heading: 4.2 Generalized Second-Price Auctions
text: For GSP, we are able to show a lemma similar to Lemma 4.1 assuming bidders are all value maximizing ( i = 0 8i 2 [n]) and they are uniform bidding. Its proof can be found in Appendix C. Lemma 4.5. For any problem instance I with i = 0 8i 2 [n], let ⇥u be the set of undominated uniform bids for GSP with with reserve r and boost z. Assume reserve r satisfies that ri,j < vi,j 8i 2 [n], j 2 [m], and boost z satisfies that for some ⌫ µ  1, zi,j 2 [µ · vi,j , ⌫ · vi,j) 8i 2 [n], j 2 [m]. For any b 2 ⇥u, we have bi,j vi,j , if bidder i’s value vi,j ranks in top-sj in auction j.
Combining Lemma 4.5 with Lemma 3.1, we can obtain results similar to Corollary 4.2,4.3, 4.4. We only state the strongest one with both boosts and reserve prices: Corollary 4.6. On any problem instance I with i = 0 8i 2 [n], GSP with -approx reserve and -approx boost, denoted by GSP r,b, satisfies
Wel(GSP r,b) + 1
2 · Wel(OPT) and Rev(GSP r,b(b)) · Wel(OPT),
for uniform bids b from the undominated uniform set ⇥u.
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 C.
Lemma 4.7. For any problem instance I , let ⇥ be the set of undominated bids for GSP with -approx reserve r and no boosts. For any b 2 ⇥, we have bi,j ri,j · vi,j , 8i 2 [n], j 2 [m].
Combining Lemma 4.7 with Lemma 3.1 using ↵ = , = , and µ = ⌫ = 0: Corollary 4.8. On any problem instance I , GSP with -approx reserve, denoted by GSP r , satisfies
Wel(GSP r (b)) · Wel(OPT) and Rev(GSP r (b)) · Wel(OPT),
for bids b from the undominated bids set ⇥.

heading: 4.3 First-Price Auctions
text: For FPA, if we restrict that bidders are only value maximizers and they are 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 i = 0 8i 2 [n], FPA has
Wel(FPA(b)) = Rev(FPA(b)) = Wel(OPT),
for uniform bids b from the undominated uniform set ⇥u.
When there are no restrictions on bidders, we get similar results as GSP with the following lemma. Lemma 4.9. For any problem instance I , let ⇥ be the set of undominated bids for FPA with -approx reserve r and no boosts. For any b 2 ⇥, we have bi,j ri,j · vi,j , 8i 2 [n], j 2 [m].
Combining Lemma 4.9 with Lemma 3.1 using ↵ = , = , and µ = ⌫ = 0: Corollary 4.10. On any problem instance I , FPA with -approx reserve (FPA r ) has
Wel(FPA r (b)) · Wel(OPT) and Rev(FPA r (b)) · Wel(OPT),
for bids b from the undominated bids set ⇥.

heading: 5 Experiments
text: In this section, we derive semi-synthetic data from real auction data of a major search engine to validate our theoretical findings concerning VCG auctions. VCG auctions provide a 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 a 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 our mechanisms. Therefore, we use real ad auction data for capturing variation across bidders. For the experimental purpose, we simulate VCG auctions with bids from value maximizers only, as utility maximizers do not respond to either boosts or 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 our 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 be considered in theory.
Simulation Procedures. To properly evaluate the efficiency and revenue of a new mechanism, after the generation of the dataset, we first pre-train the (uniform) bid multipliers for value maximizers in 25 iterations without reserve prices and boosts to obtain an equilibrium as a starting point. We then simulate the response of value maximizers by gradient descent on their bid multipliers in log space until convergence [Aggarwal et al., 2019, Nesterov, 2013]. Formally, let i,t be the bid multiplier for value maximizer i in iteration t. In addition, let Weli,t be value maximizer i’s total received value in iteration t, and let Revi,t be her total payment in iteration t. Then, in iteration t + 1, the value maximizer i’s bid multiplier is updated by log i,t+1 = (1 ⌘t) · log i,t + ⌘t · log Weli,tRevi,t , where ⌘t 2 (0, 1) is a properly chosen learning rate for t-th iteration. Intuitively, when Revi,t < Weli,t,
value maximizer i’s bid multiplier increases for the next iteration; otherwise, her bid multiplier decreases for the next iteration. After obtaining a 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 we continue to use auctions without reserve prices, we experiment with boosts and reserve prices using signals with different approximation factors . For each bidder i in each auction j, we will set reserve prices or give boosts based on in different treatments. Here, let s i,j be a random variable independently sampled from a Gaussian distribution with mean (1 + )/2 and standard error 0.01, truncated within [ , 1]. In treatment reserve- , we set the reserve price as s i,j · vi,j . In treatment boost- , we add an additive boost 11 · s i,j · vi,j as suggested. Finally, in treatment boost-reserve- , we set the reserve price as s i,j · vi,j and additionally give an additive boost 11 · s i,j · vi,j . All metrics we report are relative to the gap between the baseline (i.e., without treatment) and the optimal solution. More precisely, let init be the initial welfare (revenue) without reserve prices or boosts, e be the welfare (revenue) under treatment e, and (OPT) be the optimal welfare (revenue). Then the reported percentage is computed by (e init)/((OPT) init).

heading: 5.1 Experimental Results
text: Figure 1a 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 to 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 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 on welfare. However, as the value maximizers start to 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- and treatment boost- share the same , their final impact on revenue after response are close to each other, as predicted by the same welfare bounds from Corollary 4.2 and 4.3. Moreover, a 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.2 and 4.3.
Figure 1b demonstrates 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 a better welfare performance post response as shown in Figure 1a. Moreover, as the reserve prices become more precise, the average multiplier is lower after convergence. Intuitively, the welfare is maximized when all the value maximizers adopt a bid multiplier 1 so that the auction results in a ranking according to their values. Therefore, the bid multipliers getting close to 1 after response is 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 to a worse welfare performance post response as shown in Figure 1a. A combination of reserve prices and boosts induces a mild decrease of the average multiplier, resulting in a rather stable welfare performance during value maximizers’ response.
We conduct 10 runs of repeated experiments and Table 2 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 . Moreover, a 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., 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 a result, we witness difference between welfare improvement and revenue improvement even after convergence.

heading: 6 Conclusion
text: In this paper, we provide both theoretical and empirical evidence to demonstrate that introducing properly chosen reserve prices and/or boosts can improve both revenue and welfare in the autobidding world. Our results are robust to bidders’ behavior models as well as inaccurate signals that approximate bidders’ values. One limitation of our results is regarding the requirement of reserve prices not exceeding bidder values. Although one can avoid this by scaling down the reserve prices, it does require additional knowledge from the auction designer on an upper limit of the inaccurate signals. It is an intriguing question to address such an issue in a more robust way.

heading: 7 Acknowledgement
text: Thanks are due to Mohammad Mahdian, Aranyak Mehta, Renato Paes Leme, and Ying Wang for helpful discussions, and for their comments and suggestions.

Review summaries:
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.  Boosting 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.  The 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. 

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.  Their 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. 

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: 1. They show that introducing reserve prices might have a positive impact on social welfare. 2. 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.  Then the authors assess their findings by running some simulations and running real experiments that confirm their findings. 

This paper studies auction design for advertising slots when the agents are using auto-bidding optimization algorithms.  The 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.  The 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).  The 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.