Replicable Online pricing

Thank you for your positive review! Below we address your individual comments and questions.

I think the structure of the paper could be improved …

Thank you for the helpful feedback. We will make sure to incorporate your suggestion for the final version of our paper.

Does an analogous result of Theorem 3 holds even for the delegation problem?

Thank you for the question. We initially focused on the prophet inequalities problem in our lower bound, as it is the primary focus of the paper. However, you are correct that the argument can be extended to the delegation problem as well, and we will add this to the final version. The extension follows by establishing an analogue of Lemma 8 for the delegation setting, using a similar proof.

... Theorem 5, is the result provided tight?

Examining the dependence on individual parameters, the $\nu^{-1}$ term is necessary: even without replicability, identifying a single $\nu$-heavy hitter requires at least $\Omega(\nu^{-1})$ samples. As for the $\rho^{-2}$ dependence, while we do not know whether it is necessary for this specific problem, all known algorithms exhibit this dependence in the worst-case. More broadly, a $\rho^{-2}$ term commonly arises in the replicability literature and for certain problems such as mean estimation, it is necessary (see Theorem 7.1 of [ILPS22]).

Thank you for your positive review! Below we address your individual comments and questions.

… don’t give any matching lower bounds in these parameters … evidence that this polynomial blow-up is supposed to be there

Thank you for the question. In obtaining our result, we primarily had in mind the constant-parameter regime where $\rho$, $\beta$, and $\epsilon$ are set to small constants (e.g., 0.01). That said, we agree that understanding the precise dependence on these parameters is an interesting direction, both for our problem and for replicable median estimation more broadly. We will add this to the discussion of future work. Regarding the dependence on $\beta$, we recently realized that it can be improved to polylogarithmic. We will revise our paper to reflect this; the improvement follows by tracking parameter dependence in the proof sketch of Lemma 2 in [BNH+23]. For the other two parameters, we suspect that a polynomial dependence is necessary, though we do not currently have a proof. In the case of $\rho$, most prior work on replicability incurs a $\rho^{-2}$ dependence, and for some problems (e.g., mean estimation), this is known to be necessary (see Theorem 7.1 in [ILPS22]). As for $\epsilon$, the dependence is likely to be polynomial when using a median-based approach such as ours, given the known sample complexity of estimating the median even without replicability. Moreover, our lower bound in Theorem 3 relates online pricing to the interior point problem, which is closely tied to median estimation, and suggests that any algorithm for our setting may inherently need to perform some form of median estimation. While this connection is suggestive, we do not have a formal proof establishing it.

Thank you for your careful reading of our paper and feedback. Below we address your individual comments and questions.

“…matching lower bound…”

Here by matching lower bound, we intended to imply a polylog-star dependence on $|X|$ as in the place we claim an upper bound of $\text{poly}(\log^* |X|)$ and a lower bound of $\log^* |X|$. We certainly understand your concern and will revise the terminology to avoid any possible confusion. Regarding the other parameters, it is standard to take these parameters to be small constants.

“…why is $¼$…”

Note that the theorem also holds for $\alpha \in (1/4, 1/2 - \epsilon)$ by Theorem 1, which considers a more general (not necessarily i.i.d.) setting. We assumed $\alpha \le 1/4$ in Theorem 3 to simplify the proof. One cannot obtain $\alpha$ arbitrarily close to $1$ because of existing hardness results for the non-replicable version of the problem. Our main focus is small values of $\alpha$ as we want to show the linear dependence on $\alpha$ in Theorem 3 is tight.

“…use previous algorithms…”

Our improved bounds are necessary for the range we consider. Specifically, if the replicable heavy hitter algorithm has sample complexity $\nu^{-3}$ instead of $\nu^{-1}$, then in Theorem 3 we can only handle $\alpha \ge \Theta((\log^* |X|)^{-0.33})$ instead of $\Theta((\log^* |X|)^{-0.99})$. The improved bound we prove allows us to handle a much larger range. We will further emphasize this point in the paper.

“…expression with the various polynomial factors…”

