research-article

Open access

Autobidding Auctions in the Presence of User Costs

Authors:

Vahab Mirrokni,

Song ZuoAuthors Info & Claims

WWW '23: Proceedings of the ACM Web Conference 2023

Pages 3428 - 3435

https://doi.org/10.1145/3543507.3583234

Published: 30 April 2023 Publication History

All formats PDF

Abstract

We study autobidding ad auctions with user costs, where each bidder is value-maximizing subject to a return-over-investment (ROI) constraint, and the seller aims to maximize the social welfare taking into consideration the user’s cost of viewing an ad. We show that in the worst case, the approximation ratio of social welfare by running the vanilla VCG auctions with user costs could as bad as 0. To improve the performance of VCG, We propose a new variant of VCG based on properly chosen cost multipliers, and prove that there exist auction-dependent and bidder-dependent cost multipliers that guarantee approximation ratios of 1/2 and 1/4 respectively in terms of the social welfare.

References

[1]

Zoë Abrams and Michael Schwarz. 2007. Ad Auction Design and User Experience. In Proceedings of the 3rd International Conference on Internet and Network Economics (San Diego, CA, USA) (WINE’07). Springer-Verlag, Berlin, Heidelberg, 529–534.

Digital Library

[2]

Gagan Aggarwal, Ashwinkumar Badanidiyuru, and Aranyak Mehta. 2019. Autobidding with Constraints. In International Conference on Web and Internet Economics. Springer, 17–30.

[3]

Gagan Aggarwal, Ashish Goel, and Rajeev Motwani. 2006. Truthful auctions for pricing search keywords. In Proceedings of the 7th ACM Conference on Electronic Commerce. 1–7.

Digital Library

[4]

Moshe Babaioff, Richard Cole, Jason Hartline, Nicole Immorlica, and Brendan Lucier. 2021. Non-quasi-linear Agents in Quasi-linear Mechanisms. In Proceedings of 12th Innovations in Theoretical Computer Science.

[5]

Santiago Balseiro, Yuan Deng, Jieming Mao, Vahab Mirrokni, and Song Zuo. 2021. The Landscape of Auto-Bidding Auctions: Value versus Utility Maximization. In Proceedings of the 22nd ACM Conference on Economics and Computation.

Digital Library

[6]

Santiago Balseiro, Yuan Deng, Jieming Mao, Vahab Mirrokni, and Song Zuo. 2022. Optimal Mechanisms for Value Maximizers with Budget Constraints via Target Clipping. In Proceedings of the 23rd ACM Conference on Economics and Computation. https://papers.ssrn.com/sol3/papers.cfm¿abstract_id=4081457

Digital Library

[7]

Santiago R. Balseiro, Yuan Deng, Jieming Mao, Vahab S. Mirrokni, and Song Zuo. 2021. Robust Auction Design in the Auto-bidding World. In Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021. 17777–17788.

[8]

Santiago R Balseiro, Vahab Mirrokni, Renato Paes Leme, and Song Zuo. 2022. Dynamic double auctions: Toward first best. Operations Research 70, 4 (2022), 2299–2317.

Digital Library

[9]

MohammadHossein Bateni, Jon Feldman, Vahab Mirrokni, and Sam Chiu-wai Wong. 2014. Multiplicative bidding in online advertising. In Proceedings of the fifteenth ACM conference on Economics and computation. 715–732.

Digital Library

[10]

Jan Panero Benway and David M. Lane. 1998. Banner Blindness: Web Searchers Often Miss "Obvious" Links.

[11]

Edward H Clarke. 1971. Multipart pricing of public goods. Public choice 11, 1 (1971), 17–33.

[12]

Peter Cramton, Yoav Shoham, and Richard Steinberg. 2006. Combinatorial Auctions. MIT Press.

[13]

Yuan Deng, Jieming Mao, Vahab Mirrokni, Hanrui Zhang, and Song Zuo. 2022. Efficiency of the First-Price Auction in the Autobidding World. arXiv preprint arXiv:2208.10650 (2022).

[14]

Yuan Deng, Jieming Mao, Vahab Mirrokni, and Song Zuo. 2021. Towards Efficient Auctions in an Auto-bidding World. In Proceedings of The Web Conference 2021.

Digital Library

[15]

Xavier Drèze and François-Xavier Hussherr. 2003. Internet advertising: Is anybody watching¿Journal of Interactive Marketing 17, 4 (2003), 8–23. https://doi.org/10.1002/dir.10063 arXiv:https://doi.org/10.1002/dir.10063

