CS364B: Foundations of Sponsored Search
Roughgarden (Office hours: after lecture in Gates 462)
Mukund Sundararajan (Office hours: Mondays 1-2, Thursdays 2-3 in Gates 470)
Time/location: 2:15-5 PM on Mondays in 380-381U.
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.
- Lahaie/Pennock/Saberi/Vohra, Sponsored Search,
Chapter 28 in Algorithmic Game
- 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:
- 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
Early papers on GSP auctions:
More on the Vickrey auction and truthful auction design basics:
- Aggarwal/Goel/Motwani, Truthful auctions for pricing search keywords, EC '06.
Advertising and the Generalized Second Price Auction: Selling Billions
of Dollars Worth of Keywords, American Economic
- Lahaie, An
analysis of alternative slot auction designs for sponsored search,
- Varian, Position Auctions, International Journal of
Industrial Organization, 2007.
- Week 2 (Oct 1): Matching markets. Efficient allocations.
Envy-free prices. The VCG mechanism.
- 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.
- The EOS and Varian papers from Week 1.
- Week 4 (Oct 15): Bidding strategies and dynamic issues in GSP auctions.
Bidding Strategies for Keyword Auctions, EC '07.
Bidding in Keyword Auctions, SSA '06.
Bidding on Keyword Auctions, Electronic Markets, 2004.
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
- Week 5 (Oct 22): Maximizing expected revenue in the Bayesian,
single-keyword case. References:
- Week 6 (Oct 29): Online revenue-maximization with budget-constrained
- 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.
Maintaining Equilibria During Exploration in Sponsored Search Auctions, WINE '07.
An Incentive-Compatible Multi-Armed Bandit Mechanism, PODC '07.
Pay-per-percentage of Impressions: An Advertising Method that is Highly Robust to Fraud, SSA '05.
Click Fraud Resistant Methods for Learning Click-Through Rates, WINE 05.
Pay-per-action model for online advertising, WINE '07.
- Week 9 (Nov 26): Issues in interface design
and the cost of conciseness.
- 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.
Wherefore Art Thou R3579X? Anonymized Social Networks, Hidden Patterns, and Structural Steganography,