Replicable Online pricing
Authors: Kiarash Banihashem
Mohammadhossein Bateni
Hossein Esfandiari
Samira Goudarzi
MohammadTaghi Hajiaghayi
Venue: NeurIPS 2025 poster ()
Keywords: Replicable
online
pricing
Primary area: theory

Abstract: We explore the concept of replicability, which ensures algorithmic consistency despite input data variations, for online pricing problems, specifically prophet inequalities and delegation. Given the crucial role of replicability in enhancing transparency in economic decision-making, we present a replicable and nearly optimal pricing strategy for prophet inequalities, achieving a sample complexity of 
$\textnormal{poly}(\log^* |\mathcal{X}|)$, where $\mathcal{X}$ is the ground set of distributions. Furthermore, we extend these findings to the delegation problem and establish lower bound that proves the necessity of the $\log^*|\mathcal{X}|$ dependence. En route to obtaining these results, we develop a number of technical contributions which are of independent interest. Most notably, we propose a new algorithm for a variant of the heavy hitter problem, which has a nearly linear dependence on the inverse of the heavy hitter parameter, significantly improving upon existing results which have a cubic dependence.

Replicable Online pricing
Kiarash Banihashem
MohammadHossein Bateni
Hossein Esfandiari Google Research London, UK esf aefandari@googllee
University Maryland
Google Research New York City, New York, USA bateni @google com
College Park, MD, USA kiarash@umd.cnm
Samira Goudarzi University of Maryland College Park, MD, USA samirag@umd. edu
Mohammad Taghi Hajiaghayi University of Maryland College Park, MD, USA eajiaghayi@@mail.. com
Abstract
We explore the concept of replicability, which ensures algorithmic consistency despite input data variations, for online pricing problems, specifically prophet inequalities and delegation. Given the crucial role of replicability in enhancing transparency in economic decision-making, we present a replicable and nearly optimal pricing strategy for prophet inequalities, achieving a sample complexity of the ground set of distributions. Furthermore, we extend these findings to the delegation problem and establish lower bound that proves the necessity of the log" | dependence. En route to obtaining these results, we develop number of technical contributions which are of independent interest. Most notably. we propose a new algorithm for variant of the heavy hitter problem, which has nearly linear dependence the inverse of the heavy hitter parameter, significantly improving upon existing results which have a cubic dependence.
poly(log" |)))) where
Introduction
Scientific research fundamentally relies on the ability to repeat experiments and achieve similar results. This principle, known "reproducibility" is critical to validating findings and ensuring progress across fields. However, many researchers [HIB + 18 IHGP17 LKM+ 18) have raised concerns about "reproducibility crisis" where studies often fail replicate reliably. This has highlighted the pressing need for methods that guarantee reproducibility and transparency in research.
A significant challenge in achieving reproducibility is the inherent variability in data, which often stems from complex and stochastic processes. Even when researchers meticulously document their methods, others may struggle to reproduce the results due to this randomness. This variability opens the door to misleading findings, whether intentional or unintentional. For instance, practices such as "p-hacking" whheee researchers test multiple hypotheses until significant result is found can can undermine the validity of scientific conclusions.
To address these challenges from theoretical perspective, Impagliazzo et al. ILPS22 (STOC'22)
introduced the notion of replicable algorithms for statistical problems Formally, an algorithm A that takes input set of samples S C X and binary string representing its internal randomness called p-replicable if, for any distribution D over X.
Sy (A(Si:r) = A(S2: 2 1- P.
(1)
'The original work used the term "reproducible" (to align with common usage), but subsequent works have adopted "replicable", term we use here.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

where R denotes the distribution of the random bits used by the algorithm. Intuitively, Equation ensures that the algorithm's output is determined primarily by the input distribution rather than specific samples or randomness. This safeguards against data manipulation or corruption, as such actions are easily detectable by re-running the algorithm. Bun et al. [BGH 23] (STOC'23) further developed the theory of replicable algorithms by relating it to other notions of stability such as differential privacy, adaptive generalization. Replicable algorithms have been developed for numerous problems including high dimensional mean estimation [HIK+24D 244) (FOCS'244 clustering [EKM
(NeurIPS' 23), bandits [KKK*23 (ICLR 23), and learning halfspaces [KKL 24) (ICML'24).
Replicability is especially critical in settings where decisions have significant werl-world consequences, such as public systems, govemment policies, or large-scale markets. In these scenarios, faimess and transparency are paramount. Even when the secision-makiing process is publicly accessible, decision- makers could manipulate outcomes by selectively choosing data to support desired conclusions. Replicability acts as a certificate that the decision-making process is robust and immune to such manipulations, particularly in cases where the decision space is large or continuous, and no single "best" choice exists.
Motivated by these considerations, we study replicability in the context of the prophet inequalities problem, a fundamental model in online docisionnmakingg with well-established significance from both theoretical and economic perspectives [HKP04 BIK07 HKS07 CHMS1O]. In its simplest form, this problem involves sequence of random values XI...., XN arriving online, where each X; drawn from known distribution D,. The goal is to select a single value that large in expectation. A classic solution involves using fixed threshold and accepting the first value that exceeds r. It is well-known (e.g., see ( that setting т = E. [max (X1, {Xi..... XN
) / guarantees, expectation, a value at least half of the offline optimum E [max (X1,- Nx H. which is tight. Similarly, setting T to be the median of E [max {X [X....., ,.....,. XN with appropriate tie-breaking when the distribution has atoms, leads to the same 1/2 guarantee (SC84).
While the classical formulation assumes that the distributions D1. Dr are fully known, this is often unrealistic in practice. Instead, we consider a sample-based framework, where we only have access to a finite number of samples from each D,. The key challenge here is to design a replicable algorithm that uses few samples to set a threshold t achieving a competitive performance. We say a threshold is a-competitive if the corresponding strategy obtains at least atE [max (X XN]] in expectation. An algorithm solves the Replicable Online Pricing (ROP) problem with parameters (a, p. (8) if it p-replicable and outputs an a-competitive threshold with probability at least B. In order to avoid issues with tie-breaking, we use extra "coin" to decide whether element with value equal to r should be accepted (see Section 2 for further details on this formulation). In this work, we analyze the sample complexity of the ROP problem, presenting efficient algorithms and proving impossibility results.
We further study the implication of our results to the delegation problem. which has been widely studied in economics under various settings and models [Ho18] FJ3 CF98 AVIO AVIO [BI3 AE17
BGHOT KK18 HMRS24] [BHHS24]. At its core, delegation involves an authority figure, referred to as the principal, facing challenge and relying on an expert, referred to as the agent, to solve it, with the agent being responsible for searching for and proposing a solution based on their expertise. practical example of this is the relationship between a public entity and a private contractor or the intaa-ogaanzzationa workflow between corporate management and a specialized division. Each possible solution yields specífic utilities for the principal and the agent, often leading to utility misalignment due to differing incentives. To mitigate this misalignment and ensure the consideration of their interests, the principal may announce a set of acceptable solutions (e.g.. by establishing
certain criteria) before the agent begins their search. This preemptive strategy helps enforce alignment
between the principal's 's objectives and the agent's 's proposals, balancing the trade-off between granting the agent enough autonomy and maintaining control over outcomes that align with the principal's goals.
In particular, we consider a model similar to the model studied by [KK18] (EC*18). We assume there a distribution D defined over an abstract space 52 of possible solutions for the delegated task. Each solution w E Ω has an associated quality from the principal's 's perspective, denoted by z(w), and possibly different quality from the agent's perspective, denoted by y(w). The agent is supposed to
make N independent and identically distributed (i.id.) draws from the distribution D, resulting in collection of N candidate solutions W1, W2, .N, E Q. The agent then examines 2 (w4) and (wx))
2

---

for each candidate wi and then chooses one to present to the principal. As mentioned, in the absence of any constraints from the principal, the agent would trivially select the solution w, maximizing their own objective y(4;), resulting in the principal receiving the corresponding value of s(ws). To enhance this arrangement, the principal imposes constraint at the outset, specifying that they will only accept solutions w for which rr(w) exceeds a certain threshold т. As in the ROP problem, we allow the use an extra coin for tie-breaking. (see Section 2 for more details) This causes the agent to pick the w; maximizing v(-) subject to the acceptance constraint.
We assume that the principal can learn about by drawing samples and observing their associated quality value r and can use its knowledge in devising its price. The principal's 's goal is to set price such that the obtained solution provides a good approximation to the optimal wi for the principal. In particular, we say a threshold T is a-competitive if the expected utility of the principal using is at least afE [max {a((w)). .... =((N)) }}] ]. An algorithm solves the Replicable Delegation (RD) problem if it is p-replicable and with probability at least 3 outputs an a-competitive threshold.
1.1 Our contribution
Our first result is an algorithm that replicably outputs a (1/2 -)-oomeetitive threshold with high probability for finite distributions. A standard approach to prophet inequalities is to set T = E [max (x,,..-> XN KN]]/ J/2,, suggesting that one might attempt to apply this strategy the ROP problem using replicable mean estimation algorithm, such as that of [ILPS22], to approximate this threshold. However, as we discuss in Section 3 these algorithms have an additive error, preventing them from yielding competitive prices.
To overcome this limitation, we design an algorithm based on the median approach of SC84] leading to the following result.
Theorem 1. Assume that the distributions Dj are all supported on a known finite set X. For any E (0, 1/2) and p. 3 > O, there exists an algorithm solving the ROP problem with parameters (1/2 - c, p) B) using at most poly (log" px),p= 1,,1,,1,00 e) samples from each D:.
To achieve the above result, we show that good prices can be obtained by applying replicable (ap- proximate) median estimation algorithms to the distribution of max (X1...., X. Such algorithms have previously been obtained by [ILPS22] and [BGH 1 23
2] While both of these algorithms have
an approximation error in estimating the median, unlike the algorithms for mean estimation, the effect of these errors the quality of the output price can be bounded. As show in Lemma p-approximate median (see Section 2 for a formal definition) leads to a (1/2 - -)moompttiivee price. We further generalize our technique and apply it to the delegation problem, obtaining the following result.
Theorem Assume that the distribution D is supported over a known finite set X. For any (0, and p. B > O, there exists algorithm solving the RD problem with parameters (1/2-e, B) using at most N - poly (log" 1x ",-,, -1 samples from D.
For the ROP problem, we establish that the dependence on the size of X is necessary. Formally, letting the sample complexity of an algorithm denote the number of samples requires from each D; (see Definition [] we prove the following theorem.
Theorem 3. There exist constants p. 3,,,, > O and a set X with the following property. Fix > e1 (log" (.x1) and N 2 oz. Any algorithm that can solve the (a, P, reppllcaaa online pricing problem has sample complexity a0 log" 1221), even if we assume that XI...., XN are i..d
The constant 0.99 in the theorem above can be replaced with any value strictly less than 1. To prove this theorem, we reduce from the replicable interior point problem, where the goal, given a distribution D, to output a value in the range (min(D), max D)] in a replicable manner (see Section 2). By leveraging the privacyto-rrellccabee
reduction of [BGH 23), we establish that this problem requires at least "((lo"" |x')) samples (see the Appendix).
"Specifically. use the algorithm of [12], which has polynomial sample complexity. However, we note that their algorithm is not computationally efficient due to reliance on correlated sampling. Alternatively, one can use the approach of [31] which is polynomial time but has a sample complexity exponential in log" | We note that since our result is obtained via reduction to replicable median estimation (see Lemma 8), any possible future improvements for that problem would immediately yield improvements to our results as well.
3

---

Moreover, we show that the "hard distributions" for the interior point problem exhibit an additional structural property: they contain no "heavy" points. Specifically, for any a 2 ??(log" [x(1 1719 no point in the distribution has probability mass exceeding a. We then argue that, in such instances, any competitive price must lie within the interior of the distribution of X, This is proved in Lemma and the main intuition behind it is as follows. If the price is set outside this interior, the algorithm will either reject all elements or accept only the first element. Using the fact that the distribution contains no points with probability exceeding where, for an appropriate range of N 23 a -1 the first element is roughly I/N times the maximum element. Therefore, if the price is outside the interior of the distribution, its competitive ratio is at most =e 1/N. We then extend this result to arbitrary N by modifying these instances to output 0 with small probability. Further details can be found in Section 4
can construct instances of the prophet inequalities problem
We further show that, in the special case of i.i.d. distributions, we can match the dependence on or in theorem below.
Theorem 4. For any p. 3 > 0 and a s 1/4 there is an algorithm that can solve the ROP pricing problem for ii.dd distributions with parameters (a,, p. B) and sample complexity
O poly(loo p ,-1))
En route to proving our results, we develop a novel and improved replicable algorithm for outputting a heavy hitter for an input distribution. A value is called heavy v--haavy hitter for a distribution D if its sampling probability under 1) is at least v. In the heavy hitter problem, we are given a distribution D over a finite set X. which is not necessarily ordered, and the goal is to (replicably) output v-heavy hitter for D. We focus on an approximate version of the problem which assumes that the underlying distribution is guaranteed to have a (yu)) hitter. For this problem, we obtain the following result.
Theorem 5. For any p. p. > 0 and 7 2 4, there exists a p-replicable algorithm with sample +lg(((=11) with the following guarantee: Assuming (ry)-heavy hitter exists, the algorithu outputs v-heavy hitter with probability at least 1 - -.. If no (hv)-heavy hitter exists, then with probability at least 1 - B, it outputs either Null or a v-heavy hitter.
complexity O ty-'pp2'og'' (o
Existing work providing replicable algorithms for the heavy hitter problem consider variant where the goal is to return a list that contains all (heyy- hitters and is a subset of v-heavy hitters. For this variant, Impagliazzo et al. [ILPS22] obtain p-replicable algorithm with 1
success probability that has sample complexity Ö (inn(popp ). Esfandiari et al. TEKM+23
improve on this with an algorithm achieving sample complexity Ö( (("==()-1>> log(1/3)). More
recently, Hopkins et al. [HIK 24b) developed an algorithm with expected sample complexity O( 11 log( pim )). All of these results have a cubic dependence on v, whereas our approach achieves a nearly linear dependence. Although, it is worth noting that the variant considered by the previous works is more general than the one we consider here. We note that, even without replicability, one requires at least 1(1-1) samples to find a heavy-hitter and as such our result is nearly tight. We further note that without the improved dependence, the range of in Theorem would be 2((log" (2(1) -0.33) instead of 2((lo"" (21)-00.9).
To prove the above result, we design a two-stage algorithm. First, we sample a candidate set ((1) of size approximately =- Then, using a fresh set of samples 5(2), we estimate the probability of each point in ((1), The elements in 5(1) are randomly permuted, and we output the first element (in the order of the permutation) whose estimated probability exceeds threshold v', drawn uniformly from [M, rw].
A key challenge in implementing this strategy is ensuring that the random permutation is defined replicably. This is nontrivial, since the permutation depends on 5(1), which itself depends on the samples. To address this, use h- wise independent sampling based on Reed-Solomor codes to assign a number to each element in X', then sort S(1) based on these numbers. Crucially, while the numbers are not fully independent, any subset of size ||5(2) behaves as if chosen independently.
Note that one can handle E (1/4,1/2) using Theorem
4

---

Although the two-stage approach has been previously explored (e.g.. see |EKM 23I), our tailored analysis significantly reduces the sample complexity from cubic in vー to nearly linear. This improvement stems from two key insights. First, our use of random permutation reduces the number of "important" candidates (from a replicability perspective) from wー to log(v-1). Second, we leverage sharper version of the Chernoff inequality, yielding an additional factor of vー in savings. Importantly, this sharper version can only be leveraged for our problem, and not the more general variant studied by Esfandiari et al. [EKM
Map of the paper. The remainder of the paper is organized as follows. Section discusses the preliminaries of the paper. S proves the upper bound for ROP. Section proves the lower bound. Finally, Section proovides the heavy-hitter algorithm. Due to space constraints, parts of the proofs, the proof for RD, as well as the discussion of further related work is deferred to the Appendix.
2 Preliminaries
Notation and setting. Given a positive integer n, we use [r]] to denote the set prophet inequality problem is defined as follows. N random values XI...., XN arrive in an online manner, where X; is sampled from a distribution D, and the goal is to choose a single item with high value. The distributions D, are all supported over set X R2 known upfront.
The
We will focus on threshold based algorithmss for this problem: given a fixed price T E RR20 we define i(X1...., NN: T, 0)- = arg min {i: X; 2 } and i(X1..... Xx; T, 7) arg min {i: X; > r) to denote, respectively, the index of the first value greater than or equal to 7 and the index of the first value strictly greater than т. If no such value exists, we set i(.) to +oc. For simplicity, we will often write i(T, 0) and i(T, 1). Let K E [0, 1] and sample B ~ Bernoulli(x)). We say a pricing pair (T, x) a-competitive for D1..... ........ Dy if E (.)))) 2 aE [max (x,...., H., where the expectation is over the randomness of XI...., XN. B. We rely on tic- tie-breaking because our median based pricing requires the algorithm's 's acceptance probability to be close to 1/2. max X1...., XN has a large atom at its median, no single threshold achieves this without tie- the-breaking. Although one of [Xx(r.o] or E [X.(..)] must match the a-competitiveness of E [X,(,,)]] identifying which one requires full knowledge of the distributions. Intuitively, if X; occasionally takes very large values, B == 1 is preferable; otherwise, B is better, but such rare events cannot be detected from samples.
One can define a replicable variant of the prophet inequalities problem by requiring that the algorithm outputs a price in p-replicable manner while maintaining an a-competitive guarantee. That is, in expectation over both the randomness of X; and the algorithm itself, the expected output must be at least aE [max {X...... .N H. However, this formulation has a fundamental issue: an algorithm can effectively bypass the replicability requirement by outputting O with probability 1 and, with probability p. employing a non-replicable 1 1/2-competitive algorithm (e-g., the single- sample algorithm from Rubinstein, Wang, and Weinberg [RWW19)). This approach achieves a p/2-competitive ratio, which is constant for constant p. while still technically satisfying replicability. Intuitively, though, such an approach is undesirable because its competitiveness derives entirely from the non-replicable outputs.
Given the above issue, we opt for the following formulation, which requires the output price itself to be a-competitive.
Definition 1 (Replicable Online Pricing (ROP)). An algorithm A solves the Replicable Online Pricing (ROP) problem with parameters (a, p. 3) and sample complexity if it takes n samples from each distribution D., is p-replicable, and outputs an a-competitive price pair (T, k) with probability at least 1 - B.
This definition aligns with existing work on replicability in statistical problems, wherein the quality of an algorithm's 's output is assessed by defining an "acceptable set" (in this case, the set of all a- competitive prices) and requiring that the algorithm's 's output falls within this set with high probability.
The Replicable Delegation(RD) problem is defined analogously. In the delegation problem, an agent samples solutions W1, w from a distribution D. where each sample has utility s(wx) and y(w)) for the principal and the agent respectively. The principal commits to price т, which is announced to the agent beforehand, and only accepts solutions satisfying x(w;) 2 T or au())) > т. The agent then chooses the acceptable solution maximizing its own utility. Let i(T B) arg max max)))(w:)2 (wx))
5

---

for B = 0 and i(τ, B) = arg maxxxr(())>>>>) y(wn) for B = 1. We say the pricing pair (T, k) is where B Bernuuli(x). An
a-competitive if E [( BB)] alE [max (([)),...,,(())))) algorithm A solves the RD problem with sample complexity if is p-replicable, takes n.V samples from D and with probability 1 outputs an a-competitive price. Note that we allow n. samples here, instead of just n, in order to align with the ROP definition.
Throughout the paper, will frequently use the following multiplicative form of the standard Chernoff bound. Let E [0 and sample n i.i.d variables Vi,...,,, Y,, from the distribution Bernouli(p). define p Σ, Y.
[r pl 2 8p] S 2e 2e-22 6'mp/3
(2)
Interior point and approximate median. Given distribution D over ordered set X, say x in the interior point of D if min(D) I x S max(D) D) where min(D) and max (D) denote, respectively, the minimum and maximum elements with strictly positive probability under D. We say x is a 7-approximate median for 7 < 1/2 if min (Prx~D [X 2 x] Prx-D [X S x]} 2 1/2 1//2-7, The two problems closely connected; any approximate median automatically an interior point and, conversely, an algorithm for (replicable) interior point can be transformed into an algorithm for (replicable) approximate median with slight increase in sample complexity. As shown by [BGH=23] there exists an algorithm for the replicable interior point problem with sample complexity polynomial in log" |.(
Lemma 2. For any p. 0, > O, there exists a p-replicable algorithm that outputs y-approximate
median with probability at least 1 B and has sample complexity poly(log" X), p%1.p-... 1,33,,-1)
We refer to BGH 23 for the proof. Specifically, following the argument in Footnote 18 of the arXiv version of [BGH + 23) and keeping track of the relevant parameters, obtain the sample complexity
δ ( p- log" (1/8) (log" (x1)))
It is clear that if a distribution has large atom (e.g., if it takes single value with probability 1), then Prx-n [X 2 ær] can never be close to 1/2, which is required for median pricing. To address this, we extend the definition of approximate median pricing pairs (T, We say pricing pair (T, K) is 7-approximate median for D if
(1 - (1x))Prxe Pr XX 2 r] RPrx-D [> (1/2-11/22+))
We further prove the following result in the Appendix.
Proposition 3. For any p. P,B,7 > O, there is p-replicable algoritim that outputs "-- approximate median pair (T, k)) with probability at least 1 - 3 and has sample complexity poly(log" X2,, 8 -
3 Replicable Online Pricing Upper Bound
In this section, we prove Theorem I and Theorem via a reduction to the replicable (approximate) median estimation problem. As mentioned earlier, one natural approach to solving the ROP problem to use existing replicable mean estimation algorithms to compute E [max {X1,.... Xx //2. This may initially seem more appealing than our do not require a finite ground set X' and even work for continuous distributions, whereas median estimation incurs dependence on log" (x) However, these approaches introduce additive estimation error, which can be problematic when E [max {X Xxv H] small, potentially Ieading to negative outputs. While one might attempt to mitigate this issue using techniques such adjusting the error based on an initial sample set, our lower bound in Theorem GecoremBesterr establishes that no saproach-including these eliminate the dependence on log" [
approach, mean estimation algorithms
We first state the following lemma which follows folklore techniques (e.g., see KKI8 In the interest of space, we have moved the proof to the Appendix.
Lemma 4. Let (T, be a 7-approximate median pair for the distribution of (X..... Xn). Then (T, K) is a (1/2 - comopettiee price pair.
Proof of Theorem 7 Let s = poly(log" |20, p 1--,,,81,61 denote the sample complexity specified
by Proposition 3 For each 1 < i < we take samples from the random variable X, with

---

distribution D,, denoting these samples by Ei. Then, for each S S s, we define 8 := max Zij. It follows that VI.....81 Vs are s samples taken independently from the random variable Y defined as Y == max(X1,..... Xx).
Using the given p-replicable algorithm for 7-approximate median pair (T, we compute 9- approximate median of Y based on the samples ....... V/. algorithm, which we know (1/2 7) competitive by Lemma and therefore satisfies the desired properties of the (1/2
We return this as the output of our pricing
1 7; P. 8) online replicable pricing algorithm. Hence, the theorem follows. C
Proof of Theorem
We first observe that since the elements are ii.d,
E
[1]]
[x +.... Xx) 2 mmax (XI,...,X) XN3].
We therefore assume that a Z 1/N as otherwise, using the price O, we obtain (1/N)- competitive price.
Set r to Since 2 1/N, we have S N. Divide the input variables X1...., XN into groups of size [N/r]. with the last group possibly having less than [N/r] elements. Let (r, x) be 1/4- approximate median pair for max ( X[N/r1 We estimate this replicably as in Proposition By Lemma 4 using this pair the expectation of the output is at least E max Since we have at most groups however,
X(N/r]
E. [max (X1..... ........)]]] S rIE [max
Therefore, (T, is comppetiiieee Since S In this means the price it at least a-competitive.
We next bound the sample complexity of our algorithm. To calculate (r, k), suffices to have poly(log" [X(,, P. B) samples from max (X1,..., X [|N/r1]- Observe however that we always have at least r/2 full groups: if then have exactly full groups and if 2 2 we have least r - 1 2 r/2 full groups. Therefore, suffices to have polyyloo" (2'), 1p..3"33- ,33²) samples from each of the input variables. Since r = L and s 1/4, we have r 2 1
Ser which means 2 S. 16a.
Therefore, the sample complexity bound follows as well.
4 Replicable Online Pricing Lower bound
In this section we prove Theorem Our proof is obtained via a reduction from the interior point problem. Specifically, we rely on the following result.
Proposition 5. There exists p, B > 0 such that any p-replicable algorithm solving the statistical interior point problem with failure probability at most B for a distribution Z over a finite set F has sample complexity Silog" [F)
The above result follows from the hardness of the differentially private version of the problem; refer to Appendix E.2 for more details.
We note that the nature of the set F do not play a major role in the problem beyond its size; for any other ordered set F' of the same size, an algorithm for the set can be turned into an algorithm for the set F' and vice versa. Our proof of Theorem is divided into multiple steps. Due to space constraints, we sketch the steps and state the Lemmas here and refer to the Appendix for the full proofs.
We prove that the lower bound for the interior point problem holds even under the additional assumption that the underlying distribution contains no "heavy" elements-thore with sampling probability exceeding a, where a falls within the range specified in Theorem (Lemma 7). To prove this, we show that if the distribution did contain heavy elements, the statistical interior point problem could be solved using novel heavy hitter algorithm, which we introduce in Section This effectively implies that the "hard instances" for the replicable statistical interior point problem exclude heavy elements.
"This lemma also implies that this problem unsolvable with any finite sample complexity over infinite domains since solution for an infinite set would yield solution for arbitrarily large finite subsets, which by this lemma requires arbitrarily large sample complexity.
7

---

2. We next show that, for suitable choice of the set X, if the distribution X does not contain heavy element with probability 2 a, then the maximum of M = 1/a ii.d. draws of X is, in expectation, at least (MM [X] (Lemma g We refer to distributions without such heavy elements as a-light.
3. We then prove that any c-light instance for the interior point problem can be transformed into an instance of online pricing with N 2 22(1/o) such that improving on D(a))-ccmeeiiive prices only be done by solving the interior point problem. In this reduction each sample from an X; in online pricing corresponds to roughly 1/a samples for interior point (Lemma (
We proceed with a formal proof. We first extend the above hardness result to the case where the distribution does not contain any heavy elements. We call such distributions light and formally define them below.
Definition 6 (light distribution). A distribution Z is o-light if = for all
Lemma 7. There exists constants p. 8,,c1 > O with the following property. For any a satisfying 2 ai (log" [FI) 0.99 any p-replicable algorithm solving the statistical interior point problem with success probability - 3 on a set F has sample complexity Dtllo"" [Fl), even if the underlying distribution is ensured to be a-light.
We next state the following lemma that lower bounds the expectation the maximum copies of a distribution under certain conditions.
Lemma Let X = (I/e)² where E (0, 1/2) and Z is an a-light distribution over the set F {1. ... (FI). Let XI...., NM.....Ms be iid copies of X where M S 1/(2o... Defining Y max (Xi,..., X we have
E S S01/M + +Y)
We can further generalize the above lemma to N 2 M as follows.
Lemma Let X (1/E)² where is an a-light distribution and E (0,1/2). Assume that
M 2 1/a and N 2 M. Let X' be distribution that is 0 with probability 1 - M/N and is sampled from X with probubility M/N. Let (a, b) = (min( Z), max(Z)) There exists a constant such that
i & [(1/E) (1/=)*), then for any K E [0, 1] the pair (T, K) not (c(a + t) competiite for the online pricing instance X X
As show in the Appendix, the above lemma combined with the hardness of interior point implies Theorem
The same argument extends the RD problem. In the proof of Lemma if the price lies outside the range, the algorithm simply accepts the first element X,. Analogously, we may assume that r(w;) and y(wa)) are sampled independently. In this case, when the price is not within range, the algorithm selects the "first" element according to the order induced by y(w.). Since x(-) and y(-) are independent, the proof carries over.
Remark 10.
Replicable Heavy Hitter
In this section, we prove Theorem 5 Let D denote the input distribution. We first present our algorithm to solve the problem. We then move on to the analysis of the replicability of the algorithm and its correctness.
5.1 Algorithm
We first take sample 5(1) of size n1 = 0(v -og(p=lopppp 1 8-1 + + from the distribution. Next, O(log(>-1) loggp=
sample ((2) with size n2 = O (logí min(p.3) ) - (o
--1))-2--1) samples from the distribution and record, for each element x E S(1), the number of times it appears in 5(2), Sample v/ uniformly at random from the range [3/2u, 2v). Let Y denote the set of all elements in 5(1) that appear more than s v'nz times in 8(2), where we remove repetitions of an element so that each element appears at most once in Y. Y non-empty, we choose an element from it uniformly at random and return output.
8

---

The way we choose the uniform element from Y is important for ensuring replicability. If runtime is not a concemn and only sample complexity matters, then one could sort all elements in X' using the shared random bits and pick the element in Y that appears first in the permutation. However, since running time scales linearly with X, this approach is not feasible for large domain sizes. Assuming r denotes the random bits of the algorithm, we will choose value 17(1.2) .2) for each x E Y that depends only on æ and r such that, for random r, the values 17T,, a)) for z E Y are all independent and (essentially) distributed uniformly in [0, I/. Importantly, 77,,, X) does not depend on the samples ((2), We discuss below how this can be achieved using Reed Solomon codes. We then output the element in Y with the lowest value of (r..).
Intuitively, z(),x) denotes an order of the elements; we emphasize however that this order is unrelated to any pre-existing order among the elements of X and is chosen uniformly at random. Indeed, is clear from the definition of the heavy hitter problem that the set X' does not need to be ordered. Throughout the proofs, we will often implicitly assume that the elements are ordered (increasingly) based on (f,, .): e.g. we will refer to the element in set with the smallest value of n(.) as its "first" element. The above procedure ensures that we fix the random bits r, any fixed subset of elements will always be in a fixed order as long as the entire set appears in Y. This will be important for replicability as it allows us to output the same element regardless of the value of S(1, We omit the dependence of ((..) on r when it is clear from context.
To sample (r, x². we proceed as follows. Let X denote the ground set of the distribution. Choose finite field F such that the size of the field is power of 2 larger than I.Y). Embed each element t E X' as an element in F. We sample "0,,..,, Mm1-1 uniformly at random from F and define 12:-1 (ar)) = -i= u,zz.. It is clear that r7(z)) depends only on the random bits of the algorithm. It
-ell-known however that for any fixed values I1, T1,...;ZTy the values 17(21),.... (an are independent and uniformly random in F. We repeat the process (log((1 max p }]) and
concatenate the different values of 17(z) to form a single value (zx). The concatenation is made to ensure that, w.h.p, there is no tie among the elements of Y when comparing (see the analysis below).
5.2 Analysis
We next state the proof. Due to space constraints, we defer parts of the proofs to the Appendix. Let p(x) PDD [ai] denote the probability of sampling x under the distribution D. Let 2²"
{a: : p(x) 2 w denote all elements for which the sampling probability is more than v. Note that X2" has size most _ by definition. Let Fy = arg ming::(=)2w n(x) denote the first element with probability larger than //, If no such element exists, we set zq,2" to be Null. We will assume ties are broken in lexicographic order; our analysis will actually condition on the event that ties do not occur which holds with high probability. We note that the value of Ty, does not depend on any of the samples and only depends on the input distribution and the random values n()). We will show that, with probability at least 1 - p, the algorithm outputs Ty
Let x X2" denote all of the elements in S that have higher p(-) value than all elements with smaller values:
: plv) < p(x) for all E 22 such that nyv) < n((x}}
We next define few events which we later show hold with probability at least 1 - O(p). We say EV holds if all elements in 2 appear in 5()); i.c., Ev, = {x2> C {. For an element E 5(), let p(x:) denote the estimated probability of based on its repetitions in S22) Set c To IJ We say (x) holds for an æ if either p(z) < 3v and (p(x) - p(z) < E or p(x) 2 3v and p(x) 2 2v. We say EV, holds if Ev2(x) holds for all x E s(U), Let the set U denote the union of the c-neighborhoods of all x E X22; formally,
U - U 2EX (z - c, c).
We say Ev, holds if v' & U. As we show in our proofs, we can essentially bound the number of elements in" thereby lower bounding the probability of Evy. For an event Ev, let -Ev denote its complementary event.
The following lemmas bound the failure probability of the events.

---

Lemma 11. Pr [r[-Bu I min(p,
Lemma 12. Pr| [rr] < m1/10,99/110.
Lemma 13. Pr [r[3B - p/2.
We say E holds ()(x + nv()) for all distinct v, y E ( ( X2 Since |22|| S n1, we have
(5 2x I O(n)). ). It follows that
min(p,
Pr Pr[-Eva]
20
where for the second inequality we have assumed that the hidden constant under (.) in the exponent is large enough.
Lemma 14. Assume that Eu, Eug, Eug and Eug hold. The output of the algorithm is Tn,
Now, we procceed with the proof of Theorem
Proof of Theorem 3 It clear that the algorithm has the desired sample complexity. For replicability, Putting together the above lemmas, we conclude that the probability that the algorithm outputs zn, is at least 1 - p. It follows that two independent runs of the algorithm with shared randomness will have the same output with probability at least 2p, implying that the algorithm is (2p)-replicable. It is clear that by replacing with p/2, the algorithm becomes p-replicable with the same sample complexity up to constant factors.
We next prove correctness. We show that assuming Evi, Ev2, Ev, hold, the algorithm's output is correct; i.e., (a) it is either Null For proving (a), observe that if the output is not Null then it is some
u-heavy hitter and (b) if (44)-heavy hitter exists, it is not Null.
5()) such that f(x:) >> v/. By Ev2, this implies that p(x) 2 v' é 2 V, and we are done. For (b), letting x denote the point satisfying p(x") 2 4v, we have x² E S(2) because of Ev, and f(*))= 2 2v by Ev2. It follows that the output will not be Null and the proof is complete.
Conclusion
In this work, investigated replicability in online decision-making, with focus the Replicable Online Pricing (ROP) problem and its sample complexity. By designing efficient replicable algorithms and establishing fundamental lower bounds, competitiveness, and sample efficiency. We also explored the broader implications of our results for the delegation problem, key economic model of principal-agent interactions, analyzing strategies to align incentives while maintaining decision-making autonomy. As part of our technique, we obtained new algorithm for the replicable heavy hitter problem which may be of independent interest. Our findings enhance the understanding of replicability in both algorithmic and economic contexts, underscoring its importance in ensuring fairness, transparency. and reliability.
highlighted the trade-offs between replicability,
An interesting direction for future work is applying our techniques to study replicability in other pricing problems. Another promising direction is to extend methods, partieularly the lower bounds, to study broader notions of robustness-ffe example, allowing replicable algorithms to produce approximately equal outputs. Additionally, while we focused on multiplicative guarantees to align with the standard competitive analysis framework, it would be interesting to explore algorithms that allow additive error. Improving the dependence of our bounds any of the relevant parameters is also an interesting direction for future work. Finally, it would be interesting to analyze the practical implications of work using empirical evaluations.
7 Acknowledgements
The work is partially supported by DARPA QuICC, ONR MURI 2024 award on Algorithms, Learning, and Game Theory, Army-Research Laboratory (ARL) grant W91 INF2410052, NSF AF:Small grants 2218678, 2114269, 2347322, and Royal Society grant 12222222
10

---

References
[AB13] Manuel Amador and Kyle Bagwell. The theory of optimal delegation with an application tariff caps. Econometrica, 114):1541-)599 2013.
[AE17] Attila Ambrus and Georgy Egorov. Delegation and nonmonetary incentives. Journal of Economic Theory, 171:101-135, 2017.
[ABE* 17] Melika Abolhassani, Soheil Ehsani, Hossein Esfandiari, MohammadTaghi HajiAghayi, Robert Kleinberg, and Brendan Lucier. Beating 1-1/e for ordered prophets. In Pro- ceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, page 61-71, New York, NY, USA, 2017. Association for Computing Machinery.
[AGSC02] David Assaf, Larry Goldstein, and Ester Samuel-Cahn Ratio prophet inequalities when the mortal has several choices. The Annals of Applied Probability, 12(3):972 984, 2002.
[AHL12] Saeed Alaei, MohammadTaghi Hajiaghayi, and Vahid Liaghat. Online prophet- inequality matching with applications to ad allocation. In Proceedings of the 13th ACM Conference on Electronic Commerce, EC 12, page 18-35, New York, NY, USA, 2012. Association for Computing Machinery.
[AHL13] Saeed Alaei, MohammadTaghi Hajiaghayi, and Vahid Liaghat. The online stochastic generalized assignment problem. Lecture Notes in Computer Science, 01 2013.
[AKW14] Pablo D Azar, Robert Kleinberg, and S Matthew Weinberg, Prophet inequalities with limited information. In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms, pages 1358-1377.. SIAM, 2014.
[AV10] Mark Armstrong and John Vickers. A model of delegated project choice. Econometrica, 78(1):213-244, 2010.
[BD21] Curtis Bechtel and Shaddin Dughmi. Delegated Stochastic Probing. In James R. Lee, editor, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). volume 185 of Leibniz International Proceedings in Informatics (LIPlcs), pages 37:1- 37:19, Dagstuhl, Germany, 2021. Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
[BGHO1] J. Bendor, A. Glazer, and T. Hammond. Theories of delegation. Annual Review of Political Science, 4( 4(Volume 4, 2001):235-269, 2001.
[BGH+ 23] 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 Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pages 520-527, 2023.
[BHHS24] Pirmin Braun, Niklas Hahn, Martin Hoefer, and Conrad Schecker. Delegated online search. Artificial Intelligence, 134:104171, 06 2024.
[BHK Kiarash Banihashem, LaghhmmadTaghh Hajiaghayi, Dariusz R Kowalski, Piotr Krysta, and Jan Olkowski. Power of posted-price mechanisms for prophet inequalities. In Proceedings of the 2024 Annual ACM-SIAN Symposium on Discrete Algorithmm (SODA), pages 1580-4604 SIAM, 2024.
[BHKS25] Kiarash Banihashem, Mohammad Taghi Hajiaghayi, Piotr Krysta, and Suho Shin. Delegated choice with combinatorial constraints. In Proceedings of the 26th ACM Conference on Economics and Computation, pages 275-303, 2025.
[BHSS23] Kiarash Banihashem, MohammadTaghh Taghi Hajiaghayi, Suho Shin, and Alcksandrs Slivkins. Bandit social learning: Exploration under myopic behavior. arXiv preprint arXiv:2302.07225, 2023.
[BIK07] Moshe Babaioff, Nicole Immorlica, and Robert Kleinberg. Matroids, secretary problems, and online mechanisms. SODA '07, USA, 2007. Society for Industrial and Applied Mathematics.

---

[BNSV15] Mark Bun, Kobbi Nissim, Uni Stemmer, and Salil P. Vadhan. Differentially private release and learning of threshold functions. In Venkatesan Guruswami, editor, IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, pages 634. IEEE Computer Society, 2015.
[CCES22] José Correa, Andrés Cristi, Boris Epstein, and José Soto. The two-sided game of googol. Journal of Machine Learning Research, 23(1 13):1-37, 2022.
[CCES24) José Correa, Andrés Cristi, Boris Epstein, and José A Soto. Sample-driven optimal stopping: From the secretary problem to the iid prophet inequality. Mathematics of Operations Research, 49(1) (1)44) 1:44114475, 2024.
[CDF* 22] Constantine Caramanis, Paul Dütting, Matthew Faw, Federico Fusco, Philip Lazos, Stefano Leonardi, Orestis Papadigenopoulos, Emmanouil Pountourakis, and Rebecca Reiffenhäuser. Single-sample prophet inequalities via greedy coddere selection. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1298- 1325. SIAM, 2022.
[CDFS19] José Correa, Paul Dütting, Felix Fischer, and Kevin Schewior. Prophet inequalities for ii.d. random variables from an unknown distribution. In Proceedings of the 2019 ACM Conference on Economics and Computation, EC '19, page 3-17, New York, NY, USA, 2019. Association for Computing Machinery.
[CF98] Cristiano Castelfranchi and Rino Falcone. Towards a theory of delegation for agent- based systems. Robotics and Autonomous Systems, 24(3):141-157, 1998. Multi-Agent Rationality.
CCF++17 José Correa, Patricio Foncea, Ruben Hoeksma, Tim Oosterwijk, and Tjark Vredeveld. Posted price mechanisms for a random stream of customers, In Proceedings of the 2017 ACM Conference on Economics and Computation, EC 17, page 169-186, New York, NY, USA, 2017. Association for Computing Machinery.
[CHMS10] Shuchi Chawla, Jason D. Hartline, David L. Malec, and Balasubramanian Sivan. Multi- parameter mechanism design and sequential posted pricing. In Proceedings of the Forty- Forty-Second ACM Symposium on Theory of Computing. STOC '10, page 311-320, New York, NY, USA, 2010. Association for Computing Machinery.
[CZ24] Andrés Cristi and Bruno Ziliotto. Prophet inequalities require only constant number of samples. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing. pages 491-502, 2024.
[EHKS23] ERIC EATON, Marcel Hussing, Michael Kearns, and Jessica Sorrell. Replicable reinforcement learning. In Thirly-seventh Conference on Neural Information Processing Systems, 2023.
[EKK+23) 23] Hossein Esfandiari, Alkis Kalavasis, Amin Karbasi, Andreas Krause, Vahab Mirrokni, and Grigoris Velegkas. Replicable bandits. In The Eleventh International Conference on Learning Representations, 2023.
[EKM*23] 23] Hossein Esfandiari, Amin Karbasi. Vahab Mirrokni, Grigoris Velegkas, and Felix Zhou. Replicable clustering. In Alice Oh, Tristan Naumann, Amir Globerson, Kate Saenko, Moritz Hardt, and Sergey Levine, editors, Advances in Neural Information Processing Systems 36: Anmual Conference on Neural Information Processing Systems 2023, NewrlPS 2023, New Orleans, IA, USA, December 10 16, 2023, 2023.
[FGL15] Michal Feldman, Nick Gravin, and Brendan Lucier. Combinatorial auctions via posted prices. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium Discrete Algorithms,, SODA '1, page 123-135, USA, 2015. Society for Industrial and Applied Mathematics.
[F183] Eugene F. Fama and Michael C. Jensen. Separation of ownership and control. The Journal of Law and Economics, 26:301 325, 1983.
12

---

[HIB 18] Peter Henderson, Riashat Islam, Philip Bachman, Joelle Pineau, Doina Precup, and David Meger. Deep reinforcement learning that matters. AAAI Press, 2018.
18/EAAT 18.
[HIK 244]] Max Hopkins, Russell Impagliazzo, Daniel Kane, Sihan Liu, and Christopher Ye. Replicability in High Dimensional Statistics In 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS), pages 1-8, Los Alamitos, CA, USA, October 2024. JEEE Computer Society.
[HIK+24b) Max Hopkins, Russell Impagliazzo, Daniel Kane, Sihan Liu, and Christopher Ye. Replicability in high dimensional statistics. CoRR, abs/2406.02628,, 2024.
[HK82] T. P. Hill and Robert P. Kertz. Comparisons of Stop Rule and Supremum Expectations of I.I.D. Random Variables. The Annals of Probability, 10(2):336 345, 1982.
[HKP04] Mohammad Taghi Hajiaghayi, Robert Kleinberg, and David C. Parkes. Adaptive limited-supply online auctions. In Proceedings of the 5th ACM Conference on Electronic Commerce, EC "04, page 71-80, New York, NY, USA, 2004, Association for Computing Machinery.
[HKS07] Mohammad Taghi Hajiaghayi, Robert Kleinberg, and Tuomas Sandholm. Automated online mechanism design and prophet inequalities. In Proceedings of the 22nd National Conference on Artificial Intelligence- Volume 1, AAAI007, page 58-65. 65. AAAI Press, 2007.
[HMRS24) Mohammad Hajiaghayi, Mohammad Mahdavi, Keivan Rezaei, and Suho Shin. Regret analysis repeated delegated choice. Proceedings of the AAAI Conference on Artificial Intelligence, 38:9757-9764 03 2024.
[Ho180] Bengt Holmstrom. On the theory of delegation. Discussion Paper 438, Evanston, IL, 1980.
[[HGP17] Riashat Islam, Peter Henderson, Maziar Gomrokchi, and Doina Precup. Reproducibility of benchmarked deep reinforcement learning tasks for continuous control. ArXiv, abs/1708.04133,, 2017.
[ILPS22] Russell Impagliazzo, Rex Lei, Toniann Pitassi, and Jessica Sorrell. Reproducibility in learning. In Proceedings of the 54th annual ACM SIGACT symposium on theory of computing, pages 818-831, 2022.
[en87]]
D.P. Kennedy. Prophet-type inequalities for multi-choice optimal stopping. Stochastic Processes and their Applications, 24(1):77-88, 1987.
[KK18] Jon Kleinberg and Robert Kleinberg. Delegated search approximates efficient search. In Proceedings of the 2018 ACM Conference on Economics and Computation, EC 118 page 287-302, New York, NY, USA, 2018. Association for Computing Machinery.
[ Alkis Kalavasis, Amin Karbasi, Kasper Green Larsen, Grigoris Velegkas, and Felix Zhou. Replicable learning of large-margin halfspaces. In Forty-first International Conference on Machine Learning, ICMI. 2024, Vienna, Austria, July 21-27, 2024. OpenReview.net, 2024.
[KKMV23) Alkis Kalavasis, Amin Karbasi, Shay Moran, and Grigoris Velegkas. Statistical indistin- guishability of learning algorithms. In Proceedings of the 40th International Conference on Machine Learning, ICML'23. JMLR.org 2023.
[KKV724] Alkis Kalavasis, Amin Karbasi, Grigoris Velegkas, and Felix Zhou. On the compu- tational landscape of replicable learning. In The Thirty-eighth Annual Conference Neural Information Processing Systems, 2024.
[KNR22] Haim Kaplan, David Naori, and Danny Raz. Online weighted matching with sample. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1247-1272. SIAM, 2022.
13

---

[KS77] Ulrich Krengel and Louis Sucheston. Semiamarts and finite values. Bulletin of the American Mathematical Society, 83(4):745 747, 1977.
[KVYZ23] Amin Karbasi, Grigoris Velegkas, Lin Yang, and Felix Zhou. Replicability in reinforce- ment learning. In Thirly-seventh Conference Neural Information Processing Systems, 2023.
[KW12] Robert Kleinberg and Seth Matthew Weinberg. Matroid prophet inequalities. In Proceedings of the Forty-Fourts Annual ACM Symposium Theory of Computing, STOC 12, page 123-136, New York, NY, USA, 2012. Association for Computing Machinery.
[LKM* 18] Mario Lucic, Karol Kurach, Marein Michalski, Olivier Bousquet, and Sylvain Gelly, Are gans created equal? a large-scale study. In Proceedings of the 32nd International Conference Neural Information Processing Systems, NIPS' 18, page 698-707, Red Hook, NY, USA, 2018. Curran Associates Inc.
[LY24] Sihan Liu and Christopher Ye. Replicable uniformity testing. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.
[RWW19] Aviad Rubinstein, Jack Z Wang, and S Matthew Weinberg. Optimal single-choice prophet inequalities from samples. arXiv preprint /91 2019.
[SC84) Ester Samuel-Cahn. Comparison of threshold stop rules and maximum for independent nonnegative random variables. Ann. Probab., 12(4):1213-1216, 1984.
[SRH23] Suho Shin, Keivan Rezaei, and Mohammadtaghi Hajiaghayi. Delegating to multiple agents. In Proceedings of the 24th ACM Conference on Economics and Computation, EC '23, page 1081-1126 New York, NY, USA, 2023. Association for Computing Machinery.
[STCR23] Eden Saig, Inbal Talgam-Cohee and Nir Rosenfeld. Delegated classification. In Thirty-seventh Conference Neural Information Processing Systems, 2023.
[ZYKH23] Liang Zhang, Junchi Yang, Amin Karbasi, and Niao He. Optimal guarantees for algo- rithmic reproducibility and gradient complexity in convex optimization. Proceedings of the 37th International Conference Neural Information Processing Systems, NIPS '23, Red Hook, NY, USA, 2023, Curran Associates Inc.
14

---

A Further related work
A.1 Replicability
The concept of algorithmic replicability and reproducibility has attracted considerable attention in recent years, leading to the development of various theoretical frameworks and practical algorithms across multiple domains. [TLPS22] introduced the notion of reproducible algorithms within the context of learning, highlighting the balance between randomness, accuracy, and reproducibility. They developed a theoretical foundation for reproducible algorithms and examined reproducibility in statistical query (SQ) algorithms, approximate heavy hitters, medians, and learning halfspaces. They also explored some inherent trade-offss and lower bounds associated with reproducibility.
Building on this foundation, replicability has been examined across several fields. For instance, [EKK*23] extended the concept to stochastic bandits and developed replicable policies that could achieve optimal regret bounds comparable to their non-replicable counterparts. (EHKS23) initiated the study of replicable RL algorithms, providing provably replicable versions parallel value iteration and R-Max in episodic settings. Similarly, [KVYZ23] investigated replicability within reinforcement learning (RL), focusing on discounted tabular Markov Decision Processes (MDPs) with access to a generative model. They provided replicable algorithms for (c, -opttimll policy estimation. They also explored TV indistinguishability as relaxed form of replicability and introduced the notion of approximate replicability.
FKM++3 proposed replicable algorithms for statistical clustering by applying replicability con- cepts to problems like k-medians, k-means, and k-centers. The computational and statistical costs of replicability in high-dimensional tasks, such as multi-hypothesis testing and mean estimation, were examined by 244). Their study established an equivalence between optimal replicable algorithms and high-dimensional isoperimetric tilings, resolving open problems related to sample complexity.
LY24] addressed replicability in uniformity testing, presenting a replicable uniformity tester using only O (ne- (ne-?p 2==-) samples, and providing a nearly matching sample complexity lower bounds for replicable uniformity testing of symmetric algorithms invariant under domain relabeling. In convex optimization, [ZYKH23] demonstrated that optimal reproducibility and near-optimal convergence could be simultaneously achieved in various optimization settings. Additionally, [KKL,-20 24] stud- ied replicable algorithms for learning large-margin halfspaces, presenting algorithms with improved sample complexity.
In another line of work, the relation between replicability and other stability notions was explored by (3) They provided algorithmic reductions between replicability, perfect generalization, and approximate differential privacy, while also identifying computational separations that underline fundamental differences between these stability concepts. [KKMV23] explored Total Variation (TV) indistinguishability as measure of learning rule stability and investigated information-theorrtiie equiv- alences between TV indistinguishability, replicability, and differential privacy. Lastly, (KK2722) focused on the computational connections between replicability and learning paradigms like online learning, private learning, and SQ learning.
Replicable mean and median estimation. Replicable algorithms for mean and median estimation were first developed by Impagliazzo. Lei, Pitassi, and Sorrell [S22) who introduced general- purpose techniques for statistical queries under replicability constraints. Their replicable median algorithm has sample complexity exponential in log" [X]. Bun, Gaboardi, Hopkins, Impagliazzo, Lei, Pitassi, Sivakumar, and Sorrell [BGH 23] 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. Impagliazzo et al. [ILPS22] and Esfandiari et al. [EKM*23) provide algorithms that return a list of candidate heavy hitters, with sample complexity scaling cubically in 1/v. More recently, Hopkins et al. [HIK 244) improved the dependence on the failure and replicability parameters for expected sample complexity, but still maintained a - dependence. In contrast, we consider more specialized variant where only a single heavy hitter needs to be output (assuming one exists), and
15

---

give new algorithm with nearly linear V dependence, which is necessary for our lower bound construction Theorem 3.
A.2 Prophet Inequalities and delegation
The study of prophet inequalities and optimal stopping theory has seen significant growth over the years, particularly in mechanism design and online optimization. Originally introduced by [KS77], prophet inequalities provide framework for comparing the expected outcomes of prophet, who knows future events, to those of a ddecision-makee without such foresight. Kennedy [Ken87] extended the framework to multi-choice optimal stopping, identifying the best possible universal constants for scenarios where multiple selections are allowed. [AGSCO2] further refined the prophet inequality framework by introducing ratio prophet inequalities in settings where several stopping rules are available to the Recision-make and offering recursively evaluated constants that provide tight bounds for these scenarios.
The integration of prophet inequalities into mechanism design has also seen significant advancements. [HKS07] applied these concepts to online mechanism design, developing approximately efficient automated systems through new prophet inequalities motivated by the auction setting. [5GL15] investigated combinatorial auctions with posted price mechanisms in Bayesian setting and developed the first constant- factoo DSIC mechanism for Bayesian submodular combinatorial auctions.
kW12 generalized prophet inequalities to matroid settings, providing tight bounds under matroid constraints and highlighting applications in Bayesian mechanism design. Further generalizations include the work of [AHL12]. who introduced online prophet-inequality matching in bipartite graphs, particularly relevant to ad allocation, and [HLI3], who explored stochastic generalized assignment problems within this framework.
There also another line of work studying prophet inequalities on i.i.d. distributions, starting with the work of (HK82). Many years later, [AEE 17] presented threshold based algorithm that surpassed the theoretical bound of 1 - 1/e previously conjectured by [HK82). Then, [CFH* 17) investigated the performance of posted price mechanisms when customers arrive in an unknown random order, considering both adaptive and nonadaptive cases. They established tight bound of 1 1/e for the nonadaptive case, even when valuations are i.i.d., and proposed mechanism achieving better approximation factor of 0.745 the adaptive case with i.i.d. valuations. More recently, [CDFST9] studied the i.i.d case of prophet inequality when the underlying distribution is unknown. They showed that, without distributional knowledge, the best achievable bound 1 - I/e, aligning with the classic secretary problem. However, they further demonstrated that access to a limited number of samples from the distribution could significantly improve performance.
It is worth noting that many (though not all) works in the prophet incqualities literature use (pos- sibly dynamic) pricing based algorithms obtain their results and that any algorithm for prophet inequalities admits a pricing- based implementation IBHK+241
Sample- prophet inequalities. The sample-based study of prophet inequalities where the algorithm has access only to samples from the underlying distributions- has become active and evolving area of rescarch. This direction was initiated by Azar, Kleinberg, and Weinberg AKW14], who drew connections between this setting and the classical secretary problem. In the case of fixed arrival order, Rubinstein, Wang, and Weinberg [RWW19] 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. [CCES24] refining the required sample complexity. When the arrival order is random, in the prophet secretary model, Correa et al. (CCES22) 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 [CDF+22 KNR22]. More recently, Cristi and Ziliotto (CZ24) developed a unified argument showing that constant sample access suffices to achieve approximate optimality across both prophet-secretee and free-order settings, despite the exact optimal approximation ratios for these variants remaining open.
The concept of delegation, a core topic in economic theory since its introduction by [Ho10]] has been explored in many different ways over the years. However, [KK were the first to analyze the efficiency loss in delegated search, proposing methodologies to bound this loss and
Delegation
16

---

demonstrating how simple bhaeshold-based mechanisms can approximate the efficiency of direct search. Their work established a connection between delegation and prophet inequalities, resulting in surge of attention to this problem.
[BD21] introduced the concept of delegated stochastic probing, merging delegation with stochastic probing problems. [HMRS24] explored the online learning aspects of delegation through a repeated delegated choice model. Their work extends the delegation framework by incorporating dynamic learning of solution distributions, focusing on minimizing cumulative regret in various strategic settings. [STCR23 address the delegation of classification tasks to rational agents. They propose nncentive-aware frameworks that use performance- based contracts to align agents' interests with those of the principal, connecting contract design with statistical hypothesis testing. [SRH23) investigate mechanisms in multi-agent settings without monetary incentives. [BHHS224] delve into delegated online search, where agents sequentially inspect options and propose solutions in real time. [BHKS25] show that the correspondence between delegated choice and prophet inequalities holds if and only if the feasibility constraint forms a matroid. They also establish a separation between the two problems, proving that, unlike prohpet inequalities, delegated choice admits constant-factor approximation under downward-closed constraints.
B Proofs in Section
B.1 Proof of Lemma
Proof of Lemma 4
Sample B ~ Bernoulli(k). Define OPT = max; X₃. We need to show that,
E [(r, 2 (1/2 (1 (E [OPT],
where we ((.))) = 0 when i(r, B) oc. We can rewrie the left hand side as
E (x(),)
N
Σ
E E|11 (i(T, B) =]]
N
E [([ + (X; (i(t, B) = =i}]
Σ [ (i(T, B) = =)]+
Σ
R [[x; 7)0 (i(T. B) = =i]]
The first term can be lower bounded as
N
E [1 (i(T, B)) = = =1=rP(((( B) # oo]
As for the second term, define Z; E [0.1) to be 1 if X, 2 and B 0 or X; > and B = 1. Observe that
B) = i) 2 Z, (1 2j).
17

---

This is because if 2; = and all other Z3 are O, then we must have i(T, B) = i. We can therefore obtain the following lower bound
B)= = E (X, 2) II (1 2,) [X; - 7)1 B)
jtt
E(x; Z,
II Zz)
2 E[X; =),
II (1 23) j=1
- -) [i(T, ([ B) = oo
where for the first inequality we have used the fact that , XN are independent. We note however that (X; - Z) [X; r]+ This follows from case analysis. When X, < T, then have Z; = 0 and both sides are O. When X; = т, then again both sides are O. When X; > T, we have Z, and both sides equal to X; T. It follows that
N 7|+
Σ BI - 7)1 fi(T, B) +} 2 Pr [i(T, B) 00)
>Ix,
Observe however that
Pr Pr(i(T, 20] = (1--1 Pr (max X,) 2 r| + kPr (max X.) > 7
Since 7r is aaaproxximate median pair for max; X,, the above probability is in the range (1/2 - 7: 1/2 + 7). It follows that
Pr[1(T B) & oo) B) x 2 1/2 -- 7-
This in turn implies
( T+ + )
E x B) 2 -//B
E (T
T
mxax|Xi +]}}]
1=1
2 E (mă x.)
(1/2-114 -1/2-2)OPT.
B.2 Application to delegation
In this section we prove Theorem 2 which we first restate for completenes::
Theorem Assume that the distribution D is supported over known finite set X. For any E (0, 1/2) and p > O, there exists an algorithm solving the RD problem with parameters (1/2 - e, c, (3) using at most N poly (log" | --,,,-1)) samples from D.
Proof. We know that for any threshold 7 chosen by the principal, the best strategy for the agent would be to choose wi with the highest corresponding value yw:; among all those that meet the threshold <(w;)) 2 T or sr(s;) > depending on the value of B. We will denote this as (T.B) henceforth. Note that (r. might not exist, in which case neither the principal nor the agent would gain anything regardless of the agent's 's proposal. However, the existence of (T.B) warrants the principal's 's approval and gain of (t) As (r.B) can also seen as the first task with either x(w) 2 t or s(w) > when the tasks are sorted based on their corresponding value y in descending order, the problem of
18

---

choosing an appropriate threshold r for the principal is closely related to choosing an appropriate threshold for the prophet pricing problem.
We propose that the principal draw N samples from D, denoted by w/. for each S i v and 1 S j Σ 8, where denotes the sample complexity of Proposition For each 1 S I 8, we then define z; := maXicieN I (wW This construction yields ø1, Ia as independent samples from the random variable X, where X := maxigis! x(w:).
Applying the given p-replicable algorithm for computing a a-approximate median pair (T, on the samples Z1..... zs we obtain p-replicable 7-approximate median pair (7, x) for D. We report this the principal's 's mechanism, and by Lemma 15 would be (1/2 ?) competitive, which hence completes the proof.
Lemma 15, Let (T, K) be a a appprxxiittee median for the distribution of maxigigN r(ws). Then, (T, k) would yield a (1/2 7) -competitiee utility for the principal.
Proof. The proof follows the same structure Lemma Specifically, define X, =ww)). Sample B ~ Bernoulii (t). Define OPT max, X₁. As before, we need to show that
E (r. m) 2 (1/2 >) [OPT],
where we set Xitr, when i(T, B) = oc. Note that the definition of i(T,, B) is different from that of Lemma 4 instead of picking the first element in the order of time, we are picking the first
element in the order specified by y(w)). Just as before however, the algorithms obtains with
probability Pr [ū(r, B) oo) and E, [[; +]+] with probability Pr [i(T, B) oo). As before, the probabilities can be lower bounded with 1/2 y and the proof goes through.
C Proofs in Section 4
We first state the following standard tools from probability theory that will be used in the analysis. Lemma 16. Let X be distribution over the X = (x1,..., Zpp } S R220 where I; 2 for i E [ - 1. Lef xo 0. The expectation of X satisfies the following equality:
E
[
Σ E=
(z. x1-1) Pr 2z}.
Lemma (Lemma A.5. in BHSS23 Let XI...., X,, be i..dd random variables and let be an arbitrary value. Let p denote the probability Pr [X; 2 r]. Then Pr [max; X; 2 r] 2 (min {np, 1}).
We note that the lower bound in the above lemma can be written as !(np) when p S 1/n.
Proof of Lemmal 7 Let p; be half of the corresponding constants from Proposition 5 Let A rreplicablle algorithm with sample complexity that can solve the problem with failure probability at most 3 for a-light distributions. We transform this into an algorithm A' for all (not necessarily light) distributions as follows. First. we invoke the p-replicable y-heavy hitter algorithm with failure probability 3 from S v = a/4 and y = the algorithm's output not Null, we return this as the output. Otherwise, invoke algorithm A and return its output. We show below that A' is (2p)-replicable and has failure probability at most 233. By Proposition 5 this implies a lower bound on the sample complexity of A', which in turn implies lower bound the sample complexity of A.
We next analyze the algorithm A'.
Correctness. Assume that the distribution not a-iight. Then the heavy hitter algorithm will return some value 2 F Null such that Pr Z = 2] > > with probability 1 - B. Therefore, the output will be correct. If the distribution is a--igght the heavy hitter algorithm will output either a value A Null such that Pr Pr z] > 0. or it will output Null. If the output is Null, then algorithm A will output correct answer with probability at least 1 - B. union bound implies that the answer correct with probability at least - 2,3 in this case well.
19

---

Replicability. Consider two runs with samples S1 and S2 and the same random bits. With probabil- ity at least 1 p. the heavy hitter algorithm will produce the same output for the two runs. the output is not Null, then we will obtain the same answers. Otherwise, we will invoke algorithm A in both cases, which will produce the same answer with probability - p. Taking union bound implies that the algorithm is rep)-replicable.
Sample complexity.
The algorithm requires n samples for the potential run of algorithm A' by assumption and requires at most aaa log" (1/x)) samples for the single heavy hitter algorithm by Theorem 5 This means that the overall sample complexity is n + O(a (1/a).. Since the algorithm is (2p)-replicable and has failure probability at most 233 Proposition implies that
n + O(a -1 log"(1aa)) 2 (logg" [F1).
Given the assumption a, if o₁ is small enough, this means that 2 2(log" [F)) as claimed, finishing the proof.
Proof of Lemma
16
Evaluating the right hand side,
(x)
-4-
Pr
X
(1 1;-1) Pr IX = x.y]
12
|
(0e 1;-1) Pr [X = xzن]
(Double counting)
|
(xn - 2o) Pr Pr[X X = zzح
(Telescoping sum)
E [X]
(Definition of expectation)
Proof of Lemma 8 Set x; = (1/s)$ for i [[[]]. Choose smallest such that [r[X] x:] M By
definition of we have Pr[X 2 -i- > 1/M. Since the distribution Z (and therefore X) is a-light, we must have [r x
< 1/(M,), which in turn implies Pr [X > x.) 1/(2M.. Since
Pr [X 2 xy] is decreasing in j. this means that Pr X 2 æ.} < 1/M for j 2 i. We can lower bound the expectation of in two ways. Firstly,
E E =
Σ
(2g Pr Y 2 2z)
(Lemma 16
2 > (zy 1r-1)) 2 æzy
(Since D3 2z-1)
121
2 ((M) Σ (xy 2y-))PPP [X N m.)
(Lemma 17 and Pr(xx 2 2,) S 1/(M))
121
20

---

Secondly, since 2; - 2;/2 (because < 1/22 and Ej=1(z; -j--1) S 2 for all j.j'.
obtain
E Y Σ oy - 13-1 2 1zp
(Lemma T6
2 (z, 1i-1)Pr(Y 2 xi}
(Since 2j > 2z-11)
2 ((1) 3;-1)
(Lemma anand Pr [X 2:) 2 1/(2M))
2 ((1)
(Since & < 1/2)
2 O(=
(1=-1 -20 20)
(Since =E- and Zo = 0)
O Σ
(xg xz-1)
(Telescoping sum)
j=1
i-1
2 ( "
Σ
(a 2 mz}.
j=1
Combining the above incqualities we obtain
B = (1, - z 2 zy}
(Lemma 76
$ (z, - -3-1 2 z,} +
Σ - -x-
j21
S 001/ +e) EY)
finishing the proof.
Proof of Lemma 9 Let C1, CI...., Cn be i.d Bernoulli variables such that 1 1[C,=1]=MM// M/N. Sam- pling XI...., X N ii.d from the distribution of X, we can assume that X C,X,, If the price is not in the range [(1/)),, (1/e)%, there are two possibilities. The first is that is > (1/s)². In this case, accepting the first element above 7 is equivalent only O-competitive. We therefore focus on the case (1/E)². We further assume > 0 since clearly non-zero price better than 0. J E (0, (1/E)"), then accepting the first element above or equal to J or accepting the first element strictly greater than are both equivalent to accepting the first element X such that C, 1, assuming such an element exists. Since C, and X; are independent, this means that the expected value of the algorithm is at most E [X1] where we note that we have an inequality because with positive probability all C; are O. Define Y max (Xi...., X }. We need to show that [Y] 2 Q (((2==)) [X1]. Since each C, with probability M/N, we have
accepting anything, which means is
M 11=1 C. =
.. By Chernoff, this implies
N Pr
1-112
M
Σ ==1
S M/2
(1/2)1/2 -1-100 11)
Therefore, with probability 2(1), we will have EN C M/2. Conditioned on this event, since Xi...., NN are i.i.d and independent of C, Y is maximum of at least 1/(2a) copies of X,. We can assume, without loss of generality, that a S 1/8. a 4, then setting trivially as one cannot have a price that is c-compettive for c >> 1. It follows that Za > 4 which in turn implies
the lemma holds
2cx 0(1/a). Therefore, (1 |)- I O(a).
Let Y" denote the maximum of the first [1/(2a)] copies of X. It is clear that Y 2 Y'. By Lemma however,
B[X,] S 5 (
2x )) + 5(a +e))+))((())
1
Therefore, conditioned on the event ΣN C, 2 M/2 we have E 2 1 Since the event happens with constant probability, this holds without the conditioning as well, finishing the proof.
D
21

---

Proof of Theorem 3 Let d. 1,3' ,c denote the values of the constants from Lemma] 7 Let c' denote the value of c Lemma We assume without loss of generality that e' 2 since increasing c' doe not violate the lemma. Set p p² /2, B and e = Ac'e. Set a' = a/(4''), M = 11/a"] and set 0g &c'.
Note that this implies
N 2 22/a 2 M.
For the final inequality, we have used the fact that 2/a' 2 [1/a"]. This follows from the fact that 1/0' de' 2 4; note that a S as otherwise the lemma holds trivially.
Let A be algorithm that is p-replicable and with probability 1 B. outputs. price pair that is a-competitive for N i.dd variables Xi...., and has sample complexity n. We need to show that 2 f2( log" (.().
We will build an algorithm A' for the replicable interior point problem a' a'-lt distributions. Let Z be an a' al-it distribution and set = a'. Create the distribution X' as in Lemma 9 Give this as input the algorithm A and denote its output price pair with (T, (T, Note that the algorithm will attempt to sample from the distributions of X which in turn requires us to potentially sample from Z. The number of samples the algorithm will require from Z is random. If the algorithm ends up requiring more than n' = ((ogg( + log(p log(p=))) Mn samples from Z, (where C' will be specified later), we halt the algorithm and output Null. Otherwise, we round the value (e) to the nearest integer and output it.
Correctness. We will show that the algorithm's 's output is correct with probability at least 1 - 8. Assume for simplicity that instead of halting the algorithm we require more than n' samples, we allow the algorithm to continue and calculate the price but output Null in the end. It is clear that this does not change the algorithm's 's output.
The expected number of samples the algorithm takes from Z is M N . = Mn S 2. n. Therefore, by Chernoff, the probability that the number of samples we require exceeds n' most -(x'), which is < B/8 if we set C' to be large enough. Furthermore, with probability at least 1 3, the output of the algorithm A will be price pair (T, that is a-competitive. Invoking Lemma 9 conclude that such must be in range [(1/e)²; (1/e)²) since otherwise would be at most (c(a' + comppttttee and c(a' + e) = a/2. Note that the preconditions of the lemma hold. We have E = a' a4(d') 1/2. We also have M [1/o/ 2 1/a' and N 2 M.
If 7 is in the range (11/)), (1/e)*], then the output of A' will be an interior point of Z. Note that r does not correspond a value g* for an integer 2, it does not matter how we round (og.-(()) since is in the range [s",, e"", both options for rounding are acceptable. Therefore, the algorithm A' is correct with probability at least 1 - 3(1 + 1/8) 2 B'.
Replicability. As before, we assume for simplicity that instead of halting the algorithm we require more than n' samples, allow the algorithm continue and calculate the price pair (T, s). but output Null in the end. If we run the algorithm A' with two separate samples S1, S2 and the same random bits, with probability 1 p/4, neither of the the fact that the probability of returning Null C. Additionally, with probability at least p. both runs of A return the same output. It follows that with probability at least p', the output is the same.
return Null. This follows from most e e(x') which S p/4 given large enough
Sample complexity. By definition of c', have a' a/(4'') > of ((log* (..9). The algorithm A' produces an interior point of Z with probability at least 1 - 3 and is p prrepiccable. It follows from Lemma 7 that its sample complexity n'' must be at least Ô(log" [FI). Since 3 were constants, we have n' O(Mn) = O(n/a), where the second inequality follows from the fact that, since 2/0' 2 M. Therefore, n/a 2 Ø(log" [F]) and the proof is complete.
22

---

D Proofs in Section 5
Proof of Lemma 11 For any x E X2", Pr [ & sth - (1 (1-p) "())))))) I e- I e e- Since
11 (
log( r
+ p-t + ))),, with the correct constants under ( we have e e
y min(p, 3)) Since
2 S v- taking a union bound the claim follows.
We will show that for any E (KD) we have Pr [-Ev2(1)) < min(p.3) Taking union bound completes the proof. Recall that p(.) is an estimate of p(.) using ng samples. Therefore, by Chernoff (Equation (2).
Proof of Lemma 12
10n1
Pr 1 p 2 é S
2e
2202
p S 3v, then since by definition of n2 and e, this is 2e
Tox (v
15) < min(p.0) Pf < 3v, this
10n1
completes the proof. Otherwise, it is clear that the probability of Ev2(x) is maximized when p(x) =
3v, in which case since v. the above bound gives Pr ( I 2v] Pr [|p 1 2 el] 10ns
P.
We next prove the following Lemma which will be used in our proofs. Lemma 18. Conditioned on the event that n(x) # TT()) for all distinct z, E X2, the expected size of X2" is at most In(v=)) 1).
4
Proof of Lemma [8 Let z; denote the value of x E X2* with the i-the largest value for p(z), where we assume that ties are broken arbitrarily. In order for I; to be in X2", we need to have (75) > n(x;)) for all such that p(y) 2 p(z;), which in turn means that 77z3;) < m(xy)) for all < i. The probability that this happens is most 1/6 however since v-) is chosen uniformly random and is independent across T₁. Formally,
Pr I E 2 Pr (n(v) > (1x) Ay p(y) 2 p(x))
(Definition of x²2)
< Pr [n(x;) n(r,) Vj
(Since p(z;) 2 p(x;) j S (Since nTx)) is chosen uniformly random).
< 1/i
Since X C X22, summing over i we obtain
x
E [[x = Σ
Pr c E x22
(Linearity of expectation)
|
<
1n
Since |
< v- the lemma follows.
Proof of Lemma 13 For any distinct x, y, we have
Pr [m(xx) n(()) < 2 +0 min(p, 3)
20n
Since n1 2 |x20|. It follows that with probability at least 1 - (p, the values of 77()) are distinct across X 2" Condition this event. For any fixed value of 1/, since o' is chosen uniformly
2e x Taking expectation over 7), by Lemma 18
random from [3/2u, 20/), we have Pr [v' E U S
w/2
we have Pr [r/v U] <
2pv(in(e ++1] 2p/5. Since We conditioned on event with probability
1 min(p, /2, we conclude that Pr [Ev]] 2 (1 p/20) 2p/5) 2 1 - p/2, finishing the proof.
D
23

---

Proof of Lemmal 14 For simplicity, we write r" instead of In for the rest of the proof. We first handle the case where x² * Null. In this case, since x² E X we have x¹ E ((1) by E We additionally claim that x= E X If this is not the case, then there must be some y E X2" such that v(v)) < v((²") and p(y) 2 p(=*). This implies however that p(y) 2 v', which contradicts the definition of x" as the first elements (in order of v(()) with probability at least v/. Since x" E x
we conclude that p(x") 2 v' + c by Evg, which in turn implies p(z") 2 v' by Ev2. It therefore suffices to show that p(x') S v for all x' E (() such that m1x') < n)²²).
By definition of x², must have p(x') S v', which further implies that lp(x²) ((xx'))(('')) S by Evy. We further assume that p(a') 2 v; if not, we have p(x') S v + e S v², finishing the proof. Therefore x' E X22 Define T the largest element before or equal to x' in X i.c. arg max
M()). Note that ã = x' if x' E X²"
We claim that p(z) p(x'). Assume this is not the case. Set y to be the first element in X2" satisfying p(y) > p()). Formally, y = arg
n(x). Since p(x') > p(ā) and m(x²) > n()). we have n(y) S. m²x'). We also have m(y) > n(T); if not, then since ply) > p(τ)
we conclude that ā & X which is a contradiction because y E X22 It is easy to see however
that y E X2", contradicting the definition of Σ. Specifically, ply) > p(z) and p(r) Z p(x)
7(x)= < n(y) by definition of y. It follows that the initial assumption was wrong and p(ž) 2 p(x').
Given the above claim, we have ()( I m(x') I n)xx). Since F E X2", by definition of x=, we have p(z) I v/ Since T. X²" by Ev3 we conclude that p(z) S v/ c, which further implies p(x') S v/ c. Therefore, by Ev2 we have p(x') S v/, finishing the proof.
If x=- Null, then the same proof shows that p(x') S v for all x' E 5()); the only place where we used x² is for proving that p(x') I v and p(ž) I v', both of which would hold trivially if
x² = Null. Therefore, output is x² in this case well.
E Omitted proofs
E.1 Approximate median pair
In this section, we prove Proposition 3
Proof of Proposition We first invoke Lemma 2 to find (1/2- - (1/2->/2)-app) appprxxaito median 5 with the same sample complexity and parameters p/4, /4. Let 7 be the value obtained from the algorithm. Note that, if the output of the algorithm is correct, we have
Pr[X 2 Pr < 1/2 7/2-
We then replicably estimate, with error 7/8, the value of Pr Pr 2 r] and Pr[x > r]. This can be done using, e.g., the SQ algorithm of [LPS22). Let P1, P2 denote the true probabilities and let P1, P2 denote our estimates. Assuming was chosen correctly, we have p1 1/2 7/2 and P2 < 12/+>/2 This in turn implies that, if our estimates are correct, we must have P1 2 1/2- 1//2-377 37/4 and P22 1/2 + 37/4. Now, if pi < 1/2 + 37/4. then we output (x) for 0. Otherwise,
set x such that (1 - K) + xp = 1/2 + 3 /4. It is clear that
(1 - x)P1 + Kp2 = (1 x) + kop2 + (1 k)(p1 - p1) + x(p2 - p22)
If our estimates are correct, follows that (1 k)pı + Kp2 is in the range (1/2 - 7, 1/2 + 7). finishing the proof.
E.2 Replicable interior point hardness
In this section, we prove the hardness of the replicable interior point problem, as formalized in Proposition 5 We begin with some definitions. Recall that randomized algorithm A x - y is called (c, 8) DD (i.e., differentially private) if for any two multisets St, S2 differing in exactly one coordinate, and any event O C V, we have
Pr [A(S,) O] S Pr(AA())) E 0 +
24

---

where the probability is over the randomness of A. The following result from [BGH 23] shows that one can transform a replicable algorithm for a statistical problem to a differentially private algorithm for the same problem.
Lemma 19 (Theorem 3.1 in 23). Let p < 0.01. If there is p-replicable algorithm solving a statistical problem with failure probability and sample complexity n, then there is an (e. DDP algorithm solving the same statistical problem with failure probability at most O(3 log 1/2) and sample complexity n O(Y/ log 1/8 log 1/8 + log" 1/3).
Existing works on differential privacy show that, for closely related problem, any differentially private algorithm requires at least (2logg (x)) samples. We will refer this problem as the non- statistical interior point problem and define it as follows. Given a set of samples S C X, define its interior as the set Interior(S) = [min(S), max [S)]- In the non-statistical interior point problem, we are given set S and the goal is to output some point I in its interior. To avoid confusion, throughout the section we will refer to our main problem, in which the goal is to find a point in the interior of a distribution using samples, as the statistical interior point problem.
We say an algorithm A has sample complexity n for the non-statistical interior point problem with error probability/ 3 if, for any S C X' of size n., we have Pr [A(S) E Interior(S)) 2 1 3, where the probability is over the randomness of the algorithm. The following result by Bun et al. [BNSVIS]
provides a lower bound for the sample complexity of differentially private algorithms on this problem.
Lemma 20 (BNSVV5)). Fix E (0,1/4), Assume that 5(n) - 1/(50n²). For any n, solving the non-statistical interior point problem with (e, 8(n) differential privacy requires sample complexity n 2 (2ll01"0110 (x1)-
We next show how transform an algorithm for statistical interior point an algorithm for non- statistical interior point with a similar guarantee on differential privacy.
Let s < 1/2. If there is an (e, d)DP algorithm for the statistical interior point problem with error probability 3, there is an (E',8')-Do -DD algorithm for non- statisticail interior point with sample complexity and error probability B where e' = O( log 1/5) and 8' O())
Lemma 21.
Proof. Let A be the mentioned statistical algorithm. Consider the following algorithm A'. Given the set X of size n, we let S be set of n i.i.d. samples from the distribution D = X, and output A(S). We show that A' satisfies the required guarantees.
Correctness analysis. With probability 1 5, the algorithm outputs a value in the interior of D, i... the range [min D, max D). which is the same as [min(X), max(X)]
Privacy analysis. Let X1; E X be two vectors that differ in one entry. Let y denote the output space of A. We need to show that for any O S C. we have
(r() 0 S o Pr(A E +
where the probability is over the randomness of A'. Let D3 and D3 be the corresponding empirical distributions for X1 and X2. By definition of A', the above incquality is equivalent to
Pr (A(S) 0) s e Pr. (A(S) E 0) + 8',
where the randomness is over both the sampling of S and the internal randomness of A.
We may assume that the S is sampled as follows. We first sample multiset of indices U C [n] with size by uniformly sampling n values i.i.d. from [n]. Note that this means an index may appear multiple times in U. We then obtain the i-th entry of by taking the j-th entry of either X; or X2. depending on the input, where j is the i-th entry in U. It is clear that this does not change the sampling procedure. Using this view, however, we can now couple the two probabilities corresponding to X; and X₂ in order to compare them. Formally, let A(U X) denote the value of A(S) when S is obtained from the above procedure. We need to compare the values Pr (A(U; X)) for X X, and X X2. where the randomness is over the draw of U and the internal randomness of A.
25

---

Assume without loss of generality that X1, X2 differ on their first coordinate. Let I denote the number times the value appears in U. Set & 10 + In 1/á. By iterated expectation.
Pr E]
Pr| Σ
Σ
Pr| E0 7 1r
Since [4] 1. Chernoff's inequality gives
et
7r[22++0 (1+t)
(Chernoff's bound)
Set
(Since t 2 10)
$ 8
(Since 2 In 1/6).
follows that
Pr[A(U; 0 Σ (P[ =0
(4)
1=1
We next claim that
Pr [r(((;X11) o)
E 1 i] + 8
(5)
where 6; 8 T Formally, let U; [n|] denote the of all ordered vectors of length n from [n] that have exactly entries of 1. By total probability,
Pr[A(U;X) E O
=
Σ Pr[u- = =u - ( E O], MEt
where the randomness in the probability in the right hand side is now only the randomness of the algorithm A. We now note that for all u Ui
[r[A(u; X1) E O] Pr(r((( E c0}+ e
-
This holds because A is 8)-DP and the set S given input A in A(u: X1) and A(u; X2) differ in exactly coordinates. Summing over all u, we obtain Equation (5).
Plugging this in Equation 4 we obtain
Pr [A(U; E
Pr = (AU +
1=1
[| Σ
Pr :).
i=1
1=1
Pr Pr [ (P((A E 00 +
Σ 1=0
Pr [I ii0;;
i16
5o.
1=1
where in the last inequality we have used the fact that S t to bound the first expression and the non- negativity of 6, for to bound the second expression. By total probability, the first expression is most P [A; X2) O). As for the second expression, is equal to E [8y] 5 e 1]. Observe however that 7 follows binomial distribution with parameters and 1/n. Therefore,
e"
E el
n
2F
1 +
(Since e" -15 5. for < 1/2 and e < 1/2)
<
c
26

---

It follows that
8
E
[0r] <
-1) e
-1)
8(ef +
(e 1)6
(Since & < 11/2)
36.
Finally, we have 6 = O. Plugging this back in we obtain Equation (In(1/0) + 10)e, finishing the proof.
3 with 48 and e
We now prove Proposition 5
Proof of Proposition Assume that an algorithm with these properties exists. Let n denote its sample complexity. For any B, by Lemma 19 we have an (s, 8)-P algorithm for statistical interior point with failure probability O log 1/3) and sample complexity
( log log + log? 3
12211
n 0
By Lemma 21 this means that there is an (s', DDP algorithm for non non-statistical interior point with failure probability 8' and the same sample complexity where
e' 0 (slog 1 (
B' 8²= B'=0(3lo5) (00g 1
8' = 0
Set 3 such that 8 = 0.05. Note that this can be achieved for some constant value 3 >> O. We can obtain any desired value for e', 8' by setting 8' = (()) and = = O / /og 1/8'). It follows that, for any E',8', there exists (E',8')-DP algorithm with failure probability 0.05 and sample complexity N 0 (n(1 1/e' log" 1/8')) for some constant c. Set e' 0.05. If 8 c'us, then this gives us the sample complexity N en(1 + (c'")) We claim that if we choose e' to be large enough, we can ensure that 8' < 1/50N22 By definition of 8', this means we need to show that
d'a 50c2 + log (oogg(ccn )d
Given the inequalities (x y + 2)² - 3(x² + ツ²² + +²) and (x + y)² - 2(x² + y²) we have
log 2 (c'
(1 (log(e) log (nn)
- (1 + 2 2 (c) + 2 (n²))
3
< + 4 log (c) 9 (n)
It is sufficient to show that
c'n 2 150c² (1 + 1lg d' + 9og n)
Setting e' to be large enough in terms of c, the above inequality holds as each term on the right hand side is asymptotically smaller than the left hand side.
Therefore, we have obtained an 8')-DD algorithm with sample complexity and failure
probability 8' where 8' < 1/50N'2, and e', 3 < 0.05. Invoking Lemma 20 we conclude that
N 2 [(log"| Since 8' @(1/n²), this implies that log" > ?(log" (x)), which in turn implies 2 2(log" (xl) as claimed.
27

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The abstract and intro clearly and accurately reflect paper's contribution.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Claims are supported with formal proofs and the assumptions are clearly stated. As such, the limitations are clear.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
28

---

Justification:
The paper provides full proof for all of the stated results.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification: The paper is theoretical and does not contain any experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
29

---

Answer:
[NA]
Justification:
The paper is theoretical and does not contain any experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips... cc/
coiioooooollyy for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ ctpppp..cppulli//guuii wwwiiccgguie///eeeeeee CoodeSubeiiieeee ssi wwwinnolli onnolicy)))) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: The paper is theoretical and does not contain any experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: The paper is theoretical and does not contain any experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
30

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of exccution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
The paper is theoretical and does not contain any experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: Research conforms to the code of ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer:
[NA]
The paper is theoretical and we do not believe it has any societal impact worth highlighting.
Justification:
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
31

---

The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper is theoretical and does not contain any experiments.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: The paper is theoretical and does not contain any experiments.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
32

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper is theoretical and does not contain any experiments.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: The paper is theoretical.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper is theoretical.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
33

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: The paper does not LLMs beyond the standard usage for writing and editing.
Guidelines:
The answer NA
that the method development in this research does involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy for what should or should be described.
34


Reviews:
[{"review_id": "d6k7mYFSmA", "reviewer": "Reviewer_akGx", "summary": "This paper explores the concept of replicability in online pricing problems, especially in the prophet inequalities and delegation problems settings. Replicability involves the stability of an algorithm with respect to different input data, which stands central to transparency in economic decision-making. The authors present a replicable and almost optimal approach to prophet inequalities, setting the sample complexity to $poly(log^\\star(X))$, where X is the ground set of distributions. They use these findings on the delegation problem with an optimal matching lower bound setting the $\\log^*|X|$ requirement. One notable technical improvement is a new algorithm for a heavy hitter variant with a nearly linear dependence on the inverse of the heavy hitter parameter that improves upon prior work by quite a margin.", "questions": "Could the authors suggest directions for future work in empirically analyzing the implemented replicable pricing strategies, through simulations on synthetic or real datasets to test how they perform and robustify under real-world conditions?\n\nHow could the results be extended to cover distributions whose support is continuous or of unknown support addressing real environment settings?", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\nThe pricing strategy  proposed for prophet inequalities is shown to be attainable and nearly optimal, with a sample complexity polynomial in $\\log^*|X|$, a significant improvement over the additive error solutions. In fact, matching lower bounds are provided.\n\nThe paper addresses the important problem of replicability in algorithms which is indeed of interest recently. \n\nThe paper introduces a novel algorithm for a variant of the heavy hitter problem with reduced sample complexity from cubic to effectively linear dependence on the inverse of the heavy hitter parameter. This is an important technical contribution in its own right.\nThe generalization of the replicable online pricing model and results to the delegation problem demonstrates the generality and broader applicability of the authors’ techniques.\n\n\nWeaknesses\n\nThe main theorems (Theorem 1 and Theorem 2) assume the distributions have support on a given finite set $X$. While this is a typical starting assumption for theoretical computer science, it might limit straightforward application to continuous or unseen support spaces in practical use.", "was_revised": true, "final_justification": "I haven't changed my opinion on this paper, I would be happy with acceptance.", "rebuttal": "Thank you for your positive review!\nBelow we address your individual comments and questions.\n\n> .. suggest directions for future work in empirically analyzing the implemented replicable pricing strategies …\n\nWe thank you for this suggestion and will include it in our paper as a direction for future work. \n\n> How could the results be extended to cover distributions whose support is continuous or of unknown support addressing real environment settings?\n\nWe 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)"}, {"review_id": "7XjpVz9bh6", "reviewer": "Reviewer_5wxJ", "summary": "This paper studies replicable algorithms for the Prophet inequality and delegation problems. It focuses on a sample-based version of the Prophet inequality, aiming to characterize the sample complexity required for replicable algorithms to find a threshold (or price) that ensures competitiveness. The authors propose a median-based approach that is both replicable and near-optimal. They then extend this approach to the delegation problem and further establish that the dependence of the sample complexity on the size of the distribution’s support is tight.", "questions": "- Related to the weakness mentioned above: could the authors provide a separate section or dedicated paragraphs summarizing existing algorithms and results, including (but not limited to) the state of the art in sample-based Prophet inequalities, mean and median estimation algorithms, and the heavy hitter problem?\n\n- In Section 3, it is stated that using mean estimation introduces additive error, which is undesirable. Could the authors elaborate on this point or provide supporting references?\n\n- In many practical scenarios, samples are expensive. Given the increased sample complexity required for replicability, especially in pricing problems, how do the authors justify that replicability outweighs this cost?", "limitations": "NA", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 4, "originality": 3, "strengths_and_weaknesses": "Strength\n- Designing replicable algorithms is of significant importance for decision-making problems. This paper provides interesting results for the well-known Prophet inequality and demonstrates a fundamental trade-off between sample complexity, competitiveness, and replicability.\n\n- The theoretical contributions are strong, with both upper and lower bounds rigorously established.\n\nWeakness\n\n- The discussion of related work and prior results is not clearly separated from the authors’ own contributions. References to existing algorithms and techniques are often interwoven with the presentation of new results, which makes it challenging to understand what is new. It can enhance the clarity and readability of the paper by introducing a separate section or paragraph that clearly summarizes relevant prior work (The related work in Appendix does not include sufficient discussions about the algorithmic ideas and techniques).", "was_revised": true, "final_justification": "The authors have partially addressed my concerns regarding the presentation and the sample complexity. I will keep my score, as it already reflects my evaluation of the paper: it studies a classic problem using a new (though not original) framework.", "rebuttal": "Thank you for your careful reading of our paper and feedback.\nBelow we address your individual comments and questions.\n\n> “…could the authors provide a separate section or dedicated paragraphs summarizing existing algorithms and results…”\n\nOur paper already discusses relevant prior work in Appendix A, including known\nresults on replicable algorithms for mean and median estimation, as well as the\nheavy hitter problem. That said, we understand the reviewer’s concern about\nclarity and agree that separating background from our contributions would make\nthe paper easier to follow.\n\nTo 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.\n\n\n**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.\n\n**Replicable mean and median estimation.**  Replicable algorithms for mean and\nmedian 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|$.\n[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.\n\n**Replicable heavy hitters.**  Prior work has also studied replicable\nalgorithms for heavy hitter identification. [8] and [10] provide\nalgorithms that return a list of candidate heavy hitters, with sample\ncomplexity scaling cubically in $1/\\nu$.\nMore recently, [11] improved the dependence on the failure and replicability parameters for expected sample complexity,\nbut still maintained a $\\nu^{-3}$ dependence.\nIn 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}$\ndependence.\n\n\n\n\n\n> ... introduces additive error, which is undesirable ... elaborate on this point or provide supporting references\n\nWe 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.\n\n\n\n\n> …the increased sample complexity required for replicability\n\nWe 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.\n\n\n\nIf you feel that our response has adequately addressed your major concerns, we would appreciate it if you possibly adjust your score accordingly.\n\n**References**:\n\n[1] Pablo D Azar, Robert Kleinberg, and S Matthew Weinberg. Prophet inequalities with limited information. In SODA, 2014.\n\n[2] Aviad Rubinstein, Jack Z Wang, and S Matthew Weinberg. Optimal single-choice prophet inequalities from samples. Innovations in Theoretical Computer Science, 2020.\n\n[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.\n\n[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.\n\n[5] Constantine Caramanis, Paul D¨utting, Matthew Faw, Federico Fusco, Philip Lazos, Stefano Leonardi, Orestis Papadigenopoulos, Emmanouil Pountourakis, and Rebecca Reiﬀenh¨auser. Single-sample prophet inequalities via greedy-ordered selection. In SODA, 2022.\n\n[6] Haim Kaplan, David Naori, and Danny Raz. Online weighted matching with a sample. In SODA, 2022.\n\n[7] Andrés Cristi, and Bruno Ziliotto. Prophet inequalities require only a constant number of samples. In STOC, 2024\n\n[8] Russell Impagliazzo, Rex Lei, Toniann Pitassi, and Jessica Sorrell. Reproducibility in learning. In STOC, 2022\n\n[9] Mark Bun, Marco Gaboardi, Max Hopkins, Russell Impagliazzo, Rex Lei, Toniann Pitassi, Satchit Sivakumar, and Jessica Sorrell. Stability is stable: Connections between\nreplicability, privacy, and adaptive generalization. In STOC, 2023\n\n[10] Hossein Esfandiari, Amin Karbasi, Vahab Mirrokni, Grigoris Velegkas, and Felix Zhou. Replicable clustering. In NeurIPS, 2023.\n\n[11] Max Hopkins, Russell Impagliazzo, Daniel Kane, Sihan Liu, and Christopher Ye. Replicability in High Dimensional Statistics. In FOCS, 2024.\n\n\n[12] Mohammad Taghi Hajiaghayi, Robert Kleinberg, and Tuomas Sandholm. Automated online mechanism design and prophet inequalities. In AAAI, 2007.\n\n[13] Robert Kleinberg, and Matthew Weinberg. Matroid prophet inequalities. In STOC, 2012.\n\n[14] Michal Feldman, Nick Gravin, and Brendan Lucier. Combinatorial auctions via posted prices. In SODA, 2015.\n\n[15] Shuchi Chawla, Jason D. Hartline, David L. Malec, and Balasubramanian Sivan. Multi-parameter mechanism design and sequential posted pricing. In STOC, 2010."}, {"review_id": "Yld9HaLzkJ", "reviewer": "Reviewer_ZNhf", "summary": "The authors explore, for the first time, the concept of replicability for two important online decision-making problems, which sit at the intersection of computer science and economics; the classic prophet inequality and the delegation problem. Replicability is a well-established algorithmic notion in statistical learning, which intuitively states that the algorithm’s output is determined primarily by the input distribution rather than specific samples and/or other sources of randomness. It has been used so far to produce replicable algorithms in important problems of statistical/machine learning. \n\nThe authors focus on threshold-based algorithms and study the sample complexity (since, as is often assumed, the distributions are not known but we have sample access to them) and competitive guarantees of algorithms they design or inherit from previous works. By designing efficient replicable algorithms and establishing lower and upper bounds for the sample complexity (with some factors in the expression coming from the definition of the replicable online pricing problem) for the two settings, they showcase the trade-offs between replicability, competitiveness, and sample efficiency. More specifically, they give a replicable algorithm for the prophet inequality with an almost tight competitive ratio with high probability that requires relatively few samples from each distribution; they subsequently extend this result to the delegation problem. They then show that the sample complexity cannot be independent of the support size of the product distribution. To prove this, they develop a novel and improved replicable algorithm for outputting a heavy hitter for an input distribution (this is a slightly less general version of a well-known problem studied in related works), which may be of independent interest. They also provide a result that, in the iid case and for specific regimes, gives a tight factor for the dependence of the sample complexity on the competitive ratio.", "questions": "I got a bit confused from the abstract, which one is the matching lower bound? I understood that the authors show the bound has to depend on $\\log^*\\mathcal{\\mid X \\mid}$, but they don't match it up to the factor of the upper bound (?) Please clarify this, and also what happens with the other factors, so that you can have a tight bound.  \n\nI also got a bit confused in theorem 4, why is $\\alpha<=¼$? Does this mean that this the regime for which the dependence on $\\alpha$ is tight, but is $\\alpha>¼$ we don't know? \n\nIt was a bit hard to follow all steps in the appendix for the proof of Theorem 3 (including the result for the replicable heavy hitter); is it the case that you cannot use as black box the previous algorithms  for the heavy hitters problem to show the dependence on $\\log^*\\mathcal{\\mid X \\mid}$, i.e., the new algorithm with the improved factor is necessary? \n\nMinor notes: \n\nIn Lemma 2, maybe at least cite the exact lemma from the other paper, or give the expression with the various polynomial factors on $\\log^*\\mathcal{\\mid X \\mid}, 1/\\rho, 1/\\beta,  1/\\epsilon$, to make it self-contained and know what these are. And once given, you can use the $poly()$ expression for ease of exposition. \n\nIf possible, expand a bit more on the significance of Theorem 4: Why do we need to know the exact dependence on $\\alpha$?", "limitations": "yes", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths: \n\nStudying replicability in online decision-making is an interesting research direction, especially in important practical scenarios that lack replicability guarantees. \n\nIt's good that the algorithms for the two problems can give competitive ratios that are almost tight, while not requiring too many samples from each distribution; all factors in the sample complexity expression are essentially constant (since the iterated logarithm is always very small, even for relatively large support sizes). \n\nThe result that shows that the dependence of the sample complexity on $\\log^*\\mathcal{\\mid X \\mid}$ is necessary is interesting and the proof involves going through various non-trivial steps, including the new algorithm for the heavy-hitter problem. \n\nWeaknesses: \n\nI think what the authors do not mention explicitly is that from the work of Samuel-Cahn we know that setting the median as threshold also gives the optimal $½$-approximation for prophet inequalities (apart from setting half of the expectation of the max as threshold). Thus, the algorithm used is known, and since the replicable algorithm for approximate median estimation is from previous work, Theorem 1 becomes more of an observation, because it just combines the previous result with the known algorithm to get a replicable algorithm for the prophet inequality. For Theorem 2, we know from the work of Kleinberg and Kleinberg that the delegation problem is closely connected to the classic prophet inequality, so it is expected that the guarantees carry over to this setting and its slight variants.  \n\nApart from Theorem 3, which I mentioned in the strengths, it doesn't seem that the rest of the results can account for significant contributions either. Theorem 4 goes into the case of iid distributions to show a tight linear dependence on  $\\alpha$ (i.e., the competitive ratio), which is nice to know, but it's also just one of the constant factors, so the gain is to know that the tight bound will depend linearly on this specific constant. However, it’s just a small factor in the number of samples that we need. Similarly, concerning theorem 5, it's interesting that en route to prove theorem 3 the authors get an improved sample complexity for this version of the heavy hitter problem, but, as they say, they improve a bit on one factor, and some of the improvement comes already  from the concentration bound that doesn't apply to the more general setting the previous works studied. Also, they acknowledge that their two-stage approach has been previously explored, so I'm not sure if there's significant gain in terms of novel techniques that can be applied to this, or similar, problems.  \n\nStill, in practical scenarios, the single-sample algorithm of [RWW19] is very simple and optimal. I get the argument that it doesn't work with the definition of replicability that the authors follow, but it's interpretable, very easy to implement, recovers the optimal guarantee with full knowledge of the distributions, and requires just one sample from each distribution. Given that, maybe there are other online decision-making problems for which a replicable solution makes for a stronger case.", "was_revised": true, "final_justification": "The authors have mostly addressed the questions I asked in the rebuttal. I think it's an interesting topic and the authors provide a satisfactory answer to the main question they ask. However, I'm unsure about the novelty in parts of the paper, which makes my score borderline. I also think that the paper should be revised/polished, so that the new contributions and techniques and the relation to previous results can become more clear.", "rebuttal": "Thank you for your careful reading of our paper and feedback.\nBelow we address your individual comments and questions.\n\n\n> “…matching lower bound…”\n\nHere 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. \n\n> “…why is $¼$…”\n\nNote 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. \n\n> “…use previous algorithms…”\n\nOur 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.\n\n> “…expression with the various polynomial factors…”\n\nThank 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.\n\n\n> “…significance of Theorem 4…”\n\nHere 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.\n\n> “…work of Samuel-Cahn…”\n\nWe 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.\n\nIf you feel that our response has adequately addressed your major concerns, we would appreciate it if you possibly adjust your score accordingly."}, {"review_id": "kNgRyzTCi9", "reviewer": "Reviewer_mjxJ", "summary": "The paper analyzes the problem of Online Pricing where the goal is to set a threshold $\\tau$ such that the reward obtained by accepting whatever first value received that exceeds $\\tau$ is at least $\\alpha$-approximation of the maximum of the sequence with probability at east $1-\\beta$. In particular the paper focuses on replicable algorithms to design this threshold, as in algorithm where the output is determined by its input more than the internal randomization. Furthermore, they analyse the delegation problem, where a principal has to set a threshold such that the value reward chosen from him by an agent among a set of possible values exceeding the threshold is maximized. The results provided characterize the sample complexity needed in both problems to reach a $1/2 - \\epsilon$ competitive ratio. Furthermore they show that in the case of the Online Pricing problem the dependency on the support of the distribution in the sample complexity is unavoidable. Lastly,  they provide results for the same problem, in the case in which the samples are chosen in an i.i.d. fashion and design an algorithm that recognize the heavy hitters of the distribution and provide, in this case as well bounds on its sample complexity", "questions": "1. Does an analogous result of Theorem 3 holds even for the delegation problem? Or more in general are you aware if the sample complexity expressed in Theorem 2 is tight?\n\n2. Similarly for Theorem 5, is the result provided tight?", "limitations": "yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The paper analyzes a well know theoretical problem (prophet inequality) which is well-established in the machine learning community, therefore of general interest. The results provided are sound, bringing new insights about the topic. Moreover, the focus on replicability adds originality to the results. Lastly, all the assumptions required are clearly stated.\n\nOn another note, I think the structure of the paper could be improved: having the statements of the theorems before the setting and the notation is introduced, makes the paper sometimes hard to read.", "was_revised": true, "final_justification": "I think this paper is valid, hence I keep my positive score unchanged.", "rebuttal": "Thank you for your positive review!\nBelow we address your individual comments and questions.\n\n\n\n> I think the structure of the paper could be improved …\n\nThank you for the helpful feedback. We will make sure to incorporate your suggestion for the final version of our paper.\n\n> Does an analogous result of Theorem 3 holds even for the delegation problem?\n\n\nThank 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.\n\n\n> ... Theorem 5, is the result provided tight?\n\n\nExamining 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])."}, {"review_id": "CO5gZnnHoK", "reviewer": "Reviewer_Vyhk", "summary": "The authors study replicable online pricing, a variant of prophet inequalities in which the algorithm does not have direct access to the underlying distributions but can sample from them, and it is required that the acceptance threshold must be chosen so that the output is stable under resampling ($\\rho$-replicable).\nFor the case where the distributions are finitely supported, the authors design a pricing rule that is $(1/2-\\varepsilon)$-competitive using $\\textrm{poly}(\\log^*(|X|),1/\\rho,1/\\beta,1/\\varepsilon)$ samples, where $X$ is the finite support of the value distributions.\n\nThe authors also show via a reduction from replicable interior-point estimation that the $\\log^{*}(|X|)$ dependence is unavoidable.\nBeyond prophet inequalities, the paper extends the techniques to a delegation model, obtaining the same sample complexity, and introduces a new replicable heavy-hitter algorithm whose sample complexity is nearly linear in $1/\\nu$, where $\\nu$ is the heavy-hitting parameter, improving on prior cubic bounds in $1/\\nu$.", "questions": "Your sample-complexity bound is polynomial in $\\rho^{-1}, \\beta^{-1}, \\varepsilon^{-1}$, but you don’t give any matching lower bounds in these parameters. Do you have evidence that this polynomial blow-up is supposed to be there, or do you suspect those exponents could be shaved, maybe even down to log-level?\n\nTypos: line 217 \"we say that \\tau is \\alpha-competetive if...\"", "limitations": "yes", "rating": 5, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strenghts:\n1) Near-optimal sample bound for replicable prophet inequalities and delegation.\n2) Improved algorithms for the replicable heavy-hitter problem.\n\nWeaknesses:\n1) as noted in footnote 2, the proposed algorithm implicitly relies on correlated sampling and hence is not computationally efficient.", "was_revised": true, "final_justification": "I'm not familiar with the line of work this paper is about, but I enjoyed reading it and to me it's a valuable contribution. Hence, even if with low confidence, I recommend the paper for acceptance.", "rebuttal": "Thank you for your positive review!\nBelow we address your individual comments and questions.\n\n> … don’t give any matching lower bounds in these parameters … evidence that this polynomial blow-up is supposed to be there\n\nThank 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.\nRegarding 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."}]

Author rebuttal:

Meta-review: This paper explores the concept of replicability in online pricing problems, especially in the prophet inequalities and delegation problems settings. The paper has a set of concrete and solid results, and all reviewers appreciated the importance of the problem, the significance of the results, and the technical novelty of the theoretical results. 

That said, there are still some concerns regarding the statements and presentation of the results, and more importantly, on what we know from previous works and what the contributions are in terms of techniques of this one. For instance, some reviewers were not satisfied with the answer because it didn't mention/cite the paper that establishes the median algorithm for the prophet inequality problem, as it is folklore in the community. Please consider addressing the presentation issues and proper citing of prior work in the final camera-ready version of your work.
Decision: Accept (poster)