Ad Serving with a Causal model

Ad selection for n ads is NP hard

When an ad server has n eligible ads for display for k available slots, the possible choices for ad sets becomes exponential. How can the ad server choose the best ad set from so many possibilities? Of course we must use the information available about each ad’s performance and a model to make causal assumptions.  Above is a simple causal model of an ad server.

 

The model shows 6 available ads for display. Each ad has a Click node. In this example revenue is produced when a click occurs on an ad and the revenue is the bid price of the advertiser. So the expected revenue from an ad = Bid  p(Click | Placement) or Bid p(Click | Placement, Context) or Bid p(Click | Placement, Demographics).

 

Our example has simple Ad Serving Policy constraints:

1. No ad can be shown more than once
2. Maximum ads that can be shown is 6 and no less than 1.  1 ≤ AdCount ≤ 6
3. No two ads can be placed in the same position
4. The best Ad has the greatest E[Rev]
5. The best Ad set has the greatest total E[Rev]

 

In this example we have 6 Eligible ads for display. The Table to the right shows the bid and ad Quality, the relative average CTR across all possible placements. Ad C has the greatest expected revenue E[Rev] so it is the “best” ad followed quickly by Ad B. Our worst Ad is A.

 

We can use the causal model to make decisions. What is an efficient process to find the optimum ad set that will produce the greatest revenue? Once evidence (Context and demographics) is known and AdCount is set, the Click node of each ad becomes independent of all other ad Click nodes. As long as AdCount is set Expected Revenue of Ad X, E[Rev(X)] is independent of any other ad’s placement (within the constraints of the ad server).

 

Now any further decision we make for one ad does not effect any other ad (except via Rule 2 and Rule 3 in the Ad Serving Policy). We do not have to re-calculate any E[Rev] inferences.

 

 

 

 

Ad Selection Algorithm

We use this independence to perform 6 decision processes, one for each possible AdCount.

1. For each possible AdCount = 1 to 6;
   1. Do  n = 1 to AdCount:
      1. Find the Ad/Placement with the largest E[Rev].
      2. Do Placement of that Ad. Select ad n for the set.
      3. Eliminate all ads that would now (after decision) violate the serving policy.
   2. Sum the E[Rev] of each ad in the set to get E[Rev(AdCount)].
2. Display Ad Set with the maximum E[Rev(AdCount)]

The table to the right shows ad B selected for placement 3P3 the third position in a set of three. It has the highest E[Rev] of all eligible ads. The gray text are ads eliminated due to the serving Policies (listed above).

 

In this process the we greedily eat up the best ads while eliminating possible server Policy conflicts by eliminating ad eligibility (shown as graying out in right table). This process ends when the 3rd ad is selected. Ad E is selected for placement = 3P2. This completes the ad set.
C
E
B
Total Expected Revenue = $13.01

 

Another algorithm might simply rank order the ads by E[Rev]. The resulting ad set  for AdCount=3 would be:

C
B
E
Total Expected Revenue is $10.76.

 

So against a simple “straw-man” placement process our ad server does better by producing an ad set with higher expected revenue. This process requires more calculations than the straw-man approach, but these calculations are pretty simple when the Node’s data table is available.

 

If an ad’s revenue is driven by Approved users, more complicated inference is performed to find E[Rev] for each possible Ad Placement. In cases like this, the evidence e (Red nodes) are set in the model. Then an inference engine is used to calculate E[Rev] = Bid p(Approved|DO(Ad Placement=x,e) for all Ad Placements.

 

But is this the best possible process of choosing ad sets? Ultimately I would like to devise a server that would use the model to make decisions, but I want to weigh decisions based on Entropy and Entropic forces (or Freedom of Action). Wissner-Gross suggests that we should seek a future with the greatest freedom of action. When we are first presented with a call for ads our Ad Server has no cash, but it does have freedom of action.

 

I need to find how to convert this freedom action into cash or E[Rev] in an ‘intelligent’ manner. Seems that cash is the ultimate freedom of action. It seems to me that when we make ad serving decisions we reduce our freedom of future actions. How do we expend freedom of action( or ‘cash potential’ ?) to gain E[Rev]?

 

Measuring Freedom of Action

 

The Entropy of a Ad Placement node is a measure of freedom of action. The sum Entropy of all Ad Placement nodes is then the Total freedom of action of the ad server.

 

Can anyone suggest improvements?