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 Michael Kearns's Seminar on Sponsored Search, given at Penn in Fall 2006.

Deadlines:

• 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.

Possible topics:

I: Theory-ish projects:

• Bundling in Keyword Auctions
  
  • Summary: In many cases there are very few advertisers bidding on a keyword. The lack of competition can hurt a search engine's revenue.  Search engines can artificially raise competition by 'bundling' keywords together. This is an alternative to setting reserve prices.  Open Questions: Improve the approximation ratio from the first paper. Compute the optimal bundling when exact valuations are unknown, but distributions on valuations are available..
  • Status: Available.
  • Computing Optimal Bundles for Sponsored Search Ghosh, Arpita ; Nazerzadeh, Hamid ; Sundararajan, Mukund, WINE '07
  • Mixed bundling auctions. P. Jehiel, M. Meyer-ter-Vehn, and B. Moldovanu. 
  • Sponsored search with contexts. E. Even-Dar, M. Kearns, and J. Wortman. 

• Revenue Maximization with Budgets.
  • Summary:  This project is along the lines of the result by Mehta, Saberi, Vazirani and Vazirani discussed in class. The first paper shows that it is possible to use expert advice and provide a worst case guarantee. Open Questions: Can we leverage the framework from the second paper in the list (or use other methods) to combine the advice of multiple experts?
  • Status: Available
  • Allocating Online Advertisement Space with Unreliable Estimates. Mohammad Mahdian, Hamid Nazerzdeh, Amin Saberi. EC '07.
  • The Multiplicative Weights Update Method: A Meta-Algorithm and Applications . Sanjeev Arora, Elad Hazan, Satyen Kale.

• Convergence/Dynamics I
  • Summary: This paper discusses a model where advertisers valuations are more generally defined. For instance, advertisers may have different valuations for different slots. The authors show that even with such general valuations, current auctions are expressive enough to allow efficient equilibria to exist. One drawback is that the authors do not propose a dynamic process by which advertisers  arrive at such an equilibrium. Can you do this?  
  • Status:
    • Available
  • Cost of Conciseness in Sponsored Search Auctions.  Abrams, Z.; Ghosh, A.; Vee, E.

• Budgets and knapsack auctions
  • Summary: Can knapsack auctions be designed to take into account budgets?
  • Status:
    • Available.
  • Borgs, Immorlica, Mahdian, Saberi, "Multi-unit auctions with budget-constrained bidders", EC 2005.
  • Aggarwal, Hartline, "Knapsack Auctions" SODA 2006.
  • Optional Reference: Balcan, Blum, Hartline, Mansour, "Mechanism Design via Machine Learning", FOCS 2005.
  • Optional Reference: Abrams, "Revenue Maximization When Bidders Have Budgets" SODA 2006.

  II: Theory and or simulation-driven projects:

• Convergence/Dynamics II
  • Summary:  The authors prove that if all advertisers adopt a certain, natural bidding strategy the system reaches an equilibrium; the result holds when the auction employed is a first price auction. (Advertisers pay their bid.) They observe empirically that the system also converges when  a second price auction is employed. Can you supply a formal proof? Or, can you think of different enlightening simulations to run?
  • Status: Available
  • Dynamics of Bid Optimization in Online Advertisement Auctions. Borgs et. al.

• 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.
  • Status:
    • Available
  • 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 bidding agent? 
  • Status:
    • Available
  • 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 are different).
  • Mail TA for data.
  • The data has been provided by the authors of the following paper. All groups using data should cite this paper: www.cis.upenn.edu/~mkearns/papers/empss.pdf
  • 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 here.

• (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.

   

  IV: Other

• 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.