Efficiency of the First-Price Auction in the Autobidding World

Thank you for your insightful and encouraging comments.

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.

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.

Thank you for your detailed comments.

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.

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.

Comparison in table 1: There seem to be a few inaccuracies in the reviewer's comment. We provide an itemized response below.

• [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.
• [Balseiro et al., 2021b]: the paper in fact studies the multi-bidder multi-item setting.
• 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.

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

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.

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.

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.

Thank you for your insightful and encouraging comments.

Paragraph on page 3: thanks a lot for pointing this out. You are absolutely right and we will fix the paragraph.

Thank you for your insightful and encouraging comments.

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.