Efficiency of the First-Price Auction in the Autobidding World
Authors: Yuan Deng
Jieming Mao
Vahab Mirrokni
Hanrui Zhang
Song Zuo
Venue: NeurIPS 2024 poster (2024)
Keywords: first-price auctions
ad auctions
autobidding
price of anarchy
Primary area: algorithmic_game_theory
TL;DR: We give tight price of anarchy bounds for first-price auctions in the autobidding world.

Abstract: We study the price of anarchy of first-price auctions in the autobidding world, where bidders can be either utility maximizers (i.e., traditional bidders) or value maximizers (i.e., autobidders).  We show that with autobidders only, the price of anarchy of first-price auctions is $1/2$, and with both kinds of bidders, the price of anarchy degrades to about $0.457$ (the precise number is given by an optimization).  These results complement the recent result by [Jin and Lu, 2022] showing that the price of anarchy of first-price auctions with traditional bidders is $1 - 1/e^2$.  We further investigate a setting where the seller can utilize machine-learned advice to improve the efficiency of the auctions.  There, we show that as the accuracy of the advice increases, the price of anarchy improves smoothly from about $0.457$ to $1$.

Efficiency of the First-Prics Auction in the Autobidding World
Yuan Deng Google Research dengyuan@google.. com
Jieming Mao Google Research mao jm@google elg.olll...o com
Vahab Mirrokni Google Research
mirrokmi@google.comm
Hanrui Zhang
Song Zuo Google Research szuoggoogle. com
Chinese University of Hong Kong hanruiccse. cuhk. edu.hk hk
Abstract
We study the price of anarchy of first-price auctions in the autobidding world, where bidders can be either utility maximizers (i.e., traditional bidders) value maximizers (i.e., autobidders). We show that with autobidders only, the price of anarchy first-price auctions 1/2,, and with both kinds of bidders, the price of anarchy degrades to about 0.457 (the precise number is given by an optimization), These results complement the recent result by Jin and Lu [2022] showing that the price of anarchy of first-price auctions with traditional bidders is 1 - 1/e2.. We further investigate a setting where the seller can utilize sechine-learred advice improve the efficiency of the auctions. There, we show that as the accuracy of the advice increases, the price of anarchy improves smoothly from about 0.457 to
1 Introduction
Autobidding, the procedure of delegating the bidding tasks to automated agents to procure advertise- ment opportunities in online ad auctions, is becoming the prevalent bidding methods and contributing to more than 80% total online advertising traffic [Dolan] 2020]. Autobidding significantly simpli- fies the interaction between the advertisers and the ad platform: instead of submitting bids for each auction separately, the advertisers only need to specify their high-level objectives and constraints and the automated agents bid on behalf of the advertisers. A popular autobidding strategy value maximization subject to a target cestum-on-investine agents aim maximize their value, such the number of clicks/conversionss, subject minimum admissible ratio on the return-on-investment constraint. This type of bidders has been referred as value maximizers by the recent line of research on autobidding [Deng al. 2021 Balseiro al. 2021a
(ROI) constraint, in which the autobidding
As the behavior model of automated bidders is very different from the classic (quasi- linas))linear) utility maximizers maximizing the difference between value and payment, there has been a growing body of literature revisiting the effectiveness of the existing mechanisms through the lens of the autobidding world [Aggarwal et al. [219 Deng et al., 2222] Balseiro et af.) [2021a] Liaw et al.) 2022 Babaioff
al. 2021). In particular, it is well-known that running the second-price auction against utility
maximizers results in socially optimal outcomes; however, Aggarwal et al. [2019) show that the
price of anarchy (PoA) (Koutsoupias and Papadimitriou 1999 the ratio between the worst welfare
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

in equilibrium and the socially optimal welfare, of running the second-prics auction against value maximizers is 1/2 (when the bidders do not adopt dominated strategie
In addition to the change in bidding methods, there has been an industry-wide change in auction formats in recent years: shifting from the second-prics auction to the first-price auction, especially in the display ad markets, culminating in the move to the first-price auction from the Google Ad Exchange in September 2019 [Paes Leme et al.) 2020). The shift towards the first-price auction in combination with the increasing adoption of autobidding raises the question of understanding the PoA of running the first-prie price auction in the autobidding world.
1.1 Our Results
In this paper, we characterize the PoA of running the first-price auction in the fully autobidding world, where all bidders are value maximizers, and in the mixed autobidding world, where bidders could be either value maximizers or utility maximizers. Our results complement the very recent result from Jim and Lu [2022] showing that the PoA of running the first-price auction is 1 - 1/ee in a world without autobidding, i.e., all bidders are utility maximizers. The results are summarized in Table and we also include the known results for sccond-price auctions for comparison.
Mechanism
First pesst-picc auction
Second-price auction
Full autobidding
1/2
1/2
Aggarwal et al. 2019
Mixed autobidding
min1e]0011] 2 I-ttt
Int
0.457
1/2
Balseiro al. 202
No autobidding
1/e" ss 0.865 (Jin and Lu 2022)
[iickrey 1961
Table I: Summary of PoAs in second-price and first-price auctions under full autobidding, mixed autobidding, and no autobidding environments. We note that for the second-pric auction, bidders are assumed not adopt dominated strategies; otherwise the PoA can be
Our results demonstrate that in a full autobidding world, the PoA of rumning the second-price auction and the first-prics auction is the same. i.e. 1/2: however, in the mixed autobidding world with both utility maximizers and value maximizers. the PoA of running the first-price auction strictly less than the PoA of running the second-price auction. It is worth highlighting that our PoA bound for the first-price auction in the mixed autobidding world involves solving an optimization problem min 14tlot. 2-1+5ln8 and it turns out that this is the right bound we are able to construct an instance matching this bound.
In addition to the above results, we further adopt the environment introduced by Balseiro et al. (2021b) where the seller can leverage lechine advice that approximates the buyers' values for designing mechanisms. [Balseiro et al.] [2021b] show that as the advice gets more and more accurate in predicting the buyers' values, setting reserves based the advice in the second-price auction makes the PoA approaching In our setting of using machine-learned advice the first-price auction, we prove that setting reserves based on machine-learned advice is also effective in improving PoA in both full and mixed autobidding world, and the PoA approaches as the quality of the machine-learned advice increases.
1.2 Related Works
For first-price auction with utility maximizers, the price of anarchy has been extensively stud- ied (Roughgarden et al.) 2017]. In the complete-information setting with additive values, there is no efficiency loss, i.e., the price of anarchy is 1 [Feldman et al.) 2016). For Bayesian settings, [Feldman let al. [2013] first showed that the price of anarchy is at least 1/2 for subadditive valuations and SSygkaanis and Tardos 2013) showed that the price of anarchy at least 1/e for submodular valuations. These bound are shown to be tight for buyers with submodular valuations and subadditive valuations [Christodoulou et al. 2016 When agents' values are independently distributed, the price
of anarchy was later improved to R 0.743 by Hoy et al. 2018) and Hartline et al. (2014) gave concrete instance to establish an upper bound Rs 0.869. More recently, Jin and Lu [0022 show that
'When discussing the second second-price auction, we assume the bidders do not adopt dominated strategies. In the case when the bidders could adopt dominated strategies, the PoA of running the second second-price auction can be 0.

---

the price of anarchy for independently distributed values is exactly 1 1- 1/c². Paes Leme et al. [2020) provide models and analyses explain why Display Ads market shifts to use fist-price auctions.
Motivated by the emergence of autobidding in online advertising, there is a recent line of work studying auction design for value maximizers in autobidding world. [Agarwaal et al. [2099] design optimal bidding strategies in truthful auctions, show the existence of equilibrium, and prove welfare price of anarchy results. Deng et al. [202]] and and Balseiro al. [0021b] show how boosts and reserves can be used to improve the welfare efficiency guarantees given machine-learned advice approximating buyers' values. [Balseiro et al. 2021a 2022 give the characterization of the revenue-optimal optimmal auctions under various information structure. Mehta [2022] and Liaw et al. [2022) study how randomized and non-truthful mechanisms can help improve welfare efficiency for the case of two bidders. In particular, Liaw et al. (2022) show that the PoA of running the first-price auction is 1/2 when restricting to equilibria of deterministic bids. In this work, we consider general equilibria with randomized bidding strategies. Deng et al.] [2024] study the efficiency, as measured by the price of anarchy, of the generalized second-price auction in the autobidding world, and give a parametrized bound. [Liww] al. 2024] consider a setting with value maximizers only, which is similar to our "full autobidding" setting. The main difference is that they focus on the effects of budget constraints on top of ROI / ROS constraints. The high-level message there is that using the fractional optimum as the benchmark, first-price auctions become much less efficient with budget constraints, but this efficiency loss can be circumvented if we consider the (weaker) integral optimum
the benchmark. Gaitonde et al. [2023) take a somewhat different perspective, and give a bidding dynamics that does not necessarily converge, but on average achieves good welfare. Conitzer et al. [022]] study "pacing" in first-price price auctions, where constrained bidders optimize their bids in multiple auctions by choosing a single multiplier, and bidding the product of this multiplier and their value in each auction. In contrast, we do not restrict the strategy space of bidders in this paper. |Fnn et al.] (2024) study a meta-game in the context of autobidding, where human bidders strategically specify their constraints (e.g., the target ROI). They show that such strategic selection does not hurt the welfare too much in first-price
auctions. For a more comprehensive overview, see, e.g. (Aggarwal et al. 2024
2 Preliminaries
Ad auctions. Following prior work on autobidding, we consider setting with n bidders [n| and m auctions [m]. where each bidder participates in all auctions simultaneously. We generally use i to index bidders, and j to index auctions. Each bidder has a value v.j. 2 0 for winning in each auction j. We consider first-price auctions - arguably the most common and well-known auction format - as the auction mechanism throughout the paper. That is, each bidder i submits a bid bi, in each auction j. In each auction j. the bidder with the highest bid wins and is charged the winning bid as the payment. For the existence of equilibrium in the first- auction, we assume ties are broken in favor of the bidder with the higher value within an auction, which is standard assumption in the literature [Maskin and Riley| 2000 P If multiple bidders have the same value, then ties are broken in favor of the bidder with the smallest index We let Fi.j xt, ((br )v) be the indicator variable indicating that wins in auction j. Then, the value each bidder i receives in auction is val., = vali,j((br je)) = xa. (1br (b)))))) Ui.j. and the payment i makes in auction is Pi.j Pi.j (1br )v) = Ti (fbrr)e) (e)))bb, bug We remark that bidders may employ randomized bidding strategies, in which case (beg). (115). [vale and {pis} } are all random variables. Throughout the paper, we omit the dependence of f.y. val.y and prg on (be whenever it is clear from the context. For brevity, we write v. {ur, 1, b. [br,)), etc.
Utility maximizers and value maximizers. We consider two types of bidders: traditional (quasi- linear) utility maximizers and (ROI-constrained) value maximizers. In the rest of the paper, we use B2 to denote the set of utility maximizers and B, the set of value maximizers, where we always have B, B, @ and B, B. in). For each bidder i, let val, =, vali, be the total value
Maskin and Riley 2000) assume ties are broken with a second-round second-price auction among the highest bidders to guarantee the existence of equilibrium in the presence of discrete values. This tie-breaking rule is equivalent to favoring the bidder with the higher value for standard utility maximizers, while the two tie- breakin rules can be different for value maximizers. We choose the without the additional definition of socond-rount second-price auction for simplicity.
'Our positive results are oblivious to tiebreaking, i.e., they remain valid no matter what tiebreaking rule is
used.
3

