Sample Complexity of Posted Pricing for a Single Item

Thank you for your thoughtful review!

Thank you for your thoughtful review and comments!

• The conceptual ideas of the work feel a bit incremental, given the long line of work in the setting of learning optimal auctions. The results are limited to a very simple setting of single item auctions.

We view the simplicity of single item auctions as a major plus of our work, and we were surprised that the sample complexity of welfare/revenue maximization even in this simple setting had not been settled before. For example, our Theorem 1 entirely removes any dependency on the number of bidders in the sample complexity for product distributions (whereas the previous best known bound was linear). In terms of conceptual ideas, we want to highlight that a key difference compared to prior work is that we want to analyze the dynamic program corresponding to the optimal posted-price mechanism. Indeed, our Theorems 1 and 2 (for product distributions) crucially exploit the structure of the dynamic program for our specific problem.

• The running time of the algorithm for correlated distributions is exponential.

The runtime is $(Tn(Tn)^{1+|\mathcal{S}|})$, i.e. exponential in $|\mathcal{S}|$. This is because there are $1+|\mathcal{S}|$ prices to decide, each of which can take $Tn$ possible values (one for each realized value in the $T$ samples of length $n$), and evaluating each combination of prices over each of the $T$ samples takes runtime linear in $n$.

We had in mind settings where $|\mathcal{S}|$ is a small constant, in which case the runtime of Empirical Risk Minimization is polynomial in $T$ and $n$, and our sample complexity is also not growing with $n$. This is well motivated in e.g. business settings where you can only change the price at the start of the month; in fact, there is substantial literature studying pricing policies where you cannot change the price too often (e.g. Cheung et al. 2017 below).

Cheung, Wang Chi, David Simchi-Levi, and He Wang. "Dynamic pricing and demand learning with limited price experimentation." Operations Research 65.6 (2017): 1722-1731.

• For example, I found the use of the word "policy" a bit confusing. Usually, this would imply some dynamic decision process, whereas here there is only a single-shot setting.

The terminology we adopt is that a policy is a specific prescription of the price to set at each time, and the goal of the (learning) algorithm is to decide on a policy from the samples. Technically the policy here still needs to be dynamic — once the item is sold, it must change the prices to infinity. So since the prophet inequality/dynamic pricing problems we study are intrinsically dynamic programming problems, we decided to use the word “policy” for generality, although we agree that we could have used a different word such as “price vector” instead.

• It would be good to use different symbols for the revenue/welfare objectives ... It might be useful to include the definition of the pseudo-dimension at least in the appendix.

Thanks for catching these typos and suggestions on exposition! We will definitely incorporate them in the next update.

Regarding line 104, the value-to-go is the expected value of the (optimal) dynamic programming solution, conditional on the item still being unsold at time i. It is referring to the quantity $r*_i$ in Section 2.2.

Regarding the proof sketch of Theorem 5, sorry for the brevity. We were trying to communicate the idea that statistically we need $\Omega(1/\epsilon^2)$ samples to get an $\epsilon$-approximation; however, under our construction, only 1/(1+|S|) fraction of the samples would be relevant. Therefore, in order to get $\Omega(1/\epsilon^2)$ relevant samples we now need $\Omega((1+|S|)/\epsilon^2)$ samples to begin with, as formally shown in Theorem 5.

• What settings other than single-item auctions can the results be extended to?

A natural next question is to extend our results to the problem of posted pricing for selling $k$ identical items (instead of one). We believe that many of our techniques can be extended to this more general setting, but we focus on the single item setting since prior to our work even that was not understood properly.

• For other types of distributions such as regular/MHR, can you derive optimal bounds?

Thanks for the interesting question! Our upper bounds in Theorems 1 and 4 are already tight (up to constants) without needing to make additional assumptions such as MHR. It is true that our lower bound constructions require distributions that are not MHR, and it is plausible to us that our lower bound construction from Theorem 2 (showing $\Omega(n/\epsilon^2)$ for product distributions) would not be possible when restricted to MHR. Put another way, it is plausible that an $O(1/\epsilon^2)$ upper bound is possible even for revenue maximization on product distributions under regular/MHR valuations, a question we leave to future work.

• For the bound on the pseudo-dimension, can't you use a direct argument like Morgenstern and Roughgarden (2016) for t-level auctions? I am not sure I understand the need to go through the dual class.

Thank you for this question! It is indeed possible to directly bound the pseudo-dimension using first principles. In fact, that was our initial approach. However, we later realized we could leverage the existing result of Balcan et al., which resulted in a shorter and cleaner proof. This is why we opted to present it this way in our paper.

• Can you comment a bit on the differences of your results/approach and [GHTZ'21]?

The primary differences are: (1) the bounds in [GHTZ'21] are only applicable to product distributions; (2) even within the context of welfare maximization for product distributions, our work removes the dependency on number of bidders $n$ in their $O(n/\epsilon^2)$ bound, as shown in Theorem 1.

Thank you for your thoughtful review and comments!

• What are the factors (multiplicative constants) in the upper and lower bounds in Theorems 1-4? What is behind O(...) and \Omega(...)?

We emphasize that because we have normalized valuations to lie in [0,1], the $O(\ldots)$ and $\Omega(\ldots)$ notation is not hiding any dependencies other than absolute numerical constants.

We would like to stress that optimizing the constants and coefficients in the sample complexity is not the main focus of our work. We are interested in whether the sample complexity grows with $n$, which in our mind is a more first-order dependence. Our main finding is that for product distributions, the sample complexity of welfare maximization does not grow with $n$, whereas the sample complexity of revenue maximization does.

• No conclusions: the paper does not have a concluding discussion

A rough, intuitive conclusion from this finding is that the dynamic programming thresholds computed from empirical distributions may be more prone to overfitting for revenue maximization than for welfare maximization. Put another way, more samples need to be collected for the revenue maximization problem in order to avoid overfitting. We will add a concluding discussion to the next version of the paper.

Thank you for your thoughtful review and comments!

• The paper assumes that one obtains independent samples from the 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.

Valuation samples can be obtained in practice through marketing research such as consumer surveys. We would like to emphasize that this is a standard model; the long line of literature on auction design from samples (e.g. CR16, and other citations in our paper) and pricing from samples (e.g. Huang et al. 2015 below) all generally focus on valuation samples. Although there are alternate models of information such as the purchase probability at a single price (e.g. Allouah et al. 2023 below), moment ambiguity sets (e.g. Wang et al. 2024 below), a difference is that these models do not consider the randomness caused by sampling.

Huang, Zhiyi, Yishay Mansour, and Tim Roughgarden. "Making the most of your samples." Proceedings of the Sixteenth ACM Conference on Economics and Computation. 2015.

Allouah, Amine, Achraf Bahamou, and Omar Besbes. "Optimal pricing with a single point." Management Science 69.10 (2023): 5866-5882.

Wang, Shixin, Shaoxuan Liu, and Jiawei Zhang. "Minimax regret robust screening with moment information." Manufacturing & Service Operations Management 26.3 (2024): 992-1012.

• Furthermore, it would be helpful if the authors could comment on alternative settings circumventing the Ω(n/ϵ^2) sample complexities incurred by the paper -- perhaps, by bounding the degree of dependence between the bidders?

Thank you for your question. This is indeed a fascinating area for future research. Recent works have explored welfare and revenue maximization under models with bounded correlations, such as linear correlations [Immorlica, Singla, and Waggoner, EC 2020] and graphical correlations of Markov Random Fields [Cai and Oikonomou, EC 2021]. It would be interesting to investigate the sample complexity within these frameworks, as these specific forms of correlations may allow one to circumvent the $\Omega(n/\epsilon^2)$ sample complexity lower bound from our Theorem 3.