User modeling in position auctions: re-considering the GSP and VCG mechanisms

ABSTRACT

We introduce a study of position auctions, with an explicit modeling of user navigation through ads. We refer to our model as the PPA model, since it is most applicable in the context of pay-per-action position auctions. In this model, which is consistent with other recent approaches to user modeling, a typical user searches sequentially over the ordered list of ads. At each point the user has some probability of performing the action associated with the given ad, some probability of moving to the next ad, and some probability of quitting. In the framework of this model, we re-consider two basic mechanisms: the VCG position auction and the generalized second price (GSP) position auction. We study properties of these mechanisms in the context of the PPA model, and in particular show that the GSP position auction possesses a pure strategy equilibrium, and characterize a set of its equilibria. Our main corollary is that the highest revenue one may obtain in an equilibrium of the GSP position auction matches the revenue obtained in the VCG position auction. This suggests that the VCG position auction is preferable to the ad publisher upon the GSP position auction in the context of the PPA position auctions model. The latter is in sharp distinction to the basic result of the usefulness of GSP over VCG in the standard position auctions model, where user behavior is not modeled explicitly. We also study various possibilities for corruption in the PPA setting, and the relative robustness of the mechanisms against the corresponding manipulations.

REFERENCES

• 1: G. Aggarwal, J. Feldman, S. Muthukrishnan, and M. Pal. Sponsored search auctions with markovian users. Working paper, presented at the 4th EC Ad Auctions Workshop, 2008.
• 2: 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]
• 3: Itai Ashlagi , Dov Monderer , Moshe Tennenholtz, Mediators in position auctions, Proceedings of the 8th ACM conference on Electronic commerce, June 11-15, 2007, San Diego, California, USA [doi>10.1145/1250910.1250951]
• 4: S. Atey and G. Ellison. Position auctions with consumer search. Working paper, presented at the 4th EC Ad Auctions Workshop, 2008.
• 5: B. Edelman, M. Ostrovsky, and M. Schwarz. Internet advertising and the generalized second price auction: Selling billions of dollars worth of keywords. American Economic Review, 97(1):242--259, 2007.
• 6: N. Immorlica, K. Jain, M. Mahdian, and K. Talwar. Click fraud resistant methods for learning click-through rates. In WINE '05: Proceedings of the First International Workshop on Internet and Network Economics, pages 34--45, 2005.
• 7: 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]
• 8: M. Mahdian and K. Tomak. Pay-per-action model for online advertising. In WINE '07: Proceedings of the Third International Workshop on Internet and Network Economics, pages 549--557, 2007.
• 9: Hamid Nazerzadeh , Amin Saberi , Rakesh Vohra, Dynamic cost-per-action mechanisms and applications to online advertising, Proceeding of the 17th international conference on World Wide Web, April 21-25, 2008, Beijing, China [doi>10.1145/1367497.1367522]
• 10: TroubleClicks. Trouble clicks. The Economist, November 23 2006.
• 11: H. R. Varian. Position auctions. International Journal of Industrial Organization, 25:1163--1178, 2007.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.4 INFORMATION SYSTEMS APPLICATIONS
      H.4.2 Types of Systems
          Subjects: Decision support (e.g., MIS)

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Multiagent systems; Coherence and coordination
  I.6 SIMULATION AND MODELING
      I.6.5 Model Development
          Subjects: Modeling methodologies

General Terms:
Algorithms, Design, Management, Theory