Efficiency of the First-Price Auction in the Autobidding World

Authors: yuan  deng
jieming  mao
vahab  mirrokni
hanrui  zhang
song  zuo
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 18:50:40

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

Main paper: 
 introduction: 
 Autobidding, the procedure of delegating the bidding tasks to automated agents to procure advertisement opportunities in online ad auctions, is becoming the prevalent bidding methods and contributing to more than 80% of total online advertising traffic [Dolan, 2020] . Autobidding significantly simplifies 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 is value maximization subject to a target return-on-investment (ROI) constraint, in which the autobidding agents aim to maximize their value, such as the number of clicks/conversions, subject to a 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 et al., 2021 , Balseiro et al., 2021a] .As the behavior model of automated bidders is very different from the classic (quasi-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., 2019 , Deng et al., 2021 , Balseiro et al., 2021a , Liaw et al., 2022 , Babaioff et 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 in equilibrium and the socially optimal welfare, of running the second-price auction against value maximizers is 1/2 (when the bidders do not adopt dominated strategies1 ).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-price 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-price auction in the autobidding world.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 Jin and Lu [2022] showing that the PoA of running the first-price auction is 1 -1/e 2 in a world without autobidding, i.e., all bidders are utility maximizers. The results are summarized in Table 1 and we also include the known results for second-price auctions for comparison.First-price auction Second-price auction Full autobidding 1/2 1/2 [Aggarwal et al., 2019 ] Mixed autobidding min t∈[0,1] 1+t ln t 2-t+t ln t ≈ 0.457 1/2 [Balseiro et al., 2021b] No autobidding 1 -1/e 2 ≈ 0.865 [Jin and Lu, 2022] 1 [Vickrey, 1961] Table 1 : 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-price auction, bidders are assumed to not adopt dominated strategies; otherwise the PoA can be 0.Our results demonstrate that in a full autobidding world, the PoA of running the second-price auction and the first-price 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 is 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 t∈[0,1] 1+t ln t 2-t+t ln t and it turns out that this is the right bound as 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 machine-learned 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 on the advice in the second-price auction makes the PoA approaching 1. In our setting of using machine-learned advice in 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 1 as the quality of the machine-learned advice increases.For first-price auction with utility maximizers, the price of anarchy has been extensively studied [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 et al. [2013] first showed that the price of anarchy is at least 1/2 for subadditive valuations and Syrgkanis and Tardos [2013] showed that the price of anarchy is at least 1 -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 ≈ 0.743 by Hoy et al. [2018] and Hartline et al. [2014] gave a concrete instance to establish an upper bound of ≈ 0.869. More recently, Jin and Lu [2022] show that the price of anarchy for independently distributed values is exactly 1 -1/e2 . Paes Leme et al. [2020] provide models and analyses to explain why Display Ads market shifts to use first-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 an autobidding world. Aggarwal et al. [2019] design optimal bidding strategies in truthful auctions, show the existence of equilibrium, and prove welfare price of anarchy results. Deng et al. [2021] and Balseiro et al. [2021b] 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 Balseiro et al. [ , 2022] ] give the characterization of the revenue-optimal 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. Liaw et 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 as 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. [2022] study "pacing" in first-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. Feng 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] . 