[16]

Benjamin Edelman, Michael Ostrovsky, and Michael Schwarz. 2007. Internet advertising and the generalized second-price auction: Selling billions of dollars worth of keywords. American Economic Review 97, 1 (2007), 242–259.

[17]

Salman Fadaei and Martin Bichler. 2016. Truthfulness and approximation with value-maximizing bidders. In International Symposium on Algorithmic Game Theory. Springer, 235–246.

[18]

Jon Feldman, Shanmugavelayutham Muthukrishnan, Martin Pal, and Cliff Stein. 2007. Budget optimization in search-based advertising auctions. In Proceedings of the 8th ACM conference on Electronic commerce. 40–49.

Digital Library

[19]

Gagan Goel, Vahab Mirrokni, and Renato Paes Leme. 2019. Pareto efficient auctions with interest rates. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 33. 1989–1995.

Digital Library

[20]

Gagan Goel, Vahab Mirrokni, and Renato Paes Leme. 2014. Clinching auctions beyond hard budget constraints. In Proceedings of the fifteenth ACM conference on Economics and computation. 167–184.

Digital Library

[21]

Negin Golrezaei, Ilan Lobel, and Renato Paes Leme. 2021. Auction design for ROI-constrained buyers. Proceedings of The Web Conference 2021 (2021).

Digital Library

[22]

Theodore Groves. 1973. Incentives in teams. Econometrica: Journal of the Econometric Society (1973), 617–631.

[23]

Chang hoan Cho and Hongsik John Cheon. 2004. Why do people avoid advertising on the Internet. Journal of Advertising (2004), 89–97.

[24]

Jun Li, De Liu, and Shulin Liu. 2013. Optimal Keyword Auctions for Optimal User Experiences. Decis. Support Syst. 56, C (dec 2013), 450–461.

[25]

Christopher Liaw, Aranyak Mehta, and Andres Perlroth. 2022. Efficiency of non-truthful auctions under auto-bidding. https://doi.org/10.48550/ARXIV.2207.03630

[26]

Aranyak Sitanshu Mehta. 2022. Auction design in an auto-bidding setting: Randomization improves efficiency beyond VCG. In Proceedings of the ACM Web Conference 2022. 173–181.

Digital Library

[27]

Vahab Mirrokni, Renato Paes Leme, Rita Ren, and Song Zuo. 2018. Dynamic mechanism design in the field. In Proceedings of the 2018 World Wide Web Conference. 1359–1368.

Digital Library

[28]

Vahab Mirrokni, Renato Paes Leme, Pingzhong Tang, and Song Zuo. 2020. Non-Clairvoyant Dynamic Mechanism Design. Econometrica 88, 5 (2020), 1939–1963.

[29]

Evelyn Mitchell. 2022. Programmatic Advertising Explainer. https://www.insiderintelligence.com/content/programmatic-advertiser-explainer. Accessed: Oct 1, 2022.

[30]

Roger B Myerson. 1981. Optimal auction design. Mathematics of Operations Research 6, 1 (1981), 58–73.

Digital Library

[31]

Hal R Varian. 2007. Position auctions. International Journal of Industrial Organization 25, 6 (2007), 1163–1178.

[32]

William Vickrey. 1961. Counterspeculation, auctions, and competitive sealed tenders. The Journal of finance 16, 1 (1961), 8–37.

[33]

Christopher A Wilkens, Ruggiero Cavallo, and Rad Niazadeh. 2017. GSP: the cinderella of mechanism design. In Proceedings of the 26th International Conference on World Wide Web. 25–32.

Digital Library

[34]

Christopher A Wilkens, Ruggiero Cavallo, Rad Niazadeh, and Samuel Taggart. 2016. Mechanism design for value maximizers. arXiv preprint arXiv:1607.04362 (2016).

Cited By

