<p>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.  </p>

CC BY-SA 2.5
2010-11-12T19:47:46.387Z
2010-11-12T19:47:46.387Z
Noam
<p>There is in fact a lot of theoretical work in this area starting with the work of <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.120.983" rel="noreferrer">Mehta, Saberi, Vazirani, Vazirani'2005</a>. More examples of papers dealing with clickthrough rates and inputs from random permutations include <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.87.9205" rel="noreferrer">Goel-Mehta'08</a>, <a href="http://arxiv.org/abs/cs.DS/0612072" rel="noreferrer">Muthukrishnan-Pal-Svitkina'07</a>.</p>

<p>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.</p>

CC BY-SA 2.5
2010-11-12T18:33:23.300Z
2010-11-12T18:33:23.300Z
Shiva Kintali
<p>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 <a href="http://en.wikipedia.org/wiki/Vickrey_auction" rel="nofollow">second price auction</a> 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 <a href="http://arxiv.org/abs/1002.4058" rel="nofollow">optimal contextual bandit algorithm</a> 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 "<a href="http://research.microsoft.com/en-us/um/people/slivkins/ec10-subm134.pdf" rel="nofollow">Truthful Mechanisms with Implicit Payment Computation</a>."</p>

CC BY-SA 2.5
2010-11-13T17:19:13.783Z
2010-11-15T17:40:47.140Z
2010-11-15T17:40:47.140Z
Lev Reyzin
<p>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...</p>

<p>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.</p>

<p>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.</p>

<p>Are you aware of some theoretical work related to this problem?</p>

CC BY-SA 2.5
2010-11-12T16:34:08.597Z
I think it's perfectly appropriate.
Suresh Venkat
<reference-request><lg.learning><gt.game-theory>
Keyword selection problem in search engine marketing auction
Sylvain Peyronnet
# Keyword selection problem in search engine marketing auction

(Asked by: username_0 on 2010-11-12)

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?

**Tags:** reference-request, lg.learning, gt.game-theory
> **Comments:**
> **username_1**: I think it's perfectly appropriate.  

---

## 3 answers

### Answer by username_4 on 2010-11-13. Score: 8 | Accepted answer

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](http://en.wikipedia.org/wiki/Vickrey_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](http://arxiv.org/abs/1002.4058) 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](http://research.microsoft.com/en-us/um/people/slivkins/ec10-subm134.pdf)."


---

### Answer by username_2 on 2010-11-12. Score: 8

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.


---

### Answer by username_3 on 2010-11-12. Score: 7

There is in fact a lot of theoretical work in this area starting with the work of [Mehta, Saberi, Vazirani, Vazirani'2005](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.120.983). More examples of papers dealing with clickthrough rates and inputs from random permutations include [Goel-Mehta'08](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.87.9205), [Muthukrishnan-Pal-Svitkina'07](http://arxiv.org/abs/cs.DS/0612072).

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.


---

