IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v69y2021i5p1450-1467.html

Deals or No Deals: Contract Design for Online Advertising

Author

Listed:
  • Anthony Kim

    (Amazon, New York, New York 10001)

  • Vahab Mirrokni

    (Google Research, New York, New York 10011)

  • Hamid Nazerzadeh

    (Marshall School of Business, University of Southern California, Los Angeles, California 90089)

Abstract

We present a formal study of first-look and preferred deals that are a recently introduced generation of contracts for selling online advertisements, which generalize traditional reservation contracts and are suitable for advertisers with advanced targeting capabilities. Under these deals, one or more advertisers gain priority access to an inventory of impressions before others and can choose to purchase in real time. In particular, we propose constant-factor approximation algorithms for maximizing the revenue that can be obtained from these deals when offered to all or a subset of the advertisers, whose valuation distributions can be independent or correlated through a common value component. We evaluate our algorithms using data from Google’s ad exchange platform and show they perform better than the approximation guarantees and obtain significantly higher revenue than auctions; in certain cases, the observed revenue is 85%–96% of the optimal revenue achievable. We also prove the NP-hardness of designing deals when advertisers’ valuations are arbitrarily correlated and the optimality of menus of deals among a certain class of selling mechanisms in an incomplete distributional information setting.

Suggested Citation

  • Anthony Kim & Vahab Mirrokni & Hamid Nazerzadeh, 2021. "Deals or No Deals: Contract Design for Online Advertising," Operations Research, INFORMS, vol. 69(5), pages 1450-1467, September.
    • Handle: RePEc:inm:oropre:v:69:y:2021:i:5:p:1450-1467
    DOI: 10.1287/opre.2020.2087
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.2020.2087
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.2020.2087?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Xiao Huang & Greys Sošić & Gregory Kersten, 2017. "Selling through Priceline? On the impact of name-your-own-price in competitive market," IISE Transactions, Taylor & Francis Journals, vol. 49(3), pages 304-319, March.
    2. Hart, Sergiu & Nisan, Noam, 2017. "Approximate revenue maximization with multiple items," Journal of Economic Theory, Elsevier, vol. 172(C), pages 313-347.
    3. Sham M. Kakade & Ilan Lobel & Hamid Nazerzadeh, 2013. "Optimal Dynamic Mechanism Design and the Virtual-Pivot Mechanism," Operations Research, INFORMS, vol. 61(4), pages 837-854, August.
    4. Ashenfelter, Orley & Genesove, David, 1992. "Testing for Price Anomalies in Real-Estate Auctions," American Economic Review, American Economic Association, vol. 82(2), pages 501-505, May.
    5. Fisher, M.L. & Nemhauser, G.L. & Wolsey, L.A., 1978. "An analysis of approximations for maximizing submodular set functions - 1," LIDAM Reprints CORE 334, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    6. Santiago R. Balseiro & Jon Feldman & Vahab Mirrokni & S. Muthukrishnan, 2014. "Yield Optimization of Display Advertising with Ad Exchange," Management Science, INFORMS, vol. 60(12), pages 2886-2907, December.
    7. Stephen M. Gilbert & Ramandeep S. Randhawa & Haoying Sun, 2014. "Optimal Per-Use Rentals and Sales of Durable Products and Their Distinct Roles in Price Discrimination," Production and Operations Management, Production and Operations Management Society, vol. 23(3), pages 393-404, March.
    8. Z. Kevin Weng, 1995. "Channel Coordination and Quantity Discounts," Management Science, INFORMS, vol. 41(9), pages 1509-1522, September.
    9. Nick Arnosti & Marissa Beck & Paul Milgrom, 2016. "Adverse Selection and Auction Design for Internet Display Advertising," American Economic Review, American Economic Association, vol. 106(10), pages 2852-2866, October.
    10. William Vickrey, 1961. "Counterspeculation, Auctions, And Competitive Sealed Tenders," Journal of Finance, American Finance Association, vol. 16(1), pages 8-37, March.
    11. Alevy, Jonathan E. & Cristi, Oscar & Melo, Oscar, 2010. "Right-to-Choose Auctions: A Field Study of Water Markets in the Limari Valley of Chile," Agricultural and Resource Economics Review, Northeastern Agricultural and Resource Economics Association, vol. 39(2), pages 1-14, April.
    12. Burguet, Roberto, 2007. "Right to choose in oral auctions," Economics Letters, Elsevier, vol. 95(2), pages 167-173, May.
    13. R. Preston McAfee & John McMillan & Michael D. Whinston, 1989. "Multiproduct Monopoly, Commodity Bundling, and Correlation of Values," The Quarterly Journal of Economics, President and Fellows of Harvard College, vol. 104(2), pages 371-383.
    14. Santiago R. Balseiro & Omar Besbes & Gabriel Y. Weintraub, 2015. "Repeated Auctions with Budgets in Ad Exchanges: Approximations and Design," Management Science, INFORMS, vol. 61(4), pages 864-884, April.
    15. Shipra Agrawal & Zizhuo Wang & Yinyu Ye, 2014. "A Dynamic Near-Optimal Algorithm for Online Linear Programming," Operations Research, INFORMS, vol. 62(4), pages 876-890, August.
    16. John Turner, 2012. "The Planning of Guaranteed Targeted Display Advertising," Operations Research, INFORMS, vol. 60(1), pages 18-33, February.
    17. Jacob K. Goeree & Charles R. Plott & John Wooders, 2004. "Bidders' Choice Auctions: Raising Revenues Through the Right to Choose," Journal of the European Economic Association, MIT Press, vol. 2(2-3), pages 504-515, 04/05.
    18. Roger B. Myerson, 1981. "Optimal Auction Design," Mathematics of Operations Research, INFORMS, vol. 6(1), pages 58-73, February.
    19. Alessandro Pavan & Ilya Segal & Juuso Toikka, 2014. "Dynamic Mechanism Design: A Myersonian Approach," Econometrica, Econometric Society, vol. 82(2), pages 601-653, March.
    20. Fisher, M.L. & Nemhauser, G.L. & Wolsey, L.A., 1978. "An analysis of approximations for maximizing submodular set functions," LIDAM Reprints CORE 341, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    21. Yannis Bakos & Erik Brynjolfsson, 1999. "Bundling Information Goods: Pricing, Profits, and Efficiency," Management Science, INFORMS, vol. 45(12), pages 1613-1630, December.
    22. William James Adams & Janet L. Yellen, 1976. "Commodity Bundling and the Burden of Monopoly," The Quarterly Journal of Economics, President and Fellows of Harvard College, vol. 90(3), pages 475-498.
    23. L. Elisa Celis & Gregory Lewis & Markus Mobius & Hamid Nazerzadeh, 2014. "Buy-It-Now or Take-a-Chance: Price Discrimination Through Randomized Auctions," Management Science, INFORMS, vol. 60(12), pages 2927-2948, December.
    24. René Caldentey & Gustavo Vulcano, 2007. "Online Auction and List Price Revenue Management," Management Science, INFORMS, vol. 53(5), pages 795-813, May.
    25. repec:feb:framed:0082 is not listed on IDEAS
    26. Ying-Ju Chen, 2017. "Optimal Dynamic Auctions for Display Advertising," Operations Research, INFORMS, vol. 65(4), pages 897-913, August.
    27. Pascal Courty & Li Hao, 2000. "Sequential Screening," The Review of Economic Studies, Review of Economic Studies Ltd, vol. 67(4), pages 697-717.
    28. Raphael Boleslavsky & Maher Said, 2013. "Progressive Screening: Long-Term Contracting with a Privately Known Stochastic Process," The Review of Economic Studies, Review of Economic Studies Ltd, vol. 80(1), pages 1-34.
    29. Dragos Florin Ciocan & Vivek Farias, 2012. "Model Predictive Control for Dynamic Resource Allocation," Mathematics of Operations Research, INFORMS, vol. 37(3), pages 501-525, August.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Ying-Ju Chen & Guillermo Gallego & Pin Gao & Yang Li, 2025. "Position Auctions with Endogenous Product Information: Why Live-Streaming Advertising Is Thriving," Management Science, INFORMS, vol. 71(11), pages 9290-9307, November.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Hana Choi & Carl F. Mela & Santiago R. Balseiro & Adam Leary, 2020. "Online Display Advertising Markets: A Literature Review and Future Directions," Information Systems Research, INFORMS, vol. 31(2), pages 556-575, June.
    2. Lu, Jingfeng & Zhao, Wenbo, 2026. "Intertemporal bundling," Journal of Economic Theory, Elsevier, vol. 231(C).
    3. Bergemann, Dirk & Pavan, Alessandro, 2015. "Introduction to Symposium on Dynamic Contracts and Mechanism Design," Journal of Economic Theory, Elsevier, vol. 159(PB), pages 679-701.
    4. Narendra Agrawal & Sami Najafi-Asadolahi & Stephen A. Smith, 2025. "Dynamic Pricing and Bidding for Display Advertising Campaigns," Manufacturing & Service Operations Management, INFORMS, vol. 27(3), pages 843-861, May.
    5. Saeed Alaei & Ali Makhdoumi & Azarakhsh Malekian, 2023. "Optimal Subscription Planning for Digital Goods," Operations Research, INFORMS, vol. 71(6), pages 2245-2266, November.
    6. Arve, Malin & Zwart, Gijsbert, 2023. "Optimal procurement and investment in new technologies under uncertainty," Journal of Economic Dynamics and Control, Elsevier, vol. 147(C).
    7. Saeed Alaei & Ali Makhdoumi & Azarakhsh Malekian & Saša Pekeč, 2022. "Revenue-Sharing Allocation Strategies for Two-Sided Media Platforms: Pro-Rata vs. User-Centric," Management Science, INFORMS, vol. 68(12), pages 8699-8721, December.
    8. Itai Ashlagi & Constantinos Daskalakis & Nima Haghpanah, 2023. "Sequential Mechanisms with Ex Post Individual Rationality," Operations Research, INFORMS, vol. 71(1), pages 245-258, January.
    9. Dirk Bergemann & Alessandro Pavan, 2015. "Introduction to JET Symposium Issue on "Dynamic Contracts and Mechanism Design"," Cowles Foundation Discussion Papers 2016, Cowles Foundation for Research in Economics, Yale University.
    10. Narendra Agrawal & Sami Najafi-Asadolahi & Stephen A. Smith, 2023. "A Markov Decision Model for Managing Display-Advertising Campaigns," Manufacturing & Service Operations Management, INFORMS, vol. 25(2), pages 489-507, March.
    11. Patrick Lahr & Axel Niemeyer, 2024. "Extreme Points in Multi-Dimensional Screening," Papers 2412.00649, arXiv.org, revised Oct 2025.
    12. Ilan Lobel, 2021. "Revenue Management and the Rise of the Algorithmic Economy," Management Science, INFORMS, vol. 67(9), pages 5389-5398, September.
    13. Tuomas Sandholm & Anton Likhodedov, 2015. "Automated Design of Revenue-Maximizing Combinatorial Auctions," Operations Research, INFORMS, vol. 63(5), pages 1000-1025, October.
    14. Ying-Ju Chen & Guillermo Gallego & Pin Gao & Yang Li, 2025. "Position Auctions with Endogenous Product Information: Why Live-Streaming Advertising Is Thriving," Management Science, INFORMS, vol. 71(11), pages 9290-9307, November.
    15. Negin Golrezaei & Hamid Nazerzadeh & Ramandeep Randhawa, 2020. "Dynamic Pricing for Heterogeneous Time-Sensitive Customers," Manufacturing & Service Operations Management, INFORMS, vol. 22(3), pages 562-581, May.
    16. Tao Zhang & Quanyan Zhu, 2019. "On Incentive Compatibility in Dynamic Mechanism Design With Exit Option in a Markovian Environment," Papers 1909.13720, arXiv.org, revised May 2021.
    17. Jian Pei, 2020. "A Survey on Data Pricing: from Economics to Data Science," Papers 2009.04462, arXiv.org, revised Nov 2020.
    18. Tao Zhang & Quanyan Zhu, 2022. "On Incentive Compatibility in Dynamic Mechanism Design With Exit Option in a Markovian Environment," Dynamic Games and Applications, Springer, vol. 12(2), pages 701-745, June.
    19. Stefano Galavotti, 2014. "Reducing Inefficiency in Public Good Provision Through Linking," Journal of Public Economic Theory, Association for Public Economic Theory, vol. 16(3), pages 427-466, June.
    20. Hernando, Andres & Villena, Mauricio & Apablaza, Valentina, 2023. "Optimal Bidding for a Bundle of Power Transmission Infrastructure Works," MPRA Paper 120849, University Library of Munich, Germany, revised 30 Apr 2024.

    More about this item

    Keywords

    ;
    ;
    ;
    ;
    ;
    ;
    ;
    ;
    ;

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:oropre:v:69:y:2021:i:5:p:1450-1467. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.