IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v61y2013i1p98-111.html
   My bibliography  Save this article

Dynamic Pay-Per-Action Mechanisms and Applications to Online Advertising

Author

Listed:
  • Hamid Nazerzadeh

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

  • Amin Saberi

    (Management Science and Engineering Department, Stanford University, Stanford, California 94305)

  • Rakesh Vohra

    (Kellogg School of Management, Northwestern University, Evanston, Illinois 60208)

Abstract

We examine the problem of allocating an item repeatedly over time amongst a set of agents. The value that each agent derives from consumption of the item may vary over time. Furthermore, it is private information to the agent, and prior to consumption it may be unknown to that agent. We describe a mechanism based on a sampling-based learning algorithm that under suitable assumptions is asymptotically individually rational, asymptotically Bayesian incentive compatible, and asymptotically ex ante efficient. Our mechanism can be interpreted as a pay-per-action or pay-per-acquisition (PPA) charging scheme in online advertising. In this scheme, instead of paying per click, advertisers pay only when a user takes a specific action (e.g., purchases an item or fills out a form) on their websites.

Suggested Citation

  • Hamid Nazerzadeh & Amin Saberi & Rakesh Vohra, 2013. "Dynamic Pay-Per-Action Mechanisms and Applications to Online Advertising," Operations Research, INFORMS, vol. 61(1), pages 98-111, February.
    • Handle: RePEc:inm:oropre:v:61:y:2013:i:1:p:98-111
    DOI: 10.1287/opre.1120.1124
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.1120.1124
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.1120.1124?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. Kojima, Fuhito & Manea, Mihai, 2010. "Incentives in the probabilistic serial mechanism," Journal of Economic Theory, Elsevier, vol. 145(1), pages 106-123, January.
    2. Pascal Courty & Li Hao, 2000. "Sequential Screening," The Review of Economic Studies, Review of Economic Studies Ltd, vol. 67(4), pages 697-717.
    3. Omar Besbes & Assaf Zeevi, 2012. "Blind Network Revenue Management," Operations Research, INFORMS, vol. 60(6), pages 1537-1550, December.
    4. Dirk Bergemann & Juuso V‰lim‰ki, 2010. "The Dynamic Pivot Mechanism," Econometrica, Econometric Society, vol. 78(2), pages 771-789, March.
    5. Alessandro Pavan & Ilya Segal & Juuso Toikka, 2008. "Dynamic Mechanism Design: Incentive Compatibility, Profit Maximization and Information Disclosure," Carlo Alberto Notebooks 84, Collegio Carlo Alberto.
    6. Jérémie Gallien, 2006. "Dynamic Mechanism Design for Online Commerce," Operations Research, INFORMS, vol. 54(2), pages 291-310, April.
    7. Benjamin Edelman & Michael Ostrovsky & Michael Schwarz, 2007. "Internet Advertising and the Generalized Second-Price Auction: Selling Billions of Dollars Worth of Keywords," American Economic Review, American Economic Association, vol. 97(1), pages 242-259, March.
    8. Alex Gershkov & Benny Moldovanu, 2009. "Dynamic Revenue Maximization with Heterogeneous Objects: A Mechanism Design Approach," American Economic Journal: Microeconomics, American Economic Association, vol. 1(2), pages 168-198, August.
    9. Susan Athey & Ilya Segal, 2013. "An Efficient Dynamic Mechanism," Econometrica, Econometric Society, vol. 81(6), pages 2463-2485, November.
    10. Roberts, Donald John & Postlewaite, Andrew, 1976. "The Incentives for Price-Taking Behavior in Large Exchange Economies," Econometrica, Econometric Society, vol. 44(1), pages 115-127, January.
    11. Chrysanthos Dellarocas, 2012. "Double Marginalization in Performance-Based Advertising: Implications and Solutions," Management Science, INFORMS, vol. 58(6), pages 1178-1195, June.
    12. Goldberg, Andrew V. & Hartline, Jason D. & Karlin, Anna R. & Saks, Michael & Wright, Andrew, 2006. "Competitive auctions," Games and Economic Behavior, Elsevier, vol. 55(2), pages 242-269, May.
    13. Josef Broder & Paat Rusmevichientong, 2012. "Dynamic Pricing Under a General Parametric Choice Model," Operations Research, INFORMS, vol. 60(4), pages 965-980, August.
    14. Gustavo Vulcano & Garrett van Ryzin & Costis Maglaras, 2002. "Optimal Dynamic Auctions for Revenue Management," Management Science, INFORMS, vol. 48(11), pages 1388-1407, November.
    15. Said, Maher, 2012. "Auctions with dynamic populations: Efficiency and revenue maximization," Journal of Economic Theory, Elsevier, vol. 147(6), pages 2419-2438.
    16. Schummer, James, 2004. "Almost-dominant strategy implementation: exchange economies," Games and Economic Behavior, Elsevier, vol. 48(1), pages 154-170, July.
    17. J. Michael Harrison & N. Bora Keskin & Assaf Zeevi, 2012. "Bayesian Dynamic Pricing Policies: Learning and Earning Under a Binary Prior Distribution," Management Science, INFORMS, vol. 58(3), pages 570-586, March.
    18. Roger B. Myerson, 1981. "Optimal Auction Design," Mathematics of Operations Research, INFORMS, vol. 6(1), pages 58-73, February.
    19. Omar Besbes & Assaf Zeevi, 2009. "Dynamic Pricing Without Knowing the Demand Function: Risk Bounds and Near-Optimal Algorithms," Operations Research, INFORMS, vol. 57(6), pages 1407-1420, December.
    20. Gul, Faruk & Postlewaite, Andrew, 1992. "Asymptotic Efficiency in Large Exchange Economies with Asymmetric Information," Econometrica, Econometric Society, vol. 60(6), pages 1273-1292, November.
    21. Nikhil Agarwal & Susan Athey & David Yang, 2009. "Skewed Bidding in Pay-per-Action Auctions for Online Advertising," American Economic Review, American Economic Association, vol. 99(2), pages 441-447, May.
    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. 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.
    2. Santiago R. Balseiro & Omar Besbes & Gabriel Y. Weintraub, 2019. "Dynamic Mechanism Design with Budget-Constrained Buyers Under Limited Commitment," Operations Research, INFORMS, vol. 67(3), pages 711-730, May.
    3. Shweta Jain & Satyanath Bhat & Ganesh Ghalme & Divya Padmanabhan & Y. Narahari, 2016. "Mechanisms with learning for stochastic multi-armed bandit problems," Indian Journal of Pure and Applied Mathematics, Springer, vol. 47(2), pages 229-272, June.
    4. 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.
    5. Santiago Balseiro & Omar Besbes & Francisco Castro, 2021. "Mechanism Design under Approximate Incentive Compatibility," Papers 2103.03403, arXiv.org, revised Mar 2022.
    6. 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.
    7. Krishnamurthy Iyer & Ramesh Johari & Mukund Sundararajan, 2014. "Mean Field Equilibria of Dynamic Auctions with Learning," Management Science, INFORMS, vol. 60(12), pages 2949-2970, December.
    8. Shivam Gupta & Wei Chen & Milind Dawande & Ganesh Janakiraman, 2023. "Three Years, Two Papers, One Course Off: Optimal Nonmonetary Reward Policies," Management Science, INFORMS, vol. 69(5), pages 2852-2869, May.
    9. Ensthaler, Ludwig & Giebe, Thomas, 2014. "Bayesian optimal knapsack procurement," European Journal of Operational Research, Elsevier, vol. 234(3), pages 774-779.
    10. Dragos Florin Ciocan & Krishnamurthy Iyer, 2021. "Tractable Equilibria in Sponsored Search with Endogenous Budgets," Operations Research, INFORMS, vol. 69(1), pages 227-244, January.
    11. Richet, Jean-Loup, 2022. "How cybercriminal communities grow and change: An investigation of ad-fraud communities," Technological Forecasting and Social Change, Elsevier, vol. 174(C).

    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. 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.
    2. 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.
    3. 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.
    4. Dirk Bergemann & Maher Said, 2010. "Dynamic Auctions: A Survey," Levine's Working Paper Archive 661465000000000035, David K. Levine.
    5. Kaplan, Todd R. & Zamir, Shmuel, 2015. "Advances in Auctions," Handbook of Game Theory with Economic Applications,, Elsevier.
    6. Said, Maher, 2012. "Auctions with dynamic populations: Efficiency and revenue maximization," Journal of Economic Theory, Elsevier, vol. 147(6), pages 2419-2438.
    7. Mierendorff, Konrad, 2016. "Optimal dynamic mechanism design with deadlines," Journal of Economic Theory, Elsevier, vol. 161(C), pages 190-222.
    8. 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.
    9. Alex Gershkov & Benny Moldovanu & Philipp Strack, 2018. "Revenue-Maximizing Mechanisms with Strategic Customers and Unknown, Markovian Demand," Management Science, INFORMS, vol. 64(5), pages 2031-2046, May.
    10. Yiwei Chen & Nikolaos Trichakis, 2021. "Technical Note—On Revenue Management with Strategic Customers Choosing When and What to Buy," Operations Research, INFORMS, vol. 69(1), pages 175-187, January.
    11. Yash Kanoria & Hamid Nazerzadeh, 2020. "Dynamic Reserve Prices for Repeated Auctions: Learning from Bids," Papers 2002.07331, arXiv.org.
    12. Mallesh M. Pai & Rakesh Vohra, 2013. "Optimal Dynamic Auctions and Simple Index Rules," Mathematics of Operations Research, INFORMS, vol. 38(4), pages 682-697, November.
    13. Deb, Rahul, 2008. "Optimal Contracting Of New Experience Goods," MPRA Paper 9880, University Library of Munich, Germany.
    14. Yash Kanoria & Hamid Nazerzadeh, 2021. "Incentive-Compatible Learning of Reserve Prices for Repeated Auctions," Operations Research, INFORMS, vol. 69(2), pages 509-524, March.
    15. Vahab Mirrokni & Renato Paes Leme & Pingzhong Tang & Song Zuo, 2020. "Non‐Clairvoyant Dynamic Mechanism Design," Econometrica, Econometric Society, vol. 88(5), pages 1939-1963, September.
    16. Gershkov, Alex & Moldovanu, Benny, 2012. "Dynamic allocation and pricing: A mechanism design approach," International Journal of Industrial Organization, Elsevier, vol. 30(3), pages 283-286.
    17. Ron Lavi & Ella Segev, 2014. "Efficiency levels in sequential auctions with dynamic arrivals," International Journal of Game Theory, Springer;Game Theory Society, vol. 43(4), pages 791-819, November.
    18. Ying-Ju Chen, 2017. "Optimal Dynamic Auctions for Display Advertising," Operations Research, INFORMS, vol. 65(4), pages 897-913, August.
    19. Philippe Jehiel & Laurent Lamy, 2020. "On the Benefits of Set-Asides," Journal of the European Economic Association, European Economic Association, vol. 18(4), pages 1655-1696.
    20. Yuqing Zhang & Neil Walton, 2019. "Adaptive Pricing in Insurance: Generalized Linear Models and Gaussian Process Regression Approaches," Papers 1907.05381, arXiv.org.

    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:61:y:2013:i:1:p:98-111. 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.