skip to main content
10.1145/3219166.3219191acmconferencesArticle/Chapter ViewAbstractPublication PagesecConference Proceedingsconference-collections
research-article

Matching Auctions for Search and Native Ads

Published: 11 June 2018 Publication History

Abstract

Unit demand auctions power today's search and native ad marketplaces. Traditional implementations make an extreme "separability" assumption: the relative value of any two ad slots is the same for all advertisers. Under this assumption, the optimal assignment problem can be conveniently solved simply by sorting; without it, efficient allocation requires solving a full-blown weighted matching problem. Motivated by prior work and our own empirical evidence against separability, we abandon that assumption and tackle the algorithmic problems of assignment and pricing for general unit demand ad auctions. Instead of computing prices directly, we take a novel approach and compute bidders' full allocation curves---complete mappings from each agent's bid space to their allocation under the optimal assignment function---from which it is trivial to compute most prices of interest, like those of the Generalized Second Price (GSP) or Vickrey-Clarke-Groves (VCG) auctions. Remarkably, we show that these full allocation curves (and therefore prices) can be computed in the same asymptotic runtime required to compute the optimal matching alone.

Supplementary Material

MP4 File (p663.mp4)

References

[1]
Gagan Aggarwal, S. Muthukrishnan, Dávid Pál, and Martin Pál. 2009. General Auction Mechanism for Search Advertising. Proceedings of the 18th International Conference on World Wide Web (WWW '09). ACM, New York, NY, USA, 241--250.
[2]
Sushil Bikhchandani and Joseph M. Ostroy. 2006. Combinatorial Auctions. MIT Press, Chapter From the assignment model to combinatorial auctions.
[3]
Liad Blumrosen, Jason D. Hartline, and Shuzhen Nong. 2008. Position Auctions and Non-uniform Conversion Rates ACM EC Workshop on Advertisement Auctions.
[4]
Ruggiero Cavallo, Prabhakar Krishnamurthy, Maxim Sviridenko, and Christopher A. Wilkens. 2017. Sponsored Search Auctions with Rich Ads. In Proceedings of the 26th International Conference on World Wide Web (WWW '17). International World Wide Web Conferences Steering Committee, Republic and Canton of Geneva, Switzerland, 43--51.
[5]
Ruggiero Cavallo and Christopher A. Wilkens. 2014. Web and Internet Economics: 10th International Conference, WINE 2014, Beijing, China, December 14--17, 2014. Proceedings. Springer International Publishing, Cham, Chapter GSP with General Independent Click-through-Rates, 400--416.
[6]
Ran Duan and Seth Pettie. 2014. Linear-Time Approximation for Maximum Weight Matching. J. ACM, Vol. 61, 1, Article no1 (Jan. 2014), 23 pages. 1981. Optimal Auction Design. Math. Oper. Res., Vol. 6, 1 (Feb. 1981), 58--73. 0364--765X
[7]
Renato Paes Leme. 2017. Gross substitutability: An algorithmic survey. Games and Economic Behavior Vol. 106, C (2017), 294--316. https://EconPapers.repec.org/RePEc:eee:gamebe:v:106:y:2017:i:c:p:294--316
[8]
Lyle Ramshaw and Robert E. Tarjan. 2012. On Minimum-Cost Assignments in Unbalanced Bipartite Graphs. (2012).
[9]
Uriel G. Rothblum. 1992. Two-sided matching: A study in game-theoretic modeling and analysis: By Alvin E. Roth and Marilda A. Oliveira Sotomayor, Econometric Society Monographs, Cambridge Univ. Press, Cambridge, MA, 1990. 265
[10]
xiii pp. Games and Economic Behavior Vol. 4, 1 (1992), 161--165. https://EconPapers.repec.org/RePEc:eee:gamebe:v:4:y:1992:i:1:p:161--165
[11]
Hal R. Varian. 2007. Position auctions. International Journal of Industrial Organization Vol. 25 (2007), 1163--1178.
[12]
Hal R. Varian and Christopher Harris. 2014. The VCG Auction in Theory and Practice. American Economic Review Vol. 104, 5 (2014), 442--45.
[13]
Christopher A. Wilkens, Ruggiero Cavallo, and Rad Niazadeh. 2016. Mechanism Design for Value Maximizers. CoRR Vol. abs/1607.04362 (2016). http://arxiv.org/abs/1607.04362
[14]
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 (WWW '17).

Cited By

View all
  • (2023)Learning-Based Ad Auction Design with Externalities: The Framework and A Matching-Based ApproachProceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3580305.3599403(1291-1302)Online publication date: 6-Aug-2023
  • (2023)Distributed dominance graph-based neural multi-objective evolutionary strategy for sponsored search real-time biddingKnowledge-Based Systems10.1016/j.knosys.2023.110921279(110921)Online publication date: Nov-2023
  • (2022)Equilibria in Auctions with Ad TypesProceedings of the ACM Web Conference 202210.1145/3485447.3512052(68-78)Online publication date: 25-Apr-2022
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
EC '18: Proceedings of the 2018 ACM Conference on Economics and Computation
June 2018
713 pages
ISBN:9781450358293
DOI:10.1145/3219166
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 11 June 2018

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. GSP
  2. ad auctions
  3. algorithmic mechanism design
  4. allocation curves
  5. generalized gsp
  6. native advertising
  7. unit demand markets

Qualifiers

  • Research-article

Conference

EC '18
Sponsor:

Acceptance Rates

EC '18 Paper Acceptance Rate 70 of 269 submissions, 26%;
Overall Acceptance Rate 664 of 2,389 submissions, 28%

Upcoming Conference

EC '25
The 25th ACM Conference on Economics and Computation
July 7 - 11, 2025
Stanford , CA , USA

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)13
  • Downloads (Last 6 weeks)0
Reflects downloads up to 07 Jan 2025

Other Metrics

Citations

Cited By

View all
  • (2023)Learning-Based Ad Auction Design with Externalities: The Framework and A Matching-Based ApproachProceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3580305.3599403(1291-1302)Online publication date: 6-Aug-2023
  • (2023)Distributed dominance graph-based neural multi-objective evolutionary strategy for sponsored search real-time biddingKnowledge-Based Systems10.1016/j.knosys.2023.110921279(110921)Online publication date: Nov-2023
  • (2022)Equilibria in Auctions with Ad TypesProceedings of the ACM Web Conference 202210.1145/3485447.3512052(68-78)Online publication date: 25-Apr-2022
  • (2020)The Ad Types ProblemWeb and Internet Economics10.1007/978-3-030-64946-3_4(45-58)Online publication date: 6-Dec-2020

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media