Revenue and Reserve Prices in a Probabilistic Single Item Auction

Abstract

We investigate the effect of limiting the number of reserve prices on the revenue in a probabilistic single item auction. In the model considered, bidders compete for an impression drawn from a known distribution of possible types. The auction mechanism sets up to $\ell$ reserve prices, and each impression type is assigned the highest reserve price lower than the valuation of some bidder for it. The bidder proposing the highest bid for an arriving impression gets it provided his bid is at least the corresponding reserve price, and pays the maximum between the reserve price and the second highest bid. Since the number of impression types may be huge, we consider the revenue $R_{\ell }$ that can be ensured using only $\ell$ reserve prices. Our main results are tight lower bounds on $R_{\ell }$ for the cases where the impressions are drawn from the uniform or a general probability distribution.

1 Introduction

Real-time bidding has become a standard tool in advertising, especially in the context of ad exchanges [10]. A major setting of interest in this regard is the multi-billion-dollar display advertisement market, where publishers (such as MSN and Yahoo) attempt to maximize the revenue they collect from the advertisers (say, Nike or Coca-Cola) by wisely targeting their ads at the right users. For example, an ad referring to the surfing lifestyle on the sunny beaches of the Pacific Ocean may be most valuable when targeted at a teenager from California; perhaps less so when targeted at a 10 years old from Oregon; and even less when targeted at older folks in areas that are far from the ocean. In this setting each advertiser has his own valuation for each user type, and the different user types appear according to some probability distribution.

The above type of situations has been recently formalized and studied [3, 9] in a framework termed a probabilistic single-item auction, in which m bidders participate in a second-price auction for a single item, which is chosen randomly from a set of n indivisible goods according to a commonly known probability distribution $p \in \varDelta (n)$. This stylized model captures the above advertising setting, where goods are in fact user impressions in a publisher’s site.

Existing ad exchanges usually perform second price auction with reserve prices. A reserve price is a minimum price set by the auctioneer. If no bid exceeds the reserve price, the item is left unsold. Otherwise, the player with the highest bid gets the item for the price of the second highest bid, but no less than the reserve price. Reserve prices are a major tool for revenue optimization [11], and were shown also to be a powerful tool in Internet settings [12].

In this paper we extend the framework of [3, 9] by allowing actions with reserve prices. Assuming familiarity of the auctioneer with the bidders’ values, which is a standard assumption in the above framework,¹ allowing an independent reserve price for each one of the possible goods would allow the auctioneer to get for each good the maximum valuation of any bidder. However, realistic ad exchanges usually segment the set of possible goods, and set a uniform reserve price for all the goods in a given segment. Often each segment represents a logical category. For example, all user impressions related to cars are assigned the same reserve price. Hence, the number of different reserve prices is often small in comparison to the number of possible goods (which can be very large as every combination of user attributes defines a different good). Our main objective in this paper is to investigate the effect of limiting the number of different reserve prices on the revenue.

More formally, given an instance of an auction,² let $R_\ell$ be the maximum expected revenue that can be achieved using up to $\ell$ different reserve prices. Notice that $R_\infty = R_n$ is the optimal value that can be achieved by assigning an independent reserve price for each good. We are interested in bounding the ratio $R_\ell {/} R_\infty$ as a function of $0 \le \ell \le n$, i.e., determining the fraction of $R_\infty$ that is guaranteed to be achieved by a second price auction using up to $\ell$ reserve prices.

A particularly interesting case of our problem is when the probability distribution over the goods is uniform. This distribution corresponds not only to the case of selling a particular good selected according to the uniform probability distribution, but also to that where the aim is to sell a single instance of each good. This case is related to the famous bundling problem considered by a rich literature in economics originated in [13] (see, e.g., [4] and the references therein for more recent works on this problem).

Observe that $R_\ell \le R_\infty$ because having more reserve prices can only improve the revenue. Our main results are tight bounds on the lowest value $R_\ell {/} R_\infty$ can take as a function of $\ell$ for both general and uniform probability distributions. The bounds we prove are summarized in Table 1. Note that although, for the proofs, it is convenient to state these bounds for the case of uniform probabilities separately for small values of $\ell$ and for large ones, the table actually shows that for uniform probabilities and every possible value of $\ell$, $R_{\ell }$ is always at least $(1-o(1))\frac{\ell }{\ln n} (1-e^{-\ln n/\ell })R_{\infty }$, and this is tight. Here and throughout the paper, the o(1)-term tends to 0 as n tends to infinity.

Table 1 Bounds on $R_\ell / R_\infty$

In particular, the above bounds imply that for uniform probabilities $c \cdot \ln n$ reserve prices are enough to guarantee that $R_\ell$ is at least $(1 - {\varepsilon }) \cdot R_\infty$ for an arbitrary small constant ${\varepsilon }> 0$, provided $c=c({\varepsilon })$ is chosen appropriately (and the best possible value of this $c({\varepsilon })$ can be computed as well). Our results are constructive, but we believe they are also interesting as existential results, bounding the guarantee that can be ensured with a given number of reserve prices. We stress that all the results in Table 1 are tight up to low order terms for every value of $\ell$. The number in parentheses beside each result in the table is the number of the theorem proving this result.

The results given in Table 1 are proved in Sect. 3. On the algorithmic side, we describe in Sect. 4 an efficient algorithm for calculating the optimal set of reserve prices. One can think of the previous results as lower bounds on the performance of this algorithm.