Thank you for the suggestion. Following the argument in Footnote 18 of the arXiv version of [BGH+23] and keeping track of the relevant parameters, we obtain the bound $\tilde{O}(\\epsilon^{-4} \rho^{-2} \log^2(1/\beta) (\log^*|X|)^3)$. We will further revise our paper to reflect this.

“…significance of Theorem 4…”

Here we intend to show that the linear dependence on $\alpha$ in Theorem 2 is tight. Additionally, the theorem is conceptually interesting as it shows that, if we are willing to settle for smaller values of $\alpha$, we can obtain replicable prices using fewer samples.

“…work of Samuel-Cahn…”

We assumed that the work of Samuel-Cahn is folklore in the community. We will certainly clarify this in our paper to avoid any confusion for readers outside the field.

If you feel that our response has adequately addressed your major concerns, we would appreciate it if you possibly adjust your score accordingly.

Thank you for your careful reading of our paper and feedback. Below we address your individual comments and questions.

“…could the authors provide a separate section or dedicated paragraphs summarizing existing algorithms and results…”

Our paper already discusses relevant prior work in Appendix A, including known results on replicable algorithms for mean and median estimation, as well as the heavy hitter problem. That said, we understand the reviewer’s concern about clarity and agree that separating background from our contributions would make the paper easier to follow.

To address this, we will add the following paragraphs to the paper. If there are any other important references you believe should be discussed, please let us know and we would be happy to include them.

Sample-based prophet inequalities. The sample-based study of prophet inequalities—where the algorithm has access only to samples from the underlying distributions—has become an active and evolving area of research. This direction was initiated by Azar, Kleinberg, and Weinberg [1], who drew connections between this setting and the classical secretary problem. Specifically, they provide a general reduction, showing that any algorithm in the order-oblivious secretary setting implies an algorithm in the single-sample prophet inequalities setting. For the case of single-choice prophet inequalities problem, Rubinstein, Wang, and Weinberg [2] showed that even a single sample per distribution suffices to achieve the optimal 1/2-approximation. In the i.i.d. variant, they also proved that a constant number of samples is enough, with later work by Correa et al. [3] refining the required sample complexity. When the arrival order is random, as in the prophet secretary model, Correa et al. [4] established that a single sample still enables a 0.635-approximation. This sampling approach has since been extended to more structured selection problems, such as those involving matroids and matchings [5, 26]. More recently, Cristi and Ziliotto [7] developed a unified argument showing that constant sample access suffices to achieve approximate optimality across both prophet-secretary and free-order settings, despite the exact optimal approximation ratios for these variants remaining open.

Replicable mean and median estimation. Replicable algorithms for mean and median estimation were first developed by [8], who introduced the notion of replicability and provided replicable algorithms for several important problems. Their replicable median algorithm has sample complexity exponential in $\log^* |X|$. [9] later improved on this algorithm by drawing connections to differential privacy, obtaining an algorithm with sample complexity that is polynomial in $\log^* |X|$, albeit without computational efficiency.

Replicable heavy hitters. Prior work has also studied replicable algorithms for heavy hitter identification. [8] and [10] provide algorithms that return a list of candidate heavy hitters, with sample complexity scaling cubically in $1/\nu$. More recently, [11] improved the dependence on the failure and replicability parameters for expected sample complexity, but still maintained a $\nu^{-3}$ dependence. In contrast, we consider a more specialized variant where only a single heavy hitter needs to be output (assuming one exists), and give a new algorithm with nearly linear $\nu^{-1}$ dependence.

... introduces additive error, which is undesirable ... elaborate on this point or provide supporting references

We focus on multiplicative error, as it is the standard metric for evaluating algorithmic performance in the context of prophet inequalities (e.g., see [1–7, 12–15]). Multiplicative guarantees are preferred over additive ones because they remain meaningful even when the offline optimum is small. For example, an algorithm that achieves expected value within $\epsilon$ of the offline optimum $\textnormal{OPT}$ (i.e., additive error) offers no useful guarantee when $\textnormal{OPT} < \epsilon$. In contrast, a multiplicative guarantee ensures that the algorithm's performance is always an approximation of the optimum, regardless of its magnitude.

