Offline Learning of Reserve Prices from Censored Bids
Organizations: Department of Industrial and Enterprise Systems Engineering, University of Illinois Urbana-Champaign
Abstract
We study how a seller can learn a reserve price for a second-price auction from censored historical bid data. Because values below past reserves are unobserved, even unlimited data may not reveal which reserve earns the most revenue. Under a monotone hazard rate (MHR) assumption, we characterize exactly when an optimal reserve is identified, even though the value distribution may not be: either revenue has not yet begun to fall at the lowest historical reserve, so the best reserve lies among the observed bids, or the censored fraction is as large as MHR allows, which pins down the entire distribution. When identification fails, we derive the reserve that minimizes worst-case revenue regret over distributions consistent with the data, and prove that this unique minimax reserve and its regret depend on just two observable quantities: the censored fraction and the hazard just above the lowest historical reserve. With historical bidders, the optimal reserve is learned with expected worst-case regret when it lies among the observed bids, and from the censored count alone when the censored fraction is as large as MHR allows and the optimum lies at or below the lowest reserve. In the nonidentifiable regime, plugging estimates of the two quantities into the minimax reserve gives expected worst-case regret within of the population minimum under local density smoothness, with a matching minimax lower bound on a smooth class. Beyond MHR, we solve the minimax problem for regular and unrestricted distributions and prove an learning bound in the regular nonidentifiable regime, given known bounds on the boundary parameters. Experiments on synthetic and eBay data show gains from exploiting MHR and the benefits of the robust rule when parametric models are misspecified.
Figures & tables
| Regime | Case | Boundary condition | Rule | Regret rate |
|---|---|---|---|---|
| Identifiable | Tail-optimal | Empirical tail | ||
| Fully identified | Linear completion | |||
| Nonidentifiable | — | , | Plug-in |
| MHR | Regular | Unrestricted | |||||
|---|---|---|---|---|---|---|---|
| Instance | Worst-case | Actual | Worst-case | Actual | Worst-case | Actual | |
| Rayleigh | |||||||
| Weibull | |||||||
| Weibull | |||||||
| Worst-case regret | Actual regret under each distribution | ||||
|---|---|---|---|---|---|
| Rule | Weibull | Equalizer | Exponential | Tangent | |
| Plug-in, Auto-selector | |||||
| Plug-in (Weibull hazard) | |||||
| Weibull MLE | |||||
| Gamma MLE | |||||
| Lognormal MLE | |||||
| Censored MLE | |||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
| Item | Full-info | Plug-in | Auto-selector | Weibull | Gamma | Lognormal | Linear compl. | Boundary | Drop | ||
| Palm Pilot | |||||||||||
| Palm Pilot | |||||||||||
| Palm Pilot | |||||||||||
| Worst-case | Held-out | |||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Item | Regime | Detected | Auto-selector | Weibull | Auto-selector | Weibull | Boundary | |||||||
| Palm Pilot | ident. | ident. | ||||||||||||
| Palm Pilot | ident. | nonident. | ||||||||||||
| Palm Pilot | ident. | ident. | ||||||||||||
| Palm Pilot | nonident. | nonident. | ||||||||||||
| Palm Pilot | nonident. | nonident. | ||||||||||||
Appendix figures & tables27 assets
Supplementary material from the paper’s appendix.
Appendix
| Symbol | Meaning |
|---|---|
| , | Number of bidders in the target auction; number of historical records subject to censoring at the lowest reserve , one per bidder who faced it. |
| , , | True distribution, a compatible completion, and the censoring boundary (the lowest historical reserve). |
| Ambiguity set: all completions of the observed tail; subscripts restrict the shape. | |
| , | Hazard and cumulative hazard; MHR means convex. |
| , | Virtual value and single-bidder revenue curve in quantile coordinates; regularity means concave. |
| , | Second-price auction revenue at reserve , and its optimal value. |
| Rule | How the reserve is chosen |
|---|---|
| Full-info | The full-information reserve of the held-out eBay study: the exact revenue maximizer on simulated auctions among the uncensored training bidders. It sees the values that censoring hides from every other rule and serves as the oracle row. |
| Plug-in | Algorithm 5.1 , at the projected boundary estimates. |
| Auto-selector | Algorithm 5.2 : empirical tail rule on (on with the larger of and twice the largest observed record in the opening-bid study of Section 7.4 ) when the raw ; plug-in otherwise. |
| Plug-in (Weibull hazard) | Algorithm 5.1 with the boundary hazard replaced by the censored Weibull fit’s hazard at ; the count estimate is kept. |
| Censored MLE | Maximum likelihood fit in a Weibull, gamma (shape at least one) or lognormal family. Observed bids contribute their fitted density; no-bid records contribute the fitted probability below . Post the fitted distribution’s optimal reserve. It is an oracle MLE when the full distribution belongs to the fitted family. |
| Linear completion | The linear-completion reserve of ( 5.3 ): it uses only the censored fraction and is optimal when the body hazard is constant below . |
| Item | Regime | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Palm Pilot | nonident. | |||||||||
| Palm Pilot | nonident. | |||||||||
| Palm Pilot | nonident. | |||||||||
| Xbox | ident. | |||||||||
| Xbox | nonident. | |||||||||
| Xbox | nonident. |
| Significant decrease | Contrast (90% interval) | ||||||
|---|---|---|---|---|---|---|---|
| Item | bw | pointwise | sup- | Peak (90%) | |||
| Palm Pilot | no | no | [247, 255] | [20.8, 28.0] | [15.6, 26.5] | [7.5, 19.6] | |
| Palm Pilot | no | no | [252, 259] | [18.0, 23.0] | [13.6, 19.4] | [9.0, 14.2] | |
| Palm Pilot | no | no | [264, 269] | [12.0, 13.8] | [8.6, 10.0] | [6.1, 7.1] | |
| Xbox | yes | yes | [103, 205] | [ 8.6, 1.4] | [ 3.5, 4.9] | [0.5, 8.2] | |
| Xbox | yes | yes | [106, 119] | [ 8.7, 2.0] | [ 4.8, 2.6] | [ 1.0, 5.6] | |
| Kernel fit | Isotonic MHR refit | ||||||||
|---|---|---|---|---|---|---|---|---|---|
| Item | Regime | Regime | |||||||
| Palm Pilot | nonident. | nonident. | |||||||
| Palm Pilot | nonident. | nonident. | |||||||
| Palm Pilot | nonident. | nonident. | |||||||
| Xbox | ident. | ident. | |||||||
| Xbox | nonident. | nonident. | |||||||
| MHR | Regular | Unrestricted | ||||||
|---|---|---|---|---|---|---|---|---|
| Item | Regime | Worst-case | Actual | Worst-case | Actual | Worst-case | Actual | |
| Palm Pilot | nonident. | |||||||
| Palm Pilot | nonident. | |||||||
| Palm Pilot | nonident. | |||||||
| Xbox | ident. | |||||||
| Xbox | nonident. | |||||||
| Worst-case regret | Actual regret under each distribution | ||||
|---|---|---|---|---|---|
| Rule | Refit | Equalizer | Exponential | Tangent | |
| Plug-in, Auto-selector | |||||
| Plug-in (Weibull hazard) | |||||
| Weibull MLE | |||||
| Gamma MLE | |||||
| Lognormal MLE | |||||
| Cell | Rule | |||||
|---|---|---|---|---|---|---|
| under | under | |||||
| Palm Pilot, | Plug-in | |||||
| Weibull MLE | ||||||
| Gamma MLE | ||||||
| Lognormal MLE | ||||||
| Palm Pilot, | Plug-in | |||||
| Censored MLE | |||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
| Item | Full-info | Plug-in | Auto-selector | Weibull | Gamma | Lognormal | Linear compl. | Boundary | Drop | ||
| Cartier | |||||||||||
| Cartier | |||||||||||
| Cartier | |||||||||||
| Xbox | |||||||||||
| Xbox | |||||||||||
| Worst-case | Held-out | |||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Item | Regime | Detected | Auto-selector | Weibull | Auto-selector | Weibull | Boundary | |||||||
| Cartier | ident. | ident. | ||||||||||||
| Cartier | ident. | ident. | ||||||||||||
| Cartier | ident. | nonident. | ||||||||||||
| Xbox | ident. | nonident. | ||||||||||||
| Xbox | ident. | ident. | ||||||||||||
| Rate | Detected | Reserve | Auto-selector | Weibull | |||
|---|---|---|---|---|---|---|---|
| 10 | ident. | ||||||
| 10 | ident. | ||||||
| 10 | ident. | ||||||
| 10 | ident. | ||||||
| 10 | ident. | ||||||
| 50 | nonident. |
| Worst-case regret | Actual regret | ||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
| Item | Plug-in | Weibull | Gamma | Lognormal | Linear compl. | Boundary | Plug-in | Weibull | |||
| Palm Pilot | |||||||||||
| Palm Pilot | |||||||||||
| Palm Pilot | |||||||||||
| Palm Pilot | |||||||||||
| Palm Pilot | |||||||||||
| Item | Winner’s record | Records | Regime | ||||||
|---|---|---|---|---|---|---|---|---|---|
| Palm Pilot | Kaplan–Meier | nonident. | |||||||
| nonident. | |||||||||
| nonident. | |||||||||
| Palm Pilot | closing price | nonident. | |||||||
| nonident. | |||||||||
| nonident. |
| Plug-in | Auto-selector | Linear compl. | Frontier | ||||
|---|---|---|---|---|---|---|---|
| (0.038) | (0.038) | (0.090) | |||||
| (0.059) | (0.059) | (0.031) | |||||
| (0.132) | (0.132) | (0.030) | |||||
| (0.119) | (0.119) | (0.018) | |||||
| (0.113) | (0.113) | (0.012) | |||||
| (0.167) | (0.913) | (0.006) |
| bound | /bound | |||||||
|---|---|---|---|---|---|---|---|---|
| Family | Side | Misclass. | Plug-in | Auto-selector | Tail | Linear compl. | |||
| Weibull( ) | tail-optimal | (2.9) | (0.005) | (0.011) | (0.011) | (0.000) | |||
| Weibull( ) | tail-optimal | (1.2) | (0.000) | (0.003) | (0.003) | (0.000) | |||
| Weibull( ) | tail-optimal | (3.4) | (0.008) | (0.016) | (0.015) | ||||
| Weibull( ) | tail-optimal | (2.3) | (0.001) | (0.002) | (0.001) | ||||
| Weibull( ) | tail-optimal | (3.4) | (0.009) | (0.013) | (0.012) | (0.000) | |||
| Weibull( ) | tail-optimal | (3.3) | (0.003) | (0.003) | (0.001) | (0.000) |
| Distribution | Plug-in | Auto-selector | Drop | |
|---|---|---|---|---|
| Lognormal | (0.00) | (0.00) | (0.00) | |
| Lognormal | (0.02) | (0.02) | (0.01) | |
| Lognormal | (0.00) | (0.01) | (0.01) | |
| Lognormal | (0.00) | (0.01) | (0.01) |
| Instance | ||||
|---|---|---|---|---|
| Rayleigh(1) | ||||
| Weibull(1.5,1) | ||||
| Weibull(2.5,1.5) |
| Instance | Computed minimax regret | Refinement change | |
|---|---|---|---|
| Rayleigh(1) | |||
| Weibull(1.5,1) | |||
| Weibull(2.5,1.5) |
| Quantity | Bound | Largest measured / bound |
|---|---|---|
Minimax Regret
Minimax regret studies decision rules that minimize worst-case loss relative to an informed benchmark under uncertainty.
See all 69 papers