Real-Time Bidding (RTB) has become a relevant paradigm in display advertising. It mimics stock exchanges and utilizes computer algorithms to buy and sell ads in real-time automatically. Imagine that you have to participate in $N \gg 1$ of those online ad auctions with a limited bidding budget. The task is to create such a bidding strategy that you can win some of them, and that the placed ads generate at least $N_C$ clicks. That should be done by spending as little money as possible. In the following, we will look at a possible solution to this problem.
1. Real-Time Bidding ecosystem
2. Problem description
3. Solutions to the optimization problem
We will consider an analytically solvable case that can be used to check if our numerical solution is implemented correctly. Then we will briefly describe some of the problems that arise if we apply this approach to real data: the large system of equations that have to be solved and the approximation of the winning bid probability distribution by using a finite number of observations. A numerical approach that addresses these two problems can be found in this Github repository.
3.1 Single click-through probability and winning bid distribution
We will assume that the winning bid distribution for every auction n can be parametrized by an exponential distribution: \begin{align} p_{S_n}(s) & = \alpha_n e^{-\alpha_n s} \hspace{4.0mm} \alpha_n > 0. \end{align} It follows that the probability to win auction $n$ if our bid is $x_n$ is given by: \begin{align} p_{W_n | x_n} (x_n) & = \int^{x_n}_{0} p_{S_n} (s) ds \nonumber \\ & = \int^{x_n}_{0} \alpha_n e^{-\alpha_n s} ds \nonumber \\ & = 1 - e^{-\alpha_n x_n}. \end{align} To make the problem analytically solvable we have assumed that the probability distribution functions to win the auctions $1, \ldots N$ and the corresponding user click-through probabilities are all the same: \begin{align} \alpha_n & = \alpha, & n\in \{ 1, \ldots N \} \\ p_{C_n} & = p_C & n\in \{ 1, \ldots N \}. \end{align} By applying the method of the Lagrange multipliers, we obtain the optimal bid price $x_n$ and the expected amount of money spent to be: \begin{align} x_n & = \frac{1}{\alpha} \ln \Big( \frac{N \cdot p_C}{ N \cdot p_C - N_C } \Big), \hspace{4.0mm} n\in \{ 1, \ldots N \} \\ \mathbb{E}(M) & = \frac{N_C}{p_C} \frac{1}{\alpha} \ln \Big( \frac{N \cdot p_C}{ N \cdot p_C - N_C } \Big). \end{align} In real situations, we expect that $N \cdot p_c \gg N_c$ (i.e. we have to win only a small fraction of all auctions to achieve the goal of getting $N_c$ clicks) which allows us to expand $\log ()$ around $1$: \begin{align} x_n & \approx \frac{1}{\alpha} \frac{N_C}{N \cdot p_C}, \\ \mathbb{E}(M) & \approx \frac{1}{\alpha}\frac{N^2_C}{N \cdot p^2_C} . \end{align} Since $1/\alpha$ is the mean value of the exponential distribution function and $N_c/(N \cdot p_c) \ll 1$, it follows that $x$ is a very low value, i.e. we are participating at every auction with a very low bid price. We may speculate that a similar result is obtained if we use different probability distribution functions for the prices of successful bids, i.e. that we will only be interested in the left side of the distribution because that is where the optimal value is located. This also implies that we should have a very precise description of $p_{W|x}$ for a small $x$, which in practice could be a difficult task to achieve.
3.2 Multiple click-through probabilities and winning bid distributions
The general case where each auction is described by a unique probability distribution function and where the click-through probabilities can be different for each $n$ can be solved numerically using the Python scipy library. This approach quickly becomes unfeasible if $N$ is in the order of $10^3$, which is not sufficient for more realistic cases with $N > 10^6$. To make the problem manageable by the python scipy library, we will assume that the winning bid distribution of an auction can be described by one out of $I$ different possible probability distribution functions: \begin{align} \tilde{p}_{S_i}(s) \hspace{5.0mm} i \in \{1, 2, \ldots I \}. \end{align} The same idea can be applied to the click-through probability which can only take $J$ different values: \begin{align} \tilde{p}_{C_j} \hspace{5.0mm} j \in \{1, 2, \ldots J \}. \end{align} If we look closely at the solution to the optimization problem \eqref{eq:lagrange_multipliers}, we see that the optimal bid price is the same for all auctions with the same distribution of successful bids $i$ and the same click-through probability $j$. We will denote this optimal price with $\tilde{x}_{ij}$. With these considerations in mind, the functions $f$, $g$ from the Lagrange optimization problem \eqref{eq:lagrange_multipliers} can be rewritten to: \begin{align} f(\tilde{x}) & = \sum\limits^{I}_{i=1} \sum\limits^{J}_{j=1} N_{ij} \cdot \tilde{x}_{ij} \cdot \tilde{p}_{W_i|\tilde{x}_{ij}} (\tilde{x}_{ij}) , \\ g(\tilde{x}) & = \sum\limits^{I}_{i=1} \sum\limits^{J}_{j=1} N_{ij} \cdot \tilde{p}_{C_j} \cdot \tilde{p}_{W_i|\tilde{x}_{ij}} (\tilde{x}_{ij}) - N_C, \end{align} where $N_{ij}$ is equal to the number of cases where the distribution of successful bids is of type $i$ and the click-through probability is of type $j$. With this simplification, we can numerically solve problems where $I·J <10^3$.
To demonstrate the applicability of this approach, we have considered the case where $I=3$ and $J=2$:
\begin{align}
\tilde{p}_{C_1} & = 0.005, \nonumber \\
\tilde{p}_{C_2} & = 0.01, \nonumber \\
\tilde{p}_{S_i} (s) & = b_i s^{b_i-1} \exp \big(1 +s^{b_i} - \exp(s^{b_i}) \big) \hspace{5.0mm}
b_1 =2, \hspace{1.0mm}
b_2 =4, \hspace{1.0mm}
b_3=6.
\end{align}
The optimal solution is shown in the following figure:
3.3 Obtain probability distribution functions from real data
Under realistic conditions, we have to infer the probability distribution of successful bids from the events (prices of successful bids) in our data. We can count the number of events for a grid of $x$ values and then use spline interpolation as an approximation of the distribution function. We have applied this idea to the previous example, where instead of using the analytical form of the winning bid distribution, we have sampled data points from this distribution. From the table above you can see that the differences between the two solutions are minimal. We must take into account that the number of sampled data points per distribution is in the order of $10^6$. A lower number of sampled data points inevitably leads to a lower accuracy of the spline approximation. We also have to keep in mind that the spline approximation generates a function $h(x)$ whose second derivative $d^2h(x)/dx^2$ is zero at the boundaries of the $x$ grid. This restriction can become problematic for probability distribution functions that do not go to $0$ for $x \rightarrow 0$. One such example is the exponential probability distribution function, where the second derivative at $x = 0$ is: \begin{align} \frac{d^2}{dx^2} \alpha e^{-\alpha x} \Big\vert_{x=0} & = \alpha^3 > 0. \end{align} Another problem is that with the spline approximation we cannot guarantee that the resulting function is non-negative.
Summary
In this article, we have created a simple bidding strategy by assuming that we know the winning bid probability distribution function of each auction and the click-through probability for each advertising event. From the two examples we have considered, we have seen that the optimal solution requires precise knowledge of the left side of the winning bid probability distribution function.
Resources