---

i receives from all auctions, and p: = E, Pi.j be the total payment makes. Fixing other bidders' bidding strategies, utility maximizer bids in a way such that the total quasi-linear utility, i.c., val, Pt, maximized, without additional constraints. On the other hand, value maximizer bids in a way such that the total value val; that receives is maximized, subject to the ROI constraint that the ratio between the total value val; and the total payment 2; least some predetermined threshold. Without loss of generality we assume this threshold is 1 i.e., we require the total payment Ps is at most the total value val; for each value maximizer i. Formally, fixing other bidders' bids, a value maximizer i solves the following optimization problem to determine their bids {br,})y
maximize subject to
E [val
E vall - p.] 0.
Here, the expectations are taken over the randomness introduced by bidders bidding randomly. We note that when deciding how to bid, i can observe the distributions, but not the realizations, of the other bidders' bids.
Equilibria and the price of anarchy. The focus of this paper is on the efficiency of the first-price auction in equilibrium. That is, when each bidder i's bidding strategy b; is optimal for that bidder's objective, given all other bidders' bidding strategies {by Je (or b for brevity). In other words, each bidder's ss strategy is a best response to other bidders' strategies, Note that since each bidder i cannot observe the realizations of other bidders' bids, all bidders' bids {b;}: J. must be independent. The way we measure efficiency is through the classical notion of the price of anarchy (PoA) [Koutsoupias and Papadimitriou 1999). , i.e., the ratio between the welfare resulting from the worst equilibrium possible, and the optimal welfare. Formally, given a problem instance of (n, m. B.. B., {Vr.g D) we are interested in the instance- PoA defined as follows:
E[val.
inf PoA(n, m, B,, B,, (Righ) [b.). equilibrium
E, max; V...
Our goal to pin down the PoA of the first-price auction, which the infimum of the instance- wise PoA taken over all instances of the problem. We assume Ej max, UA >> 0 in order for the PoA to be well-defined.
Equilibrium bidding behavior of value maximizers. In this paper, we do not put further re- strictions on bidders' equilibrium bidding behavior, such no-overbidding. This is in contrast to some prior work: In prior work, since overbidding is a dominated strategy for utility maximizers, the no-overbidding assumption is often imposed for analyzing the PoA of utility maximizers in second-price auctions and first-price auctions (otherwise, the PoA could be 0). However, in the model we consider, assuming no overbidding for value maximizers with ROI constraints may rule out their optimal strategies. More importantly, with the no overbidding assumption, the optimal strategy for maximizess would be bid their values in first- firs-pprice auctions since such strategy maximizes their bids without violating the ROI constraints, leading to the trivial welfare-optimal outcome in world with maximeiexxs only. In other words, the welfare inefficiency in the autobidding world is mainly caused by the overbidding behavior from value maximizers, and such inefficiency can only be analyzed without assumptions such as no-overbidding (although such assumptions might make sense in other contexts).
3 PoA of the First-price Auction in a Full Autobidding World
In the literature Aggarwal et al. 2019 Deng et al. 202 Balseiro et al. 2021b), the analyses of PoA for the second-price auction in full autobididng world mainly leverage the fact that the second-price auction is truthful for utility maximizers, nice property implying that value maximizers adopt uniform bidding strategy in equilibrium [Aggarwal et al. 2201]. Here, a uniform bidding strategy for value maximizer is strategy in which she bids ky Ut,j with a constant bid multiplier k; in each auction j- However, as the first-price auction is not truthful for utility maximizers, a uniform bidding strategy is generally no longer a best response for value maximizer. A value maximizer i may adopt
"See Appendix for why this is without loss of generality, as well as further justifications for considering the liquid welfare in the autobidding world.

---

non-uniform bidding strategy using different bid multiplier ki in different auction j, and the bid multipliers can even be randomized.
Liaw et al. 2022 show that the PoA of running the first-price auction in a full autohidding world 1/2 when restricting equilibria of bidding in deterministic way (i.e., restricted to pure Nash equilibria). In this section, we devise a novel argument to analyze equilibria with possibly randomized non-uniform bidding strategies to show that the PoA of the first-price auction in a full autobidding world is exactly 1/2.
Theorem 1. When all bidders are value maximizers, the PoA of the first-price auction in a full autobidding world is 1/2. Formally,
inf 2
PoA(n. m. B. = B. = [n], (ush)) 1/2.
We remark that the proof of Theorem I in fact establishes the following claim, which will be building block in our analysis of PoA of the first-price auction in a mixed autobidding world with both value maximizers and utility maximizers.
All missing proof' are deferred to Appendix B
Lemma 1. For any n, m, Bu By and {righ h. (b; form an equilibrium, then
Σ E[val]]
Σ
Elpaa] 2
Σ max Vj.j1
(.J.WG))BB.
j=w())EB.
where rw(j) argmax, Va, denotes the "rightful winner" of each auction with ties broken in favor of the bidder with the smallest index.
4 PoA of the First-price Auction in a Mixed Autobidding World
In this section, proceed to the main result of the paper: characterizing the exact PoA of running the first-price auction in a mixed autobidding world with both utility maximizers and value maximizers participating in the auctions. The entire section is devoted to the proof of the following claim. Theorem 2. The PoA of the first-price auction in mixed autobidding world is given by:
1 fnt
inf Bem.B..e..oo..
PoA(n, m, Bu, Bu, (vig)) = min r 2 L + lll ~ 0.457.
Roadmap. the rest of the section, we first establish a PoA lower bound. At first sight, one might be tempted to adapt the proof of Theorem [ hoping to get the same lower bound of 1/2 in the presence of utility maximizers. In doing so, one faces the following intuitive difficulty: for a utility maximizer i, the value i receives when best responding is not necessarily lower bounded by the value i receives when using the proxy bidding strategy K/55 = Vi.. This is because aiming to maximize utility, may bid in way such that both the value receives and the payment i makes smaller, but their difference (which is the utility i gets) is larger. One simple fix is to consider instead the following proxy strategy: by, vt.s/2. Adapting the proof of Theorem I it is not hard to show this alternative proxy strategy gives PoA lower bound of 1/4. However, unlikely that such fix would yield the tight ratio of about 0.457.
In order to overcome this obstacle, we present novel local analysis (Lemma 3) for the first-price auction that handles auctions where the rightful winner a utility maximizer, which roughly says that if the expected value that the rightful winner receives from such an auction is small, then the expected payment that other bidders make in the same auction must be large. This argument relies on characterization of the structure of the best response of a utility maximizer. Given the local analysis, one can already get a lower bound of about 0.317 on the PoA by exploiting the tradcoff between value and payment.
To obtain the right ratio, we further combine the local analysis for utility maximizers with the bound for value maximizers (Lemma [ discussed earlier. The idea is to consider 4 quantities separately: (A) the total value that all value maximizers receive, (B) the total value that all utility maximizers receive from auctions where they are the rightful winner, (C) the total payment made in auctions where the rightful winner a value maximizer, and (D) the total payment made in auctions where the rightful winner is utility maximizer, by bidders who are not the rightful winner.
5

---

One can show that the welfare in equilibrium is lower bounded by very specific combination of these 4 quantities (Lemma Moreover, Lemma provides a tradeoff between (A) and (C), and the local analysis (Lemma 3) provides tradeoff between (B) and (D). Therefore, one can lower bound the PoA by solving an optimization problem involving few number of parameters to get the worst-case tradeoffs. We show that this optimization gives the right ratio of about 0.457 (Lemma Finally, we present a problem instance where there exists an equilibrium where the gap between the actual welfare and the optimal welfare is precisely the right ratio (Lemma 6). This, together with the matching lower bound, concludes the proof of Theorem 2
4.1 A Local Analysis
In this subsection, we propose local analysis of the first-price auction to analyze the tradeoff between welfare and payment in equillibrium when the rightful winner of the auction is utility maximizer. Although the analysis is mainly designed for utility maximizers towards establishing the lower bound of PoA, it also works when the rightful winner of the auction is value maximizer. For the remainder of this subsection, we fix n, m, {vi.) J. and an equilibrium profile {b;] Ji, and consider any fixed bidder i and auction j where is the rightful winner. For brevity, we also let = v.j.
Saate- frontiers. We first try to understand the maximum expected value i can get in auction j when paying particular amount in expectation. Let F be the CDF of the highest other bid, i..., for any x 2 0,
F = Pr max by S b-i (t
Note that in the first-price auction j. if bidder bids 1, the bidder pays t. F(t) and earns value v- Ft)). For any x 2 O, consider a function G RR+ - [0, v) such that
G(x)
sup e F()....
120: (FF(t)
In other words, G maps a desired expected payment the maximum (or strictly speaking, supre- mum) value can get by bidding deterministically. when paying at most the desired payment æ in expectation. By bidding randomly, can further achieve any value- palle- pair that is convex combination of points on G. In light of this, we further consider the concave envelope H of G, which captures the value-payment frontier when i can bid randomly. Note that for utility maximizers, although there always exists deterministic best response (since all bids with positive probability in a randomized bidding strategy must result in the same quasi-linear utility), the equilibrium bidding strategies may still be randomized for the sake of stability.
Characterizing the best response. Given the definition of the value- panment frontier H, one can
further observe that when best responding, i's expected utility E[val,,j - Pt.jl depends only on H. In fact, intuitively, since Hl is concave, i's expected value and payment auction j must correspond to the "rightmost" point on H where the derivative is larger than or equal to 1 (this is informal since (1) the point may not be unique and (2) the derivative may be undefined). Formally, when i a utility maximizer, i's best response in j, bs.j, has the following property.
Lemma 2. For any b 2 0 in the support of ba.j. have for any 2 b- F(b), H(w) ((b- < w - b. F(b).
We remark that the same property also holds when is a value maximizer, with minor modifications in the proof.
tradeoff between value and payment in equilibrium. We are ready to present a tradeoff between the value i receives and the payment other bidders make in auction j. The intuition is that given Lemma the curve must be relatively flat to the right of (pi., H (p(.)) (i.e., with slope at most 1), which means the CDF function F of the highest other bid must also be with relatively small slope. On the other hand, the payment made by other bidders can written as
bij (D-F((b.)))
(1 F(t)
This means if F(be.). ) the probability that i wins when bidding be.j. is small, then since F is with small slope to the right of bi.j. the payment must be relatively large. The following claim formally captures this tradcoff.

---

Lemma 3. There exists some x: E [0, 1] such that
Elval = x- U and
Epps (1 x 1ln)..)) e.
Right
We remark that Lemma 3 alone already implies lower bound of about 0.317 on the PoA: summing the bound in Lemma 3 over and j where rw(j) i and exploiting the convexity of the mapping
2 + - + z 2, one can show there is some x: E [0, 1] such that
Σ E[vaa:] 2 x E max Vij and Σ Elpa] N (1 x ll
E max Vi.i
Since E, [[[va,]] 2 E, Elp:), the worst case scenario is when = - x + x xlnn which gives J 0.317, lower bound on the PoA.
4.2 Putting Everything Together
In this subsection, we combine Lemma and Lemma to obtain an improved (and in fact, tight) lower bound the PoA of the first-price auction in the mixed autobidding world. Fixing n, m, Bu. B, and {uij} we consider four key quantities in the proof. (A): the total value that all value maximizers receive; (B): the total value that all utility maximizers receive from auctions where they are the rightful winner; (C): the total payment made in auctions where the rightful winner is value maximizer; and (D): the total payment made in auctions where the rightful winner utility maximizer, by bidders who are not the rightful winner. Formally,
A = Σ
E[[aal::
B =
Σ
E [[vals.j]
iEB
iE (ro
C
Σ
D
E E|pa.l
(j:w()))
(.jow(j) B, and rw(i)
We first show that the welfare can be bounded by a combination of the above quantities. Lemma 4, For any bidding strategies (b:); that form equilibrium, always have
E[vall max (A,C D)
We are now ready to prove our main PoA lower bound. Lemma 5. In mixed autobidding world with both utility maximizers and value maximizers, the PoA of the first-price auction has the following lower bound:
1 1lt
B...B.......... PoA(n, m, Bu, Bu, {v,,))
inf
min |E[0,1]
2= 0.457.
2 - t t ilnt
Remark 1. Our analysis involves bounds (e.g., Lemma 3) of similar forms to those normally seen in the smoothness framework (Syrgkanis and Tardos 2013| and its instantiations (e.g.. [Hartline al. 20144), and it is conceivable that might be able fit part of our analysis in the smoothness framework. However, is unlikely that doing so would substantially simplify or change the nature of the analysis. In particular, in order to instantiate the smoothness framework in the proper way that produces the light bounds, presumably one would need to carry out essentially the same argument as in our analysis.
4.3 A Matching Upper Bound
To conclude this section, we present a problem instance in which our PoA lower bound can be actually achieved, even with 2 bidders and = 2 auctions.
Lemma 6. When n = m = 2, there exists Bu, B, and {vis} such that
1 + t ilnt ~ 0.457.
PoA(n, m. B,, B,, (vigh) min
[ 2 Int
Theorem is direct corollary of Lemma and Lemma 6
7

---

Improved Efficiency with ML Advice
In this section, we turn more muneticaly-motivaan setting, where the seller can rely on machine- learned advice to set reserves and thereby further improve the efficiency of the first-price auction. In particular, we show that as the advice gets more and more accurate, there is a way to set reserves such that the PoA of the first-price auction approaches 1.
Setup. Following prior work Balseiro et al. [021bb, we consider the setting in which for each auction j. the seller can access a signal s.. which approximates the highest value max; Vijj in this auction. Formally, we assume there a constant y E [0, 1] such that 8j E h max; Ma.j max; %,,] for each auction i As BBlsserro al. 2021b) argue, the model is a reasonable simplification of the actual problem, which enables clean theoretical results while still making practical sense. In particular, the assumption that the signal never overestimates the value can be relaxed: if there is a
bound on how much the signal might overestimate the maximum value, then one can scale everything down accordingly and retain the PoA bound Theorem (with high probability).
First-price auction with machine-learned reserves. The way we exploit machine-learnet signals is to use them as reserve prices in the first-price auction. To be more specific, in each auction j. we set a reserve r3 = 8j, such that a bidder i can win only if i's bid b.j 2 vy. particular, max; bij < ri then no one wins in auction j. This is different from the first-price auction without reserves, where there always exactly 1 winner.
We overload the notations and let Iii = [T fbr be the indicator variable that i wins in auction j. and define {val..) and {p(.) in similar way such that all these variables depend on both the reserves } and the bidding profile {b For any n. m, Bu, Be, and {vt,h J. we consider the following parametrized instance-win wise PoA when each ry 83 E by max; Ve,5, max, vayl:
E, [[vak]
(n,, m, Bu: Bu, forst)
inf
[br,]] } form an equilibrium MjrryE(y-mas Vay max, Pt.e]
E, max; Vi.j
Our main result in the section is captured by the following theorem.
Theorem 3. For any n, m, Bu. B., {us,}} and y E [o, 1].
1 + tltntt 7tnnt--t1100n
(n m, Bay Bu: (mrgt) min
1 2 - 7 (1
One way to interpret the lower bound is it provides smooth transition between the case without machine-learned advice (or with totally unreliable advice, i.c., 7 = 0), and the case where the advice is perfectly accurate (i.e., each auction. In the former scenario corresponding to 7 = 0, we recover the tight PoA bound stated in Theorem In the latter scenario corresponding to 7 = 1, as one would expect, the theorem gives a lower bound of 1, which means the auctions are perfectly efficient. More generally, for y between 0 and 1, the lower bound in Theorem 3 increases monotonically as y increases, since the fraction within the min increases in y for any fixed E [0, 1]:
1) and the seller knows precisely the value of the rightful winner in
1 + Int - 7t(1 Int)
++ (2 12-1+ (1 (nl) (1 (1+1 11) 1+4nl
(1-
2 2-1 1 7 (1-7)
where + ini 10 and 2 t tht 12 (1+1hnt)
In order words, the efficiency of the first-price auction with machine-learned reserves improves as the reserves become more and more accurate. To better illustrate the rate which the efficiency improves, we plot our lower bound against the accuracy 7 in Figure [ As the plot shows, our lower bound improves approximately linearly as the accuracy 7 increases from 0 to 1.
$ As we focus on the single slot environment this paper. for ease of presentation, our assumption here is weaker than Balseiro et al. (0211) as they assume for each bidder and each auction j. there is a signal $;, [y Biyy V. and setting 8, max; $iy gives the signals which can be used in our setting. Our result can be extended to the multi-slot environment by adopting the assumption from Balseiro et al. 2021bb.
8

---

1.0
0.9
0.8
PoAy
0.7
0.6
0.5
0.4
0.0
0.2
0.6
1.0
Figure 1: The efficiency of the first-price auction with machine-learned reserves when the accuracy of the reserves is 7 E [0, 1].
To prove Theorem 3 the plan apply Lemma 4 which provides lower bound on the welfare in any equilibrium, and consider tradeoffs between the 4 quantities involved in the lower bound. The key difference is that we obtain better tradeoffs with machine-learnet reserves. In the rest of the section, we fix m, Bu. B., and {utj}. With machine-learned reserves, the tradeoff given by Lemma | limproves to following (note the factor of (1 7) on the left hand side).
Lemma 7. In auctions with machine-learne reserves of accuracy E an equilibrium,
[0, 1], for any (bi); that form
(1-7)- Σ E[val]] +
Σ
E[pry] 2
k.j:w())ER.
j.nw(i)
We note that the above lemma also implies a lower bound of 1/(2 7)) on the PoA of the first-price auction with machine-learned reserves in the full autobidding world in which all bidders are value maximizers. When + O (i.e., reserves are extremely unreliable), the bound degrades to 1/2; when y - 1 (i.e., reserves are extremely accurate), the bound approaches 1, which means the auctions are efficient.
Corollary For any n, m, { and y e 1). (o m, B, 0, B. [m], (v,,)) Z 1/(2-7).
For utility maximizers, adapt the local analysis, and obtain the following improved tradcoff between value and payment.
Lemma 8. In auctions with machine-learned reserves of accuracy y E [0, 1]. for any (b,), J. that form an equilibrium, and any bidder i and auction j where rw(j) = i, there exists x E [0, [0 such that
Ejval;,j] r 0.
and Σ Elprol 2 (1 x + (1 7)2 In)) 025-
We can now prove Theorem by plugging Lemma and Lemma g into Lemma
Acknowledgments and Disclosure of Funding
We thank anonymous reviewers for their helpful feedback.
References
Gagan Aggarwal, Ashwinkumar Badanidiyuru, and Aranyak Mehta. Autobidding with constraints. In International Conference on Web and Internet Economics, pages 17-30. Springer, 2019.

---

Gagan Aggarwal, Ashwinkumar Badanidiyuru, Santiago R Balseiro, Kshipra Bhawalkar, Yuan Deng. Zhe Feng, Gagan Goel, Christopher Liaw, Haihao Lu, Mohammad Mahdian, et al. Auto-bidding and auctions in online advertising: A survey. ACM SIGecom Exchanges, 22(1):159-183, 2024.
Moshe Babaioff, Richard Cole, Jason Hartline, Nicole Immorlica, and Brendan Lucier. Non-quasi- linear agents in quasi-linear mechanisms. In Proceedings of 12th Innovations in Theoretical Computer Science, 2021.
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, Yuan Deng, Jieming Mao, Vahab Mirrokni, and Song Zuo. Optimal mechanisms for value maximizers with budget constraints via target clipping. In Proceedings of the 23rd ACM Conference on Economics and Computation, 2022. URL httpstt//pperss..stttt
com/ /o13/
papers.
censstract_id408811
Santiago R. Balseiro, Yuan Deng, Jieming Mao, Vahab Mirrokni, and Song Zuo. Robust auction design in the auto-bidding world. In Marc' Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan, editors, Advances in Neural Information Process- ing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, pages 17777 17788. 2021b. URL U neurips. wttpiips.ccpppppe//0/// 0tt0:////.........66666666666110
Awwtract.tttttttt html
George Christodoulou, Annamária Kovács, Alkmini Sgouritsa, and Bo Tang. Tight bounds for the price of anarchy of simultaneous first-price auctions. ACM Transactions on Economics and Computation (TEAC), 4(2):1-33, 2016.
Vincent Conitzer, Christian Kroer, Debmalya Panigrahi, Okke Schrijvers, Nicolas E Stier-Moses, Eric Sodomka, and Christopher A Wilkens. Pacing equilibrium in first price auction markets. Management Science, 68(12):8515-855) 8835, 2022.
Yuan Deng, Jieming Mao, Vahab Mirrokni, and Song Zuo. Towards efficient auctions in an auto- bidding world. In Proceedings of The Web Conference 2021, 2021.
Yuan Deng, Mohammad Mahdian, Jieming Mao, Vahab Mirrokni, Hanrui Zhang, and Song Zuo. Efficiency of the generalized second-price auction for value maximizers. In Proceedings of the ACM on Web Conference 2024, pages 46-56, 2024.
Shelagh Dolan. US Programmatic Digital Display Ad Spending Will Grow Despite Fandemic-Relatee programmatic- diiiiiddiiiiipppppli display-ad -d--aaddd-s---wweeeeee------ will- Recession. htt.pppppeepppeeeeeeeeeereeeeese 2020. Accessed: 9 Jul 2022.
grow-despite-pandemiie
Michal Feldman, Hu Fu, Nick Gravin, and Brendan Lucier. Simultaneous auctions are (almost) efficient. In Proceedings of the forty-fifth annual ACM symposium on Theory of computing, pages 201-210, 2013.
Michal Feldman, Brendan Lucier, and Noam Nisan. Correlated and coarse equilibria of single-item auctions. In International Conference Web and Internet Economics, pages 131-144. Springer, 2016.
Yiding Feng, Brendan Lucier, and Aleksandrs Slivkins. Strategic budget selection in competitive autobidding world. In Proceedings of the 56th Anmual ACM Symposium on Theory of Computing. pages 213 2024.
Jason Gaitonde, Yingkai Li, Bar Light, Brendan Lucier, and Aleksandrs Slivkins. Budget pacing in repeated auctions: Regret and efficiency without convergence. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023), volume 251, page 52. Schloss Pagstuhl-Leibing Zentrum f ür Informatik, 2023.
Jason Hartline, Darrell Hoy, and Sam Taggart. Price of anarchy for auction revenue. Proceedings of the fifteenth ACM conference on Economics and computation, pages 693-710, 2014.
10

---

Darrell Hoy, Samuel Taggart, and Zihe Wang. A tighter welfare guarantee for first-prics auctions. In Proceedings of the 50th Anmual ACM SIGACT Symposium on Theory of Computing, pages 132-137, 2018.
Yaonan Jin and Pinyan Lu. First price auction is 1-1/e2 efficient. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 179-187. IEEE Computer Society, 2022.
Elias Koutsoupias and Christos Papadimitriou. Worst-case equilibria. In Annual symposium theoretical aspects of computer science, pages 404 Springer, 1999.
Christopher Liaw, Aranyak Mehta, and Andres Perlroth. Efficiency of non-truthful auctions under auto-bidding, 2022. URL https: /ttp://aaxvv..///a//aa/ http:/aaxivv....aaab/a/ abs 03630
Christopher Liaw, Aranyak Mehta, and Wennan Zhu. Efficiency of non-truthful auctions in auto- bidding with budget constraints. In Proceedings of the ACM on Web Conference 2024, pages 223-234, 2024.
Eric Maskin and John Riley. Equilibrium in sealed high bid auctions. The Review of Economic Studies, 67(3):439 454, 2000.
Aranyak Sitanshu Mehta. Auction design in an bidoing setting: Randomization improves efficiency beyond veg. In Proceedings of the ACM Web Conference 2022, pages 173-181, 2022.
Renato Paes Leme, Balasubramanian Sivan, and Yifeng Teng. Why do competitive markets converge to first-price auctions? In Proceedings The Web Conference 2020, pages 596-605, 2020.
Tim Roughgarden, Vasilis Syrgkanis, and Eva Tardos. The price of anarchy in auctions. Journal of Artificial Intelligence Research, 59:59-101, 2017.
Vasilis Syrgkanis and Eva Tardos. Composable and efficient mechanisms. In Proceedings of the forty-fitth annual ACM symposium on Theory of computing, pages 211-220, 2013.
William Vickrey. Counterspeculation, auctions, and competitive sealed tenders. The Journal of finance, 16(1):8-37, 1961.
A More on Liquid Welfare
Following prior work on autobidding [Aggarwal al. 2019 Deng et al. 202 Balseiro al. 202 la
Liaw et al. 2022], we consider the liquid welfare as the objective throughout this paper. The liquid welfare is the maximum amount of payment that can be extracted from the bidders given a certain allocation. Formally, assuming each bidder i's target ROI ratio is T;, and each bidder i's value in each auction j is vi.j. the liquid welfare under allocation {aa,5] is defined as follows:
Σ Zis Uig/TT.
In particular, we let = for each utility maximizer i, which simply means is individually rational. One check the above definition is consistent with the classical social welfare when all bidders utility maximizers, and it is also consistent with prior work on autobidding when all bidders are value maximizers. The benchmark we consider in this paper is the first-best liquid welfare, i.c.
Σ max Va.j/T=
This can be achieved by allocating to the bidder with the highest target- arget-adjusted value vt.5/T /T, in each auction Observe that the quantity that actually matters in the (first-best) liquid welfare is the target-adjusted value / T4. Therefore, without loss of generality, we can replace each bidder i's value in each auction j with the target-adjusted value u and assume all bidders" target ROI ratios are 1.
The liquid welfare makes more sense than the classical social welfare in the presence of value maximizers, because a bidder with high target ROI ratio and low values behaves in the same way as bidder with low target ROI ratio and high values, as long as their target-adjusted values are the same. There is no way for the mechanism to distinguish between the two types of bidders, and thus, it is infeasible to try to maximize the classical social welfare.
11

---

B Omitted Proofs
Proof of Thhhormmm 7 First provide simple hard instance, which implies upper bound of 1/2 on the PoA. Consider an instance with n = 2 bidders and m = 2 auctions, where both bidders are value maximizers, We set V1,1 I, 222 = E, and 21.2 2 22 O, where 0 is small quantity to be fixed later. Consider the following deterministic bidding strategies: b1.1 62.1 = 0 (so bidder 1 wins in auction 1 by tiebreaking and pays 0), b1_2 - 1, and 22.2 (so bidder wins in auction 2 and pays 1). First we verify this is in fact an equilibrium. Observe that the ROI constraints of both bidders are satisfied. Bidder does not want to deviate from b1, since bidder already gets the maximum value possible, i.e., 1. Bidder 2 would ideally want to bid higher (possibly randomly) in auction 2 in order to win with some probability and get positive value. However, given 61_2 bidder 2 would have to bid at least in order to win, which means P2.2 2 1 whenever 22, 1. This would violate bidder 2's ROI constraint. So both bidders' strategies are best responses, and therefore form an equilibrium. On the other hand, the optimal welfare is 11, + 22 = 2 and the welfare resulting from the above equilibrium is only U1 = 1, which means the PoA is at most 1/(2 E). Letting& 0 yields upper bound of 1/2.
Now we focus on lower bounding the instance-wise PoA fixing any n, m, and {or,): }. Consider any equilibrium, induced by bidding strategies {b:).. Our task is show that
Σ E[val:] Z Σ max Uj.j1
where the expectations, as well as all expectations in the rest of the proof, are taken over {b:).. For each auction j. let rw(j) = argmax, Vi be the "rightful winner" of auction j. where ties are broken in favor of the bidder with the smaller index. Now fix a bidder i, and consider the following proxy bidding strategy b; of bidder i: b/.j = Vi, in each auction j. i.e., the proxy bidding strategy b; is a strategy in which bidder i bids truthfully. Then, for each auction j where i = rw(j). the probability that wins in auction j under the proxy bidding strategy b/, fixing all other bidders' strategies b-;, is
Pr Pr(mss(M b1) = Pr b_t
max S K..s b_. i'
Pr b-.
maxbes S vi.j
Also, observe that i's ROI constraint is satisfied under the proxy bidding strategy b', since under the proxy bidding strategy byg the following holds deterministically:
(B,, b.:) (.b, b..)
Σ zig 3: b (v)) bb.,) _ Da. (1: m..) 0.
Taking the expectation over b. we see that i's ROI constraint is satisfied (and is in fact binding). The above observations imply the following fact: There exists bidding strategy (i.e., b)), under which i's ROI constraint is satisfied, and the expected value receives is
(V, b-)1 >
Σ Pr(mas(be b bis)) = Vig = Σ Pr
max by S vas 18
f:H=(())
j:t=((())
Observe that since is a value maximizer and b, is a best response to b we must have
Ebval:(b:, b-:)] 2 (bVa b.)) N
Σ Pr
max by S 0ig V.j- PI1
f:t=w(())
On the other hand, fix a bidder and consider the total payment collected in any auction j with rw(j)= = i, under (b., b_.). By the properties of the first-price auction, we have
Σ E pe (bb.j 6 b.,)) = -E max by
EE
max by i'
Uii = (1
max byr S vass ) V..j. .us. i'ts
Pr b
max by > Va.j
Pr b,
Zti
Summing over all auctions j with rw(j) = we have
Σ
Epp b_:))
Σ
(1
(1-Po
Pr b_,
max bys S mas) mes 8+1
(
jiz=w(())
12

---

Combining this with the bound on the total expected value i receives, we get
E[val; b-:) +
Elyy b-))] N
):
Further summing (and omitting dependence on (b;: b-i)), the above gives
Elival:] + Σ B'pil Σ max max
Finally, observe that for any bidder i, the ROI constraint implies Elp,] I E[val;], and therefore we can conclude the proof with
2 Σ E[val:] 2
Σ E[val:] + Σ Blps] N
Σ max Vi.j
Proof of Lemma 2 Suppose towards a contradiction that there exists w > b F(b) such that H (w) ( F(b)) - b F(b), equivalently, H(w) - H(b F(b)) b F(b). Let by be possibly randomized bidding strategy that realizes the point (w, H (w)). i.e., when using b i receives value H(w) and pays in expectation in auction j. Then, the utility that i receives from when using the new strategy b', is H(w) - w. On the other hand, consider the deterministic bidding strategy B = b. Since b in the support of b..j. 8", must also be a best response. However, under K/,5- i receives utility H(b F(b)) b. F(b), which is strictly worse than the utility i receives when using the alternative strategy b/.3. In other words, bi cannot be a best response, a contradiction. O
Proof of Lemma is to show
Let [[F(b Clearly [0, 1] and E[val,,] = z Our remaining task
Σ s
Elpval 2 (1 + xln))
Recall that
Σ
Elpy
E biij
big (1 F(bis)) (L-
( dt
f 00 bb..
As result, in order to lower bound the payment, we want to pointwise upper bound F. Fix any in the support of the best-response strategy bi.j. we must have
H(b. F(b)) G(b F(b)) = F(b...
By Lemma 2 for any w 2 F(b). we have H(w) H(b F(b)) S w - b- F(b), which implies that (w) ((b- F(b)) + - b. F(b). Also, since H is the concave envelope of G, the same
upper bound applies to G, and we have
G(w)= < (w))= S Hb F(b)) + w b- F(b) = v. F(b) + w F()).
Due to the monotonicity of F(x), we have that for any 1 2 b. we have -- FF(() 2 b- Fb)). Therefore, given the relation between G and F, the above implies that for any [b, 1) (note that this range might be empty),
(v b) F(b)
v. F(t) G(t F(t) +t b- F(b)
F(t)
We next bound the payment conditioned on big b. We consider two possible cases: b 2 v and b < v. If v. simply have
Σ Elpess big = b] = b. F(b)) + / (1 - FLF(())) dt
2 bb. b. (1- F(b)) 2 (1 - F(b)) v 2 (1- F(b) + F(b) In F(b))
13

---

In particular, the last inequality is because F(b) In F(b) & O when F(b) E [0, 1]. If < we must have b (u 13.15 F(6), and result,
Σ Elprs = = b F(b)) + (1 d( #
2b. (.-1F(()) + ()-1))
(v (U- ( ( P(bb) d
(u-( (()-bb((F()) F())
(1 F(b)) 2 (v -b)
b). bF) In(u $){
(1 F(b)) u (v - b) F(b) In F(b)
(1 F(b) + F(b) F(b)) v.
Combining the two cases and further taking expectation over bi.j we get
Σ Elpral
E [11 (b).)) + F F(b.,) In F(b e) 21 - In biy
where the last inequality is due to Jensen's 's inequality, the fact that 2 ト 1 - 2 + a In is convex on [0, 1], and chose [[[((b)))]-
Proof of Lemma 4
Observe that
2
E2 E[val,]
E[vak:]
+ Σ
[[[al:]]
=
B.
i6 B..
max
E E[val,],
Σ
E[pil
E[val,]
B.
i.
<C Bi
max
E v[aaa
Σ Elpil
E +
Σ
Elvala.]
B
FEB.
ie (un
iE i.
max
A,
Elpa]
B+
Σ
Elvals.].
B.
Note that for each E Bu and j. we always have B[[akky] 2 Elp,,> since is best responding and the utility receives in is least O. Therefore, we can further relax the above into the following:
Σ E[val:] 2 max A, Σ
Elp
B
Σ
Elpcs]
B
max
A,
Σ
E(p.]
+
Σ
Elpaol
B.
RE
Rearranging the sums within the max, have that
Σ Elp.]
Σ
Elps,1
Σ Elpd]
Σ
Elpr.]
R
JWW
Σ
E Elpr
Σ
E(Pty]
i.j:w())BBB
(.:m(())BB and mw()
=C + D.
Substituting in the max gives the bound to be proved.
Proof of Lemma Fix any n, m, Bu, B., and {vi)). Consider any bidding strategies {b:}: that form an equilibrium. Let
V==
Σ
max Wigt
V3 =
max U.
jiwwjjEBB..
jinr(j)BB,
14

---

By Lemma we have
E, Eivak Ej max; Vijj
max(A, C. + D) + B V V/2
By Lemmal 1 we have + C' V1. So there must be some x E [0, 1], such that A x: Vi and 2 (1 2) V1. As for B and D, apply Lemma 3 For each j where rw(j) E Bu. Lemma
states that there exists some Dj E [0, 1]. such that
E[val Mj vijs
Elpual 2 (1 Mi + Mj In max Vi.j.
(t(()
Let y B/V2. Since B E Ejm(()) El $ Σ Eiww)EBB. max; Vs V2, we have y E [0, 1]. In particular.
E Jinii))BB E(vallw())
EjswbjeB. Uj max; Vs.j
Σ Ejmo(j)eB max, V.j
Ejm(ije max; Vaj
Since & + 1 11-t- + tln is convex, by Jensen's inequality, we must have
D= Σ Σ
E[P.J] M
Σ (1- + y وy max Vt,
j:w(()) Bu (pFw()
B.
2 (1 y + y yn
E
max Ui = (1 y yllllyy V/2
j.wwi)EB.. B.
Plugging in the above derived lower bounds for A, B, C, and D, we have
Σ, V[al]]] max C + DJ + max(= V1, (1 x) V1 + - (1- V13 + y.. V/2
En max, Vis
V + V/2
V/2 + V/2
where V1, 1/2 2 V. + 1/2 > 0 and x, E [0, 1]. In other words, we must have
max(# V1, x) V1 (1 y + ylny)
V23 y V/2
PoA(n, m. Bu; Bo, (v.))) 2
V2.120,11 inf (2>00
V + V/2
A careful analysis (see Lemma in Appendix C of the right-hand-side shows that it equals to
min 1 + ln y
R 0.457,
2 y/ y Iny
which is achieved when x = 1 and 1/2 = - y + y y V2. This concludes the proof.
Proof of Lemmn 6 Let B,, {1) and B, = {2]. We choose U1, = and U1,2 22 0. and leave ,22 > to be fixed later. The idea is to let bidder win in auction 2 for free, and therefore bidder gains enough slackness in the ROI constraint and can therefore compete with bidder 1 in auction 1. To be specific, in order for bidder to win for free in auction 2, we choose 61,2 = 62.2 = so that bidder 2 wins by tiebreaking and pays O. We want bidder I's value-paymen
frontier in auction 1 to have the following shape: the curve starts at (0, t) for some E [o, 1] (to be fixed later), and then increases linearly with slope precisely 1, until it hits the upper bound, i.e., when the y-axis becomes a best response. Translating this to bidder 2's bidding strategy, we would like that for any 2 0.
V1.1 = 1. This ensures that bidder bidding b1.1 = 0 deterministically
Pr|b2,1 S = min { 1 1-b
One can show that the expected payment that bidder 2 makes in auction 1 is 1 t + t f. In order to satisfy bidder 2's ROI constraint, we choose 12 = t + innt. One may check that the above bidding strategies in fact form an equilibrium. Note that E[val]] Pr[62.1 E[valy] = 2222 = 1 & Int.
V1 = f, and
Considering the ratio between the optimal welfare and the welfare resulting from the above equilib- rium, we have
E[val1 valg]
1 1+thm tnt
PoA(n, m, Bu, Boy (wr,))) S
U1.1 22.2
f + tlnf
15

---

for any & E [0, 1]. Minimizing over t gives
+ tlt
PoA(n, m. Bu, (orn))
<
min :e[0.1] 2 + tln
Proof of 7 The proof is similar to that of Lemma I at a high level, except that the expected
payment is higher, because in each auction j. the rightful winner rw(j) must bid least r3 (which is
a constant fraction of ()w()))) unless the highest competing bid is at least Vnw()). with probability 1.
Again fix any equilibrium strategies {b,}. value maximizer& i E B,, we have
By the same argument as in the proof of Lemma for any
E[val:]
>
Σ f:i=)w(s)
Vi.j Pr
max br S Vi.j 8#1
Also, observe that for any value maximizer E B, and auction j where rw(j) i, at least one of the following properties must hold: Either (1) b.j 2 ri,j deterministically, or (2) Pr[maxx- by 2 v..il 1. This is because if neither of the holds, then i for any b <r in the support of bi.j would be better off by moving probability mass from b to Ui which preserves feasibility and strictly increases the value i receives from j. For each where (1) holds, we have
)
Σ Elpr Ur 2 vis"
1 - Pr
max maxbbr S Vh.s r'f
+ +ry Pr
max bys S Und xat
2 Ui,j"
1 - Pr
max bys S vi.s iz
+7. Vij
Pr
max by S Ui.j F'gs
-ij (1 ?) v.j Pr max
ma S oid
For each j where (2) holds, we immediately know that
Σ Elp Jl 2 U.
Pr
max
by 2 %/.
Uii 2 Vijj - (1 7) ois Pr
max by S Uns
s'ts
So combining the two cases and summing over j where = rw(i),
bu S vais 1)
Σ Elpval
Σ
Ui.j (1 7) Uais Pr
max #t
(f):
j=w(())=
Combining this with the lower bound on B[vak]] above, we get
(1 7) E[[al,]
+
Σ E] 2
Vij-
Y ((jow())=
joww(j)=
Further summing over E B, gives the inequality to be proved.
Proof of Lemma 8 The first part of the reasoning is almost identical the proof of Lemma 3 For any in the support of b Lemma gives us a way to upper bound the CDF of the highest other bid, and subsequently to lower bound the payment made by other bidders. Without repeating the entire argument, we start directly from this lower bound. Let F' be the CDF of the highest other bid, i.c., for any 2
F(() Pr
max be 51) ("
When 2 v. we have
Σ
E Epps b b] 2 (1 F(b) v (1- (1-7) -Fb) In F(b)) v.g.
When b < U, again must have one of the following two: Either (1) 2 ry 2 7 Ui.j. (2)
F(vis) = 1. When (1) holds, we have
Σ Elpro b.. 6) 2 (I-F(b)). +F() F()) - (1- (--00))))) In F F(b)) -v...
16

---

When (2) holds, clearly we have
Σ
Elpe. bas b) 2 vig F(u..) = m. 2 (1 F(b) + (1 (1-7)) (1b)) F(b)) Wi.j-
Combining these cases and taking the expectation over buj (again letting x: = [F()()) we get
Σ Elpral 2 E[(1 F ((b.,) + (1 In F(b.))) m. 2 (1 x + (1 7) x Iu Cijo Viy
where the last inequality from Jensen's inequality since ++ 2 + -) 2 In is convex on [0, 1] for any [0, 1].
Proof of Theorem Reproducing the argument in the proof of Lemma 5 (but with the improved
tradeoff's given by Lemma 7 and Lemma 8). we can lower bound PoA, m, Bu, Bu {ur. }) by
max x V1, (1 (1 7) V1 + (1 y + (1 7)y In y) V2) + y V2
inf Vi.220..ttVuuueeeeell...
V1 + 1/2
careful analysis (see Lemma 10 in Appendix C of the infimum shows that it equals to
+ y In rV(1 In v) min v=|0,1] 2 - 7 + (1 7)y
C Analysis of the Infimum
Lemma 9.
max x V1, 2) V1 (1 (1-9 4 yly)) V22 v.v.
1 In
min yc (0.1) 2 - + y Iu
V. A.V.20.V++V>>0..ee0000
V1 + V/2
Proof. Without loss of generality, suppose V1 + 1/2 1, so the domain is compact, and only need to prove that
max(x Vi, x) Vi + y + V2} + y V/2
+ y Iay ve 0 2 - + y yly
inf
min
V++1= V...v..
V1 + 1/2
Since the term inside the infimum is continuous the domain other words, there exists Vir, Vgz x and y that achieve the minimum. If 1/2 = 0, then clearly is lower bounded by 1/2 (which is clearly suboptimal). So must have V/2 > 0.
replace the inf with a min. In
Now observe that the two terms within the inner max must be equal when the minimum is achieved. This is because: if V 2 (1-y" +y" In v").V/ then x" must equalize the two terms (any other choice of x=" would be suboptimal). Otherwise, the inner max must be (1-x*)-V4 (1-1 +y" In y²))"²/ which means x" must be 1, in which case V/* does not appear at all. But then, increasing V and decreasing V/2 simultaneously would strictly decrease the value, which contradicts the optimality of these choices. So we must have
(1 - y² + "y"""y") V22
xr' VV (1-z")-V VT +(1 +y" 1ny")VV
and x" E (1/2,
2x
Plugging this in, the minimum simplifies to
r² (1 + y- In 5¹) 3
2x y² + 1" In Iny"
Observe that the denominator the above fraction is always positive whenever x" E (1/2, 1] and y" E [O, 1). Moreover, depending the value of y², the partial derivative of the above fraction with respect to x= is either never 0 or always 0. In the former case, it must be the case that x = 1 (any other choice cannot be optimal); in the latter case, the value of x does not matter, without loss of generality we can choose x² = Plugging this in, the minimum simplifies to
1 + n² Iny" 8" + y* Iyy" ve
+ ylny min
y + yyyy
This concludes the proof.
17

---

Lemma 10.
max (1-(111111)1) (1-7)=) 14 + (1 yy-++t 7110111))))) V2) + y V/2
inf V.
Vi +
min 1 y y yy( In
yElu,1] 2 - 7 (1 ln
Proof. When 7 1, is easy to check the above minimum is 1. In the rest of the proof, we assume 7 [0, 1). We break this into cases:
When
(1 - y + (1 7) Ahylngg y) V/2
V (1
V/2 = V1 <
the minimum becomes
min (1- V1 + (1 (1 (1-7)y1111)) V/2
Vi + 1/2
and the minimum must be achieved when x 1, in which case it further simplifies to
min 7 Y. V1 + (1 + (1 7yy [y V22
V1 + V/2
Since yln y E 1/e,, and + (1- In y) > y we want Vi to be as large as possible, which means Vi (1 (1 7)y In y) 1/2(11 - 7). Plugging this in, the minimum becomes
1 ylyly y 73(11 + Iny)
min - - 7yylny
When
(1 y + (1 (111)yylnng) y) V/
2 y
(1-y (1-7)y 1)
V/2
Vi
1-7
the minimum must be achieved when the two terms within the inner max are equalized, i.e.
= Vi (1 11-2 y + (1 - 7)y In y) V/2
x- 1/ =
(2 - (2-
This also means we can restricted the domain of x to x E (1/(2- - 7), 1]. Plugging this in, the minimum simplifies
2 (1++y-g
min
72 1 In
Observe that the denominator is always positive for æ and y in the domain, so the derivative the fraction with respect to either never minimum can only be achieved when x = 1; in the latter case, the value of x' does not matter, so we can without loss of generality choose I Plugging x 1 in, the minimum simplifies to
always In the former case, the
1 + In yy(1 + Iny)
min
- - + (1 Iyyy
Combining the two cases concludes the proof.
18

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The abstract and introduction discuss the claims proved in the paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: The paper discusses settings where the results do not apply, and also presents negative results.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
19

---

Justification:
The full model is defined and all results are proved.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification:
No experimental results.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
20

---

Answer:
[NA]
Justification:
No data or code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cm
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ cppppi.ccppulli//uuuia wwwtii/gguie///eeeeceoocc CoodeSubeiiie ssi wswonnolli onnolicy)))) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification:
No experimental results.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification:
No experimental results.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
21

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
No experimental results.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: httpp:s:///errpss.../ http:pss....ppoccccccccccceeeee.
Answer:
[Yes]
Justification: In particular, have done our best preserve anonymity.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: The paper is theoretical without immediate broader impacts.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to
22

---

generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative socictal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: No data models released.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: No existing assets used.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, wwppppswpptseeee whw.ree.wthhhe....c. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's is creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
23

---

Answer:
[NA]
Justification: No new assets introduced.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/codeemoodll as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
No crowdsourcing human subjects involved.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: No human subjects involved.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
24


Reviews:
[{"review_id": "KgjNgAvQEs", "reviewer": "Reviewer_9Zo1", "summary": "Autobidding is the technique of using optimization algorithms to assign ad slots to bidders while respecting their constraints (e.g., budget, ROI, ROAS, etc.). It generates about 80% of the total online ad revenue for major tech companies, and is therefore quite a significant topic to study. Within this topic, there is the question of \"price of anarchy\", a notion introduced by Koutsoupias and Papadimitriou, which measures the ratio of the worst welfare in equilibrium to the socially optimal welfare; the smaller this is, the better. Finally, given the recent emergence of the trend of first-price auctions by companies like Google, the question this paper studies is: What is the price of anarchy of running the first-price auction in autobidding? \n\nThe most surprising component of their result is that the price of anarchy is the same for first-price and second-price auctions in the fully autobidding world. The key technical hurdle in comparison with second-price auction is that the first-price auction is not truthful for utility maximizers, so uniform bidding isn't the best strategy for value maximizers.", "questions": "Questions: I'm curious about the comparison with the paper, \"Efficiency of Non-Truthful Auctions in Auto-bidding with Budget Constraints\" by Liaw,", "limitations": "N/A, primarily a theory paper", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "-", "weaknesses": "I found the details of the paper somewhat difficult to follow, though the authors do seem to have put quite a bit of effort in making the proofs intuitive. (My background isn't in algorithmic game theory so perhaps I'm not really the intended audience for this.)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your insightful and encouraging comments.\n\n**The Liaw et al. paper**: thank you for pointing us to the paper.  This paper is indeed quite relevant and we will discuss it in our paper.  In short, they consider a similar setting with autobidders (value maximizers) only, which is close to our \"full autobidding\" setting.  The main difference is that they focus on the effects of budget constraints on top of ROI / ROS constraints.  The high-level message there is that using the fractional optimum as the benchmark, first-price auctions become much less efficient with budget constraints, but this efficiency loss can be circumvented if we consider the (weaker) integral optimum as the benchmark.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "AjRMC2WN4f", "reviewer": "Reviewer_fGt9", "summary": "The authors study the price of anarchy of first-price auctions where the bidders can be either only autobidders (value maximizers), or a mix of autobidders and traditional bidders (utility maximizers). The setting consist of $n$ bidders and $m$ auctions. Each bidder bids a value $b_{i,j}$ for each auction $j$ and the one with maximum bid, wins the auction and has to pay $b_{i,j}$. Utility maximizers try to maximize the value minus the payment, while value maximizers try to maximize the value, subject to the constraint that the ratio between value and payment is at least a certain threshold. The price of anarchy is the ratio between an equilibrium with worst social welfare (sum of the values) and the optimal social welfare.\n\nThe authors prove that in a full autobidding world, (even) when bidders can bid randomly, the price of anarchy is $1/2$. This improves the result of Liaw et al. who prove the price of anarchy in this setting when bidders bid deterministically is $1/2$. More importantly, the authors prove the price of anarchy in the mixed setting with the presence of both autobidders and traditional bidders is $0.457$. They prove a lower bound and give an example with this price of anarchy, and thus matching the lower and upper bound for this setting. Moreover, they prove that if the seller can predict the value of the bidders (using machine-learned advice), it can set reserves to improve the efficiency (price of anarchy). The more precise the advice is, the better the price of anarchy gets in the range of $0.457$ to $1$.", "questions": "I do not have any questions.", "limitations": "Yes. The authors discuss for which settings the results apply and for which ones they do not apply. It also gives a negative result.", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "- The paper is very well-written and self-contained. \n\n- The addressed setting seems to be a very natural one to consider as also motivated in the paper. \n\n- The results are strong and complete the picture of price of anarchy in the first-price auctions.\n\n- While the proof is not easy and it is novel as the authors claim, it is partitioned into small parts to be more presentable.", "weaknesses": "I did not find any major weaknesses. \n\nThe paragraph Utility maximizer and value maximizers in page 3 was a bit confusing. In line 109, \"at most\" should be \"at least\" I think and in line 111 \"at least\" should be \"at most\".", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your insightful and encouraging comments.\n\n**Paragraph on page 3**: thanks a lot for pointing this out.  You are absolutely right and we will fix the paragraph.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "pIUGfz7p64", "reviewer": "Reviewer_wwix", "summary": "This paper studies the price of anarchy of simultaneous first-price auction, where there are $n$ bidders and $m$ auctions/items for sale. The underlying assumption of this paper is that all bidders have a **fixed** valuation. This paper considers 2 types of bidders: 1) a utility-maximizing bidder which maximizes $x(v-p)$, and 2) a value maximize which maximizes the total value of the goods. For value-maximizer only, they show that there is a tight PoA of approximately 1/2. For mixed bidder behavior, they show a tight PoA of approximately 0.457. Finally, they studied how to set a reserve price as a function of the underlying **value**, and how the change of this reserve price affects the PoA of the resulting first price auction with reserve.", "questions": "Please see the weakness section.", "limitations": "The paper doesn't explicitly state the limitations.", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 1, "strengths": "- This paper studies an important and timely topic of auto bidding, i.e., simultaneous first price. \n- This paper has some figure illustrations of the results.", "weaknesses": "- The introduction of the paper missed a lot of related work on the related work for auto-bidding, i.e., [1], [2], [3].\n- For the model considered in this paper, it is more reasonable to assume that the bidder is unit-demand or has a submodular utility instead of additive utility. \n- **The settings in Table 1 are not comparable**: \n\n-- For the 1/2 of full auto bidding in a second-price auction( i.e.,  [Aggarwal et al., 2019]), they consider the setting where each bidder has a **budget**, and the welfare is defined as liquid welfare instead of sum over-valuations.\n\n-- For the no auto-bidding in the first price auction ( i.e., [Balseiro et al., 2021b]), they consider the **single item** multi-bidder setting.\n\n-- This paper studied the **multi-bidder multi-item** setting, and, since everyone pays what he bids, it's natural and reasonable to assume no overbidding compared to other settings, i.e., second price.\n\n- [line 110] \"without generality we assume this threshold is 1\". In the related discussion of this sentence in Appendix A, this paper has an **unconventional liquid welfare** definition. In addition, the cited papers all use conventional or **other** versions of liquid welfare:  \n-- [Aggarwal et al., 2019] use the liquid welfare of the budgeted version as, $\\sum_{i \\in [n]}  \\text{min}\\{ B_i, \\sum_{j} v_{i,j} x_{i ,j } \\}$.\n-- [Deng et al] use above definition as well.\n-- [Balseiro et al., 2021a] doesn't use liquid welfare but first best revenue.\n-- [Liaw et al ., 2022] uses $\\sum_{i \\in [n]} \\tau_i \\sum_{j \\in [m]} x_{i,j}  v_{i,j} $. where $\\tau_i$ is the ROI for bidder $i$. \n-- As a result, the WLOG actually only holds for the liquid welfare specifically defined in this setting.\n- For the PoA definition, the paper never defined the equilibrium considered in this paper, Bayesian Nash, or Competitive, or Coarse Correlated.\n- Section 5 proposed a reserve price that depends on the **value** but not the bid, which is not observable and hence cannot be applied in practice. \n- There is no conclusion of this paper. \n\nMinor Comment:\n- line 317, $\\{ v_{i,j}\\}$ should be $\\{ v_{i,j}\\}_{i \\in [n], j \\in [m] }$.\n\n\n \n\n\n\n\n\n\n[1]: Gaitonde, J., Li, Y., Light, B., Lucier, B., & Slivkins, A. (2022). Budget pacing in repeated auctions: Regret and efficiency without convergence. ITCS 2023. \n\n[2]: CONITZER, Vincent, et al. Pacing equilibrium in first price auction markets. Management Science, 2022, 68.12: 8515-8535.\n\n[3]: AGGARWAL, Gagan; BADANIDIYURU, Ashwinkumar; MEHTA, Aranyak. Autobidding with constraints. In: Web and Internet Economics: 15th International Conference, WINE 2019, New York, NY, USA, December 10–12, 2019, Proceedings 15. Springer International Publishing, 2019. p. 17-30.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed comments.\n\n**Related work**: we will discuss these results but we do want to note that the third missing citation of Aggarwal et al. mentioned by the reviewer (which is one of the earliest papers on autobidding) is the first entry in our list of references.\n\n**Submodular / unit-demand bidders in autobidding**: while we appreciate the suggestion, we'd like to note that additive bidders are the predominant assumption in the autobidding literature adopted in almost every paper, including the three papers mentioned by the reviewer.  It would certainly be interesting to see whether our results extend to richer valuations, such as submodular ones; but we would like to highlight that it is already technically non-trivial to develop PoA bounds for additive bidders in first-price auctions.\n\n**Comparison in table 1**: There seem to be a few inaccuracies in the reviewer's comment.  We provide an itemized response below.\n- [Aggarwal et al., 2019]: the bound still applies when there is no budget constraint (or equivalently, when each bidder has an infinite budget); and this result is almost folklore now in the autobidding literature.\n- [Balseiro et al., 2021b]: the paper in fact studies the multi-bidder multi-item setting.\n- No overbidding: the assumption would make the problem trivial.  In fact, the only reason a bidder would ever want to underbid is to save budget so they could overbid elsewhere and compete for items that don't \"rightfully belong\" to them.  If we were to assume no overbidding, then a dominant strategy for each bidder would be to bid their true value everywhere, and the resulting PoA would be 1 (i.e., full efficiency).  On the other hand, rational overbidding is a reasonable strategy for value maximizers because they don't directly care about the utility.  In other words, they are happy to pay more than an item's value as long as that item is worth *something* to them and the overall ROI is large enough.  This is precisely what happens in the lower bound constructions in the proofs of Theorem 1 and Lemma 5.  We have discussed in detail why no-overbidding makes less sense in the last paragraph in Section 2.\n\n**\"Unconventional\" liquid welfare definition**: we are not sure we follow this question, since the definitions of liquid welfare mentioned by the reviewer are equivalent to ours.  In particular, the version with budget constraints reduces to ours by setting $B_i = \\infty$, and the Liaw et al. definition (note that their $T_i$ is our $1 / \\tau_i$, which makes no difference because these are input parameters) is precisely ours due to the reasons specified in Appendix A. In general, all the definitions of liquid welfare from the literature as well as our paper share the same characteristic that they capture the maximum achievable revenue while satisfying all advertisers’ constraints. \n\n**PoA definition**: the auction game we consider is perfect-information, and the solution concept we consider is the standard Nash, which we believe are reflected in our definitions in Section 2. We do not consider Bayesian (correlated) equilibria or competitive equilibria in this paper.\n\n**Price in Section 5 depending on value**: this is the common assumption in the literature of algorithms / mechanisms with predictions.  The idea is to design algorithms / mechanisms which have a reasonable worst-case guarantee, and whose performance improves as the accuracy of the machine-learning-powered predictions ($\\{s_j\\}$ in our model) increases.  A similar model is also studied in [Balseiro et al., 2021b].  When such predictions are not available, one can always fall back to the standard model that we study in Sections 3 and 4.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "FEjCqKt1Nb", "reviewer": "Reviewer_HcJX", "summary": "This work studies the efficiency of first-price auctions when bidders in the market are all value maximizers or mixed value and utility maximizers. With all value maximizers, the PoA is 1/2, while with partial value maximizers, it is approximately 0.457. The paper also considers the case when the seller has machine-learned reserves on bidders' values, which are approximates of their true values with lower and upper bound guarantees. In this case, the PoA is also given with different approximate guarantees.", "questions": "Please see the weaknesses above. Also, what does $\\mathsf{rw}(j)$ mean at the end of Page 4?", "limitations": "The authors have addressed the limitations of their work.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper studies an important problem in the efficiency of first-price auctions in the auto-bidding world after the emergence of results on the tight PoA for traditional utility maximizers given by Jin and Lu, 2022. In this work, tight PoAs are given for the full auto-bidding world with value maximizers. Also, similar results for the mixed world are shown. In this sense, the contributions of this work are solid. Involving machine-learned reserves is also a good idea, and corresponding results are also presented. I think this paper is above the bar of NeurIPS.", "weaknesses": "That being said, I still have some minor problems with this work. For example, how is the PoA related to the number of value and utility maximizers in the mixed auto-bidding world? The authors seem only to give the infimum of all PoAs in the mixed world. I think more details hidden behind the PoA can be dug.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your insightful and encouraging comments.\n\n**PoA parametrized by number of bidders**: this is a great question, and indeed we have given some thoughts to it.  In short: any nontrivial refinement (if there is one) beyond the 0.457 bound would require a more sophisticated parametrization, which would necessarily take into consideration parameters other than the numbers of bidders of the two types.  The reason is that in the proof of Lemma 6 (the lower bound on the PoA with mixed bidders), we construct a tight instance with only 1 value maximizer and 1 utility maximizer.  This means the lower bound of 0.457 holds as long as there exists one bidder of each type, because one can always add dummy bidders of both types who value all items at 0.  Therefore, a bound that depends only on the numbers of bidders of the two types would look like: (1) if there is no value maximizer, the bound reduces to prior results for settings with utility maximizers only, (2) if there is no utility maximizer, the bound is 1/2, and (3) otherwise the bound is 0.457.\n\n**rw(j)**: sorry for the confusion.  rw(j) here denotes the index of the \"rightful winner\" in auction j, who has the highest value in auction j and therefore should win in a welfare-maximizing allocation.  The notation is introduced in the proof of Theorem 1, which has been moved to Appendix B because of space constraints.  We will fix this and define rw(j) in the main paper.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The question this paper studies is: What is the price of anarchy of running the first-price auction in autobidding?
The most surprising component of their result is that the price of anarchy is the same for first-price and second-price auctions in the fully autobidding world. More importantly, the authors prove the price of anarchy in the mixed setting with the presence of both autobidders and traditional bidders is 0.457.

The paper is in the middle between two strains of literature: the one about price of anarchy of auctions, and the second about algorithms for autobidding auctions. According the first direction, it appears to be a non trivial advancement. However, it should be noted that literature in the second direction direction considered more general settings, and different equilibria concepts than the ones considered in this work.

The paper fails to compare itself with the direction of autobidding literature (and focus in details on a specific set of papers coming from the same group), and justify most of the conventions and notation (often standard in the literature about price of anarchy in auctions) to readers that do not know this literature. Authors are invited to address these issues in the next revision of the paper, since also appears that there is room for this.
Decision: Accept (poster)