More Web Proxy on the site http://driver.im/

article

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

Authors:

Hamid Nazerzadeh,

Rakesh VohraAuthors Info & Claims

Operations Research, Volume 61, Issue 1

Pages 98 - 111

Published: 01 January 2013 Publication History

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.

References

[1]

Agarwal, N, Athey, S and Yang, D, "Skewed bidding in pay per action auctions for online advertising," Amer. Econom. Rev., v99, pp. 441-447, 2009.

[2]

Aggarwal, G, Goel, A and Motwani, R, "Truthful auctions for pricing search keywords," Proc. 7th ACM Conf. Electronic Commerce, ACM, New York, pp. 1-7, 2006.

Digital Library

[3]

Akan, M, Ata, B and Dana, J, "Revenue management by sequential screening," 2008.

[4]

Athey, S and Nekipelov, D, "Equilibrium and uncertainty in sponsored search advertising," 2010.

[5]

Athey, S and Segal, I, "An efficient dynamic mechanism," 2007.

[6]

Audibert, J-Y and Bubeck, S, "Minimax policies for adversarial and stochastic bandits," Annual Conf. Learn. Theory---COLT, 2009.

[7]

Auer, P, Cesa-Bianchi, N and Fischer, P, "Finite-time analysis of the multiarmed bandit problem," Machine Learn., v47, pp. 235-256, 2002a.

Digital Library

[8]

Auer, P, Cesa-Bianchi, N, Freund, Y and Schapire, RE, "The nonstochastic multiarmed bandit problem," SIAM J. Comput., v32, pp. 48-77, 2002b.

Digital Library

[9]

Babaioff, M, Kleinberg, R and Slivkins, A, "Truthful mechanisms with implicit payment computation," ACM Conf. Electronic Commerce, ACM, New York, pp. 43-52, 2010.

Digital Library

[10]

Babaioff, M, Sharma, Y and Slivkins, A, "Characterizing truthful multi-armed bandit mechanisms," ACM Conf. Electronic Commerce, ACM, New York, pp. 79-88, 2009.

Digital Library

[11]

Bergemann, D, Said, M and Cochran, JJ, "Dynamic auctions: A survey," Wiley Encyclopedia Operations Research Management Science, John Wiley & Sons, Hoboken, NJ, 2011.

[12]

Bergemann, D and Välimäki, J, "The dynamic pivot mechanism," Econometrica, v78, pp. 771-789, 2010.

[13]

Berry, D and Fristedt, B, Bandit Problems, Chapman and Hall, London, 1985.

[14]

Besbes, O and Zeevi, A, "Dynamic pricing without knowing the demand function: Risk bounds and near-optimal algorithms," Oper. Res., v57, pp. 1407-1420, 2009.

Digital Library

[15]

Besbes, O and Zeevi, A, "Blind network revenue management," Oper. Res., v60, pp. 1537-1550, 2012.

Digital Library

[16]

Borodin, A and Salminen, P, Handbook of Brownian Motion: Facts and Formulae, Springer, Berlin, 2002.

[17]

Broder, J and Rusmevichientong, P, "Dynamic pricing under a general parametric choice model," Oper. Res., v60, pp. 965-980, 2012.

Digital Library

[18]

Cesa-Bianchi, N and Lugosi, G, Prediction, Learning, and Games, Cambridge University Press, New York, 2006.

Digital Library

[19]

Courty, P and Li, H, "Sequential screening," Rev. Econom. Stud., v67, pp. 697-717, 2000.

[20]

Crawford, K, "Google CFO: Fraud a big threat," CNN/Money, 2004.

[21]

Daskalakis, C, Mehta, A and Papadimitriou, CH, "A note on approximate Nash equilibria," Theoret. Comput. Sci., v410, pp. 1581-1588, 2009.

Digital Library

[22]

d'Aspremont, C and Grard-Varet, L-A, "Incentives and incomplete information," J. Public Econom., v11, pp. 25-45, 1979.

[23]

Dellarocas, C, "Double marginalization in performance-based advertising: Implications and solutions," Management Sci., v58, pp. 1178-1195, 2012.

Digital Library

[24]

Devanur, NR and Kakade, SM, "The price of truthfulness for pay-per-click auctions," ACM Conf. Electronic Commerce, ACM, New York, pp. 99-106, 2009.

Digital Library

[25]

Edelman, B, Ostrovsky, M and Schwarz, M, "Internet advertising and the generalized second price auction: Selling billions of dollars worth of keywords," Amer. Econom. Rev., v97, pp. 242-259, 2007.

[26]

Ëso, P and Szentes, B, "Optimal information disclosure in auctions and the handicap auction," Rev. Econom. Stud., v74, pp. 705-731, 2007.

[27]

Feder, T, Nazerzadeh, H and Saberi, A, "Approximating Nash equilibria using small-support strategies," ACM Conf. Electronic Commerce, ACM, New York, pp. 352-354, 2007.

Digital Library

[28]