preliminaries: 
 Ad auctions. Following prior work on autobidding, we consider a 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 i has a value v i,j ≥ 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 b i,j 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-price auction, we assume ties are broken in favor of the bidder with the higher value within an auction, which is a standard assumption in the literature [Maskin and Riley, 2000 ]. 2 If multiple bidders have the same value, then ties are broken in favor of the bidder with the smallest index. 3 We let x i,j = x i,j ({b i ′ ,j } i ′ ) be the indicator variable indicating that i wins in auction j. Then, the value each bidder i receives in auction j is vali,j = val i,j ({b i ′ ,j } i ′ ) = x i,j ({b i ′ ,j } i ′ ) • v i,j, and the payment i makes in auction j isp i,j = p i,j ({b i ′ ,j } i ′ ) = x i,j ({b i ′ ,j } i ′ ) • b i,j. We remark that bidders may employ randomized bidding strategies, in which case {b i,j }, {x i,j }, {val i,j } and {p i,j } are all random variables. Throughout the paper, we omit the dependence of x i,j , val i,j and p i,j on {b i ′ ,j } i ′ whenever it is clear from the context. For brevity, we writev i = {v i,j } j , b i = {b i,j } j , etc.Utility maximizers and value maximizers. We consider two types of bidders: traditional (quasilinear) utility maximizers and (ROI-constrained) value maximizers. In the rest of the paper, we use B u to denote the set of utility maximizers and B v the set of value maximizers, where we always haveB u ∩ B v = ∅ and B u ∪ B v = [n].For each bidder i, let val i = j val i,j be the total value i receives from all auctions, and p i = j p i,j be the total payment i makes. Fixing other bidders' bidding strategies, a utility maximizer i bids in a way such that the total quasi-linear utility, i.e., val i -p i , is maximized, without additional constraints. On the other hand, a value maximizer i bids in a way such that the total value val i that i receives is maximized, subject to the ROI constraint that the ratio between the total value val i and the total payment p i is at least some predetermined threshold. Without loss of generality we assume this threshold is 14 , i.e., we require the total payment p i is at most the total value val i for each value maximizer i. Formally, fixing other bidders' bids, a value maximizer i solves the following optimization problem to determine their bids {b i,j } j : maximizeE [val i ] subject to E [val i -p i ] ≥ 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 i is optimal for that bidder's objective, given all other bidders' bidding strategies {b i ′ } i ′ ̸ =i (or b -i for brevity). In other words, each bidder's 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 i } i 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 u , B v , {v i,j }), we are interested in the instance-wise PoA defined as follows:PoA(n, m, B u , B v , {v i,j }) = inf {bi}i form an equilibrium i E[val i ] j max i v i,j .Our goal is to pin down the PoA of the first-price auction, which is the infimum of the instance-wise PoA taken over all instances of the problem. We assume j max i v i,j > 0 in order for the PoA to be well-defined.Equilibrium bidding behavior of value maximizers. In this paper, we do not put further restrictions on bidders' equilibrium bidding behavior, such as 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 value-maximizers would be to bid their values in first-price auctions since such a strategy maximizes their bids without violating the ROI constraints, leading to the trivial welfare-optimal outcome in a world with value-maximizers 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 WorldIn the literature [Aggarwal et al., 2019 , Deng et al., 2021 , Balseiro et al., 2021b] , the analyses of PoA for the second-price auction in a full autobididng world mainly leverage the fact that the second-price auction is truthful for utility maximizers, a nice property implying that value maximizers adopt uniform bidding strategy in equilibrium [Aggarwal et al., 2019] . Here, a uniform bidding strategy for a value maximizer i is a strategy in which she bids k i • v i,j with a constant bid multiplier k i 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 a value maximizer. A value maximizer i may adopt a non-uniform bidding strategy using different bid multiplier k i,j 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 autobidding world is 1/2 when restricting to equilibria of bidding in a 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 n,m,{vi,j } PoA(n, m, B u = ∅, B v = [n], {v i,j }) = 1/2.All missing proofs are deferred to Appendix B. We remark that the proof of Theorem 1 in fact establishes the following claim, which will be a building block in our analysis of PoA of the first-price auction in a mixed autobidding world with both value maximizers and utility maximizers. Lemma 1. For any n, m, B u , B v , and{v i,j }, if {b i } i form an equilibrium, then i∈Bv E[val i ] + i,j:rw(j)∈Bv E[p i,j ] ≥ j:rw(j)∈Bv max i v i,j ,where rw(j) = argmax i v i,j denotes the "rightful winner" of each auction j, with ties broken in favor of the bidder with the smallest index.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 in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on 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 a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a 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 be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
theory assumptions and proofs: 
 Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof? Answer: [Yes] Justification: In particular, we have done our best to 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 circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in 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 a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used 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. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
