Extracted main text — title through conclusion, appendix excluded. This is what our citation measures are computed over, published so the extraction can be checked by eye.
18,935 characters · 6 sections · 22 citation commands
Grenander-type Density Estimation under Myerson Regularity
The estimation of the density of private valuations (also referred to as willingness-to-pay) is an important topic of econometrics and industrial organization. This paper focuses on estimating the density function, using an independent and identically distributed (iid) sample of valuations. These valuations are observed from truth-revealing mechanisms such as second-price auctions on digital platforms including eBay, Google Ads, and Meta Ad Auction.
Conventionally, nonparametric procedures involve the use of smoothing-based estimators such as the kernel density estimator and the local polynomial estimator. However, these estimators present three primary challenges. First, the researcher must determine a tuning parameter (bandwidth), which significantly influences the estimator's performance. This optimization is a complex task often requiring the estimation of higher-order derivatives of the density function. Second, inference procedure often requires undersmoothing because the asymptotic normal distribution achieved under the optimal convergence rate has a nonnegligible bias term. Third, computation becomes complex as an estimate needs to be computed for each value within the density function's domain.
To address these issues, this paper utilizes a shape restriction on the valuation distribution, which is more naturally suited to the economic setting than the smoothness condition. We propose a nonparametric density estimator that eliminates the need for any tuning parameter. The asymptotic distribution under the optimal convergence rate is Chernoff's distribution, which is centered at zero. This estimator is computationally more efficient as it is defined piecewise.
The shape restriction we focus on is the convexity of $(1-F)^{-1}$, where $F$ is the cumulative distribution function of the valuations. This convexity constraint is equivalent to the well-known myerson1981optimal regularity condition, which states that the virtual valuation function needs to be increasing. As pointed out by bulow1996auctions, Myerson regularity is also equivalent to the concavity of the revenue function from selling the item.
The asymptotic properties of our proposed estimator is nonstandard. Under mild assumptions, we derive the cube-root consistency and the non-normal asymptotic distribution of the estimator. We also demonstrate that the cube-root convergence rate is minimax optimal under the set of assumptions under consideration.
The literature on valuation density estimation has explored nonparametric methods under shape restrictions HENDERSON2012empirical,luo2018integrated,ma2021monotonicity,pinkse2019estimation. These papers primarily focus on first-price auctions, in which the private values are not directly observed and the monotonicity constraints they consider are different from Myerson regularity. To our knowledge, this study is the first to leverage Myerson regularity as a shape constraint in nonparametric estimation.
This paper is related to the literature on nonparametric estimation under shape restrictions. The common theme of this literature is to estimate a monotone or convex (resp. concave) function with a crucial step of taking the greatest convex minorant (resp. least concave majorant) of a preliminary estimator. These estimators are often referred to as Grenander-type estimators due to the pioneer work of grenander1956theory for the estimation of a monotone density. Other examples of Grenander-type estimators include the estimation of a concave distribution function beare2017weak, the estimation of a monotone hazard rate marshall1965maximum,rao1970estimation, and isotonic regression robertson1975consistency. General asymptotic results for nonparametric estimation under shape restrictions can be found in, for example, durot2007mathbb,durot2012limit,westling2020unified and the book groeneboom_jongbloed_2014. Our paper contributes to this literature by considering a new shape restriction on the distribution function based on the economically meaningful Myerson regularity condition.
We consider the second-price auction model with independent private values. An indivisible object is auctioned. We assume that there are multiple auctions which are homogeneous. All bidders are risk neutral and symmetric. Without loss of generality, we pool all the bidders together. Their private values $V_1,\cdots,V_n$ are iid draws from a common distribution $F$, which we call the value distribution. The distribution $F$ is absolutely continuous with density function $f$ and compact support $[\underline{v},\bar{v}]$.
The second-price auctions are truth revealing: it is a dominant strategy for the bidders to truthfully report their valuations. Therefore, we can assume that the researcher observes the values $V_1,\cdots,V_n$. The goal is to estimate the density function $f$ based on this sample.
It is impossible to estimate $f$ without imposing assumptions on the value distribution. The typical procedure is to assume some smoothness condition on the density function $f$ and then apply the smoothing-based methods such as the kernel density estimator. However, in the auction setting, there is a more natural restriction on the density $f$ that arises from the microeconomic theory --- myerson1981optimal regularity condition.
Myerson regularity condition is a very important condition in the mechanism design theory. Some of the most celebrated results in the theory of mechanism design require the underlying valuation distribution to be regular. For example, the second-price auction with reserve price maximizes the revenue only under the condition of regularity.
There is an economic intuition behind Myerson regularity condition explained by bulow1996auctions. Suppose the seller sets the price $p$ in a market with measure one buyers whose private value follows the distribution $F$. There are $1-F(p)$ buyers whose value is higher than the price $p$. These buyers will choose to purchase. The quantity sold is therefore equal to $q = 1-F(p)$. The revenue collected by the seller as a function of the quantity sold is
where we assume that $F$ is strictly increasing with inverse $F^{-1}$. The marginal revenue is equal to
Myerson regularity condition states that the marginal revenue $R'(q)$ is nondecreasing in the price $p$, which implies that it is nonincreasing in the quantity $q$. This means that Myerson regularity is equivalent to the concavity of the revenue function $R$.
From the statistical perspective, Assumption (ref) imposes a restriction on the shape of the density function $f$ that can be utilized for estimation. To facilitate estimation, we consider an equivalent condition of Myerson regularity under a mild technical assumption.
Besides the continuity of $f$, Assumption (ref) also requires that the upper Dini derivative $\limsup_{\varepsilon \rightarrow 0^+} (f(v+\varepsilon) - f(v))/\varepsilon$ is finite. This is a very mild technical condition that can be satisfied if, for example, the density $f$ is locally Lipschitz continuous. Following ewerhart2013regular, we can now equivalently state Myerson regularity as follows.
We can better illustrate Proposition (ref) by assuming that the density $f$ is differentiable with derivative $f'$. Denote $\lambda$ as the derivative of $\Lambda$:
Then we have
The respective signs of $\varphi'(v)$ and $\lambda'(v)$ coincide and are both determined by the sign of $2f(v)^2 + (1-F(v))f'(v)$. Proposition (ref) is the generalization of this equivalence result to the case where $f$ is not differentiable.\footnote{Condition ((ref)) was first pointed out by mcafee1987auctions in footnote 11. ewerhart2013regular drew a connection between $f/(1-F)^{-2}$, the derivative of $(1-F)^{-1}$, and the probability rate of being the next to fail. SZECH2011optimal offered a different perspective on the condition, relating it to the monotonicity of the sequence of increments of expected second order statistics. Lastly, fang2017nonparametric provided an additional interpretation of the condition, viewing it as the convexity of odds ratio.}
Condition ((ref)) is the key to the estimation procedure we propose. Based on the empirical distribution function $F_n(v) \equiv \frac{1}{n} \sum_{i=1}^n \mathbf{1}\{V_i \leq v\}$, we can construct an estimator for $\Lambda(v)$ as
where we add the term $1/n$ in the denominator to avoid dividing by zero. The estimator $\Lambda_n$ is converging to $\Lambda$ but may not be convex in finite samples. Let $\hat{\Lambda}_n$ be the greatest convex minorant (gcm) of $\Lambda_n$. That is, $\hat{\Lambda}_n$ is the largest convex function that lies below $\Lambda_n$. Since $\hat{\Lambda}_n$ is convex, it is almost everywhere differentiable. Take $\hat{\lambda}_n$ as the left-derivative of $\hat{\Lambda}_n$. Since $\hat{\lambda}_n$ is an estimator for $\lambda = f/(1-F)^2$, we can naturally estimate $f$ by the estimator
This nonparametric estimator is tuning-parameter-free. In particular, we do not need to choose the bandwidth as in kernel-based estimators.
In this section, we derive the asymptotic properties of the estimator $\hat{f}_n$. It is well-known that Grenander-type estimators can behave badly near the boundary points woodroofe1993penalized,kulikov2006behavior,balabdaoui2011grenander. Therefore, we focus on a subinterval $[a,b]$ of the support $[\underline{v},\bar{v}]$, where $\underline{v} < a < b < \bar{v}$.
We first derive the uniform consistency of the estimator $\Lambda_n$, which can be derived based on the uniform consistency of the empirical distribution.
The following theorem states the (uniform) consistency of $\hat{f}_n(v)$ under the (uniform) continuity of the density function $f$. The idea is that (uniform) conintuity corresponds to (uniform) consistency.
Because $\hat{\lambda}_n$ is the derivative of $\hat{\Lambda}_n$, to derive its asymptotic distribution, we need to first study the local behavior of $\Lambda_n - \Lambda$. Define the stochastic process $J_n(t)$ as
The following lemma establishes the weak convergence of $J_n(t)$, which is useful in deriving the asymptotic distribution of $\hat{f}_n(v)$.
The distribution of $Z$, the argmax of two-sided brownian motion with quadratic drift, is referred to as Chernoff's distribution as it first arose in chernoff1964estimation on mode estimation. The density, distribution function, quantiles, and moments of Chernoff's distribution are computed in groeneboom2001computing. In particular, its density function is symmetric around zero, and hence our estimator does not have asymptotic bias. In contrast, kernel density estimators often has asymptotic bias when converging at the minimax optimal rate. The variance of $Z$ is approximately $0.26$. As suggested by dykstra1999distribution, the distribution of $Z$ can be approximated by the normal distribution $N(0,(0.52)^2)$.
To conduct inference on $f(v)$, one can estimate the density derivative $f'(v)$ using the conventional methods and obtain an estimate for $C(v)$. To obtain the quantiles of $Z$, one can use Table 3 in groeneboom2001computing. Notice that it is difficult to obtain a cube-root test statistic based on the kernel density estimator when the density is only first-order differentiable. In general, inference procedures need undersmoothing to eliminate the asymptotic bias, thus leading to suboptimal convergence rates.
We are interested to know whether our estimator attains the optimal rate of convergence given the current set of assumptions that we are considering. To do that, our goal is to derive lower bounds on the convergence rate achievable by any estimation procedure. These lower bounds represent the intrinsic difficulty of the estimation problem at hand. From stone1980optimal, we know that the lower bound for estimating a continuously differentiable density is $n^{-1/3}$, which is achievable by the kernel density estimator. Nonetheless, our problem deviates from this scenario due to the incorporation of Myerson regularity in addition to smoothness.
Notice that evaluating the estimators' performance with respect to a particular density is not feasible. This is due to the existence of an invariably superior estimation method: simply discard the data and return that particular density function. Consequently, we should focus on assessing the performance of the estimators across a set of distributions, in a minimax sense. Therefore, we need to consider the performance of the set of estimators over a set of distributions in the minimax sense. In our case, the relevant set of densities is $\mathcal{F}$, defined as the set of distributions that have a.e. continuously differentiable densities and satisfy Assumptions (ref) - (ref). The following theorem demonstrates a minimax lower bound on the convergence rate of any estimator as $n^{-1/3}$ (multiplied by a constant). Therefore, our estimator $\hat{f}_n$ achieves the optimal rate.
This paper applies the Myerson regularity condition as a shape constraint on the valuation distribution for nonparametric density estimation. We introduce a nonparametric estimator that is entirely data-driven and does not require tuning parameters. We demonstrate the consistency of this estimator at the cube-root rate, which is proven to be the minimax optimal convergence rate. We further derive the asymptotic Chernoff's distribution of the estimator and describe valid inference procedures.