Revenue Optimization with Approximate Bid Predictions
In the context of advertising auctions, finding good reserve prices is a notoriously challenging learning problem. This is due to the heterogeneity of ad opportunity types, and the non-convexity of the objective function. In this work, we show how to reduce reserve price optimization to the standard setting of prediction under squared loss, a well understood problem in the learning community. We further bound the gap between the expected bid and revenue in terms of the average loss of the predictor. This is the first result that formally relates the revenue gained to the quality of a standard machine learned model.
This paper studies revenue optimization from samples for one bidder. It is motivated by ad auction design where there are trillions of different items being sold. For many items, there is often little or no information available about the bidder’s value for that precise good. As a result, previous techniques in sample-based auction design do not apply because the auction designer has no samples from the bidder’s value distribution for many of the items. Meanwhile, ads (for example) are often easily parameterized by feature vectors, so the authors make the assumption that items with similar features have similar bid distributions. Under this assumption, the authors show how to set prices and bound the revenue loss.
At a high level, the algorithm uses the sample and the bid predictor h(x) to cluster the feature space X into sets C1, …, Ck. The algorithm finds a good price ri per cluster Ci. On a freshly sampled feature vector x, if the feature vector falls belongs to the cluster Ci, then the reserve price r(x) = ri. The clustering C1, …, Ck is defined to minimize the predicted bid variance of each group Cj. Specifically, the objective is to minimize sum_{t = 1}^k \sqrt{\sum_{i,j:xi,xj \in Ct} (h(xi) – h(xj))^2}. The authors show that this can be done efficiently using dynamic programming. The best price per cluster can also be found in polynomial time. For each cluster Ct, let St be the set of samples (xi, bi) such that xi falls in Ct. The algorithm sets the price rt to be the bid bi such that (xi,bi) falls in St and bi maximizes empirical revenue over all samples in St.
 
The authors bound the difference between the expected revenue achieved by their learning algorithm and an upper bound on optimal revenue. This upper bound is simply E_{(x,b)}[b]. They show that the bound depends on the average bid over the sample and the error of the bid predictor h. The bound is also inversely proportional to the number of clusters k and the number of samples. They perform experiments on synthetic data and show that their algorithm performs best on “clusterable” synthetic valuation distributions (e.g., bimodal). It also seems to perform well on real ad auction data.
 
Overall, I think the motivation of this work is compelling and it’s an interesting new model for the sample-based mechanism design literature. I’d like to see more motivation for the assumption that the learner knows the bid prediction function h. Is it realistic that an accurate prediction function can be learned? It seems to me as though the learner would probably have to have a pretty robust knowledge about the underlying bid function in order for this assumption to hold. The paper could potentially be strengthened by some discussion about this assumption.
 
In the experimental section, it would be interesting to see what the theoretical results guarantee for the synthetic data and how that compares to the experimental results.
 
I’m confused about equation (12) from the proof of lemma 1. We know that r(x) >= h(x) – eta^{2/3}. Therefore, Pr[b < r(x)] >= P[b < h(x) – eta^{2/3}] = P[h(x) – b > eta^{2/3}]. But the proof seems to require that Pr[b < r(x)] <= P[b < h(x) – eta^{2/3}] = P[h(x) – b > eta^{2/3}]. Am I confusing something?
=========After feedback =========
Thanks, I see what you mean in Lemma 1. Maybe this could be made a bit clearer since in line 125, you state that r(x) := max(h(x) - eta^{2/3}, 0).