Some suggested project topics for CS364B (Foundations of Sponsored Search)
Most recent update: 10/5/07
Note: The info below show be enough to easily find most of the
papers on the Web. If you can't find one of the papers below after 5
minutes of searching, contact the TA for a copy.
Note: We expect projects to be done in teams of 2-3.
Note: You might get further ideas by checking out
Seminar on Sponsored Search, given at Penn in Fall 2006.
- By Monday 10/16/07: pick a project topic. You are highly
encouraged to design your own, in which case you should schedule
a brief meeting with the TA (during office hours) to discuss it.
- By Monday 11/5/07: 2 Page summary of papers. 2 Page project proposal.
- By Monday 12/3/07: Final project due. Suggested report length:
around 15 pages.
- Competing search engines.
- Summary: Most analyses of keyword auction assume that there is one
auctioneer in the system. Practically there are multiple auctioneers. What
happens when there are multiple auctioneers each interested in maximizing its
revenue? One approach is to propose a model by which bidders switch
between search engines, and then investigate what happens theoretically
or by simulation.
- McAfee, R. P. (1993) Mechanism Design by Competing Sellers. Econometrica, 61, 1281-1312.
- Look at Page 39 of the Klemperer's book, Auctions: Theory and Practice (http://www.paulklemperer.org/index.htm, click on the `A Survey of Auction Theory' link and go to physical page 39 and find section 1.13.5 entitled `Competing Auctioneers')
- Bidding Agents
- Summary: Advertisers with large budgets often bid on
thousands of keywords. They use bidding agents to manage their campaigns.
Study a bidding agents (theoretically and/or by simulation),
possibly the one mentioned in the first paper.
Discuss what would happen if everyone used the same bidding agent. Would the
system reach equilibrium? Can you use ideas from the second paper to design a
- Optimal bidding for keyword auctions. Brendan Kitts , Benjamin LeBlanc.
- The Multiplicative Weights Update Method: A Meta-Algorithm and Applications
. Sanjeev Arora, Elad
Hazan, Satyen Kale.
III: Data-Driven Topics
- Guidelines for a data analysis-based project:
- Multiple teams can do such projects (as long as the proposals
- Mail TA for data.
- The data has been provided by the authors of the following paper. All
groups using data should cite this paper:
- The above paper is also an example of the kind of things that you can do
with data. We expect projects using data to be systematic and carefully
reason about various observations.
- The data is a snapshot only --- i.e. every search term was priced only
once, so there is unfortunately no time-series data
- As described in the paper, the search terms used are the cross
product of two lists, one of "base terms" like product names/types
("digital camera"), the other of modifiers of these base terms
(e.g. "discount", "premium")
- The data comes in two forms, a shorter bids-only form and
a longer one that includes ad text.
- Another potentially relevant paper is
- (One Possible Topic) Is the System at a Nash Equilibrium?
- Summary: The first paper shows that if the advertising system
reaches a Nash Equilibrium then certain inequalities must be observable in
the bid-data. Open Questions: If such inequalities are observed in the
data, does that imply that the system is in Nash Equilibrium? If a small
fraction inequalities don't hold, does the imply that the system is
far away from a Nash Equilibrium? The second paper discusses
techniques for answering such questions.
- Status: Available
- Position Auctions. Hal Varian 2006.
- Nonparametric analysis of optimizing behavior with
measurement error. Hal R. Varian. 1985.
Compare the user interfaces of various search engines. Are there preferences
that are expressible in one search engine that an advertiser cannot express
in another? What is the impact on the advertiser's cost of bid preparation?
Will this have an impact on the efficiency or revenue achievable by the
search engine? Will convergence suffer because of lack of expressibility?
Read the paper on the 'Cost of conciseness' above, as well as
Section 4 of the following book chapter for background on the consequences of such design decisions.