Gallien, J, "Dynamic mechanism design for online commerce," Oper. Res., v54, pp. 291-310, 2006.

Digital Library

[29]

Gershkov, A and Moldovanu, B, "Dynamic revenue maximization with heterogeneous objects: A mechanism design approach," Amer. Econom. J.: Microeconomics, v1, pp. 168-198, 2009.

[30]

Goldberg, A, Hartline, J, Karlin, A, Saks, M and Wright, A, "Competitive auctions," Games Econom. Behav., v55, pp. 242-269, 2006.

[31]

2007.

[32]

Grow, B, Elgin, B and Herbst, M, "Click fraud: The dark side of online advertising," BusinessWeek, v47, 2006.

[33]

Gul, F and Postlewaite, A, "Asymptotic efficiency in large exchange economies with asymmetric information," Econometrica, v60, pp. 1273-1292, 1992.

[34]

Hajiaghayi, MT, Kleinberg, RD and Parkes, DC, "Adaptive limited-supply online auctions," ACM Conf. Electronic Commerce, ACM, New York, pp. 71-80, 2004.

Digital Library

[35]

Hajiaghayi, MT, Kleinberg, RD, Mahdian, M and Parkes, DC, "Online auctions with re-usable goods," ACM Conf. Electronic Commerce, ACM, New York, pp. 165-174, 2005.

Digital Library

[36]

Harrison, JM, Keskin, NB and Zeevi, A, "Bayesian dynamic pricing policies: Learning and earning under a binary prior distribution," Management Sci., v58, pp. 570-586, 2012.

Digital Library

[37]

Immorlica, N, Jain, K, Mahdian, M and Talwar, K, "Click fraud resistant methods for learning click-through rates," Internet and Network Econom., First Internat. Workshop, Springer, Berlin, 2005.

Digital Library

[38]

Kakade, S, Lobel, I and Nazerzadeh, H, "Optimal dynamic mechanism design and the virtual pivot mechanism," 2010.

[39]

Kojima, F and Manea, M, "Incentives in the probabilistic serial mechanism," J. Econom. Theory, v145, pp. 106-123, 2010.

[40]

Lipton, RJ, Markakis, E and Mehta, A, "Playing large games using simple strategies," ACM Conf. Electronic Commerce, ACM, New York, pp. 36-41, 2003.

Digital Library

[41]

Mahdian, M and Tomak, K, "Pay-per-action model for online advertising," Internet and Network Econom., Third Internat. Workshop, Springer, Berlin, pp. 549-557, 2007.

Digital Library

[42]

Mitchell, D, "Click fraud and halli-bloggers," New York Times, 2005.

[43]

Myerson, R, "Optimal auction design," Math. Oper. Res., v6, pp. 58-73, 1981.

Digital Library

[44]

Nazerzadeh, H, Saberi, A and Vohra, R, "Dynamic cost-per-action mechanisms and applications to online advertising," Proc. 17th Internat. Conf. World Wide Web, ACM, New York, pp. 179-188, 2008.

Digital Library

[45]

Pai, M and Vohra, R, "Optimal dynamic auctions and simple index rules," 2009.

[46]

Parkes, D, Nisan, N, Roughgarden, T, Tardos, E and Vazirani, VV, "Online mechanisms," Algorithmic Game Theory, Cambridge University Press, Cambridge, UK, pp. 411-439, 2007.

[47]

Parkes, DC and Singh, SP, "An MDP-based approach for online mechanism design," Proc. 17th Conf. Neural Inform. Processing Systems, Vancouver and Whistler, British Columbia, Canada, 2003.

[48]

Pavan, A, Segal, I and Toikka, J, "Dynamic mechanism design: Incentive compatibility, profit maximization and information disclosure," 2009.

[49]

Roberts, J and Postlewaite, A, "The incentives for price-taking behavior in large exchange," Econometrica, v44, pp. 115-129, 1976.

[50]

Said, M, "Auctions with dynamic populations: Efficiency and revenue maximization," J. Econom. Theory, v147, pp. 2419-2438, 2012.

[51]

Schummer, J, "Almost-dominant strategy implementation," Games Econom. Behav., v48, pp. 154-170, 2004.

[52]

Skrzypacz, A and Board, S, "Optimal dynamic auctions for durable goods: Posted prices and fire-sales," 2010.

[53]

Slivkins, A and Upfal, E, "Adapting to a changing environment: The Brownian restless bandits," 21st Annual Conf. Learn. Theory---COLT, Omnipress, Madison, WI, pp. 343-354, 2008.

[54]

Spencer, S, Google deems pay-per-action as the “Holy Grail”, CNET News, 2007.

[55]

Sutton, RS and Barto, AG, Reinforcement Learning, an Introduction, MIT Press/Bradford Books, Cambridge, MA, 1998.

Digital Library

[56]

Vulcano, G, van Ryzin, G and Maglaras, C, "Optimal dynamic auctions for revenue management," Management Sci., v48, pp. 1388-1407, 2002.

Digital Library

[57]