Additional related work The related work on reserve prices in economics is huge, and it would be impossible to do justice with all of its aspects. Let us just emphasize that it deals with both theory extending upon Myerson work (see, e.g., [2, 6, 7]) and empirical issues (see, e.g., [1, 8]) under a variety of assumptions. The importance of reserve prices has been in particular noticed by the multi-agent systems community, and delicate aspects of the design of reserve prices have been studied, e.g., in two items VCG-like auctions [14] and in realistic single item auctions [15]. The design of reserve prices in the context of segmentation and its combinatorial structure, which are central to this work, were not studied to the best of our knowledge.

2 Model

In our model there are n impression types and m bidders. Each bidder $d_j$ has a non-negative value v(i, j) for every impression type $t_i$. Every arriving impression is of type $t_i$ with probability $p_i$ (hence, $\sum _{i = 1}^n p_i = 1$). The auction mechanism can set up to $\ell$ reserve prices $r_1, r_2, \ldots , r_\ell$, where $\ell$ is a parameter of the mechanism. Every impression type $t_i$ is assigned the highest reserve price which is still lower or equal to v(i, j) for some j (0 if there is no such reserve price). Let us denote this reserve price by $r'_i$. Whenever an impression whose type $t_i$ arrives, the bidders are notified about its exact type, and then each bidder $d_j$ declares a bid b(i, j). Let $d_h$ and $d_s$ be the bidders who gave the highest and second highest bids, respectively (if there is only one bidder, we assume $d_s$ is a dummy bidder with a bid of 0). The bidder winning the good and the payment are determined by the following rules:

• If $b(i, h) < r'_i$, no bidder gets the item.

• If $b(i, s) < r'_i \le b(i, h)$, bidder $d_h$ gets the item and pays $r'_i$.

• If $r'_i \le b(i, s)$, bidder $d_h$ gets the item and pays b(i, s).

One can observe that the above mechanism is truthful for every given choice of reserve prices, and therefore, given an impression of type $t_i$, declaring a bid of $b(i, j) = v(i, j)$ is a (weakly) dominant strategy for bidder $d_j$.³ To present our results and analyze them, we need the following notation:

$R_\ell$::

The expected revenue achieved by the above auction mechanism using the best choice of up to $\ell$ reserve prices.

$h_i$::

The maximal value given by any bidder for impressions of type $t_i$. Unless otherwise is explicitly stated, we assume, without loss of generality, $h_1 \ge h_2 \ge \cdots , h_n$.

The following formula for $R_\infty$ follows immediately from the definitions, and is used often in our proofs.

Observation 1

$R_\infty = \sum _{i = 1}^n h_i \cdot p_i$.

Figure 1 depicts an example demonstrating our notation.

Fig. 1

Example of an auction. Matrix b gives the bids—the entry at row j and column i is the bid of bidder $d_j$ for impression type $t_i$. The numbers below matrix b are the $h_i$ values corresponding to the various impression types. Notice that the $h_i$ values are ordered in a non-increasing order following our assumption. The table on the right gives the values of $R_\ell$ for $\ell \in \{1, 2, 3, \infty \}$ and the set of reserve prices yielding each value, assuming uniform probabilities

3 Bounding $R_\ell / R_\infty$

Our aim in this section is to find out how much lower can $R_\ell$ be in comparison to $R_\infty$. Theorem 1 considers the relation of $R_\infty$ and $R_\ell$ for uniform probabilities and relatively small values of $\ell$, while Theorem 2 does the same for large values of $\ell$. General probabilities are treated by Theorem 3.

Lemma 1

Assume uniform probabilities, $R_1 \ge R_\infty / H_n$, where $H_n$ is the nth harmonic number.

Proof

By choosing a single reserve price of $h_i$, the auctioneer can get a revenue of at least $h_i$ from impressions of types $t_1, t_2, \ldots , t_i$, resulting in a total revenue of at least $i \cdot h_i {/} n$. If for some i, $i \cdot h_i {/} n \ge R_\infty {/} H_n$, then we are done. To complete the proof, let us show that assuming $h_i {/} n < R_\infty {/} (i \cdot H_n)$ for every i leads to a contradiction. Summing our assumption over all i, we get:

$$\begin{aligned} \sum _{i = 1}^n h_i / n < \sum _{i = 1}^n R_\infty / (i \cdot H_n) = R_\infty / H_n \cdot \sum _{i = 1}^n \frac{1}{i} = R_{\infty }. \end{aligned}$$

However, the left hand side of the inequality from the previous line is also $R_\infty$, which is a contradiction. $\square$

Using the above lemma, we can get a general theorem for $R_\ell$, when $\ell$ is not too large (compared to n).

Theorem 1

Assume uniform probabilities. For every $1 \le \ell \le \ln ^{1/2-{\varepsilon }} n$, where ${\varepsilon }> 0$ is an arbitrary small constant, it always holds that $R_\ell \ge (1 - o(1)) \cdot \ell /H_n \cdot R_\infty$, where $H_n$ is the nth harmonic number. Moreover, there exists an instance with uniform probabilities for which $R_\ell \le \ell /H_n \cdot R_\infty$.

Proof

We begin by proving the first part of the theorem. Note that we may and will assume throughout the proof that n is sufficiently large. Define $c = \ln ^{\varepsilon }n$, and observe that $c^\ell \le n$. If $\sum _{i = 1}^{c^\ell } h_i / n \ge R_\infty / c$, then by Lemma 1, a single reserve price can be used to get a revenue of at least:

