Advanced Banner-Rotation Algorithms

Question

I'm going to be starting a banner-rotation script soon and I'm getting a bit perplexed over how exactly to develop it. Suppose a client asks for

"10,000 impressions in the next 10 days for $10,000 dollars."

Another client asks for

"1,000 impressions for $100 dollars."

And a third asks for

"1,000 clicks or 10,000 impressions for $5,000."

How exactly do I determine which banner to show upon a page-request? How do I weigh one against another? Clearly the first request is rather important, as I'm expected to serve a set number of impressions within a time-window.

The second client is not nearly as important, as they don't care about a time-window, they just want some face-time.

And the last client wants to place an n or m restraint on the impressions/clicks, making matters slightly more difficult.

I'm already pretty confident that I'll need to abstract some weight from these scenarios to determine who gets the most attention. My question is what type of algorithm could handle this, and secondly how could I serve up banners by weight without always serving up the most important banner with each request?

Answer 1

Use a random-number generator to pick which ad to show, and weight it with a priority for each ad. Set the weighting factor higher for clients that want more impressions or have a deadline. You can increase weighting factor if the time is almost up.

Once a client hits their requested impressions, drop weighting to 0 to prevent their ad from showing.

Default weighting could be 1 or so, with clients being allowed to pay extra to increase priority (without telling them the mechanics -- bill it as "premium" placement, etc).

---

Edit: weighting details

You can make this as simple or complex as you like, but a basic version would include the following terms:

• weight is 0 if ad has reached purchased impressions/clicks
• base weighting (1.0 probably)
• multiply weight by impressions_remaining / TOTAL impressions remaining for all clients
• add a small constant if remaining impressions/clicks is small -- ensures they get the last few ones needed to finish the account
• for deadline clients: add term for (remaining impressions/purchased impressions)/(time left/total time)

The deadline clients should be capped at 90% of all page displays or something to ensure they don't outcompete others. The last term gives the "urgency" for deadline clients -- it goes to infinity as deadline hits, so you should put a condition on the remaining time piece to prevent problems with this.

Answer 2

The difficulty comes from the time constraint more than anything else. I would divide anyone's priority who did not specify a time constraint by 365 (a year), and then use time as part of the weight factor. So:

Client 1 priority: 10000/10 = 1000 
Client 2 priority: 1000/365 ~ 3 
Client 3 priority: 10000/365 ~30

That should get you a fairly decent indicator of priority. Now, you can't mix and match impressions and clicks can you? They either go the impression route or the click route. Seeing as you cannot control click, but you can control impressions (at least, moreso than clicks), I would weigh it according to impressions.

Answer 3

I really like AlbertoPL's time-based approach, but he doesn't factor in the clicks. Its easy to demonstrate pathological cases where clicks are relevant:

• Client A offers $1000 for 1 click or 10,000 impressions
• Client B offers $1000 for 5000 clicks or 10,000 impressions.

Any reasonable person would give the 1-click guy higher priority. The calculation is actually pretty trivial: assume your click-through is 100 impressions per click.

• Client A wants 10,000 impressions or 1 click, so we require a bare minimum of 100 impressions to get paid. At a cost of $1000 per 100 impressions, you can figure that your client is willing to pay $10/impression.

• Client B wants 10,000 impressions or 5000 clicks. 5000 clicks requires 500,000 impressions, we'll clearly meet the 10,000 impression mark before then, so we assume the client is really offering to pay $1000 for 10,000 impressions, or $0.10/impression.

We maximize revenue by maximizing our $$$$$/impression, so client A takes priority. Let's use the figures provided in the OP:

Client 1:

• 10,000 impressions in the next 10 days for $10,000 dollars
• = minimum of 10,000 impressions * $1/impression / 10 days
• = $1000/day

Client 2:

• 1,000 impressions for $100 dollars
• = minimum of 1,000 impressions * $.01/impression / 365 days
• = $0.27/day.

Client 3:

• 1,000 clicks or 10,000 impressions for $5000
• = min(100,000 impressions to get 1,000 clicks, 10,000 impressions) = 10,000 impressions for $5000
• = minimum of 10,000 impressions * $0.5/impression / 365
• = $13.7/day.

Clients take priority based on how much they pay per day.