Wilson, R and Bewley, T, "Game-theoretic analyses of trading processes," Advances in Economic Theory: Fifth World Congress, Cambridge University Press, Cambridge, UK, pp. 33-70, 1987.

Cited By

Balseiro SBesbes OCastro F(2024)Mechanism Design Under Approximate Incentive CompatibilityOperations Research10.1287/opre.2022.235972:1(355-372)Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1287/opre.2022.2359
Gupta SBansal SDawande MJanakiraman G(2024)Trust-and-EvaluateManagement Science10.1287/mnsc.2022.0112170:11(7811-7828)Online publication date: 1-Nov-2024
https://dl.acm.org/doi/10.1287/mnsc.2022.01121
Gupta SChen WDawande MJanakiraman G(2023)Three Years, Two Papers, One Course OffManagement Science10.1287/mnsc.2022.448269:5(2852-2869)Online publication date: 1-May-2023
https://dl.acm.org/doi/10.1287/mnsc.2022.4482
Show More Cited By

Recommendations

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 ...
On the design of sponsored keyword advertising slot auctions: An analysis of a generalized second-price auction approach

The generalized second-priceauction mechanism is commonly used in research in the context of keyword advertising slot auctioning. The mechanism sets the clearing prices for advertising slots on a search engine's Web pages such that the advertiser will ...
Dynamic cost-per-action mechanisms and applications to online advertising
WWW '08: Proceedings of the 17th international conference on World Wide Web

We study the Cost-Per-Action or Cost-Per-Acquisition (CPA) charging scheme in online advertising. In this scheme, instead of paying per click, the advertisers pay only when a user takes a specific action (e.g. fills out a form) or completes a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Operations Research

Operations Research Volume 61, Issue 1

01-02 2013

268 pages

ISSN:0030-364X

Issue’s Table of Contents

Publisher

INFORMS

Linthicum, MD, United States

Publication History

Published: 01 January 2013

Accepted: 01 September 2012

Received: 01 June 2009

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 10 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Balseiro SBesbes OCastro F(2024)Mechanism Design Under Approximate Incentive CompatibilityOperations Research10.1287/opre.2022.235972:1(355-372)Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1287/opre.2022.2359
Gupta SBansal SDawande MJanakiraman G(2024)Trust-and-EvaluateManagement Science10.1287/mnsc.2022.0112170:11(7811-7828)Online publication date: 1-Nov-2024
https://dl.acm.org/doi/10.1287/mnsc.2022.01121
Gupta SChen WDawande MJanakiraman G(2023)Three Years, Two Papers, One Course OffManagement Science10.1287/mnsc.2022.448269:5(2852-2869)Online publication date: 1-May-2023
https://dl.acm.org/doi/10.1287/mnsc.2022.4482
Chen DYan QChen CZheng ZLiu YMa ZYu CXu JZheng BAl Hasan MXiong L(2022)Hierarchically Constrained Adaptive Ad Exposure in FeedsProceedings of the 31st ACM International Conference on Information & Knowledge Management10.1145/3511808.3557103(3003-3012)Online publication date: 17-Oct-2022
https://dl.acm.org/doi/10.1145/3511808.3557103
Ciocan DIyer K(2021)Tractable Equilibria in Sponsored Search with Endogenous BudgetsOperations Research10.1287/opre.2020.205269:1(227-244)Online publication date: 1-Jan-2021
https://dl.acm.org/doi/10.1287/opre.2020.2052
Kanoria YNazerzadeh H(2021)Incentive-Compatible Learning of Reserve Prices for Repeated AuctionsOperations Research10.1287/opre.2020.200769:2(509-524)Online publication date: 1-Mar-2021
https://dl.acm.org/doi/10.1287/opre.2020.2007
Iyer KJohari RSundararajan M(2019)Mean Field Equilibria of Dynamic Auctions with LearningManagement Science10.1287/mnsc.2014.201860:12(2949-2970)Online publication date: 5-Jan-2019
https://dl.acm.org/doi/10.1287/mnsc.2014.2018
Shen WWang ZZuo S(2018)Ex-post IR dynamic auctions with cost-per-action paymentsProceedings of the 27th International Joint Conference on Artificial Intelligence10.5555/3304415.3304487(505-511)Online publication date: 13-Jul-2018
https://dl.acm.org/doi/10.5555/3304415.3304487
Shen WWang ZZuo SAndre EKoenig SDastani MSukthankar G(2018)Ex-post IR Dynamic Auctions with Cost-per-action PaymentsProceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems10.5555/3237383.3238077(2076-2078)Online publication date: 9-Jul-2018
https://dl.acm.org/doi/10.5555/3237383.3238077
Nazerzadeh HPaes Leme RRostamizadeh ASyed UConitzer VBergemann DChen Y(2016)Where to SellProceedings of the 2016 ACM Conference on Economics and Computation10.1145/2940716.2940771(597-598)Online publication date: 21-Jul-2016
https://dl.acm.org/doi/10.1145/2940716.2940771

View Options

View options

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 Issue’s Table of Contents