$$\begin{aligned} \frac{\sum _{i = 1}^{c^\ell } h_i / n}{H_{c^\ell }} \ge {}&(1 - o(1)) \cdot \frac{R_\infty / c}{\ell \ln c} \ge (1 - o(1)) \cdot \frac{\ell \cdot R_\infty }{\ln ^{1 - 2{\varepsilon }} n \cdot c \cdot \ln c}\\ ={}&(1 - o(1)) \cdot \frac{\ell \cdot R_\infty }{\ln ^{1 - {\varepsilon }} n \cdot \ln \ln ^{\varepsilon }n} = (1 - o(1)) \cdot \frac{\ln ^{\varepsilon }n}{\ln \ln ^{\varepsilon }n} \cdot \frac{\ell }{\ln n} \cdot R_\infty \\ \ge {}&(1 - o(1)) \cdot \frac{\ell }{H_n} \cdot R_\infty , \end{aligned}$$

The proof for this case is complete by observing that $\ell$ reserve prices are always at least as good as 1. Thus, we can assume from now on that $\sum _{i = 1}^{c^\ell } h_i / n < R_\infty / c$.

Let us now define n different possible sets of reserve prices. To do that, we need to define $r_{k, i}$ as follows:

$$\begin{aligned} r_{k, i} = {\left\{ \begin{array}{ll} h_{\lfloor i \cdot c^{k - 1} \rfloor } &{}\quad \text{ if } \,i \cdot c^{k - 1} \le n,\\ 0 &{}\quad \text{ otherwise. } \end{array}\right. } \end{aligned}$$

The ith set of reserve prices is simply $L_i = \{r_{k, i} | 1 \le k \le \ell \}$. By the definition of $R_\ell$, no one of the above sets yields a revenue of more than $R_\ell$, hence, it must be that for every $1 \le i \le n$:

$$\begin{aligned}&\frac{\lfloor i \cdot c^0 \rfloor \cdot r_{i, 1}}{n} + \sum _{k = 2}^\ell \frac{[\lfloor i \cdot c^{k - 1} \rfloor - \lfloor i \cdot c^{k - 2} \rfloor ] \cdot r_{i, k}}{n} \le R_\ell \nonumber \\&\quad \Rightarrow {} \frac{i \cdot r_{i, 1}}{n} + \frac{i \cdot (c - 2)}{n} \cdot \sum _{k = 2}^\ell c^{k - 2} \cdot r_{i, k} \le R_\ell \nonumber \\&\quad \Rightarrow {} \frac{r_{i, 1}}{n} + \frac{c - 2}{n} \cdot \sum _{k = 2}^\ell c^{k - 2} \cdot r_{i, k} \le \frac{R_\ell }{i}. \end{aligned}$$

(1)

Notice that $\sum _{i = 1}^n r_{i, 1} = \sum _{i = 1}^n h_i = n \cdot R_\infty$. Similarly, by the fact that the h’s form a non-increasing series, we also have for every $2 \le k \le \ell$:

$$\begin{aligned} \sum _{i = 1}^n r_{i, k} ={}&\sum _{i = 1}^{\lfloor n / c^{k - 1} \rfloor } h_{\lfloor i \cdot c^{k - 1} \rfloor } \ge \frac{\sum _{i = c^{k - 1}}^{n} h_i}{c^{k - 1}} = \frac{\sum _{i = 1}^{n} h_i - \sum _{i = 1}^{c^{k - 1} - 1} h_i}{c^{k - 1}}\\ \ge {}&\frac{n \cdot R_\infty - n \cdot R_\infty / c}{c^{k - 1}} = n \cdot R_\infty \cdot \frac{1 - 1/c}{c^{k - 1}}, \end{aligned}$$

where the last inequality follows from our assumption that $\sum _{i = 1}^{c^\ell } h_i / n < R_\infty / c$. Adding up Eq. (1) for every $1 \le i \le n$, and applying the last observation to the result, we get:

$$\begin{aligned} R_\infty +&(c - 2) \cdot \sum _{k = 2}^\ell c^{k - 2} \cdot \left[ R_\infty \cdot \frac{1 - 1/c}{c^{k - 1}}\right] \le R_\ell \cdot H_n\\ \Rightarrow {}&R_\infty + (\ell - 1) \cdot (1 - 2/c)(1 - 1/c) \cdot R_\infty \le R_\ell \cdot H_n\\ \Rightarrow {}&R_\infty + (\ell - 1) \cdot (1 - 2/c)^2 \cdot R_\infty \le R_\ell \cdot H_n\\ \Rightarrow {}&R_\infty \cdot \ell \cdot (1 - 2/c)^2 \le R_\ell \cdot H_n \\ \Rightarrow {}&R_\ell \ge (1 - 2/c)^2 \cdot \frac{\ell }{H_n} \cdot R_\infty = (1 - o(1)) \cdot \frac{\ell }{H_n} \cdot R_\infty . \end{aligned}$$

We now get to the second part of the theorem. Consider an instance with uniform probabilities and a single bidder whose value for impressions of type $t_i$ is 1 / i. In this instance $h_i = 1/i$ for every $1 \le i \le n$, and thus, $R_\infty = \sum _{i = 1}^n (1/i)(1/n) = H_n / n$. Let us upper bound $R_\ell$. Let $r_1, r_2, \ldots , r_\ell$ be the optimal choice of reserve prices for the instance constructed. Clearly we can assume without loss of generality that every reserve price in this optimal set is equal to $h_i$ for some $1 \le i \le n$, and is, therefore, different from 0. Moreover, we can also assume that every reserve price is unique, i.e., no two reserve prices are equal (if $r_{i_1}$ and $r_{i_2}$ are two identical reserve prices, then replacing $r_{i_1}$ with an arbitrary other value can only increase the revenue).

Since there is only a single bidder, the revenue of the auctioneer from every impression type $t_i$ must be equal to either 0 or some reserve price. Let us construct for every reserve price $r_k$ a set $T_k$ containing all impression types which yield a revenue of $r_k$. $R_\ell$ can be calculated using the following formula: $R_\ell = n^{-1} \cdot \sum _{k = 1}^\ell |T_k| \cdot r_k$. Consider some reserve price $r_k$. We already know $r_k$ is equal to $h_i$ for some $1 \le i \le n$. Thus, the set $|T_k|$ can contain at most the i elements of values $1, 1/2, \ldots , 1/i$. Hence, $|T_k| \cdot r_k \le i \cdot (1/i) = 1$. Plugging this into the previous formula yields:

$$\begin{aligned} R_\ell \le \frac{1}{n} \cdot \sum _{k = 1}^\ell 1 = \frac{\ell }{n} = \frac{\ell }{H_n} \cdot R_\infty . \end{aligned}$$

$\square$

The following theorem bounds the ratio $R_\ell / R_\infty$ for large values of $\ell$.

Theorem 2

Assume uniform probabilities. Then, for every $\omega (1) \le \ell \le n$,

$$\begin{aligned} R_\ell \ge (1 - o(1)) \cdot c\left( 1 - e^{-1/c}\right) \cdot R_\infty , \end{aligned}$$

where $c = \ell / \ln n$. Moreover, there exist an instance for which

$$\begin{aligned} R_\ell \le (1 + o(1)) \cdot c\left( 1 - e^{-1/c}\right) \cdot R_\infty . \end{aligned}$$

Before getting to the proof of the theorem, we need the following lemma.

Lemma 2

For every choice of $1 \ge r_1 > r_2 > \cdots > r_\ell \ge 1/n$,

$$\begin{aligned}&r_1 \cdot \lfloor 1/r_1 \rfloor + \sum _{k = 1}^{\ell - 1} r_{k + 1} \cdot (\lfloor 1/r_{k + 1} \rfloor - \lfloor 1/r_k \rfloor )\\&\quad \le {} 1 + (\ell - 1) \left( 1 - n^{-1/(\ell -1)} \right) . \end{aligned}$$

Proof

Notice that the expression on the left hand side of the above inequality is upper bounded by:

$$\begin{aligned} r_1 \cdot 1/r_1 + \sum _{k = 1}^{\ell - 1} r_{k + 1} \cdot (1/r_{k + 1} - 1/r_k) = 1 + \sum _{k = 1}^{\ell - 1} \left( 1 - r_{k + 1}/r_k \right) . \end{aligned}$$

(2)

Let $1 \ge r'_1 > r'_2 > \cdots > r'_\ell \ge 1/n$ be the $\ell$ values maximizing (2). The derivative of (2) by $r_1$ is: $\partial [-r_2/r_1] / \partial r_1 = r_2/r_1^2$, which is always positive. Thus, the value of $r'_1$ must be 1, the largest value it can take. Next, the derivative of (2) by $r_\ell$ is: $\partial [- r_\ell /r_{\ell - 1}] / \partial r_\ell = - 1/r_{\ell - 1}$, which is always negative. Thus, the value of $r'_\ell$ must be 1 / n, the smallest value it can take. Finally, the derivative of (2) by $r_k$, for $1 < k < \ell$ is:

$$\begin{aligned} \frac{\partial [- r_{k + 1}/r_k - r_k/r_{k - 1}]}{\partial r_k} = r_{k + 1}/r_k^2 - 1/r_{k - 1}, \end{aligned}$$

which is zero for $r_k = \sqrt{r_{k + 1} r_{k - 1}}$, negative for larger values and positive for small values. Thus, it must be that $r'_k = \sqrt{r'_{k + 1} r'_{k - 1}}$, and after rearranging: $r'_k / r'_{k - 1} = r'_{k + 1} / r'_k$. Clearly, this implies that the $r'_k$’s form a geometric series, i.e., $r'_k = n^{-(k-1)/(\ell -1)}$. Plugging this into (2) gives:

$$\begin{aligned} 1 + \sum _{k = 1}^{\ell - 1} (1 - r_{k + 1}/r_k) \le {}&1 + \sum _{k = 1}^{\ell - 1} \left( 1 - n^{-k/(\ell -1)} / n^{(k-1)/(\ell -1)} \right) \\ ={}&1 + \sum _{k = 1}^{\ell - 1} \left( 1 - n^{-1/(\ell -1)} \right) = 1 + (\ell - 1) \cdot \left( 1 - n^{-1/(\ell -1)} \right) . \end{aligned}$$

$\square$

We are now ready to prove Theorem 2.

Proof of Theorem 2

We begin by proving the first part of the theorem. Let $b = \lceil \ell (1 + \ln \ln n / \ln n) \rceil + 1$. We first lower bound $R_b$, and then show how to translate this lower bound into a lower bound on $R_\ell$. Let $B = \{t_i ~|~ h_i \le h_1 \cdot e^{(1-b)/c}\}$ be the set of impression types with very low value (compared to $h_1$). Observe that the total contribution to $R_\infty$ of these impression types is only:

$$\begin{aligned} n \cdot \left( h_1 \cdot e^{(1-b)/c}\right) \big / n \le h_1 \cdot e^{-(\ln n + \ln \ln n)} = h_1 \cdot n^{-1} \cdot \ln ^{-1} n \le R_\infty \cdot \ln ^{-1} n. \end{aligned}$$

Hence, we can upper bound $R_\infty$ by:

$$\begin{aligned} R_\infty \le \sum _{i \not \in B} h_i \big / n + R_\infty \cdot \ln ^{-1} n \Rightarrow R_\infty \le \frac{\sum _{i \not \in B} h_i / n}{1 - \ln ^{-1} n}. \end{aligned}$$

Let x be a uniformly chosen random number from the range [0, 1]. For every $1 \le j \le b$, let us define a set $S_j = \{t_i \not \in B | h_1 \cdot e^{(2 - j - x)/c} \ge h_i > h_1 \cdot e^{(1 - j - x)/c}\}$. Observe that every impression type outside of B belongs to exactly one set $S_j$. Since we are lower bounding $R_b$, we should define b reserve prices. Thus, let us define the jth reserve price, for every $1 \le j \le b$, to be $r_j = h_1 \cdot e^{(1 - j - x)/c}$. Observe that, under these reserve prices, all impression types of a set $S_j$ pay at least $r_j$. Using this observation, we can now calculate the expected value of $R_b$ (recall that x is a random number). Let $y_i$ be the value for which $h_i = h_1 \cdot e^{(1-y_i)/c}$. Impression type $t_i$ belongs to set $S_{\lceil y_i \rceil }$ if $x \le 1 + y_i - \lceil y_i \rceil$, and belongs to $S_{\lceil y_i \rceil - 1}$ otherwise. Thus, the expected contribution to $R_b$ of $t_i$ is:

$$\begin{aligned}&\int _0^{1 + y_i - \lceil y_i \rceil } h_1 \cdot e^{(1 - \lceil y_i \rceil - x)/c} dx + \int _{1 + y_i - \lceil y_i \rceil }^1 h_1 \cdot e^{(2 - \lceil y_i \rceil - x)/c} dx\\&\quad ={} \left. -h_1c \cdot e^{(1 - \lceil y_i \rceil - x)/c} \right| _0^{1 + y_i - \lceil y_i \rceil } - \left. h_1c \cdot e^{(2 - \lceil y_i \rceil - x)/c} \right| _{1 + y_i - \lceil y_i \rceil }^1\\&\quad ={} h_1c \cdot \left[ e^{(1 - \lceil y_i \rceil )/c} - e^{-y_i/c}\right] + h_1c \cdot \left[ e^{(1-y_i)/c} - e^{(1 - \lceil y_i \rceil )/c}\right] \\&\quad ={} h_1c \cdot e^{-y_i/c} \cdot (e^{1/c} - 1) = h_i \cdot c\left( 1 - e^{-1/c}\right) . \end{aligned}$$

Hence, by the linearity of the expectation, the total expected contribution to $R_b$ from impression types outside of B is at least: $c(1 - e^{-1/c}) \cdot \sum _{i \not \in B} h_i/n$. Thus, there must exist a set of b reserve prices which proves that: $R_b \ge c(1 - e^{-1/c}) \cdot \sum _{i \not \in B} h_i/n$. Recall now that we actually need to lower bound $R_\ell$. However, by averaging we get:

$$\begin{aligned} R_\ell&\ge {} \frac{\ell }{b} \cdot R_b \ge \frac{\ell }{b} \cdot c\left( 1 - e^{-1/c}\right) \cdot \sum _{i \not \in B} h_i/n \\&\ge \frac{\ell \cdot c\left( 1 - e^{-1/c}\right) }{\lceil \ell (1 + \ln \ln n / \ln n) \rceil + 1} \cdot (1 - \ln ^{-1} n) \cdot R_\infty \\&>{} \frac{\ell \cdot (1 - \ln ^{-1} n)}{\ell (1 + \ln \ln n / \ln n) + 2} \cdot c\left( 1 - e^{-1/c}\right) \cdot R_\infty \\&= \frac{1 - o(1)}{1 + o(1) + 2/\ell } \cdot c\left( 1 - e^{-1/c}\right) \cdot R_\infty . \end{aligned}$$

Recalling that $\ell = \omega (1)$, we get $2/\ell = o(1)$, and the first part of the theorem follows immediately from the above inequality.

As for the second part of the theorem. First, consider the case $\ell \ge \ln ^2 n$. In this case:

$$\begin{aligned} c \left( 1 - e^{-1/c}\right) \ge {}&c \left( \frac{1}{c} - \frac{1}{2c^2}\right) = 1 - \frac{1}{2c} = 1 - \frac{\ln n}{2\ell }\\ \ge {}&1 - \frac{\ln n}{2\ln ^2 n} = 1 - \frac{1}{2\ln n} = 1 - o(1). \end{aligned}$$

Thus, in this case, the second part of the theorem follows from the inequality: $R_\ell \le (1 + o(1))(1 - 1 / (2\ln n)) R_\infty$, which is trivially true, as $R_\ell \le R_\infty$. Hence, the second part of the theorem is meaningful only for $\ell < \ln ^2 n$. Therefore, we assume this is the case from now on.

Consider an instance with uniform probabilities and a single bidder whose value for impressions of type $t_i$ is 1 / i. In this instance $h_i = 1/i$ for every $1 \le i \le n$, and thus, $R_\infty = \sum _{i = 1}^n (1/i)(1/n) = H_n / n$. We would like to upper bound $R_\ell$ in this instance. Let $r_1 > r_2 > \cdots > r_\ell$ be some set of $\ell$ reserve prices. Clearly, we can assume $1 \ge r_i \ge 1/n$ for every $1 \le k \le \ell$ (otherwise, $r_i$ can be either increased or decreased without affecting the revenue). The revenue when using these reserve prices is given by 1 / n times the following expression:

$$\begin{aligned} r_1 \cdot \lfloor 1/r_1 \rfloor + \sum _{k = 1}^{\ell - 1} r_{k + 1} \cdot \left( \lfloor 1/r_{k + 1} \rfloor - \lfloor 1/r_k \rfloor \right) \le 1 + (\ell - 1) \left( 1 - n^{-1/(\ell -1)} \right) , \end{aligned}$$

where the last inequality follows from Lemma 2. Thus,

$$\begin{aligned} R_\ell \le 1/n + (\ell - 1) \cdot \left( 1 - n^{-1/(\ell - 1)} \right) \Big /n. \end{aligned}$$

Using the same arguments, one can also get: $R_{\ell + 1} \le 1/n + \ell \left( 1 - n^{-1/\ell } \right) /n$, and clearly, $R_\ell \le R_{\ell + 1} \le 1/n + \ell \left( 1 - n^{-1/\ell } \right) /n$. Next, observe that:

$$\begin{aligned} \ell \left( 1 - n^{-1/\ell }\right) ={}&\ell \left( 1 - e^{-\ln n/\ell }\right) \ge \ell \cdot \left( \frac{\ln n}{\ell } - \frac{\ln ^2 n}{2\ell ^2}\right) \\ ={}&\ln n - \frac{\ln ^2 n}{2\ell } > \ln n - \frac{\ln ^2 n}{2\ln ^2 n} = \ln n - \frac{1}{2}. \end{aligned}$$

Thus, $R_\ell \le 1/n + \ell (1 - n^{-1/\ell })/n$ = $(1 + o(1)) \cdot \ell (1 - n^{-1/\ell }) / n$. Finally, recall that $R_\infty = H_n / n$, and therefore,

$$\begin{aligned} R_\ell \le (1 + o(1)) \cdot \ell \left( 1 - n^{-1/\ell }\right) / n = (1 + o(1)) \cdot c\left( 1 - e^{-1/c}\right) \cdot R_\infty , \end{aligned}$$

where the equality uses the definition $c = \ell / \ln n$, which implies that $\ell = c \ln n$ and $n^{-1/\ell } = e^{-1/c}$. $\square$

The last theorem of the section deals with the relatively simple case of general probabilities, for all values of $\ell$.

Theorem 3

Assume general probabilities. Then, for every $1 \le \ell \le n$,

$$\begin{aligned} R_\ell \ge (\ell /n) \cdot R_\infty . \end{aligned}$$

Moreover, there exists an instance for which

$$\begin{aligned} R_\ell \le (1 + o(1)) \cdot (\ell /n) \cdot R_\infty . \end{aligned}$$

Proof

We begin by proving the first part of the theorem. Notice that $R_\infty = \sum _{i = 1}^n p_i \cdot h_i$. Thus, there exists a set S of $\ell$ impression types for which $R_\infty \le (n / \ell ) \cdot \sum _{t_i \in S} p_i \cdot h_i$. Let us now choose the following set of up to $\ell$ reserve prices: $\{h_i ~|~ t_i \in S\}$. Clearly, when using this set of reserve prices the revenue from every impression of type $t_i \in S$ is at least $h_i$. Thus, $R_\ell \ge \sum _{t_i \in S} p_i \cdot h_i \ge (\ell / n) \cdot R_\infty$.

Next, consider the second part of the theorem. Let $f_0, f_1, f_2, \ldots , f_n$ be a set of values such that for every $1 \le i \le n$, $f(i) = \omega (n) \cdot f(i - 1)$ (notice that $\omega (n)/n$ tends to infinity with n). Consider an instance with a single bidder whose value for impressions of type $t_i$ is $v(i, 1) = 1/f_i$, and the probability of impressions of type $t_i$ is $p_i = f_i / [\sum _{j = 1}^n f_j]$. For consistency, we also define $p_0 = f_0 / [\sum _{j = 1}^n f_j]$. The contribution of impressions of type $t_i$ to $R_\infty$ is $p_i/f_i$, for every $1 \le i \le n$, and therefore, $R_\infty = \sum _{i = 1}^n [p_i/f_i] = n / [\sum _{i = 1}^n f_i]$. Consider now $R_\ell$. Let $r_1, r_2, \ldots , r_\ell$ be the best set of $\ell$ reserve prices. Clearly we can assume without loss of generality that for every $1 \le k \le \ell$, the reserve price $r_k$ is equal to $1 / f_i$ for some $1 \le i \le n$, and let us denote this i by i(k). Moreover, we can also assume each reserve price is unique, i.e., no two reserve prices are equal.

Since there is only a single bidder, the revenue from every impression type $t_i$ must be equal to either 0 or some reserve price. Let us construct for every reserve price $r_k$ a set $T_k$ containing all impression types which contribute $r_k$ to $R_\ell$. Then, $R_\ell$ can be calculated using the following formula: $R_\ell = \sum _{k = 1}^\ell \left( r_k \cdot \sum _{t_i \in T_k} p_i\right)$. Consider an arbitrary reserve price $r_k$. Every impression type $t_i \in T_k$, except for $t_{i(k)}$, must have $i < i(k)$. Hence,

$$\begin{aligned} r_k \cdot \sum _{t_i \in T_k} p_i \le {}&r_k \cdot (p_{i(k)} + n \cdot p_{i(k) - 1}) = \frac{p_{i(k)}}{f_{i(k)}} + \frac{n \cdot p_{i(k) - 1}}{f_{i(k)}}\\ ={}&\frac{1}{\sum _{j = 1}^n f_j} + \frac{n \cdot f_{i(k) - 1} / f_{i(k)}}{\sum _{j = 1}^n f_j} = \frac{1 + o(1)}{\sum _{j = 1}^n f_j}. \end{aligned}$$

Plugging this into the previous formula yields:

$$\begin{aligned} R_\ell \le \sum _{k = 1}^\ell \left( r_k \cdot \sum _{t_i \in T_k} p_i\right) = \ell \cdot \frac{1 + o(1)}{\sum _{j = 1}^n f_j} = (1 + o(1)) \cdot \frac{\ell }{n} \cdot R_{\infty }. \end{aligned}$$

$\square$

4 Computing the Optimal Reserve Prices

In this section we describe an algorithm for calculating the optimal set of reserve prices for a given auction instance. This is done using dynamic programming. The algorithm fills up a table T of size $n \cdot \ell$, where cell $T(n', \ell ')$ contains the optimal set of reserve values for an auction where only the last $n'$ impression types appear (i.e., $t_{n - n' + 1}, t_{n - n' + 2}, \ldots , t_n$), and only $\ell '$ reserve prices are allowed.⁴ To simplify the discussion, we consider the case of a single bidder. The same reasoning easily extends to the general case of many bidders as well.

Lemma 3

For every $1 \le n' \le n$, $T(n', 1)$ can be efficiently computed.

