Summary
The paper considers the problem of statistically estimating the optimal posted price mechanism for selling one item to multiple buyers. Here, it is assumed that the buyers appear sequentially, a price is presented to each of them and the sale is completed if the price posted to them is lower than their valuation. The mechanism aims to optimize one of two targets -- the welfare, defined here as the value of the bidder who wins the auction and revenue of the auctioneer which is the price paid by the winning bidder. It is assumed that the valuations of the bidders are drawn from a distribution and the paper aims to analyze the sample complexity of determining near-optimal posted prices for each of these settings where it is assumed that the learner receives iid samples from the bid distributions. Depending on the degree of dependence between the valuations of the bidders, the paper considers two settings -- firstly, the independent setting where the values are determined independently for each bidder and the dependent setting where the valuations are correlated across the bidders.
In the independent setting, it is shown that there exists a separation between the sample complexities of welfare and revenue maximization. They show that essentially $1 / \epsilon^2$ samples suffice for welfare maximization whereas revenue maximization necessarily \emph{requires} $\Omega (n / \epsilon^2)$ samples where $n$ is the number of bidders and $\epsilon$ an additive error parameter. In this case, they obtain near-optimal characterization of the sample complexity while the upper and lower bounds from prior work are $n / \epsilon^2$ and $1 / \epsilon^2$ respectively. In contrast, when the bids are correlated, the paper shows that $\Omega (n / \epsilon^2)$ is \emph{required} for both revenue and welfare maximization. To partially address this pessimistic bound, the paper also considers the setting where the class of possible posted prices is restricted. The particular restriction considered in the paper is by restricting the change points of the price schedule; that is, the price is only allowed to change at $k$ points in the sequence of prices. Here, it is shown that sample complexities independent of $n$ are obtainable and instead only depend on $k$.
The proof of the upper bound independent of $n$ for welfare maximization in the independent valuation setting is quite interesting. Essentially, the paper analyzes the dynamic programming algorithm for welfare maximization. Observing that the (welfare of the) posted prices have a closed-form solution in terms of the welfare of the next step, the paper proves that the sub-optimality of the posted prices may be bounded by a sum of error terms which satisfy a backwards martingale structure. The use of standard Martingale concentration bounds then yield the required bound. This proof is elegant and appears to be novel. Unfortunately, such martingale structure does not hold in the presence of dependencies between the valuations. Instead, they adopt a classical uniform convergence based approach and show that the statistical complexity may be controlled by the pseudo-dimension of the policy class.
Overall, this is a nice paper that obtains nearly optimal statistical characterizations in several fundamental settings, making several interesting contributions. The proofs of the results, the welfare maximization for independent valuations in particular, are elegant and well-presented. My main concerns are with the assumptions underlying the learning problem. The paper assumes that one obtains independent samples from the \emph{valuations} of the bidders. It is not clear how such samples are obtained -- it is not clear how one may obtain such samples in practice. More exposition on this point would be helpful. Furthermore, it would be helpful if the authors could comment on alternative settings circumventing the $\Omega (n / \epsilon^2)$ sample complexities incurred by the paper -- perhaps, by bounding the degree of dependence between the bidders?