CS364B: Foundations of Sponsored Search

Instructor: Tim Roughgarden (Office hours: after lecture in Gates 462)

Teaching Assistant: Mukund Sundararajan (Office hours: Mondays 1-2, Thursdays 2-3 in Gates 470)

Time/location: 2:15-5 PM on Mondays in 380-381U.

Course description: Survey of current research on sponsored search auctions used by search engines such as Google and Yahoo!. Topics include: fundamentals of dominant-strategy auction design and the VCG mechanism; matching markets and envy-free pricing; generalized second-price (GSP) auctions and their equilibria; bidding strategies in and convergence properties of GSP auctions; Bayesian auction theory and revenue-maximization; the role of bidder budgets in revenue maximization and bidding strategies; click fraud; and economic issues in auction interface design. Time permitting, we will conclude by surveying one or two other topics at the interface of game theory and contemporary Internet algorithms, such as prediction markets or reputation systems. Prerequisites: 154N and 161, or equivalents.

Course requirements: 2-3 problem sets and a course project. Students taking the course pass/fail can skip the problem sets but must complete the project.

• Problem Set #1 (Out Mon 10/1, due in class Mon 10/8.)
• Problem Set #2 (Out Mon 10/8, due in class Mon 10/15.)
• Problem Set #3 (Out Mon 10/29, due in class Mon 11/12.)

• Suggested project topics.
  Deadline for choosing a topic: October 15.
• Mid-term report due November 12. Instructions.
• Final report due Noon, December 3. No extensions. Instructions.

General references:

• Lahaie/Pennock/Saberi/Vohra, Sponsored Search, Chapter 28 in Algorithmic Game Theory.
  • Hard copies handed out on the first day of class.
  • The entire AGT book can be read online by clicking on the above link (username=agt1user, password=camb2agt).
• Michael Kearns's Seminar on Sponsored Search, given at Penn in Fall 2006.
• Proceedings from Sponsored Search Workshops: 2006 and 2007.
• An interesting transcript of a 2006 panel discussion on the future of sponsored search research.

Schedule and references: (Under construction.)

• Week 1 (Sept 24): Introduction to sponsored search; generalized second-price (GSP) auctions; the Vickrey auction and mechanism design basics. References:
  • Easley/Kleinberg, lecture notes on keyword auctions from a course at Cornell.
  • Fain/Pedersen, Sponsored Search: A Brief History, 2nd Sponsored Search Workshop, 2006.
  Early papers on GSP auctions:
  • Aggarwal/Goel/Motwani, Truthful auctions for pricing search keywords, EC '06.
  • Edelman/Ostrovsky/Schwarz, Internet Advertising and the Generalized Second Price Auction: Selling Billions of Dollars Worth of Keywords, American Economic Review, 2007.
  • Lahaie, An analysis of alternative slot auction designs for sponsored search, EC '06.
  • Varian, Position Auctions, International Journal of Industrial Organization, 2007.
  More on the Vickrey auction and truthful auction design basics:
  • Ausubel/Milgrom, Chapter 1 of Combinatorial Auctions, 2006.
  • Section 1 of old 364B lecture notes.

• Week 2 (Oct 1): Matching markets. Efficient allocations. Envy-free prices. The VCG mechanism. References:
  • Easley/Kleinberg, lecture notes on matching markets and keyword auctions.
  • Demange/Gale/Sotomayor, Multi-item auctions, Journal of Political Economy, 1986.
  • Section 28.3 of the Lahaie/Pennock/Saberi/Vohra chapter.
  • Sections 4 and 5 of the AGM paper from last week.

• Week 3 (Oct 8): Connections between envy-free prices and the VCG mechanism. Equilibrium analysis of GSP auctions. References:
  • The EOS and Varian papers from Week 1.

• Week 4 (Oct 15): Bidding strategies and dynamic issues in GSP auctions. References:
  • Cary/Das/Edelman/Giotis/Heimerl/Mathieu/Schwarz, Greedy Bidding Strategies for Keyword Auctions, EC '07.
  • Zhou/Lukose, Vindictive Bidding in Keyword Auctions, SSA '06.
  • Kitts/LeBlanc, Optimal Bidding on Keyword Auctions, Electronic Markets, 2004.
  • Borgs/Chayes/Etesami/Immorlica/Jain/Mahdian, Dynamics of Bid Optimization in Online Advertisement Auctions, WWW '07.
  • For the basics of repeated games and folk theorems, see (e.g.) Chapter 8 of Osborne/Rubinstein, A Course in Game Theory, MIT Press, 1994.
  • The difficulties of modeling repeated auctions are also covered in this SSA '06 panel discussion.

• Week 5 (Oct 22): Maximizing expected revenue in the Bayesian, single-keyword case. References:
  • Myerson, Optimal Auction Design, Mathematics of Operations Research, 1981.
  • Old CS364B lecture notes by Jason Hartline.
  • Edelman/Schwarz, Optimal Auction Design in a Multi-unit Environment: The Case of Sponsored Search Auctions, Working paper, 2006.

• Week 6 (Oct 29): Online revenue-maximization with budget-constrained bidders.
  • Mehta/Saberi/Vazirani/Vazirani, Adwords and Generalized On-line Matching, FOCS '05.
  • Section 28.4 of the Lahaie/Pennock/Saberi/Vohra chapter.
  • Buchbinder/Jain/Naor, Online Primal-Dual Algorithms for Maximizing Ad-Auctions Revenue, ESA '07.

• Week 7 (Nov 5): no class this week

• Week 8 (Nov 12): Learning click-through rates; click fraud; pay-per-action auctions. References:
  • Pandey/Olston, Handling Advertisements of Unknown Quality in Search Advertising, NIPS '06.
  • Wortman/Vorobeychik/Li/Langford, Maintaining Equilibria During Exploration in Sponsored Search Auctions, WINE '07.
  • Gonen/Pavlov, An Incentive-Compatible Multi-Armed Bandit Mechanism, PODC '07.
  • Goodman, Pay-per-percentage of Impressions: An Advertising Method that is Highly Robust to Fraud, SSA '05.
  • Immorlica/Jain/Mahdian/Talwar, Click Fraud Resistant Methods for Learning Click-Through Rates, WINE 05.
  • Mahdian/Tomak, Pay-per-action model for online advertising, WINE '07.

• Week 9 (Nov 26): Issues in interface design and the cost of conciseness.
  • Abrams/Ghosh/Vee, Cost of Conciseness in Sponsored Search Auctions, WINE '07.
  • Johari/Tsitsiklis, Efficiency of Scalar-Parameterized Mechanisms, submitted, 2007. See Section 5. See also Section 21.4 of the AGT book.

• Week 10 (Dec 3): When is a data set anonymous? (Or, why is sponsored search data so hard to get?)
  • Sweeney, k-anonymity: a model for protecting privacy, International Journal on Uncertainty, Fuzziness and Knowledge-based Systems, 10 (5), 2002; 557-570.
  • A Face Is Exposed for AOL Searcher No. 4417749, New York Times, August 9, 2006.
  • Narayanan/Shmatikov, How To Break Anonymity of the Netflix Prize Dataset, 2007.
  • Backstrom/Dwork/Kleinberg, Wherefore Art Thou R3579X? Anonymized Social Networks, Hidden Patterns, and Structural Steganography, WWW '07.