Deng YMao JMirrokni VTeng YZuo SChua TNgo CKa-Wei Lee RKumar RLauw H(2024)Non-uniform Bid-scaling and Equilibria for Different Auctions: An Empirical StudyProceedings of the ACM Web Conference 202410.1145/3589334.3645659(256-266)Online publication date: 13-May-2024
https://dl.acm.org/doi/10.1145/3589334.3645659
Liaw CMehta AZhu WChua TNgo CKa-Wei Lee RKumar RLauw H(2024)Efficiency of Non-Truthful Auctions in Auto-bidding with Budget ConstraintsProceedings of the ACM Web Conference 202410.1145/3589334.3645636(223-234)Online publication date: 13-May-2024
https://dl.acm.org/doi/10.1145/3589334.3645636
Deng YMahdian MMao JMirrokni VZhang HZuo SChua TNgo CKa-Wei Lee RKumar RLauw H(2024)Efficiency of the Generalized Second-Price Auction for Value MaximizersProceedings of the ACM Web Conference 202410.1145/3589334.3645360(46-56)Online publication date: 13-May-2024
https://dl.acm.org/doi/10.1145/3589334.3645360
Show More Cited By

Index Terms

Autobidding Auctions in the Presence of User Costs
1. Theory of computation
  1. Theory and algorithms for application domains
    1. Algorithmic game theory and mechanism design

Recommendations

Individual Welfare Guarantees in the Autobidding World with Machine-learned Advice
WWW '24: Proceedings of the ACM Web Conference 2024

Online advertising channels commonly focus on maximizing total advertiser welfare to enhance channel health, and previous literature has studied augmenting ad auctions with machine learning predictions on advertiser values (also known asmachine-learned ...
Efficiency of the Generalized Second-Price Auction for Value Maximizers
WWW '24: Proceedings of the ACM Web Conference 2024

We study the price of anarchy of the generalized second-price auction where bidders are value maximizers (i.e., autobidders). We show that in general the price of anarchy can be as bad as 0. For comparison, the price of anarchy of running VCG is 1/2 in ...
Incentive-Compatible Learning of Reserve Prices for Repeated Auctions
How can an auctioneer optimize revenue by learning the reserve prices from the bids in the previous auctions? How should the long-term incentives and strategic behavior of the bidders be taken into account? Motivated in part by applications in online ...
Large fractions of online advertisements are sold via repeated second-price auctions. In these auctions, the reserve price is the main tool for the auctioneer to boost revenues. In this work, we investigate the following question: how can the auctioneer ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

WWW '23: Proceedings of the ACM Web Conference 2023

April 2023

4293 pages

ISBN:9781450394161

DOI:10.1145/3543507

Copyright © 2023 Owner/Author.

This work is licensed under a Creative Commons Attribution International 4.0 License.

Sponsors

SIGWEB: ACM Special Interest Group on Hypertext, Hypermedia, and Web

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 30 April 2023

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed limited

Conference

WWW '23

Sponsor:

SIGWEB

WWW '23: The ACM Web Conference 2023

April 30 - May 4, 2023

TX, Austin, USA

Acceptance Rates

Overall Acceptance Rate 1,899 of 8,196 submissions, 23%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
389
Total Downloads

Downloads (Last 12 months)232
Downloads (Last 6 weeks)19

Reflects downloads up to 28 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Deng YMao JMirrokni VTeng YZuo SChua TNgo CKa-Wei Lee RKumar RLauw H(2024)Non-uniform Bid-scaling and Equilibria for Different Auctions: An Empirical StudyProceedings of the ACM Web Conference 202410.1145/3589334.3645659(256-266)Online publication date: 13-May-2024
https://dl.acm.org/doi/10.1145/3589334.3645659
Liaw CMehta AZhu WChua TNgo CKa-Wei Lee RKumar RLauw H(2024)Efficiency of Non-Truthful Auctions in Auto-bidding with Budget ConstraintsProceedings of the ACM Web Conference 202410.1145/3589334.3645636(223-234)Online publication date: 13-May-2024
https://dl.acm.org/doi/10.1145/3589334.3645636
Deng YMahdian MMao JMirrokni VZhang HZuo SChua TNgo CKa-Wei Lee RKumar RLauw H(2024)Efficiency of the Generalized Second-Price Auction for Value MaximizersProceedings of the ACM Web Conference 202410.1145/3589334.3645360(46-56)Online publication date: 13-May-2024
https://dl.acm.org/doi/10.1145/3589334.3645360
Pu XLei TWen WFeng WWang ZChen QJin S(2023)Incentive Mechanism and Resource Allocation for Collaborative Task Offloading in Energy-Efficient Mobile Edge ComputingIEEE Transactions on Vehicular Technology10.1109/TVT.2023.327451372:10(13775-13780)Online publication date: Oct-2023
https://doi.org/10.1109/TVT.2023.3274513

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

HTML Format

View this article in HTML Format.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents