Models of malicious behavior in sponsored search

ABSTRACT

Search engines such as Google, Yahoo, and MSN now auction off search terms to potential advertisers. The potential advertisers place their bids on each search term of interest, as well as specifying a daily budget. Each search on this term displays an advertisement that is linked to the advertiser's website, and the advertiser pays the search engine every time the link is activated. When an advertiser's budget is reached, the search engine stops displaying their ad. This kind of advertising is extremely popular -- the combined revenue of Yahoo and Google in 2005 was estimated at over 4.5 billion dollars. We develop small models which still have the property that malicious behavior such as bid-jamming still occurs as a rational best-response strategy. Such malicious behavior occurs frequently in practice. We are able to derive bidding strategies which are the best-responses when the budget of the bidder is low relative to her competitors, as well as strategies which protect against bid-jamming.

REFERENCES

• 1: Gagan Aggarwal , Ashish Goel , Rajeev Motwani, Truthful auctions for pricing search keywords, Proceedings of the 7th ACM conference on Electronic commerce, p.1-7, June 11-15, 2006, Ann Arbor, Michigan, USA [doi>10.1145/1134707.1134708]
• 2: Apex Pacific Dynamic Bid Maximizer, see http://www.apexpacific.com/bidmax.html.
• 3: Atlas Search BidManager, see http://www.gotoast.com/products/bidmanager.
• 4: Christian Borgs , Jennifer Chayes , Nicole Immorlica , Mohammad Mahdian , Amin Saberi, Multi-unit auctions with budget-constrained bidders, Proceedings of the 6th ACM conference on Electronic commerce, p.44-51, June 05-08, 2005, Vancouver, BC, Canada [doi>10.1145/1064009.1064014]
• 5: F. Brandt, T. Sandholm, and Y. Shoham. Spiteful bidding in sealed-bid auctions. In Proceedings of the 7th Workshop on Game Theoretic and Decision Theoretic Agents (GTDT), 2005.
• 6: G. Brown, M. Carlyle, R. Harney, E. Skroch, and K. Wood. How to optimally interdict a belligerent project to develop a nuclear weapon. submitted for publication, 2005.
• 7: G. Brown, M. Carlyle, J. Royset, and K. Wood. On the complexity of delaying an adversary's project. In B. Golden, S. Raghavan, and E. Wasil, editors, The Next Wave in Computing, Optimization and Decision Technologies, pages 3--17. Springer, New York, NY, 2005.
• 8: ClickTracs BidHero, see http://www.clicktracks.com/products/bidhero/index.php.
• 9: Digital Point online forum, see http://forums.digitalpoint.com/showthread.php?t=30805.
• 10: Winning a search advertising bidding war. Domains Magazine, 2006. Online magazine, see http://domainsmagazine.com/Domain/Domains_18/ Domain_2945.shtml.
• 11: B. Edelmann, M. Ostrovsky, and B. Schwartz. Internet advertising and the generalized second price auction. Technical Report 11765, NBER Working Paper, 2005.
• 12: G. lyengar, D. J. Phillips, and C. Stein. Strategies for sequential auctions with budgets. Technical report, CORC, Columbia University, 2005. Working paper.
• 13: KeywordMax BidDirector, see http://www.keywordmax.com/bid_director.html.
• 14: V. Krishna. Auction Theory. Academic Press, San Diego, CA, 2002.
• 15: Sébastien Lahaie, An analysis of alternative slot auction designs for sponsored search, Proceedings of the 7th ACM conference on Electronic commerce, p.218-227, June 11-15, 2006, Ann Arbor, Michigan, USA [doi>10.1145/1134707.1134731]
• 16: Quick tips for bid jamming prevention. Marketer-Today.com, 2005. Online magazine, see http://www.marketertoday.com/archives/2005/ 10/quick_tips_for.html.
• 17: P. R. Milgrom and R. J. Weber. Theory of auctions and competitive bidding. Econometrica, 50(6):1089--1122, 1982.
• 18: Shmuel S. Oren and Michael H. Rothkopf. Optimal bidding in sequential auctions. Operations Res., 23(6): 1080--1090, 1975.
• 19: D. Pastemak and K. Lee. Winning the search bidding wars. Multichannel Merchant, 2003. Online magazine, see http://multichannelmerchant.com/webchannel/seo/marketing_winning_search_bidding.
• 20: C. Pitchik. Budget-constrained sequential auctions with incomplete information. Unpublished Manuscript, 1994.
• 21: S. Spencer. Web marketing blog, see http://www.stephanspencer.com/archives/2005/09/06/bid-jamming-and-gap-surfing/.
• 22: V. H. Stackelberg. The Theory of Market Economy. Oxford University Press, Oxford, 1952.
• 23: H. R. Varian. Position auctions. Technical report, UC Berkeley, 2006.
• 24: Weblmarketing company homepage, see http://www.weblmarketing.com/glossary.php?term=Bid+Jamming.
• 25: Y. Zhou and R. Lukose. Vindictive bidding in keyword auctions. In Proceedings of the Second Workshop on Sponsored Search Auctions (SSA), 2006.

INDEX TERMS

Keywords:
approximation algorithms, auction theory, sponsored search