Proof

Cells of the form $T(n', 1)$ represent an auction with a single reserve price. The only values that make sense for this reserve price are $h_{n - n' + 1}, h_{n - n' + 2}, \ldots , h_n$. Hence, we have only a linear number of options to check. $\square$

Lemma 4

For every $1 \le n' \le n$ and $1 < \ell ' \le \ell$. Given that $T(n'', \ell ' - 1)$ is known for every $1 \le n'' \le n$, the value $T(n', \ell ')$ can be efficiently computed.

Proof

Let $r_1, r_2, \ldots , r_{\ell '}$ be the set of optimal reserve prices for the auction represented by $T(n', \ell ')$, ordered in an increasing order, and let $S_k$ be the set of impression types which give a revenue of $r_k$, for every $1 \le k \le \ell '$. Notice that the assumption $h_1 \ge h_2 \ge \cdots \ge h_n$ implies that the sets $S_k$ are continuous, i.e., the indices of the impression types of $S_k$ form a continues range of integers. Moreover, we can assume that $r_k$ is equal to $h_i$, where i is the largest index for which $t_i$ belongs to $S_k$. It is possible to guess the size s of $S_{\ell '}$, the set with the range of impression types of the lowest indices. Once we make this guess, it is easy to see that the optimal choice for $r_{\ell '}$ is $h_{n - n' + s}$, which results in a revenue of $r_{\ell '} \cdot \sum _{i = n - n' + 1}^{n - n' + s} p_i$ from the impressions of $S_{\ell '}$.

Let us now make the following mental experiment. Let us remove the reserve price $r_{\ell '}$ together with all the impression types of $S_{\ell '}$. Are the remaining reserve prices optimal for the remaining auction? We claim they are. Let A be the original auction, and $A' = A {\setminus } S_{\ell '}$ be the remaining auction after the removal of the impression types of $S_{\ell '}$. We also denote by R the above set of $\ell '$ reserve prices, and by $R' = R {\setminus } \{r_{\ell '}\}$ the remaining reserve prices. Using this notation, we need to prove that $R'$ is the optimal set of reserve prices for $A'$.

Assume there is a better set of reserve prices $\bar{R}'$ for $A'$. Then, the set $\bar{R} = \bar{R}' \cup \{r_{\ell '}\}$ is a new set of reserve prices for A. Let us denote by V(A, R) the revenue from an auction A and a set R of reserve prices. Let H be the largest $h_i$ for any impression type $t_i \in A'$. Observe that by the definition of $S_{\ell '}$, $r_{\ell '}$ is larger than H. Thus, we get:

$$\begin{aligned} V\left( A', R'\right) = V\left( A', R\right) {,} \qquad V\left( A', \bar{R}'\right) = V\left( A', \bar{R}\right) {.} \end{aligned}$$

Clearly, we can assume that both R and $\bar{R}$ contain no reserve price larger than H, other than $r_{\ell '}$. Thus, the revenue from the impression types of $S_{\ell '}$ is equal under both the set R and $\bar{R}$ of reserve prices. Hence,

$$\begin{aligned} V(A', R) + r_{\ell '} \cdot \left( \sum _{i = n - n' + s + 1}^{n} \,p_i\right) = V(A, R), \end{aligned}$$

and

$$\begin{aligned} V(A', \bar{R}) + r_{\ell '} \cdot \left( \sum _{i = n - n' + s + 1}^{n} \,p_i\right) = V(A, \bar{R}). \end{aligned}$$

Combining all these inequalities, with the fact that by definition $V(A', \bar{R}') > V(A', R')$, we get $V(A, \bar{R}) > V(A, R)$, contradicting the definition of R as the optimal set of reserve prices for A.

From the above experiment, we learn that once we know the size s of $S_{\ell '}$ and $r_{\ell '}$, the rest of the optimal set of reserve prices is given by $T(n' - s, \ell ' - 1)$ (if $n' - s = 0$, then we can assume $T(0, \ell '-1) = \varnothing$). $\square$

Theorem 4

The optimal set of reserve prices can be calculated efficiently.

Proof

Using Lemmata 3 and 4, we can fill up the table T. The optimal set of reserve prices is now given by $T(n, \ell )$. $\square$

To demonstrate our algorithm, let us consider an auction instance with 4 items and 2 advertisers. The values of the items (to each adversertiser) are given by the following matrix (the value of advertiser j for item i is given by the cell (j, i) in this matrix):

$$\begin{aligned} \left( \begin{array}{c@{\quad }c@{\quad }c@{\quad }c} 5 &{} 0 &{} 1 &{} 2 \\ 1 &{} 3 &{} 2 &{} 0 \end{array} \right) . \end{aligned}$$

Observe that the items in the above matrix are already sorted in a decreasing $h_i$ order. Given the above auction instance, our algorithm will construct the following table T.

$\ell$	$n'$
	1	2	3	4
1	$\{2\}$	$\{2\}$	$\{2\}$	$\{2\}$
2	$\{2\}$	$\{2\}$	$\{2, 3\}$	$\{2, 5\}$
3	$\{2\}$	$\{2\}$	$\{2, 3\}$	$\{2, 3, 5\}$

Let us explain how three of the above entries were calculated:

• T(4, 1). There are three possible guesses for the the single reserve price $r_1$ in the solution: $h_1 = 5$, $h_2 = 3$ and $h_3 = h_4 = 2$. The values of the solutions corresponding to these guesses are: 5, 6 and 8, respectively. Thus, the last guess is used, which yields the solution $\{2\}$.

• T(3, 2). There are three possible guesses for the size of $S_2$ when considering only the three last items. If $S_2 = \{t_2\}$, then $r_2 = h_2 = 3$, which results in the solution $\{3\} \cup T(2, 1) = \{2, 3\}$, whose value is 7. If $S_2 = \{t_2, t_3\}$, then $r_2 = h_3 = 2$, which results in the solution $\{2\} \cup T(1, 1) = \{2\}$, whose value is 6. Finally, if $S_2 = \{t_2, t_3, t_4\}$, then $r_2 = h_4 = 2$, which results in the solution $\{2\} \cup T(0, 1) = \{2\}$, whose value is again 6. Thus, the best solution is $\{2, 3\}$.

• T(4, 2). There are four possible guesses for the size of $S_2$ when considering all four items. If $S_2 = \{t_1\}$, then $r_2 = h_1 = 5$, which results in the solution $\{5\} \cup T(3, 1) = \{2, 5\}$, whose value is 11. If $S_2 = \{t_1, t_2\}$, then $r_2 = h_2 = 3$, which results in the solution $\{3\} \cup T(2, 1) = \{2, 3\}$, whose value is 10. If $S_2 = \{t_1, t_2, t_3\}$, then $r_2 = h_3 = 2$, which results in the solution $\{2\} \cup T(1, 1) = \{2\}$, whose value is 8. Finally, if $S_2 = \{t_1, t_2, t_3, t_4\}$, then $r_2 = h_4 = 2$, which results in the solution $\{2\} \cup T(0, 1) = \{2\}$, whose value is again 8. Thus, the best solution is $\{2, 5\}$.

5 Concluding Remarks

We studied the effect of limiting the number of reserve prices on the revenue in a probabilistic single item auction. If $R_{\infty }$ denotes the maximum possible (expected) revenue that can be obtained using an unlimited number of reserve prices, and $R_{\ell }$ denotes the revenue that can be ensured using $\ell$ reserve prices, we have determined the best possible lower bound for the ratio $R_{\ell }{/}R_{\infty }$, for all admissible values of $\ell$ under uniform probabilities and under general probabilities. In particular we have shown that for uniform probabilities a number of reserve prices that is logarithmic in the number of types suffices to ensure a revenue that is comparable to the total revenue that can be obtained using an unlimited number of such prices. It is worth noting that the proof of this statement itself is not complicated, when we do not care about precise constants, and the main technical contribution is getting tight estimates, up to low order terms, for all possible values of the parameters. Getting tight estimates is very important in the ad exchanges business, where every small change in the constants of the estimates may correspond to millions of dollars in revenue.

Our investigation is motivated by the study of the display advertisement market, where the number of possible reserve prices is often limited. This limitation may arise due to the difficulty of communicating a large number of reserve prices to the bidders, or due to logical segmentation rules. In the last case it may be interesting to study this problem further when these rules do not enable the mechanism to assign reserve prices arbitrarily to the different types, but force some additional constraints on this assignment.

We study the uniform distribution because it is natural and corresponds to the bundling problem of [4, 13]. The general distribution is the other extreme, and hence, interesting. Other distributions may be worthwhile to study as well, but as it is not clear which distributions are most relevant for the display advertisement market; this paper refrains from addressing this issue. We believe our analysis of the two end point distributions should give an intuitive idea as to the properties of the distribution that affect the necessary number of reserve prices.

When the number of items is very large or when there is an insufficient log history to determine the values of the different items to the bidders, it might not be possible to find the optimal set of reserve prices using our algorithm. In these scenarios, our results can be interpreted as showing that it is possible to do well with a realistic number of reserve prices.

One possible extension of our work is comparing $R_\ell$ with auctions using signaling. Auctions with signaling are second-price auctions where the auctioneer decides, strategically, which part of the information to communicate to the bidders (as opposed to the auctions considered in this paper, where the instantiation is fully revealed). The concealment of information in signaling auctions is used as method for maximizing the revenue, instead of reserve prices, which are often missing in this kind of auctions. Auctions with signaling were considered, e.g., by [5]. In a complementary study we compare the revenue of second-price auctions with reserve prices to the revenue obtained by second-price auctions with signaling. Our preliminary results in this direction show that one can indeed get a better bound when comparing against the best signaling scheme, as opposed to comparing with the theoretical value of $R_\infty$.