Efficiency of the First-Price Auction in the Autobidding World

We study the price of anarchy of the first-price auction 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 the first-price auction 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 the first-price auction with traditional bidders only 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$.

Paper

References (31)

Scroll for more · 19 remaining

Similar papers

Peer review

Reviewer HcJX6/10 · confidence 4/52024-07-09

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.

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.

Questions

Please see the weaknesses above. Also, what does $\mathsf{rw}(j)$ mean at the end of Page 4?

Rating

6

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

The authors have addressed the limitations of their work.

Reviewer wwix3/10 · confidence 4/52024-07-10

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.

Strengths

- This paper studies an important and timely topic of auto bidding, i.e., simultaneous first price. - 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]. - 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

Please see the weakness section.

Rating

3

Confidence

4

Soundness

2

Presentation

2

Contribution

1

Limitations

The paper doesn't explicitly state the limitations.

Reviewer wwix2024-08-14

Maintain my current score

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.

Reviewer fGt98/10 · confidence 3/52024-07-11

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

Strengths

- The paper is very well-written and self-contained. - The addressed setting seems to be a very natural one to consider as also motivated in the paper. - The results are strong and complete the picture of price of anarchy in the first-price auctions. - 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. 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

I do not have any questions.

Rating

8

Confidence

3

Soundness

3

Presentation

4

Contribution

4

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.

Reviewer 9Zo16/10 · confidence 3/52024-07-30

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.

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

Questions

Questions: I'm curious about the comparison with the paper, "Efficiency of Non-Truthful Auctions in Auto-bidding with Budget Constraints" by Liaw,

Rating

6

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

N/A, primarily a theory paper

Reviewer fGt92024-08-08

Thanks for the response. I'm happy to keep my score.

Program Chairsdecision2024-09-25

Decision

Accept (poster)

© 2026 NYSGPT2525 LLC