10
$\begingroup$

First of all, I am still not sure whether cstheory is well adapted for this question, so I won't be offended if the crowd thinks it is not the case...

In search engine marketing, several problems are interesting. Design of fair (and profitable) auction mechanisms and computation of optimal bidding strategies under bounded monetary resources are two examples of interesting (and well documented) problems.

Another problem of interest is the one of keyword selection: how to select the most profitable keyword (without any link to the amount of money available or to the "topic" of the keyword). "Profitable" can be either giving the best revenue, or the best profit. These problem deals with uncertainty: the clickthrough rate of a keyword is not known, the conversion rate is not known either.

Are you aware of some theoretical work related to this problem?

$\endgroup$
  • 2
    $\begingroup$ I think it's perfectly appropriate. $\endgroup$ – Suresh Venkat Nov 12 '10 at 16:34
8
$\begingroup$

This is a great question, one I've put a lot of thought into. In an internet ad auction, you want a pricing policy that encourages truthful revelation. You could run a normal second price auction on the bid prices, but then the selected ads might be terrible in terms of clickthrough and profit -- what you really want to do is to look at the expected revenue of an ad, something like bid times expected clicktrough (but you can't figure out the expected clickthrough without some experimenting, which might violate "strategy-proofness"). On the other hand, you could just run an optimal contextual bandit algorithm to display the ads most clicked on, but that might not be profitable, nor easily priced. Handling both aspects simultaneously makes for a nice theory problem. One good recent paper that tackles a lot of these issues is "Truthful Mechanisms with Implicit Payment Computation."

$\endgroup$
8
$\begingroup$

In the most basic form this can be viewed as a learning problem: each keyword gives some profit (taking into account CTR, conversion rate, prices, etc.) which is not known and needs to be learned. More or less a Multi-armed bandit problem.

$\endgroup$
7
$\begingroup$

There is in fact a lot of theoretical work in this area starting with the work of Mehta, Saberi, Vazirani, Vazirani'2005. More examples of papers dealing with clickthrough rates and inputs from random permutations include Goel-Mehta'08, Muthukrishnan-Pal-Svitkina'07.

There is a wealth of research done on several variants of ad-auction problems, especially in the last two years. You will find more related papers in the proceedings of International Workshop On Internet And Network Economics (WINE) and Electronic Commerce (EC) conferences. Since these conferences are well-represented by attendees from companies like Yahoo, Google, Amazon etc., you will find papers addressing very practical variants of your problem.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.