…the increased sample complexity required for replicability

We note that $\log^* (.)$ is an extremely slow-growing function; for example, $\log^*(x) \le 5$ for any $x \le 2^{65536}$. As a point of comparison, the number of atoms in the observable universe is estimated to be around $2^{265}$. Sample complexity is one of the main measures in context of replicability. Our work provides both upper and lower bounds on the sample complexity of the problem, thereby quantifying the price of replicability in this setting.

If you feel that our response has adequately addressed your major concerns, we would appreciate it if you possibly adjust your score accordingly.

References:

[1] Pablo D Azar, Robert Kleinberg, and S Matthew Weinberg. Prophet inequalities with limited information. In SODA, 2014.

[2] Aviad Rubinstein, Jack Z Wang, and S Matthew Weinberg. Optimal single-choice prophet inequalities from samples. Innovations in Theoretical Computer Science, 2020.

[3] Jos´e Correa, Andr´es Cristi, Boris Epstein, and Jos´e A Soto. Sample-driven optimal stopping: From the secretary problem to the iid prophet inequality. Mathematics of Operations Research, 2023.

[4] Jos´e Correa, Andr´es Cristi, Boris Epstein, and Jos´e Soto. The two-sided game of googol. The Journal of Machine Learning Research, 23(1):4870–4906, 2022.

[5] Constantine Caramanis, Paul D¨utting, Matthew Faw, Federico Fusco, Philip Lazos, Stefano Leonardi, Orestis Papadigenopoulos, Emmanouil Pountourakis, and Rebecca Reiffenh¨auser. Single-sample prophet inequalities via greedy-ordered selection. In SODA, 2022.

[6] Haim Kaplan, David Naori, and Danny Raz. Online weighted matching with a sample. In SODA, 2022.

[7] Andrés Cristi, and Bruno Ziliotto. Prophet inequalities require only a constant number of samples. In STOC, 2024

[8] Russell Impagliazzo, Rex Lei, Toniann Pitassi, and Jessica Sorrell. Reproducibility in learning. In STOC, 2022

[9] Mark Bun, Marco Gaboardi, Max Hopkins, Russell Impagliazzo, Rex Lei, Toniann Pitassi, Satchit Sivakumar, and Jessica Sorrell. Stability is stable: Connections between replicability, privacy, and adaptive generalization. In STOC, 2023

[10] Hossein Esfandiari, Amin Karbasi, Vahab Mirrokni, Grigoris Velegkas, and Felix Zhou. Replicable clustering. In NeurIPS, 2023.

[11] Max Hopkins, Russell Impagliazzo, Daniel Kane, Sihan Liu, and Christopher Ye. Replicability in High Dimensional Statistics. In FOCS, 2024.

[12] Mohammad Taghi Hajiaghayi, Robert Kleinberg, and Tuomas Sandholm. Automated online mechanism design and prophet inequalities. In AAAI, 2007.

[13] Robert Kleinberg, and Matthew Weinberg. Matroid prophet inequalities. In STOC, 2012.

[14] Michal Feldman, Nick Gravin, and Brendan Lucier. Combinatorial auctions via posted prices. In SODA, 2015.

[15] Shuchi Chawla, Jason D. Hartline, David L. Malec, and Balasubramanian Sivan. Multi-parameter mechanism design and sequential posted pricing. In STOC, 2010.

Thank you for your positive review! Below we address your individual comments and questions.

.. suggest directions for future work in empirically analyzing the implemented replicable pricing strategies …

We thank you for this suggestion and will include it in our paper as a direction for future work.

How could the results be extended to cover distributions whose support is continuous or of unknown support addressing real environment settings?

We note that our lower bound in Theorem 3 shows that the problem cannot be solved with finite sample complexity for infinite sets. This is because a solution for an infinite set would yield a solution for arbitrarily large finite subsets, which by this theorem requires arbitrarily large sample complexity (see also footnote 3 in page 6)