lottery.md

Lottery Selection

Overview

• Broadly speaking a lottery is a game in which the players each receive a number of lottery balls with their name on them. Those balls are placed in a sack. A ball is selected from the sack at random. The winner is the player whose name is on the selected ball.

• In the adserver the players are ads in the lottery priority that have passed the filtering phase (ie. the ads in the priority whose targeting criteria match the properties of the user and request context for the decision).

• The number of lottery balls an ad can play in the lottery is given by its weight.

• There is a system-wide constant, max_weight — a scaling constant related to the system's desired sensitivity and numerical stability requirements.

• For an ad with a percentage goal the weight is a fixed percentage of the max weight (ie. weight = goal / 100 * max_weight, rounded to the nearest integer). Note that the goal may be greater than 100.

• For an ad with a goal other than a percentage goal (eg. impression goal, click goal, revenue goal, etc.) the weight is managed by a feedback system to regulate the rate at which the ad serves so that it may achieve its goal. The weight is normally an integer in the interval [0, max_weight], however it may exceed max_weight by up to 200% in some cases (eg. when the ad is nearing its end date and is projected to underserve significantly).

• If the total number of balls in the sack is less than max_weight after all ads have added their balls, "no-winner" balls are added to the sack until the total number of balls reaches max_weight. If a no-winner ball is selected in a lottery drawing there is no winner for that lottery.

Example Scenario 1

max_weight = 10 // chosen to be small enough to fit in this diagram

  A.weight = 3  // ad A
  B.weight = 2  // ad B
  C.weight = 1  // ad C

  Z.weight = max(0, 10 - 3 - 2 - 1)
           = max(0, 4)
           = 4  // no-winner

Total number of balls: 3 + 2 + 1 + 4 = 10

Lottery:   1   2   3   4   5   6   7   8   9  10
         +---+---+---+---+---+---+---+---+---+---+
         | A | A | A | B | B | C | Z | Z | Z | Z |
         +---+---+---+---+---+---+---+---+---+---+
                                       |
+--------------------------------------+
|
A random number is selected between 1 and 10 (say 8). The selected ball
belongs to Z, the no-winner player, so none of the ads won this lottery.

Example Scenario 2

max_weight = 10 // chosen to be small enough to fit in this diagram

  A.weight = 3  // ad A
  B.weight = 2  // ad B
  C.weight = 8  // ad C

  Z.weight = max(0, 10 - 3 - 2 - 8)
           = max(0, -3)
           = 0  // no-winner

Total number of balls: 3 + 2 + 8 = 13

Lottery:   1   2   3   4   5   6   7   8   9  10  11  12  13
         +---+---+---+---+---+---+---+---+---+---+---+---+---+
         | A | A | A | B | B | C | C | C | C | C | C | C | C |
         +---+---+---+---+---+---+---+---+---+---+---+---+---+
                                       |
+--------------------------------------+
|
A random number is selected between 1 and 13 (say 8). The selected ball
belongs to ad C, so ad C won this lottery.

Notes

• Ads with percentage goals in a lottery priority are given special preference — these ads are entered into a separate lottery drawing which excludes non-percentage goal ads. Only when this lottery fails to select a winner is a second lottery conducted for the non-percentage goal ads.