Source-linked AI summary
Learning Theory and Algorithms for Revenue Optimization in Second-Price Auctions with Reserve
Mehryar Mohri, Andres Muñoz Medina
TL;DR
The paper asks how to choose reserve prices that optimize revenue in second-price auctions, where reserve selection directly affects online-market revenue. It formulates this choice as a learning problem, analyzes a non-convex loss, and develops algorithms whose effectiveness is demonstrated on synthetic and real data. The analysis also identifies computational limitations for some optimization procedures in higher dimensions.
Problem
Selecting revenue-maximizing reserve prices is important for online sites, but convex surrogates are not useful and bidder distributions may be unavailable in practice.
Method
The paper analyzes a calibrated continuous non-convex surrogate, derives learning guarantees, and solves the resulting DC program with combinatorial and DC-algorithm approaches.
Results
The experiments on synthetic data and eBay data demonstrate the effectiveness of the proposed algorithms.
Takeaways & Limitations
Reserve-price revenue optimization can be treated as a practically applicable learning problem with algorithms for both no-feature and feature-based settings.
Takeaways & Limitations
The proposed no-feature optimization can require O(m2) computation, while combinatorial DC-programming methods can be extremely slow in moderately high dimensions.
Abstract
from arXiv · showhide
Second-price auctions with reserve play a critical role for modern search engine and popular online sites since the revenue of these companies often directly de- pends on the outcome of such auctions. The choice of the reserve price is the main mechanism through which the auction revenue can be influenced in these electronic markets. We cast the problem of selecting the reserve price to optimize revenue as a learning problem and present a full theoretical analysis dealing with the complex properties of the corresponding loss function. We further give novel algorithms for solving this problem and report the results of several experiments in both synthetic and real data demonstrating their effectiveness.
1. Introduction
Online ad exchanges generate substantial revenue, making reserve-price selection an important optimization problem. The paper casts reserve-price choice as a learning problem and develops non-convex surrogates, theoretical guarantees, and algorithms for feature-based and no-feature settings.
- Reserve-price selection matters because second-price auctions with reserve generate a large fraction of popular online sites’ revenue.
- The paper uses historical auction data and user features to learn reserve prices directly rather than first estimating bidders’ value distributions.
- The learning scenario extends prior work by incorporating features and providing an O(m log m) algorithm for a key no-feature optimization subroutine.
- The learning problem is technically difficult because a convex surrogate loss is not calibrated, requiring an alternative non-convex surrogate with new theoretical guarantees.
- The analysis covers a combinatorial algorithm for the no-feature case and combines it with the DC algorithm for the general feature-based case.
2. Reserve price selection problem
The paper models reserve-price selection as minimizing negative auction revenue over a hypothesis class. In the feature-based setting, a hypothesis maps auction features to reserve prices, and empirical loss is evaluated on logged auction samples.
- The reserve price r is the seller’s main mechanism for influencing revenue, and auction outcomes depend on the highest and second-highest bids.
- In the no-feature case, the objective is to choose a single reserve price r that maximizes expected auction revenue.
- With features x, a hypothesis h maps each feature vector to a reserve price h(x), and the goal is to select a high-expected-revenue hypothesis from H.
- The paper minimizes loss defined as negative revenue, using expected loss under the unknown distribution of features and bid pairs.
- Given an i.i.d. training sample, empirical loss provides the optimization objective for studying the reserve-price learning problem.
3. Learning guarantees
The revenue-learning loss is non-convex, discontinuous, and difficult to optimize, so convex surrogates are uninformative. The paper derives complexity and generalization guarantees, then introduces calibrated non-convex surrogates with stronger consistency results.
- Generalization bounds: The resulting generalization theorem bounds the learning guarantees uniformly over hypotheses using the hypothesis pseudo-dimension, sample size, confidence level, and the maximum first bid M.The theorem is obtained by combining the complexity bounds for the decomposed loss components with a standard Rademacher-complexity bound.
- Loss complexity: The original loss is neither Lipschitz nor convex, and sums of its terms are generally not quasi-convex, complicating both complexity analysis and empirical optimization.The analysis decomposes the loss into l1 and l2, using Lipschitz and pseudo-dimension arguments to bound their Rademacher complexities.
- Surrogate failure: A convex piecewise-linear surrogate may be convenient computationally but is not calibrated and can produce a minimizer unlike that of the true empirical objective.The paper illustrates this mismatch by comparing sums of the true loss with convex-surrogate losses.
- Convex surrogates: Convex surrogates cannot be consistent here: any bounded convex surrogate consistent with the target loss must be constant and therefore uninformative.The paper strengthens this result from individual convex surrogates to weakly consistent sequences, which converge uniformly to a constant function.
- Non-convex surrogates: The proposed non-convex surrogate Lγ matches the original loss near its minimum, is calibrated, and can yield stronger consistency as γ and the sample size are appropriately chosen.Although Lγ is a lower bound and its convergence to L is non-uniform, matching the loss around the minimizer makes its solutions informative.
4. Algorithms
The algorithms exploit the structure of non-convex v-functions to optimize reserve-price objectives, first without features and then with feature-dependent hypotheses. The no-feature problem admits an O(m log m) combinatorial algorithm, while the general case is formulated and solved using DC programming with line searches.
- 4.1 No feature case: A v-function generalizes the losses Lγ and L, remains non-convex for fixed bids, and attains its minimum at the highest bid.The algorithmic analysis therefore targets sums of piecewise-defined v-functions rather than convex losses.
- 4.1 No feature case: The minimum of a sum of v-functions is attained at one of the highest bids, reducing the no-feature search to m candidate reserve prices.This structural result makes it sufficient to evaluate the objective at the first-order bids.
- 4.1 No feature case: Sorting all boundary points and updating objective values between consecutive points yields an O(m log m) algorithm for the no-feature optimization problem.Only constant-time updates are needed between successive boundary points after sorting.
- 4.1 No feature case: The no-feature algorithm extends to reserve prices bounded by Λ without changing its O(m log m) computational complexity.The bounded problem additionally evaluates the upper endpoint Λ.
- 4.2 General case: The DC algorithm is generally guaranteed to converge only to a critical point, while global DC optimization methods can be impractical in high dimensions.The paper notes slow practical convergence for some global methods and exponential cost for explicitly representing the relevant piecewise-linear function.
- 4.2 General case: With features, the objective is expressed as a difference-of-convex program and optimized by iteratively solving convex subproblems using subgradients and line searches.Positive homogeneity reduces each line search to a one-dimensional v-function optimization, which uses the no-feature combinatorial algorithm.
5. Experiments
Experiments compare the proposed DC algorithm with convex-surrogate, ridge-regression, and feature-ignoring strategies on synthetic and eBay auction data. The DC method outperforms the alternatives in noiseless synthetic data, while convex-surrogate performance worsens with more samples and approaches no-reserve performance in a generative setting.
- Experimental design: The experiments compare DC, convex-surrogate, ridge-regression, and feature-ignoring strategies on synthetic and realistic auction data.Synthetic experiments vary feature–bid correlation and noise; the realistic evaluation uses eBay collector sport-card auctions.
- Artificial data sets: Increasing bid noise reduces the performance of feature-based algorithms because the features become less relevant to prediction.The synthetic experiments use Gaussian noise standard deviations of 0, 0.25, and 0.5.
- Artificial data sets: DC outperforms all other techniques in the noiseless synthetic setting.Figure 7(a) reports expected revenue as a function of sample size for the compared algorithms.
- Artificial data sets: As sample size increases, the convex-surrogate algorithm’s performance decreases and, in the generative setting, approaches the no-reserve strategy.The finding empirically verifies the paper’s inconsistency result for convex surrogates.
- Realistic data sets: The eBay evaluation reports mean revenues and standard deviations over ten repeated train–validation–test splits, comparing DC with convex-surrogate, feature-ignoring, no-reserve, and highest-bid strategies.The highest bid was approximated from repeated-card sale prices because eBay did not report it directly.
6. Conclusion
The paper develops a theoretical and algorithmic treatment of revenue optimization in second-price auctions with reserve. Its experiments support the practical applicability of the proposed algorithms, and parts of the calibration analysis may extend to other learning problems.
- 6. Conclusion: The paper presents a comprehensive theoretical and algorithmic analysis of revenue optimization in second-price auctions with reserve.The analysis addresses the specific properties of the learning problem’s loss function and develops new learning guarantees.
- 6. Conclusion: The proposed algorithmic solutions are practically applicable to revenue optimization in realistic second-price-auction settings.The authors state that experimental results further demonstrate their effectiveness.
- 6. Conclusion: The calibration analysis and algorithms may also be relevant to other learning problems.The conclusion identifies this as a possible broader interest of the work.
Appendix A. Contraction lemma
The appendix states and proves a contraction lemma for empirical Rademacher complexity when the composed functions are individually Lipschitz. The proof proceeds by conditioning on each Rademacher variable and applying the Lipschitz property.
- Appendix A. Contraction lemma: Lemma 18 bounds the empirical Rademacher complexity of compositions with μ-Lipschitz functions Ψ1, …, Ψm.The hypothesis class H maps X to R, and the lemma applies to a sample of m points.
- Appendix A. Contraction lemma: The proof rewrites the empirical Rademacher complexity and selects hypotheses attaining the relevant suprema.When suprema are not attained, the argument uses hypotheses that are ε-close to them.
- Appendix A. Contraction lemma: Conditioning on each Rademacher sign and using the corresponding Lipschitz property proves the lemma by iterating over all coordinates.The argument explicitly handles σm and then proceeds similarly for every other σi.