How Does Facebook Decide Which Ads to Show?

The clickmaniac project raised the question of how Facebook decides which ads to show when and to whom. Facebook is given a set of advertisers and their bids for various ads, each targeted towards a particular demographic. Facebook also knows each advertiser's daily budget. The best way to go about showing ads using this information is not clear. I attempted to do some research and see if I could provide some insight as to how Facebook does it.

First I found the site http://www.facebook.com/help/?faq=173594992698822, a site run by Facebook that provides some explanation as to how their ad auctions work. The key features are as follows. As we talked about in class they use some variant of a second-price auction in which each advertiser pays the minimum amount they would have needed to bid in order to win their slot. However, they also take into account the ad's performance. It is not specified how exactly this is done but they say that ads that have a high clickthrough rate in the past are more likely to be shown again. This explains why a tactic that I thought up for clickmaniac doesn't work. I tried bidding a very high price per click for a very unpopular ad that was targeted towards the kind of people who would not want to click on it. The hope was that the high bid would cause it to "win the auction" and get shown the most. Since no one would click on it, it wouldn't cost us anything. As expected no one clicked on the ad, but it wasn't shown nearly as much as we had hoped it would be, probably because Facebook realized it had a low clickthrough rate. It of course makes sense for Facebook to show ads with high clickthrough rate (at least if advertisers are paying per click) in order to maximize their profit.

Another source I looked at is the news article www.stanford.edu/~saberi/sara.pdf. It details a theoretical solution to the ad auction problem (in the context of Google) proposed by a group of computer science researchers. They made an analogy between the ad auction problem and a problem called the online matching problem which they had already studied. The online matching problem is as follows:

"A matchmaker and n boys are gathered in a room, in which n girls appear, one at a time. Each girl has a list of boys who are acceptable to her, which she reveals to the matchmaker as she appears. The matchmaker matches her to one of the boys on her list or, if they are all taken, leaves her unmatched. The matchmaker’s goal is to maximize the total number of matches."

In the analogy, the girls are the advertisers and the boys are the advertising slots. The difficult part of the problem is the incomplete information -- the fact that the matchmaker doesn't know who is on each girl's list until it's that girl's turn to be matched. Using knowledge of the optimal solution to the online matching problem (which is detailed in the article), the researchers were able to derive the optimal solution for their formulation of the ad auction problem. An interesting attribute of the solution is that it depends both on the advertisers' bids and the fraction of their budget that is left. The algorithm favors displaying ads of advertisers who have a lot of budget left. I can think of one intuitive explanation for this. Each advertiser provides various ads that can be shown upon various Google search queries. Having many diverse advertisers allows Google to show ads upon almost any query. However, once an advertiser's budget is used, Google can no longer make money on that advertiser's ads and has less flexibility. If too many advertisers run out of budget, Google may be left with no ads to show on a particular query. (This is analagous to leaving a girl unmatched in the online matching problem.) It is in Google's favor to resist depleting any advertiser's budget in order to keep its options open for continuing to solve the matching problem in the future.

Sources:
http://www.facebook.com/help/?faq=173594992698822
www.stanford.edu/~saberi/sara.pdf