poa of the first-price auction in a mixed autobidding world: 
 In this section, we 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 a mixed autobidding world is given by:inf n,m,Bu,Bv,{vi,j } PoA(n, m, B u , B v , {v i,j }) = min t∈[0,1] 1 + t ln t 2 -t + t ln t ≈ 0.457.Roadmap. In 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 1, 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 b ′ i,j = v i,j . This is because aiming to maximize utility, i may bid in a way such that both the value i receives and the payment i makes are smaller, but their difference (which is the utility i gets) is larger. One simple fix is to consider instead the following proxy strategy: b ′′ i,j = v i,j /2. Adapting the proof of Theorem 1, it is not hard to show this alternative proxy strategy gives a PoA lower bound of 1/4. However, it is unlikely that such a fix would yield the tight ratio of about 0.457.In order to overcome this obstacle, we present a novel local analysis (Lemma 3) for the first-price auction that handles auctions where the rightful winner is 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 a 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 tradeoff 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 1) 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 is a value maximizer, and (D) the total payment made in auctions where the rightful winner is a utility maximizer, by bidders who are not the rightful winner.One can show that the welfare in equilibrium is lower bounded by a very specific combination of these 4 quantities (Lemma 4). Moreover, Lemma 1 provides a tradeoff between (A) and (C), and the local analysis (Lemma 3) provides a tradeoff between (B) and (D). Therefore, one can lower bound the PoA by solving an optimization problem involving a few number of parameters to get the worst-case tradeoffs. We show that this optimization gives the right ratio of about 0.457 (Lemma 5). 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.In this subsection, we propose a 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 a 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 a value maximizer. For the remainder of this subsection, we fix n, m, {v i,j }, and an equilibrium profile {b i } i , and consider any fixed bidder i and auction j where i is the rightful winner. For brevity, we also let v = v i,j .Value-payment frontiers. We first try to understand the maximum expected value i can get in auction j when paying a particular amount in expectation. Let F be the CDF of the highest other bid, i.e., for any x ≥ 0,F (x) = Pr b-i max i ′ ̸ =i b i ′ ,j ≤ x .Note that in the first-price auction j, if bidder i bids t, the bidder i pays t • F (t) and earns value v • F (t). For any x ≥ 0, consider a functionG : R + → [0, v] such that G(x) = sup t≥0: t•F (t)≤x v • F (t).In other words, G maps a desired expected payment x to the maximum (or strictly speaking, supremum) value i can get by bidding deterministically, when paying at most the desired payment x in expectation. By bidding randomly, i can further achieve any value-payment pair that is a 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 a deterministic best response (since all bids with a 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-payment frontier H, one can further observe that when best responding, i's expected utility E[val i,j -p i,j ] depends only on H. In fact, intuitively, since H is concave, i's expected value and payment in 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 is a utility maximizer, i's best response in j, b i,j , has the following property. Lemma 2. For any b ≥ 0 in the support of b i,j , we have for anyw ≥ b • F (b), H(w) -H(b • F (b)) ≤ w -b • F (b).We remark that the same property also holds when i is a value maximizer, with minor modifications in the proof.A 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 2, the curve H must be relatively flat to the right of (p i,j , H(p i,j )) (i.e., with slope at most 1), which means the CDF function F of the highest other bid must also be with a relatively small slope. On the other hand, the payment made by other bidders can be written asb i,j • (1 -F (b i,j )) + ∞ bi,j (1 -F (t)) dt.This means if F (b i,j ), the probability that i wins when bidding b i,j , is small, then since F is with a small slope to the right of b i,j , the payment must be relatively large. The following claim formally captures this tradeoff.Lemma 3. There exists some x ∈ [0, 1] such thatE[val i,j ] = x • v and i ′ ̸ =i E[p i ′ ,j ] ≥ (1 -x + x ln x) • v.We remark that Lemma 3 alone already implies a lower bound of about 0.317 on the PoA: summing the bound in Lemma 3 over i and j where rw(j) = i and exploiting the convexity of the mapping z → 1 -z + z ln z, one can show there is somex ∈ [0, 1] such that i E[val i ] ≥ x • j max i v i,j and i E[p i ] ≥ (1 -x + x ln x) • j max i v i,j . Since i E[val i ] ≥ i E[p i ],the worst case scenario is when x = 1 -x + x ln x, which gives x ≈ 0.317, a lower bound on the PoA.In this subsection, we combine Lemma 1 and Lemma 3 to obtain an improved (and in fact, tight) lower bound on the PoA of the first-price auction in the mixed autobidding world. Fixing n, m, B u , B v and {v i,j }, 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 a value maximizer; and (D): the total payment made in auctions where the rightful winner is a utility maximizer, by bidders who are not the rightful winner. Formally,A = i∈Bv E[val i ], B = i∈Bu,j:rw(j)=i E[val i,j ] C = i,j:rw(j)∈Bv E[p i,j ], D = i,j:rw(j)∈Bu and rw(j)̸ =i E[p i,j ].We first show that the welfare can be bounded by a combination of the above quantities. Lemma 4. For any bidding strategies {b i } i that form an equilibrium, we always havei E[val i ] ≥ max{A, C + D} + B.We are now ready to prove our main PoA lower bound. Lemma 5. In a mixed autobidding world with both utility maximizers and value maximizers, the PoA of the first-price auction has the following lower bound:inf n,m,Bu,Bv,{vi,j } PoA(n, m, B u , B v , {v i,j }) ≥ min t∈[0,1] 1 + t ln t 2 -t + t ln t ≈ 0.457.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 et al., 2014] ), and it is conceivable that one might be able to fit part of our analysis in the smoothness framework. However, it 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 tight bounds, presumably one would need to carry out essentially the same argument as in our analysis.To conclude this section, we present a problem instance in which our PoA lower bound can be actually achieved, even with n = 2 bidders and m = 2 auctions. Lemma 6. When n = m = 2, there exists B u , B v and {v i,j } such thatPoA(n, m, B u , B v , {v i,j }) ≤ min t∈[0,1] 1 + t ln t 2 -t + t ln t ≈ 0.457.Theorem 2 is a direct corollary of Lemma 5 and Lemma 6. 
improved efficiency with ml advice: 
 In this section, we turn to a more practically-motivated setting, where the seller can rely on machinelearned 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. [2021b] , we consider the setting in which for each auction j, the seller can access a signal s j , which approximates the highest value max i v i,j in this auction. Formally, we assume there is a constant γ ∈ [0, 1] such thats j ∈ [γ • max i v i,j , max i v i,j ]for each auction j.5 As Balseiro et 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 (high-probability) bound on how much the signal might overestimate the maximum value, then one can scale everything down accordingly and retain the PoA bound in Theorem 3 (with high probability).First-price auction with machine-learned reserves. The way we exploit machine-learned 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 r j = s j , such that a bidder i can win only if i's bid b i,j ≥ r j . In particular, if max i b i,j < r j , then no one wins in auction j. This is different from the first-price auction without reserves, where there is always exactly 1 winner.We overload the notations and let x i,j = x i,j (r j , {b i ′ ,j } i ′ ) be the indicator variable that i wins in auction j, and define {val i,j } and {p i,j } in a similar way such that all these variables depend on both the reserves {r j } and the bidding profile {b i ′ ,j } i ′ . For any n, m, B u , B v , and {v i,j }, we consider the following parametrized instance-wise PoA when eachr j = s j ∈ [γ • max i v i,j , max i v i,j ]: PoA γ (n, m, B u , B v , {v i,j }) = inf {bi,j } form an equilibrium ∀j,rj ∈[γ•maxi vi,j ,maxi vi,j ] i E[val i ] j max i v i,j.Our main result in the section is captured by the following theorem. Theorem 3. For any n, m, B u , B v , {v i,j } and γ ∈ [0, 1],PoA γ (n, m, B u , B v , {v i,j }) ≥ min t∈[0,1] 1 + t ln t -γt(1 + ln t) 2 -t -γ + (1 -γ)t ln t .One way to interpret the lower bound is it provides a smooth transition between the case without machine-learned advice (or with totally unreliable advice, i.e., γ = 0), and the case where the advice is perfectly accurate (i.e., γ = 1) and the seller knows precisely the value of the rightful winner in each auction. In the former scenario corresponding to γ = 0, we recover the tight PoA bound stated in Theorem 2. In the latter scenario corresponding to γ = 1, as one would expect, the theorem gives a lower bound of 1, which means the auctions are perfectly efficient. More generally, for γ between 0 and 1, the lower bound in Theorem 3 increases monotonically as γ increases, since the fraction within the min increases in γ for any fixed t ∈ [0, 1]:1 + t ln t -γt(1 + ln t) 2 -t -γ + (1 -γ)t ln t = (1 -t) 2 (2 -t + t ln t)(1 + t ln t) -(1 + t ln t) 2 γ + t + t ln t 1 + t ln t ,where 1 + t ln t ∈ (0, 1] and 2 -t+ t ln t ≥ 1 ≥ γ ≥ γ • (1 + t ln t).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 at which the efficiency improves, we plot our lower bound against the accuracy γ in Figure 1 . As the plot shows, our lower bound improves approximately linearly as the accuracy γ increases from 0 to 1. To prove Theorem 3, the plan is to apply Lemma 4, which provides a 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-learned reserves. In the rest of the section, we fix n, m, B u , B v , and {v i,j }. With machine-learned reserves, the tradeoff given by Lemma 1 improves to the following (note the factor of (1 -γ) on the left hand side). Lemma 7. In auctions with machine-learned reserves of accuracy γ ∈ [0, 1], for any {b i } i that form an equilibrium,(1 -γ) • i∈Bv E[val i ] + i,j:rw(j)∈Bv E[p i,j ] ≥ j:rw(j)∈Bv max i v i,j .We note that the above lemma also implies a lower bound of 1/(2 -γ) 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 γ → 0 (i.e., reserves are extremely unreliable), the bound degrades to 1/2; when γ → 1 (i.e., reserves are extremely accurate), the bound approaches 1, which means the auctions are efficient.Corollary 1. For any n, m, {v i,j } and γ ∈[0, 1], PoA γ (n, m, B u = ∅, B v = [n], {v i,j }) ≥ 1/(2 -γ).For utility maximizers, we adapt the local analysis, and obtain the following improved tradeoff between value and payment. Lemma 8. In auctions with machine-learned reserves of accuracy γ ∈ [0, 1], for any {b i } i that form an equilibrium, and any bidder i and auction j where rw(j) = i, there exists x ∈ [0, 1] such thatE[val i,j ] = x • v i,j and i ′ ̸ =i E[p i ′ ,j ] ≥ (1 -x + (1 -γ)x ln x) • v i,j .We can now prove Theorem 3 by plugging Lemma 7 and Lemma 8 into Lemma 4.Following prior work on autobidding [Aggarwal et al., 2019 , Deng et al., 2021 , Balseiro et al., 2021a , 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 τ i , and each bidder i's value in each auction j is v i,j , the liquid welfare under allocation {x i,j } is defined as follows:i,jx i,j • v i,j /τ i .In particular, we let τ i = 1 for each utility maximizer i, which simply means i is individually rational.One can check the above definition is consistent with the classical social welfare when all bidders are 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.e.,j max i v i,j /τ i .This can be achieved by allocating to the bidder i with the highest target-adjusted value v i,j /τ i in each auction j. Observe that the quantity that actually matters in the (first-best) liquid welfare is the target-adjusted value v i,j /τ i . Therefore, without loss of generality, we can replace each bidder i's value in each auction j with the target-adjusted value v i,j /τ i , 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 a high target ROI ratio and low values behaves in the same way as a bidder with a 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.Proof of Theorem 1. First we provide a simple hard instance, which implies an 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 v 1,1 = 1, v 2,2 = 1 -ε, and v 1,2 = v 2,1 = 0, where ε > 0 is a small quantity to be fixed later. Consider the following deterministic bidding strategies: b 1,1 = b 2,1 = 0 (so bidder 1 wins in auction 1 by tiebreaking and pays 0), b 1,2 = 1, and b 2,2 = 0 (so bidder 1 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 1 does not want to deviate from b 1 , since bidder 1 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 b 1,2 = 1, bidder 2 would have to bid at least 1 in order to win, which means p 2,2 ≥ 1 whenever x 2,2 = 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 v 1,1 + v 2,2 = 2 -ε, and the welfare resulting from the above equilibrium is only v 1,1 = 1, which means the PoA is at most 1/(2 -ε).Letting ε → 0 yields an upper bound of 1/2. Now we focus on lower bounding the instance-wise PoA fixing any n, m, and {v i,j }. Consider any equilibrium, induced by bidding strategies {b i } i . Our task is to show that2 i E[val i ] ≥ j max i v i,j ,where the expectations, as well as all expectations in the rest of the proof, are taken over {b i } i . For each auction j, let rw(j) = argmax i v i,j 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 ′ i of bidder i: b ′ i,j = v i,j in each auction j, i.e., the proxy bidding strategy b ′ i is a strategy in which bidder i bids truthfully. Then, for each auction j where i = rw(j), the probability that i wins in auction j under the proxy bidding strategy b ′ i , fixing all other bidders' strategies b -i , isPr b-i [x i,j (b ′ i,j , b -i,j ) = 1] = Pr b-i max i ′ ̸ =i b i ′ ,j ≤ b ′ i,j = Pr b-i max i ′ ̸ =i b i ′ ,j ≤ v i,j .Also, observe that i's ROI constraint is satisfied under the proxy bidding strategy b ′ i , since under the proxy bidding strategy b ′ i , the following holds deterministically:val i (b ′ i , b -i )-p i (b ′ i , b -i ) = j x i,j (b ′ i,j , b -i,j )•(v i,j -b ′ i,j ) = j x i,j (b ′ i,j , b -i,j )•(v i,j -v i,j ) = 0.Taking the expectation over b -i , we see that i's ROI constraint is satisfied (and is in fact binding). The above observations imply the following fact: There exists a bidding strategy (i.e., b ′ i ), under which i's ROI constraint is satisfied, and the expected value i receives isE[val i (b ′ i , b -i )] ≥ j:i=rw(j) Pr b-i [x i,j (b ′ i,j , b -i,j ) = 1] • v i,j = j:i=rw(j) Pr b-i max i ′ ̸ =i b i ′ ,j ≤ v i,j • v i,j .Observe that since i is a value maximizer and b i is a best response to b -i , we must haveE[val i (b i , b -i )] ≥ E[val i (b ′ i , b -i )] ≥ j:i=rw(j) Pr b-i max i ′ ̸ =i b i ′ ,j ≤ v i,j • v i,j .On the other hand, fix a bidder i and consider the total payment collected in any auction j with rw(j) = i, under (b i , b -i ). By the properties of the first-price auction, we havei ′ E[p i ′ ,j (b i,j , b -i,j )] = E max i ′ b i ′ ,j ≥ E max i ′ ̸ =i b i ′ ,j ≥ Pr b-i max i ′ ̸ =i b i ′ ,j > v i,j • v i,j = 1 -Pr b-i max i ′ ̸ =i b i ′ ,j ≤ v i,j • v i,j .Summing over all auctions j with rw(j) = i, we havei ′ ,j:i=rw(j) E[p i ′ ,j (b i , b -i )] ≥ j:i=rw(j) 1 -Pr b-i max i ′ ̸ =i b i ′ ,j ≤ v i,j • v i,j .Combining this with the bound on the total expected value i receives, we getE[val i (b i , b -i )] + i ′ ,j:i=rw(j) E[p i ′ ,j (b i , b -i )] ≥ j:i=rw(j) v i,j .Further summing over i (and omitting dependence on(b i , b -i )), the above gives i E[val i ] + i E[p i ] ≥ j max i v i,j .Finally, observe that for any bidder i, the ROI constraint impliesE[p i ] ≤ E[val i ],and therefore we can conclude the proof with2 i E[val i ] ≥ i E[val i ] + i E[p i ] ≥ j max i v i,j .Proof of Lemma 2. Suppose towards a contradiction that there existsw > b • F (b) such that H(w) - H(b • F (b)) > w -b • F (b), or equivalently, H(w) -w > H(b • F (b)) -b • F (b). Let b ′ i,j be a possibly randomized bidding strategy that realizes the point (w, H(w)), i.e., when using b ′ i,j , i receives value H(w) and pays w in expectation in auction j. Then, the utility that i receives from j when using the new strategy b ′ i,j is H(w) -w. On the other hand, consider the deterministic bidding strategy b ′′ i,j = b. Since b is in the support of b i,j , b ′′ i,j must also be a best response. However, under b ′′ i,j , i receives utilityH(b • F (b)) -b • F (b), which is strictly worse than the utility i receives when using the alternative strategy b ′ i,j . In other words, b ′′ i,j cannot be a best response, a contradiction.Proof of Lemma 3. Let x = E[F (b i,j )]. Clearly x ∈ [0, 1] and E[val i,j ] = x • v. Our remaining task is to show i ′ ̸ =i E[p i ′ ,j ] ≥ (1 -x + x ln x) • v.Recall thati ′ ̸ =i E[p i ′ ,j ] = E bi,j b i,j • (1 -F (b i,j )) + ∞ bi,j (1 -F (t)) dt .As a result, in order to lower bound the payment, we want to pointwise upper bound F . Fix any b in the support of the best-response strategy b i,j , we must haveH(b • F (b)) = G(b • F (b)) = v • F (b). By Lemma 2, for any w ≥ b • F (b), we have H(w) -H(b • F (b)) ≤ w -b • F (b), which implies that H(w) ≤ H(b • F (b)) + w -b • F (b).Also, since H is the concave envelope of G, the same upper bound applies to G, and we haveG(w) ≤ H(w) ≤ H(b • F (b)) + w -b • F (b) = v • F (b) + w -b • F (b).Due to the monotonicity of F (x), we have that for any t ≥ b, we have t• F (t) ≥ b • F (b). Therefore,given the relation between G and F , the above implies that for any t ∈ [b, v) (note that this range might be empty),v • F (t) ≤ G(t • F (t)) ≤ v • F (b) + t • F (t) -b • F (b) =⇒ F (t) ≤ (v -b) • F (b) v -t .We next bound the payment conditioned on b i,j = b. We consider two possible cases: b ≥ v and b < v. If b ≥ v, we simply havei ′ ̸ =i E[p i ′ ,j | b i,j = b] = b • (1 -F (b)) + ∞ b (1 -F (t)) dt ≥ b • (1 -F (b)) ≥ (1 -F (b)) • v ≥ (1 -F (b) + F (b) ln F (b)) • v.In particular, the last inequality is becauseF (b) ln F (b) ≤ 0 when F (b) ∈ [0, 1]. If b < v, we must have b = v -(v -b) • 1 ≤ v -(v -b) • F (b), and as a result,i ′ ̸ =i E[p i ′ ,j | b i,j = b] = b • (1 -F (b)) + ∞ b (1 -F (t)) dt ≥ b • (1 -F (b)) + v-(v-b)•F (b) b 1 - (v -b) • F (b) v -t dt = (1 -F (b)) • v + (v -b) • F (b) • ln(v -t) v-(v-b)•F (b) b = (1 -F (b)) • v + (v -b) • F (b) • ln F (b) ≥ (1 -F (b) + F (b) ln F (b)) • v.Combining the two cases and further taking the expectation over b i,j , we geti ′ ̸ =i E[p i ′ ,j ] ≥ E bi,j [(1 -F (b i,j ) + F (b i,j ) ln F (b i,j )) • v] ≥ (1 -x + x ln x) • v,where the last inequality is due to Jensen's inequality, the fact that z → 1 -z + z ln z is convex on [0, 1], and we chosex = E[F (b i,j )]. Proof of Lemma 4. Observe that i E[val i ] = i∈Bv E[val i ] + i∈Bu E[val i ] = max i∈Bv E[val i ], i∈Bv E[p i ] + i∈Bu E[val i ] = max i∈Bv E[val i ], i∈Bv E[p i ] + i∈Bu,j:rw(j)=i E[val i,j ] + i∈Bu,j:rw(j)̸ =i E[val i,j ] = max A, i∈Bv E[p i ] + B + i∈Bu,j:rw(j)̸ =i E[val i,j ].Note that for each i ∈ B u and j, we always have E[val i,j ] ≥ E[p i,j ] since i is best responding and the utility i receives in j is at least 0. Therefore, we can further relax the above into the following:i E[val i ] ≥ max A, i∈Bv E[p i ] + B + i∈Bu,j:rw(j)̸ =i E[p i,j ] ≥ max    A, i∈Bv E[p i ] + i∈Bu,j:rw(j)̸ =i E[p i,j ]    + B.Rearranging the sums within the max, we have that i∈BvE[p i ] + i∈Bu,j:rw(j)̸ =i E[p i,j ] = i E[p i ] - i∈Bu,j:rw(j)=i E[p i,j ] = i,j:rw(j)∈Bv E[p i,j ] + i,j:rw(j)∈Bu and rw(j)̸ =i E[p i,j ] = C + D.Substituting in the max gives the bound to be proved.Proof of Lemma 5. Fix any n, m, B u , B v , and {v i,j }. Consider any bidding strategies {b i } i that form an equilibrium. LetV 1 = j:rw(j)∈Bv max i v i,j , V 2 = j:rw(j)∈Bu max i v i,j .By Lemma 4, we havei E[val i ] j max i v i,j ≥ max{A, C + D} + B V 1 + V 2 .By Lemma 1, we haveA + C ≥ V 1 . So there must be some x ∈ [0, 1], such that A ≥ x • V 1 and C ≥ (1 -x) • V 1 .As for B and D, we apply Lemma 3. For each j where rw(j) ∈ B u , Lemma 3 states that there exists some y j ∈ [0, 1], such thatE[val rw(j),j ] = y j • max i v i,j , i̸ =rw(j) E[p i,j ] ≥ (1 -y j + y j ln y j ) • max i v i,j . Let y = B/V 2 . Since B = j:rw(j)∈Bu E[val rw(j),j ] ≤ j:rw(j)∈Bu max i v i,j = V 2 , we have y ∈ [0, 1]. In particular, y = j:rw(j)∈Bu E[val rw(j),j ] j:rw(j)∈Bu max i v i,j = j:rw(j)∈Bu y j • max i v i,j j:rw(j)∈Bu max i v i,j.Since t → 1 -t + t ln t is convex, by Jensen's inequality, we must haveD = j:rw(j)∈Bu i̸ =rw(j) E[p i,j ] ≥ j:rw(j)∈Bu (1 -y j + y j ln y j ) • max i v i,j≥ (1 -y + y ln y)j:rw(j)∈Bu max i v i,j = (1 -y + y ln y) • V 2 .Plugging in the above derived lower bounds for A, B, C, and D, we havei E[val i ] j max i v i,j ≥ max{A, C + D} + B V 1 + V 2 ≥ max{x • V 1 , (1 -x) • V 1 + (1 -y + y ln y) • V 2 } + y • V 2 V 1 + V 2 , where V 1 , V 2 ≥ 0, V 1 + V 2 > 0 and x, y ∈ [0, 1].In other words, we must havePoA(n, m, B u , B v , {v i,j }) ≥ inf V1,V2≥0,V1+V2>0,x,y∈[0,1] max{x • V 1 , (1 -x) • V 1 + (1 -y + y ln y) • V 2 } + y • V 2 V 1 + V 2 .A careful analysis (see Lemma 9 in Appendix C) of the right-hand-side shows that it equals to min y∈[0,1]1 + y ln y 2 -y + y ln y ≈ 0.457, which is achieved when x = 1 and V 1 = (1 -y + y ln y) • V 2 . This concludes the proof.Proof of Lemma 6. Let B u = {1} and B v = {2}. We choose v 1,1 = 1 and v 1,2 = v 2,1 = 0, and leave v 2,2 > 0 to be fixed later. The idea is to let bidder 2 win in auction 2 for free, and therefore bidder 2 gains enough slackness in the ROI constraint and can therefore compete with bidder 1 in auction 1. To be specific, in order for bidder 2 to win for free in auction 2, we choose b 1,2 = b 2,2 = 0 so that bidder 2 wins by tiebreaking and pays 0. We want bidder 1's value-payment frontier in auction 1 to have the following shape: the curve starts at (0, t) for some t ∈ [0, 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 v 1,1 = 1. This ensures that bidder 1 bidding b 1,1 = 0 deterministically is a best response. Translating this to bidder 2's bidding strategy, we would like that for any b ≥ 0,Pr[b 2,1 ≤ b] = min 1, t 1 -b .One can show that the expected payment that bidder 2 makes in auction 1 is 1 -t + t ln t. In order to satisfy bidder 2's ROI constraint, we choose v 2,2 = 1 -t + t ln t. One may check that the above bidding strategies in fact form an equilibrium. Note thatE[val 1 ] = Pr[b 2,1 = 0] • v 1,1 = t, and E[val 2 ] = v 2,2 = 1 -t + t ln t.Considering the ratio between the optimal welfare and the welfare resulting from the above equilibrium, we have Proof of Lemma 7. The proof is similar to that of Lemma 1 at a high level, except that the expected payment is higher, because in each auction j, the rightful winner rw(j) must bid at least r j (which is a constant fraction of v rw(j),j ) unless the highest competing bid is at least v rw(j),j with probability 1.PoA(n, m, B u , B v , {v i,j }) ≤ E[val 1 + val 2 ] v 1,1 + v 2,2 = 1 + tAgain fix any equilibrium strategies {b i }. By the same argument as in the proof of Lemma 1, for any value maximizer i ∈ B v , we haveE[val i ] ≥ j:i=rw(j) v i,j • Pr max i ′ ̸ =i b i ′ ,j ≤ v i,j .Also, observe that for any value maximizer i ∈ B v and auction j where rw(j) = i, at least one of the following properties must hold: Either (1) b i,j ≥ r i,j deterministically, or ( 2)Pr[max i ′ ̸ =i b i ′ ,j ≥ v i,j ] = 1. This is because if neither of the two holds, then i for any b < r j in the support of b i,j , i would be better off by moving probability mass from b to v i,j , which preserves feasibility and strictly increases the value i receives from j. For each j where (1) holds, we havei ′ E[p i ′ ,j ] ≥ v i,j • 1 -Pr max i ′ ̸ =i b i ′ ,j ≤ v i,j + r j • Pr max i ′ ̸ =i b i ′ ,j ≤ v i,j ≥ v i,j • 1 -Pr max i ′ ̸ =i b i ′ ,j ≤ v i,j + γ • v i,j • Pr max i ′ ̸ =i b i ′ ,j ≤ v i,j = v i,j -(1 -γ) • v i,j • Pr max i ′ ̸ =i b i ′ ,j ≤ v i,j .For each j where (2) holds, we immediately know thati ′ E[p i ′ ,j ] ≥ v i,j • Pr max i ′ ̸ =i b i ′ ,j ≥ v i,j = v i,j ≥ v i,j -(1 -γ) • v i,j • Pr max i ′ ̸ =i b i ′ ,j ≤ v i,j .So combining the two cases and summing over j where i = rw(j),i ′ ,j:rw(j)=iE[p i ′ ,j ] ≥ j:rw(j)=i v i,j -(1 -γ) • v i,j • Pr max i ′ ̸ =i b i ′ ,j ≤ v i,j .Combining this with the lower bound on E[val i ] above, we get(1 -γ) • E[val i ] + i ′ ,j:rw(j)=i E[p i ′ ,j ] ≥ j:rw(j)=i v i,j .Further summing over i ∈ B v gives the inequality to be proved.Proof of Lemma 8. The first part of the reasoning is almost identical to the proof of Lemma 3: For any b in the support of b i,j , Lemma 2 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.e., for any t ≥ 0,F (t) = Pr max i ′ ̸ =i b i ′ ,j ≤ t .When b ≥ v, we havei ′ ̸ =i E[p i ′ ,j | b i,j = b] ≥ (1 -F (b)) • v ≥ (1 -F (b) + (1 -γ) • F (b) ln F (b)) • v i,j .When b < v, again we must have one of the following two: Either (1) b ≥ r j ≥ γ • v i,j , or (2) F (v i,j ) = 1. When (1) holds, we havei ′ ̸ =i E[p i ′ ,j | b i,j = b] ≥ (1-F (b))•v i,j +F (b) ln F (b)•(v i,j -b) ≥ (1-F (b)+(1-γ)F (b) ln F (b))•v i,j .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 as long as it is clear that these goals are not attained by the paper. 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: No data or models released. Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a 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 is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort. 12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected? 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 or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 13. New Assets Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?When discussing the 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-price auction can be 0.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-breaking rules can be different for value maximizers. We choose the one without the additional definition of second-round second-price auction for simplicity.Our positive results are oblivious to tiebreaking, i.e., they remain valid no matter what tiebreaking rule is used.See Appendix A for why this is without loss of generality, as well as further justifications for considering the liquid welfare in the autobidding world.As we focus on the single-slot environment in this paper, for ease of presentation, our assumption here is weaker thanBalseiro et al. [2021b] as they assume for each bidder i and each auction j, there is a signal si,j ∈ [γ • vi,j, vi,j], and setting sj := maxi si,j gives the signals which can be used in our setting. Our result can be extended to the multi-slot environment by adopting the assumption fromBalseiro et al. [2021b]. 
 
 Appendix:  


Decision: 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.

Reviews: review: paper_summary: paper_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? 

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. 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.
strength_weakness: strength_weakness: 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.)
questions: 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: limitations: N/A, primarily a theory paper
paper_summary: paper_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.

The 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$.
strength_weakness: strength_weakness: I did not find any major weaknesses. 

The 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".
questions: questions: I do not have any questions.
limitations: 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.
paper_summary: paper_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.
strength_weakness: strength_weakness: - The introduction of the paper missed a lot of related work on the related work for auto-bidding, i.e., [1], [2], [3].
- 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. 
- **The settings in Table 1 are not comparable**: 

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

-- For the no auto-bidding in the first price auction ( i.e., [Balseiro et al., 2021b]), they consider the **single item** multi-bidder setting.

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

- [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:  
-- [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 } \}$.
-- [Deng et al] use above definition as well.
-- [Balseiro et al., 2021a] doesn't use liquid welfare but first best revenue.
-- [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$. 
-- As a result, the WLOG actually only holds for the liquid welfare specifically defined in this setting.
- For the PoA definition, the paper never defined the equilibrium considered in this paper, Bayesian Nash, or Competitive, or Coarse Correlated.
- 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. 
- There is no conclusion of this paper. 

Minor Comment:
- line 317, $\{ v_{i,j}\}$ should be $\{ v_{i,j}\}_{i \in [n], j \in [m] }$.


 






[1]: Gaitonde, J., Li, Y., Light, B., Lucier, B., & Slivkins, A. (2022). Budget pacing in repeated auctions: Regret and efficiency without convergence. ITCS 2023. 

[2]: CONITZER, Vincent, et al. Pacing equilibrium in first price auction markets. Management Science, 2022, 68.12: 8515-8535.

[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.
questions: questions: Please see the weakness section.
limitations: limitations: The paper doesn't explicitly state the limitations.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
questions: questions: Please see the weaknesses above. Also, what does $\mathsf{rw}(j)$ mean at the end of Page 4?
limitations: limitations: The authors have addressed the limitations of their work.

Comments: title: Maintain my current score
Thank you for your response
comment: I’m a bit surprised by the number of positive reviews this paper has received, especially considering the following factors: 

- **This paper did not use the full 9 pages.** The paper could have used the remaining 1/2 page space to add the **missing conclusion**. 


- **First price pacing equilibrium has more positive structural properties than the equilibrium studied in this paper**, To further elaborate, budget pacing already guarantees there exists a pacing equilibrium and such equilibrium can be computed or even by learning algorithms efficiently. Especially considering that this paper studies the autobidders, we need to examine whether this equilibrium can be efficiently achieved, i.e., whether an equilibrium exists that can be found efficiently, and whether there is a learning dynamic such that when all bidders use it, an equilibrium can be reached. **However, this paper lacks these important analyses of the equilibrium.**


- **the gaps in the literature it cites**. The paper cites papers w.r.t pacing equilibrium only from Google but **misses a lot of important work from both academia and other companies**, i.e.,  [1], [2], [3], [5], [6]. **The missed citations and the paper writing give the impression that the paper’s contribution is more significant than it is**. This should be considered when assessing the overall impact of the work.


Here is my response to the author's rebuttal below. 

- **Submodular / unit-demand bidders in autobidding**. [3] already studies the first price pacing for general utility, so it is possible to consider the utility model beyond additive. 


- **Unconventional" liquid welfare definition.** Liquid welfare is initially (and by convention) defined when the bidder has a **budget constraint,** so the definition of liquid welfare has a max over total value a bidder could have and his own budget, please see [4] as the reference. This paper does not include a budget, which is why the reviewer still believes the liquid welfare discussed is different from the commonly used version.


- **PoA definition**. There is no formal definition of the equilibrium you've considered in this paper. This is a presentation issue.


- **Price in Section 5 depending on value:**: "this is the common assumption in the literature of algorithms / mechanisms with predictions." **Please support this argument with references**. From the reviewer's perspective, however, this reserve method cannot be applied iteratively to obtain the most efficient equilibrium due to strategic issues, see [7]. In this light, **the reserve method would have an insignificant improvement over no-reserve in practice**. 


[1] Conitzer, V., Kroer, C., Panigrahi, D., Schrijvers, O., Stier-Moses, N. E., Sodomka, E., & Wilkens, C. A. (2022). Pacing equilibrium in first price auction markets. Management Science, 68(12), 8515-8535.

[2] Gao, Y., & Kroer, C. (2023). Infinite-dimensional fisher markets and tractable fair division. Operations Research, 71(2), 688-707.

[3] Feng, Y., Lucier, B., & Slivkins, A. (2024, June). Strategic Budget Selection in a Competitive Autobidding World. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing (pp. 213-224).

[4] Dobzinski, S., & Leme, R. P. (2014, July). Efficiency guarantees in auctions with budgets. In International Colloquium on Automata, Languages, and Programming (pp. 392-404). Berlin, Heidelberg: Springer Berlin Heidelberg.

[5] Lucier, B., Pattathil, S., Slivkins, A., & Zhang, M. (2024, June). Autobidders with budget and roi constraints: Efficiency, regret, and pacing dynamics. In The Thirty Seventh Annual Conference on Learning Theory (pp. 3642-3643). PMLR.

[6] Golrezaei, N., Jaillet, P., Liang, J. C. N., & Mirrokni, V. (2023, April). Pricing against a budget and roi constrained buyer. In International Conference on Artificial Intelligence and Statistics (pp. 9282-9307). PMLR.

[7] Amin, K., Rostamizadeh, A., & Syed, U. (2013). Learning prices for repeated auctions with strategic buyers. Advances in neural information processing systems, 26.
Thanks for the response. I'm happy to keep my score.
Thanks for your response. Appreciate that!
Dear authors, 

Thank you for your response. I'm happy to keep my score and advocate for acceptance of your paper. (I'll increase my confidence score to 3). 

Best wishes!