Sample Complexity of Posted Pricing for a Single Item
Authors: Billy Jin
Thomas Kesselheim
Will Ma
Sahil Singla
Venue: NeurIPS 2024 spotlight (2024)
Keywords: sample complexity
revenue
welfare
pricing
online
prophet inequality
Primary area: algorithmic_game_theory
TL;DR: We obtain tight bounds on the sample complexity of posted pricing for a single item, for both independent and correlated distributions on the buyers' values.

Abstract: Selling a single item to $n$ self-interested bidders is a fundamental problem in economics, where the two  objectives  typically considered are welfare maximization and revenue maximization.   Since the optimal auctions are often impractical and do not work for sequential bidders, posted pricing auctions, where fixed prices are set for the item for different bidders, have emerged as a practical and effective alternative. This paper investigates how many samples are needed from bidders' value distributions to find near-optimal posted prices, considering both independent and correlated bidder distributions, and welfare versus revenue maximization.  We obtain matching upper and lower bounds (up to logarithmic terms) on the sample complexity for all these settings.

Sample Complexity of Posted Pricing for a Single Item
Billy Jin"
Thomas Kesselheim²
Will Ma
Sahil Singla
Abstract
Selling single item to self-interested buyers is fundamental problem in economics, where the two objectives typically considered are welfare maximization and revenue maximization. Since the optimal mechanisms often impractical and do not work for sequential buyers, posted pricing mechanisms, where fixed prices are for the item for different buyers, have emerged practical and effective alternative. This paper investigates how many samples are needed from buyers' value distributions to find near-optimal posted prices, considering both independent and correlated buyer distributions. and welfare versus revenue maximization. We obtain matching upper and lower bounds (up to logarithmic factors) on the sample complexity for all these settings.
Introduction
A fundamental problem in Economics is how to sell single indivisible item set of n self- interested buyers. This problem challenging because the value associated to the item private knowledge of each buyer and thus can be strategically misreported. The mechanism designer usually has one of two objectives: winning buyer, and (b) revenue maximization where want to maximize the price paid by the winning buyer. The welfare maximization problem was resolved by Vickrey in 1961 [Vic61] and the revenue maximization problem was resolved (for independent distributions) by Myerson in 1981 [Mye8T], both of whom were awarded the Nobel prize Economics for their contributions. In either case the optimal mechanism is truthful auction, in which buyers report their values and have incentive to misreport.
(a) welfare maximization where we want to maximize the value of the
Although we know optimal mechanisms for selling a single item, these auctions are often diffi- cult/impossible to implement practice. For instance, the buyer does not know exactly how much they will pay if they win the item and these auctions do not work for online settings where the buyers arrive one-by-one [AM* 06 HR09]. Thus, the last two decades has seen a lot progress on under- standing the power of simple but near-optimal mechanisms. In this regard, posted pricing mechanisms have been identified to be very successful (see books and surveys [Rou 16 Harl3 CFH + 19 Lucl7]). Here, the mechanism designer puts (carefully chosen) price π. the item and then the i-th buyer takes the item the item is not already sold and if they value above т; Posted pricing mechanisms have several advantages: they truthful since does not depend on the i-th buyer's value; the buyer knows exactly how much they pay on winning an item; and they work even for online settings so the buyers do not have to be simultaneously present. Additionally, in the setting of Myerson's 1981 paper of independent buyer valuations, they are known to give a 2-approximation both the optimal welfare (which usually called Prophet Inequality) and the optimal revenue
"Comell University, School of Operations Research and Information Engineering, bzj3@ cornell.cdu. UUiveersity of Bonn, Institute of Computer Science and I Lamarr Institute for Machine learning and Artificial Intelligence, wew.malessslehemeeee... @ unni-bonn.de
'Columbia University, Graduate School of Business and Data Science Institute, @m2428@ gs..columbia.ddu GGerriaa Tech, School of Computer Science, ssingla gatech.edu. Supported in part by NSF award CCE. 2327010.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

KS77 KS78
CHK07 CFPV19), long as the posted prices are set correctly. This raises the main
question of the current paper:
How many samples are necessary from the value distributions of the buyers to find near-optimal posted prices for single item? Is there a difference between indepen- dent vs. correlated distributions or between welfare revenue maxinization?
Despite being a natural question, the tight sample complexity bounds for single item posted pricing are unknown, both for independenn/comrllted and welfare/revenue settings.
1.1 Model
Before stating our results, we formally describe our model.
Posted pricing. There is single copy of an item. Buyers == I..... n arrive in order, each with private value (willingness to pay) V; for that item. Price πं is offered to buyer i, and the first buyer (if any) for whom Vi 2 ny end up buying the item, "winning" the auction. The objective is to maximize either welfare, which is the value of the item to the winner, or revenue, which the price paid by the winner.
Distributions and policies. We will assume that the vector of values V (Vis..., Vn) is drawn from an unknown but fixed distribution D over [0, 1J". If each V; is drawn independently from some marginal distribution D;, then D is called a product distribution, written as D Di X DR.- Meanwhile, posted pricing policies are defined by a vector of prices π (T1, nT) that must be fixed before the first buyer arrives, and possibly restricted to some subclass II. The objective of policy under buyer values V is denoted by T (V). which equals Vargmin (iom, SV;). and ( SV: for the welfare and revenue objectives respectively, understood
be 0 if the item is not sold. We (abusively) let x (D) == Ev (V) denote the expected objective of and let IID) suPxen π (D) denote the best expected objective of policy in IT knowing D.
Note that if we are given the product distribution on buyer values, the optimal policy (for either objective) can be easily computed using dynamic programming (C Consequently, for product distributions we consider the full policy class II = [0, 1J". and omit the dependence on II.
Learning problem. A learning algorithum takes as input samples V that are drawn independently and identically distributed (IID) from the unknown distribution and an error parameter E (0, 1), and seeks to return policy π E II that satisfies TD) 2 IIDD) E, which is called E-approximation. Given a failure probability E (0, 1). the sample complexity is the minimum number of samples required for there exist a learning algorithm that, under any distribution D, returns an e-additive approximation with probability at least 1 - 8, noting that the randomness is over both the samples and any random bits in the algorithm. The sample complexity and learning algorithm will depend on the problem variant, defined by the objective (welfare or revenue), any parameters of the policy class II, and whether D is restricted to be product distribution or not. The sample complexity will also depend on the parameters E, 8 0.
1.2 Our Contributions to Posted Pricing for Product Distributions
The study of sample complexity for posted pricing goes back to at least the seminal work of Kleinberg and Leighton [KL03] who study revenue maximization for selling single item to single buyer (welfare maximization is trivial for single buyer since we just allocate the item by setting 0 price). For the general posted pricing problem with n buyers, the best known sample complexity bounds were due to Guo et al. [GTTZ2I] who showed that ((n/=²) samples suffice from each buyer's distribution for both welfare and revenue maximization objectives. Although there is a simple (21//²) lower bound for both welfare and revenue maximization settings, prior to our work it was unclear if polynomial dependency on the number of buyers n is necessary.
Our first result for product distribution shows that for welfare maximization using posted pricing (a.k.a. prophet inequality), the sample complexity is independent of the number of buyers n.
Theorem 1 (proved in Subsection 2.1). For product distributions, the sample complexity of welfare maxinization is (1L/E² (1)8()

---

Proof sketch. We start by constructing the product empirical distribution using the samples, where for each we take the uniform distribution the ((1/c²) samples and then take the product distribution for different i. Our main result is that the optimal policy (dynamic programming solution) on this product empirical distribution is an e-approximation with high probability. Although one could use standard concentration bounds to bound the gap between the learned and optimal thresholds, such arguments lose a poly(n) factor. This is because the difference between successive thresholds is bounded by 1, so naïvely the total variance of n thresholds could be (2().. Our main idea is instead study a martingale that adds up the errors made in the dynamic programming solution. This way, too high values for one buyer and too low values for another buyer balance each other. On this martingale, we use Freedman's 's inequality (which is martingale variant of Bernstein's inequality), which allows us to bound the total variance in terms of conditional variances. A careful application of another concentration bound allows us to bound these conditional variances in terms of the change in the optimal value, whose sum is always at most 1. This latter concentration bound is what causes the additional factor of (1/8) in the sample complexity.
Our second result for product distribution shows a separation between welfare and revenue maxi- mization using posted pricing. by proving that the (nn==" sample-complexity result of [GHTZ2I] for revenue maximization is tight up to log factors.
Theorem 2 (proved in Subsection 2.2 For revenue maxinization product distributions, any learning algorithm requires O2( (t) samples to return an s-additive approximation with probability greater than 6/7.
Proof sketch. We construct for each buyer i two possible value distributions that add the same amount (roughly 1) to the value-to-go of the optimal dynamic program. However, these distributions have different optimal prices, and making a mistake (choosing an incorrect price) in isolation loses roughly value. Although these mistakes accumulate in non-linear fashion, we show that making
Finally, these value distributions have probabilities on the scale of Itss with the same supports (essentially, only 1/n of samples provide information), which means that 22 ((2) samples are needed to avoid making a constant fraction of mistakes.
M mistakes must lose in total 2 =M* n
1.3 Our Contributions Posted Pricing for Correlated Distributions
Independence among buyer valuations can be a strong modeling assumption for many applications. Although for arbitrary correlated distributions the optimal policy is not learnable, one could hope to learn the best policy in the class of all posted pricing policies. recent work of Balcan et al. BDD+21 can be applied this setting to show that ((n/e²) samples are sufficient to learn e- optimal posted pricing. As discussed in Theorem [ this linear in n dependency is necessary for revenue maximization, even for product distributions. Our first observation that for correlated distributions, we need to lose this factor even for welfare maximization.
Theorem 3 (corollary of Theorem 5) algorithm requires O ( samples to return an E-additive approximation with constant probability.
For welfare maximization with correlated buyers, any learning
Given this lower bound, natural next question is to consider the subclass of posted pricing policies where the algorithm is only allowed to change its threshold at a small number of given locations. Can now remove the linear in n dependency from sample complexity? ? The motivation to study this class comes from posted pricing applications where it is not possible for the algorithm designer to update the prices at each time step, e.g., due to business constraints.
Formally, for S S f2,...... ... ...,.,, n}. we say that posted pricing policy и respects change-poing S if π; can differ from Ri-1 only when i E S. We let IIs denote the class of all policies that respect change- points S, noting that policies in (0) post a static price for all buyers, and [T([2...., = [0, 1 1 Our following result shows that one can obtain sample complexity that is independent of n. depending only on the size of
Theorem 4 (proved in Subsection 3.1
For correlated distributions, the sample complexity of welfare
or revenue maxinization is O (1+ ST (o (1+ +lgg+)/ (1/8)) when the policy is restricted to IIs, for any
S C (2....,n.) n).
3

---

Proof sketch. By existing results in learning theory, it suffices bound the pseudo-dimension of TTs. This will boil down to understanding the structure of "good sets", which are sets of the form { 11g: TT() 2}. for some imput v and some target 2. We will show that for a natural parameterization of lls, any good set can be expressed as the union and intersection of Q([S) + 1) halfspaces, which implies the pseudo-dimension of IIs is O([SS + 1) log(IS) + 1)) by result of [BDD+21. This bound on the pseudo-dimensio translates to the above sample complexity bound.
The learning algorithm which achieves the sample complexity bound in Theorem 4 is simply sample average approximation (SAA), which returns the policy in Iīs with the highest objective value averaged over the samples. SAA can be computed in time ([In(In))+ are 1 + |S] prices to decide, each of which can take T'n possible values (one for each realized value in the T samples of length n),, and evaluating each combination of prices over each of the T samples takes runtime linear in n. We leave as an open question whether there is a more efficient algorithm.
This is because there
Finally, we complement our sample complexity upper bounds for correlated distributions by giving matching lower bounds (up to polylogs).
Theorem 5 (proved in Appendix A.5 For welfare or revenue maximization on correlated distribu- tions, a learning algorithm requires S2( e² samples to return an E-additive approximation with constant probability, when restricted to the policy class IIs for any C 12....,
Proof sketch. In the construction for Theorem 5 on each trajectory exactly one of the + [S] decision points (randomly selected) will be relevant, essentially diluting the samples by factor of 1 1+ |S] and leading lower bound of 2( ((1))))).
1.4 Further Related Work
In 2007, Hajiaghayi et [HKS07 discovered connections between auction design and posted pricing via prophet inequalities. Since then, there is a long line of work understanding the power of posted
pricing for selling multiple items to combinatorial buyers [CMSIO FGLIS, DKL20 AKS21 CC23).
For single item revenue maximization with known distributions, Correa et al. [CFVV19] showed the equivalence of welfare and revenue maximization objectives for single item posted pricing.
For background on sample complexity, we suggest Wainwright's excellent textbook [Wi19]. Sample complexity of auction design has been greatly studied; e.g., see [KL03] CR14 MR16). We refer the readers to Guo et al. [HZI9). who recently resolved single item revenue maximization in the offline setting, for an overview of the literature. In [GHTZ2I]. Guo et al. generalized their techniques for revenue maximization over product distributions to all "strongly monotone" problems, which includes posted pricing for welfare and revenue maximization.
Recently, there is also lot interest in learning auctions in limited feedback models like bandit and pricing queries [GKSW24 SW24 LSTW23]. We should note that sample complexity of optimal stopping (equivalent to our welfare maximization problem) has been previously studied in [GM22), who analyze linear stopping rules a contextual setting. Our application of techniques from [BD to online algorithms over correlated sequences is also similar in spirit to some results from [MX24), who study a different application of inventory optimization.
Another related but tangential line of work focuses on prophet inequalities with samples [AKW14 14 RWW CDFS22 RWWCDDF22 CDF* 22 DKL++41 The key distinction in these works is that their benchmark is the expected hindsight optimum, rather than the optimal online policy. Notably, any online algorithm incurs at least a factor of 2 loss compared to the hindsight optimum, even in the case of single-item prophet inequalities. As a result, this line of research aims to achieve 0(1) ((1)-apprxximation guarantees, rather than the sublinear regret guarantees pursued in the current paper. Furthermore, their techniques differ significantly, as they often assume unbounded distributions. Finally, there is also work that explores the (non-)robustness of algorithms for the prophet inequality problem to inaccuracies in the distributions [DK19 and to dependencies in distributions [IS20 LPS24].

---

2
Product Distributions
In this section we first prove our improved upper bound on the sample complexity of welfare for product distributions, and then prove new lower bounds the sample complexity of revenue for product distributions.
2.1 Positive Result for Welfare: Proof of Theorem
The reward of the optimal policy is given by the following backward induction: r 0 and rf E [maxfri- V.]] E [(V 1+]+ rf+1- sets n1 17+1-
When we do not know the distributions but only have T samples from each of them, we can consider the optimal policy on the product empirical distribution, which corresponds to replacing the expectations in the above definitions by the empirical average. That is, we will analyze the policy that
sets fi+1, where i; is defined recursively by fx+1 0, = (v= fi+1)* + fs+1.
Let ry be the expected reward of this policy when starting with the i-th arrival. In order to prove the theorem, it is sufficient to show that with probability at least 8, we have ri 2 rî T 2 (5 (n(2)/))/e) for any choices of e, 5 (0,1).
Let us define 1) = f. [max (f++1, V.]] or equivalently as
1/1 7 E (V,10 - +++1++++++++ - E [(V f411)
That is, Ti denotes the error introduced by using the empirical distribution for buyer instead of the actual one. Note that 7/; can both be positive and negative.
The two key steps of our proof are as follows. We first show that
r1 rf 2 max
Σ
(1)
This inequality holds point-wise, that is for any samples drawn. Then, we show that for T' > (5 (5ln(2//8)/e) samples, we have maxj21 ->=>
S e with probability at least 1-
In order to show ① we first lower bound r1 in terms of Å1. Lemma 1. r1 2 A max.ee(0...... El= ?/s-
Proof: Let j E (0, 1........ n. be the smallest index for which rj+1 2 fJ+1, which exists because
0 Tn+1 2 Pnt1 = 0. Note that we have T4 < fg for 1 I S j. We rewrite rı as
Pr [Vi < r2]r2 [V 2 P2 [V V f2] + E [(V 12) 12)1))
Repeating this argument,
ri == - B[(V, - 144 (1 EEV, 122 + +
Inductively, we can also establish that
A - - + P(1)+ + + E, max (V() ,
Combining these equalities,
- ( ET_ -v11+ 1ott-EE(1 B((VV ri41 1122
<fr
+ I m/ A3+1 E1, + Tj+1 I1zetfu
28s+1
Σ 7 IT (v. - f141)+1) $ ET max 1 f3413 [] fz411
Σ M/-
This implies f. Ti E mmx Ei= nr. completing the proof.
5

---

A similar proof allows to prove the following lemma.
Lemma 2. ř 2 rf max,) (- Ei=1 %/)-
Proof. Let j {0, ....... n be the smallest index for which f5+1 2 rj+1 which exists because
0 = Fnt1 2 .+ = 0. Note that we have f. < rg for all S i S J, allowing us to derive
r BI( 1
T Σ (v, f++))))
T
+
E2 [mxx
V j++ H1
mVx
f3+1}
T
1=1
SPyl1
T
- -(+1+++
T Σ
(v (1) - *(+1)+
T ,341
+ E [max (Vy, f
max A5413
T
n
This implies ri - f1 S maxje j (o.....)) Ei m.), completing the proof.
The last two lemmas imply Ib. Thus, we need bound max, D Me complete the proof.
Lemma 3. For every 8, O, with probability at least 1 - 6, we have max, E nil S e if T 2 (5lm(2e/8)/e).
Proof. Observe that
Σ so it suffices to show that max, > -ー ml 2 c/2 with probability at most 8. Reversing the quantity of interest to max, EE 77s allows us to define martingale, and use Freedman's 's inequality, which a martingale version of Bernstein's inequality.
2i TI E 17 $ EE ne
Ci Th S max, EΣ nil,
Lemma 4 (Freedman, Theorem 1.6 in [Fre75). Consider a real-valued sequence {Xi Xxhee2 such that Xo and [Xe+1 Xt, Xc-1s......... Xoo] foror all Assume that the sequence is uniformly bounded, i.e., [Xel S M almost surely for all t. Now define the predictable quadratic variation
process of the martingale to be W. = E)= TE [x3 X Xi-I...., Xoo for all t. 2 1. Then for all é 2 0 and o² 0, and any stopping time we have
Pr E
l and W, I c²]
< 22xx (-xxp(=0ff1//11))
A corollary of Freedman's inequality is that Pr [ Xj > S 2 2exp
e M473
Pr [W, S o.]. In order to use Freedman's inequality, we consider n. random variables X X where X = $ ((V - ( ((--)))))))))) for n 1} and f E (1....,T): By this definition,
(O.
7: Er X(n-iT++
because (t) カ- and Vn-i are identically distributed and independent of A Moreover, for all
E[X, XI...., X,-1] and X < T

---

Let & be the event that ΣØ= E [X?
, ;h....,;--11 xj-1] > o²
1n(2c/8) 7
By Freedman's
c+1
inequality, using 2 (5 (5ln(2e/6)/e) we have
Pr max, E> 7i 2 - Pr
max,
Lj=1 Xj
I 2 2exp
2/8 0
+ Pr [
(l((2//)) (6)
/8
VT
S 2 2exp
+ Pr [8]
C
(n(26/6)
6ln(2c/8)
c+1
VT
= 2 exp
25
In
20
2e
8 )) + Pr [8]
8e
+
40
6VT
< 2 exp (-(1)
+ Pr [ = 1/2 + Pr [2]
remains to show that Pr [8] S
To this end, we observe that for any i E fo..... n 1} and
t t {I....TT),
E ++
X , XIT++-1]
((v52) fn- - E (v - F)-
B
S....,,ITHHE.
S p [vvi in- +) XI....; X
ト EE= E (v f + X XIT.
1
T Bi: fit f Fn).
where the inequality uses E [ E [ 2 E - = E [(Y [
for any random
variable Y with 0 < S almost surely. total, we have
b nT Σ
E
X3
X , X1....,,,-1]]
Σm_ E(A A+-1 A+:1: An]
As Ei=(fe (fr - 1++1 = A < almost surely, we have by Lemma 5 (see below) that
e In
2c 8
E fA Ptt1
Anl 2
with probability at most
Therefore, we have
2e
8 2
Pr S Pr
Σ R (f: - A.t [AtI, Fal
In
8
Lemma 5. Let Y1, Yz,..., Yn be a sequence of (not necessarily independent) random variables in
[0, 1] such that Ei= Yi S almost surely. Then, for any 5 >> 0, with probability at most ö, we have
Σ
E | YI...., Y--] - lg)
We defer the proof of Lemma
5 to the appendix.
2.2 Negative Result for Revenue: Proof of Theorem
Each buyer i = 1,..., has a marginal value distribution that could be D ("High") or D.. ("Low")::
n=i 4n
w.p.
n-i
w.p. In 8
2n
4n
D
n
w.p. 2n
16
D =
n
w.p. 2n + 8
4n
4n
0
w.p. 1 1 16
w.p. 1 1
which are valid distributions as long as S 1/32 and n 2 2. All 2n configurations of whether each buyer has the High or Low distribution are possible.
7

---

Optimal policy Fix any configuration of whether each buyer has the High Low distribution. Let rī denote the expected revenue to be earned under the optimal dynamic program, if buyer i is about to arrive and the item is not yet sold. We show inductively that rī = 4n n+1-i By definition r = 0, establishing r = -+1ー for = n + 1. Now consider i = n, ..... 1, and assume ri+1 = -n Note that it is better to offer one of the prices 1 + n-f + 4n than to reject the buyer by offering price of I, because both of these prices are greater than r (by the induction hypothesis). Thus, buyer i has distribution D. then
r = max { + 2 2m + 1 24),
(2 +
3 - 16 + 1 11 (1- + +1
max { - [ 16 } + n-
2+1-i.
Similarly, if buyer instead has D then
rf max 1 84), 1
a+l-i
n+l-i completing the induction. Note that r = 1/4. In either case, we have rī- = 4n
Bounding a policy's objective by its number of mistakes Now, consider arbitrary policy π = (#I...., TT) decided by the learning algorithm. Let r; denote its expected revenue earned if buyer i is about arrive and the item is not yet sold (under the true configuration of buyer distributions). We can without loss assume π to lie in { + An 1.4
R-i 1 because both prices are n-1 1 + An.
higher than ri+1. the expected revenue from rejecting (both prices are in fact higher than rf+1 an upper bound on T(+1). We say that the policy makes a mistake for buyer i if either म; 1/2 + n=i when i has the High distribution, or ग,ę makes mistake for i, then we have
= 1 + n-d when has the Low distribution. If the policy 4n
T1 T++1 S max { + - - 16 + n-
dn T141) 85))
in 4 1xx r++) 16
on the other hand, if the policy does not make mistake for i, then we have Pt Ti+1 I max { a= r++1) 2m G n-i
án rr+1) 1
(-=2 r241)
an
Hence, if the policy makes M mistakes for some M E {l...., n1,, then
ri = -i T(t1) S 1 M > im
- 1)
Now, observe that n-í T1-1 = 7 - rs+1 < A min n i, M). because the loss from making mistake is at most 45. and starting from buyer i + 1, the number of mistakes can be at most
4n
n (i + + n - and also at most M. Therefore,
1 M = + ((n-Mi) M) 4 M + 45 (M- 1) +... )
1 M - M
22 M (M+1).
Recalling that rī 1/4 4, this shows the additive error is (E)) as long as the fraction of mistakes M/n is a constant.
Computing the Hellinger distance We first analyze the Hellinger distance H HDD,, D!:) between (a single observation of) DH vs. D.P, which we note does not depend on the buyer i. The squared Hellinger distance can be bounded using 1 - HDH DF)
1 1
8
+
8
(
16 16 2)
V
2n
2n
2n
12
2m
2m
(8
+
2m
+
(1-
=1 -
where the inequality applies Lemma 6 below to each square root. This shows that HD DF) O(²), and the squared Hellinger distance is additive across independent samples. Using the fact that the Total Variation distance is upper-boundee bounded by vē times the Hellinger distance [GS02), we see that the Total Variation distance between T' independent samples of D vs. T independent samples of
D. is Ol / Ke). The proof of Lemma 6 is deferred because it is elementary.
Lemma 6. Suppose C' E (0, 1) and
|- C, C1. Then VCCC C 2
8

---

Completing the proof of Theorem 2 Suppose the distribution of each buyer is equally likely be High or Low, independently across buyers. Fix any learning algorithm and the constant probability 1/2. By the computation of Hellinger distance above, if the number of samples 7' is less than C for some constant C', then for any buyer i, the Total Variation distance between the samples observed under D vs. DJ is at most 1/2. (C' depends on the choice of constant 1/2.) This means that w.p. at decided by the learning algorithm cannot depend on whether buyer had
least 1 - 1/2, the price distribution D vs. D which means that there exists an adversarial choice of D or D. for each buyer i under which the probability of making mistake for buyer i is at least (1 - 1/2) 1/4.
Let M denote the (random) number of mistakes, under this adversarial configuration of whether each buyer has distribution D or D.- We have that [ [ 2 1/4. Although whether the algorithm makes mistake could be arbitrarily correlated across buyers i, applying A I 1, we can employ
Markov's inequality on the random variable MM to see that
P [11 M ) 2 7/8]
3/4 - 778
=
The LHS equals P| -
k1. We have shown that unless T = 2 ), there is probability at least 1/7 of making a constant fraction of mistakes, in which case
I. and hence 4
showed above that the additive error would be (e))). This completes the proof of Theorem 2
3 Correlated Distributions
In this section we prove our upper bound on the sample complexity of welfare/revenue maximization for correlated buyer distributions. We show nearly matching lower bounds in Appendix A.5
3.1 Positive Result for Welfare and Revenue: Proof of Theorem 4
To bound the sample complexity of posted pricing for correlated distributions, suffices to bound the pseudo-dimension of the policy class IIs. We use the same approach for both the welfare and revenue objectives. By standard learning theory results [BBL03], bounds on the pseudo-dimension translate to bounds on the sample complexity as follows.
Theorem 6. Let (IIm) denote the pseudo- dimension of IIg. For any e > 0, any ö E (0. 1) and any distribution D over [0, 1|", T 2 (PDim(Ils) + log })) samples sufficient ensure that with probability at least d over the draw of samples (V1...., VT) ~ D", for all E Ils.
E x(v.) - π (D) S.
We will show that (D)m( Ok log k), where t |S| + 1. This together with the above theorem immediately implies that Theorem 4 holds for the sample average approximation algorithm.
Let S = {ii, 82, is ... -1. where 1 i < is < ...
i For each j 1,2 k. let I = fig-1...., 2, 13. with the convention that in 1 and in = n + 1. In other words, I, .a...... Is consecutive intervals that partition [n]] and IIs is the class of policies that offers every customer in I, the same price. Note that every policy æ E IIg can be parameterized by ls prices p= (p1, P2..... PR), where Pj is the price offered to customers in I5. In the rest of this proof, will use T to denote the policy in IIs parameterized by p. By the definition of pseudo-dimension.
PDim(IIs) = VCdim(fls)
(2)
where πsS = [(V.2) + (( 2 2] E RR}. Let IT's denote the dual class of πss,
π = (0- (v) 2 =} v [0, ER.
We will use a result from [BDD+21] to bound the VC dimension of πs.. We state this result below in Definition [ and Theorem 7 This result essentially says that the pseudo-dimension of the primal class is bounded if the dual class is well-structured. Here, "well-struetured" essentially means that the domain can partitioned into pieces defined by a small number of boundary functions, and the function is simple on each piece.

---

with Theorem we get that Definition 1 (Definition 3.2 in 21)) A function class H C R. that maps domain y to is (F (F,9. --ieeeeeeee decomposable for class - {0,
FC R of piece functions the following holds: for every 1] of boundary functions and a class ofpicee
H. there are boundary functions goD ...... go E G and a piece function fo E F for each bit vector b E 10, such that for all E h(y) = Jú, (1) where by (w)..)).
E 13..
The main theorem in [DD states that the dual class is (F,G, -ipeceeise decomposable, then the pseudo-dimension of the primal class is bounded.
Theorem 7 (Theorem 3.3 in (BDD*211 21D.. Suppose that the dual function class Ut is (F,9.1) G.1)- piecewise decomposable with boundary functions 9 - [00,1] and piece functions S R The
pseudo dimenion of U is bounded as follows:
PDim(()) (((DDi((F") + VCdim(G")) In(D))n(PP + VCdim((*)) VCdim In
We now apply Theorem 7 to bound the VC dimension of iT 5 To do so must show that the dual class Lig (F, (FF, pieceewws decomposable for "nice" classes F and G. We will show that for both the welfare and revenue objectives, we can take F to be the family of constant functions and g to be the family of axis- axis-aligned halfspaces. This will follow from the below lemma, whose proof is deferred to the Appendix for space reasons.
Lemma 7.
Let E [0, 11"h and let z R. Let G(v, z) = & TV(V) 2 =}. For both the R
welfare and revenue objectives, there are l1, "1,-" L,, us E RRu+too such that
G(v,2) Už (u1, 00) x... (uj-1, 00) x (11, Ui] x R
(3)
Corollary 1. II's is (F, D-piecewiis decomposable, where F is the set of constant fancttion, G is the set of axis-aligned halfspaces, and I 2( + 1).
Proof. Consider a function h E īiş. By definition of Iiğ, there exist v E [0, 1]"h and z E IR such that h(()) (v) 2 2}. By Lemma 7 there are 4,, U1,....... - Lx, un such that
{p R h(pp) = 1} = Uf_ (ui, oo) x ... x (uş-1, 00) (4,, Ug] RR-j.
For each j E [b]. let T.j = (p E T Pj > 1j} and Uj = {0 E RR. Pj S Uz}. Note that I, and Uj are axis-aligned halfspaces, and
U, U E h(0) = 1} U, n. n nU, n L
Therefore, in the definition of (F,G, -pecceeee decomposable, we may take the boundary functions to be the 2k functions corresponding to the halfspaces L1, UI,.... LR, Ug. On any given piece defined by these boundary functions, a constant function (equal to either 0 or 1).
For FF the set of constant functions and g the set of axis-aligned halfspaces in R² it is easy to check that PDim((") = O and VCdim = k. Combining Corollary [
VCdin(ūls) = 0 (k: In k + kn 2k) = Okk
This completes the proof of Theorem 4
Remark. we directly apply Theorem from BDD+21 to bound (Tim) then we would get
A (k: In k) pseudo-dimente bound for the revenue objective;
A (k (n(k)) pseudo-dimension bound for welfare objective.
In particular, the bound for welfare would grow with n. This dependence on is in fact unavoidable one works with ITs directly, because for instances like corresponding to is piecewise constant with ((z) pieces, even if = 1. This is why our Corollary] focuses on the indicator functions Ii; instead. Regardless, both the bounds for welfare and revenue require our Lemma 7 that analyzes the problem-specific structure of the "good sets".
( 2 n 2..... 1), the dual function
'Note Theorem is stated to bound the pseudo-dimense dimension, but the pseudo-dimensio coincides with the VC dimension for function classes consisting of {0, valued functions.
10

---

Acknowledgement This work done in part while the authors were visiting the Simons Institute for the Theory of Computing for the program on Data-Driven Decision Processes. The authors thank Zhuoxin Chen for identifying typos an early version.
References
[AKS2I] Sepehr Assadi, Thomas Kesselheim, and Sahil Singla. Improved truthful mechanisms for subadditive combinatorial auctions: Breaking the logarithmic barrier. In Proceedings of SODA, pages 653-661, 2021.
[AKW14] Pablo Daniel Azar, Robert Kleinberg, and S. Matthew Weinberg. Prophet inequalities with limited information. In Chandra Chekuri, editor, ACM-SIAM Symposium on Discrete Algorithus, SODA, pages 1358-1377, 2014.
[AM+06] Lawrence M Ausubel, Paul Milgrom, et al. The lovely but lonely vickrey auction. Combinatorial auctions, 17(3):22-25 2006.
[BBL03] Olivier Bousquet, Stéphane Boucheron, and Gábor Lugosi. Introduction to statistical learning theory. In Summer School on Machine Learning, pages 169-207. Springer, 2003.
[BDD+21] Maria-Florina Balcan, Dan DeBlasio, Travis Dick, Carl Kingsford, Tuomas Sandholm, and Ellen Vitercik. How much data sufficient learn high-performing algorithms? generalization guarantees for data-driven algorithm design. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC, page 919-932, 2021.
[CC23] José R. Correa and Andrés Cristi. A constant factor prophet inequality for online combinatorial auctions. In Proceedings of STOC, pages 686-697, 2023.
(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 incqualities via greedy-ordered selection. In ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 1298-1325, 2022.
[CDFS22] José Correa, Paul Dütting, Felix A. Fischer, and Kevin Schewior. Prophet inequalities for independent and identically distributed random variables from an unknown distribution. Math. Oper: Res., 47(2): 127(2):2277222 127--139, 2022.
[CFH*19] 19] Jose Correa, Patricio Foncea, Ruben Hocksma, Tim Oosterwijk, and Tjark Vredeveld. Recent developments in prophet inequalities. ACM SIGecom Exchanges, 17(1):61-70, 2019.
[CFPV19] José R. Correa, Patricio Foncea, Dana Pizarro, and Victor Verdugo. From pricing to prophets, and back! Oper. Res. Leut, 47(1):25-29, 2019.
[CHK07] Shuchi Chawla, Jason D. Hartline, and Robert Kleinberg. Algorithmic pricing via virtual valuations. In Proceedings of the 8th ACM Conference Electronic Commerce, EC '07, page 243-251, 2007.
[CMS10] Shuchi Chawla, David L. Malec, and Balasubramanian Sivan. The power of randomness in bayesian optimal mechanism design. Proceedings of the l 11th ACM Conference on Electronic Commerce, EC '10, 10, page 149-158, 2010.
[CR14] Richard Cole and Tim Roughgarden. The sample complexity of revenue maximization. In Symposium on Theory of Computing, STOC, pages 243-252. ACM, 2014.
[DK19] Paul Dütting and Thomas Kesselheim. Posted pricing and prophet inequalities with inaccurate priors. In Conference on Economics and Computation, EC, pages 111-129. ACM, 2019.
[DKL200] Paul Dütting, Thomas Kesselheim, and Brendan Lucier. An ollog log m) prophet inequality for subadditive combinatorial auctions. In Proceedings of FOCS, pages 306-317, 2020.

---

[DKI,+24] Paul Duetting. Thomas Kesselheim, Brendan Lucier, Rehecca Reiffenhauser, and Sahil Singla. Online combinatorial allocations and auctions with few samples. In 65th IEEE Annual Symposium on Foundations of Computer Science, FOCS, 2024.
[FGL15] Michal Feldman, Nick Gravin, and Brendan Lucier. Combinatorial auctions via posted prices. In Proceedings of SODA, 2015.
[Fre75] David A Freedman. On tail probabilities for martingales. the Annals of Probability, pages 100-118, 1975.
[GHTZ21] Chenghao Guo, Zhiyi Huang. Zhihao Gavin Tang, and Xinzhi Zhang. Generalizing com- plex hypotheses on product distributions: Auctions, prophet inequalities, and pandora's s problem. In Conference on Learning Theory, COLT, pages 2248 2288. PMLR, 2021.
[GHZ19] Chenghao Guo, Zhiyi Huang, and Xinzhi Zhang. Settling the sample complexity Lingle-paramete revenue maximization. In Proceedings of the 51st Annual ACM SIGACT Symposium Theory of Computing, STOC, pages 662-673 ACM, 2019.
[GKSW24] Khashayar Gatmiry, Thomas Kesselheim, Sahil Singla, and Yifan Wang. Bandit al- gorithms for prophet inequality and pandora's box. Proceedings of the thirty-sixth annual ACM-SIAM symposium on Discrete Algorithms, SODA, 2024.
[GM22] Xinyi Guan and Velibor V Mišić. Randomized policy optimization for optimal stopping. arXiv preprint arXiv:2203. 13446, 2022.
[GS02] Alison L Gibbs and Francis Edward Su. On choosing and bounding probability metrics. International statistical review, 70(3):419 4355,, 2002.
[Har13] Jason D Hartline. Mechanism design and approximation. Book draft. October, 122(1), 2013.
[HKS07] Mohammad Taghi Hajiaghayi, Robert D. Kleinberg, and Tuomas Sandholm. Automated online mechanism design and prophet inequalities. In Proceedings of the Twenty-Second AAAI Conference on Artificial Intelligence, pages 58-65. AAAI Press, 2007.
[HR09] Jason D. Hartline and Tim Roughgarden. Simple versus optimal mechanisms. In Proceedings 10th ACM Conference on Electronic Commerce (EC-2009), pages 225-234. ACM, 2009.
[ISW20] Nicole Immorlica, Sahil Singla, and Bo Waggoner. Prophet inequalities with linear correlations and augmentations. In Conference on Economics and Computation, EC, pages 159-185, 2020.
[KL03] Robert D. Kleinberg and Frank Thomson Leighton. The value of knowing a demand curve: Bounds on regret for online posted-price auctions. In 44th Symposium Foundations of Computer Science, FOCS, pages 594-605. IEEE Computer Society, 2003.
[KS77] U. Krengel and L. Sucheston. Semiamarts and finite values. Bulletin of the American Mathematical Society, 83:745-747, 1977.
[KS78] U. Krengel and L. Sucheston. On semiamarts, amarts, and processes with finite value. Advances in Probability and Related Topics, 4:197-266, 1978.
[LPS24] Vasilis Livanos, Kalen Patton, and Sahil Singla. Improved mechanisms and prophet inequalities for graphical dependencies. In Conference on Economics and Computation, EC, 2024.
[LSTW23] Renato Paes Leme, Balasubramanian Sivan, Yifeng Teng, and Pratik Worah. Pricing query complexity of revenue maximization. In Proceedings of the thirty-fourth annual ACM-SIAN symposium Discrete Algorithms, 2023.
12

---

[Luc17] Brendan Lucier. An economic view of prophet inequalities. ACM SIGecom Exchanges, 16(1))24-47, 2017.
[MR16] Jamie Morgenstern and Tim Roughgarden. Learning simple auctions. In Proceedings of the 29th Conference on Learning Theory, COLT 2016, volume 49 of JMLR Workshop and Conference Proceedings, pages 1298-1318. JMLR.org. 2016.
[Mye81] Roger B. Myerson. Optimal auction design. Math. Oper. Res., 6(1):58-73, 1981.
[Rou16] Tim Roughgarden. Twenty lectures algorithmic game theory. Cambridge University Press, 2016.
[RWW] Aviad Rubinstein, Jack Z. Wang, and S. Matthew Weinberg. Optimal single-choice prophet inequalities from samples. In Ith Innovations in Theoretical Computer Science Conference, ITCS, volume 151, pages 60:1-60:10.
[SW24) Sahil Singla and Yifan Wang. Bandit sequential posted pricing via half-concavity. In Conference on Economics and Computation, EC. ACM, 2024.
[Vic61] William Vickrey. Counterspeculation, auctions, and competitive sealed tenders. The Journal of finance, 16(1):8-37, 1961.
[Wai19] Martin Wainwright. High-dimensional statistics: A non-asymptotic viewpoint, vol- ume 48. Cambridge university press, 2019.
[XMX24] Yaqi Xie, Will Ma, and Linwei Xin. Vc theory for inventory policies. arXiv preprini arXiv:2404.1 11509, 2024.
13

---

A Appendix
A.1 Proof of Lemma
Proof. Now, consider the smallest j that fg rj. Again, we know such a j exists because
0 = Fa+1 2 7+1 = 0. We claim that that é 2r + min (E Y/i 0}.
Observe that there is nothing to be shown if j because then f 2 rf. So, let's consider the case that j > 1. We can now write í as a telescoping sum
A = E - f
Since it 2 rj. we have
f--1 nj + E (V (1) -5) = i ( + 1パj-1
E [mx (V)1,, + 7111 2 E mmxx + 775-1 rj-1 + 17-11
Observe that for + < we have irt1 r Therefore
f--f++1 = 3 E (1 -(41)) [V. - f++1) + 2B - +
= -
So, in combination with
2 + 7h- 2
r4 +.)
ri + Σ 1
A.2 Proof of Lemma 5
Ignoring constants, a slick proof of this lemma is via another upplication of Freedman's 's inequality, where we define a martingale X; Y; -?, ...... Y;-1l. and cut this martingale (stop) whenever the sum of conditional variances exceeds log(1 ( /8). This bounds the sum of conditional variances by log(1/5) /5), i.e. W, I o² == log(1/ (1/)) w.p. 1. Since the lemma is upper- upper-bounding bounding the probability of the event that Σ, X, > log(1/8), we can show that this probability is (5)) by substituting log(1/5) into Freedman's inequality.
Below give another, elementary proof of this lemma.
Y-11 2 - In (g). By Markov's inequality, we have Proof. Let Z = 1 Σ 1=1 E| Y
Pr
Σ l==1
Y S 1 and =
Pr Ze -E Y. 2 e-
Ze Ei Xi
Ze-Ii-11
Yi
.e
Now, we have
E
Ze
Σn Y.
=
E
7 Y
E Z Y
Y.
E Vi Vi , Vi.......-I]]
1=1
For every single conditional expectation, we obtain by convexity
E -e-
Y Y-1] < [Y, + Y,) Yi,..., Y-1]
= E (Y - 1) Yy....,, +1
I exp (E B Yi...., (....,y--i(e--1111111
Now, consider fixed realization of Yi....,
Yn. This realization fully determines Z. If Z = 0, then
E Z Y Yi....,
Y,
E e V.
Vr....,Y-11]- =
Otherwise, with Z = 1, we have
E Z Yi
Y,
ee Yi
Yi...., Yz-1] s exp
Σ E v Yy.... (e- -1) 5
14

---

So, have upper bound of regardless of the realization. Taking expectation, we get
8
E I Y1 Yn] II E E Yi...., Yi-
which implies Pr 1= Y, & and Z = s B Ze Disi vi] e S e = 6, completing the proof.
m
A.3 Proof of Lemma 6
Proof. Let [(x) = VC[C+ = (C2 + Cx) which a continuous function over a
-- We have fz(x ] + -x)-1/2C and f"(x) = - + Cx) C3/22 both of which exist over x E [-] C]. Applying Taylor's theorem around O, we get
= f(0) + (0)) + f'(m x² =C + 2 (C² + Ccy -/2
2 c h (C C( -))
C - &.
where y lies between and x and the inequality holds because y 2 3/4 C, completing the proof. n
A.4 Proof of Lemma
If < 0 then G(v, 2) = R so we may take any values of 4, ..l....,4... up such that / = l2
- 1. and ua = co.
For the rest of the proof, assume 0. First, consider the welfare objective. We show the lemma holds for ly and uy follows:
Define I be oo v(1)) 2 2, and otherwise be max v44),,.... (........(,)))))----... m-1)) where m is the smallest index such that v(Tz)m 2 2. (If v[ī)m < z for all m, set max(v(I;)))
Define Uj to be max(v(I,)).
Let G= = {pe R$ (v( 2 2} and G' - show that G G², we'll show C G" and G.
(0), ( x ... (u)-1, x (1y, ugl R=-J, To
Case G"). If G = @ we are done, so assume otherwise. Let G. Let be the interval such that the algorithm (using thresholds p) accepts a value in v(4,). Since a value in interval j was uj. Also, since value in the previous intervals were accepted, P. >> u, for all < j. Finally, we must have Pj > Lj. since otherwise the accepted value will be less than z. Thus p E G'.
accepted, Pj S max(v(L;))
Case 2 (G' G). Let p E G'. Then p E (n1, oc) x ... x (uy-1, 00) x (42, uy] x R- for some j. Since P; > u, for all i j. the algorithm using thresholds does not accept any value in the intervals i < j. Since Pj E (lj, uj). the definitions of Ij and uj imply that value in v(T)) is accepted, and this value is greater than or equal to Thus p G.
For revenue, the only difference is that we define 1, to be min(2, max(vv (uy still defined to be ma)(v(L,)) With these definitions of Ij and Uj, very similar analysis shows that G G" in the revenue case as well.
A.5 Proof of Theorem
We let S' C {1} US be subset of decision points such that price ग; can be freely chosen for all i E S'. For welfare maximization we require i + (L.....n) .n) S' for all S', which can achieved while ensuring |S'| 2 | J. Each decision point E S' has marginal value distribution(s) that could be "High" or "Low", separately for each decision point (i.e., all 2 s'l combinations possible). For welfare maximization, they are defined as
High: V; 1/2 with probability (w.p.) V4+ w.p. 1/2 + V441 w.p. 1/2 :;
Low: V, 1/2 w.p. 1, VL- 1 w.p. 1/2 E, V+1 0 w.p. 1/2 +
15

---

For revenue maximization, they are defined
High: Vi w.p. 1/2 + E, V, = 1/2 w.p. 1/2 E;
Low: V = 1 w.p. 1/2 - E, Vi = 1/2 w.p. 1/2 + E.
The overall distribution trajectories V is then correlated as follows. First, decision point S' is drawn uniformly at random. Then, Vi (as well as V4+1 in the case of welfare maximization) is drawn according the distributions above, depending whether decision point is High Low. All other buyer values are O on this trajectory.
Given this, only the prices for decision point i are relevant, which can without loss be restricted to {1/2, 1}. The policy should optimize т; for each E as if = i. For either welfare or revenue maximization, the constructions above can be checked satisfy the following properties:
1. Setting n; (and T441 in the case of welfare maximization) to I optimal for High and earns objective 1/2 in expectation; setting to 1/2 is optimal for Low and earns objective 1/2;
2. Setting the wrong price earns expected objective 1/2 for High and 1/2 for Low, incurring a loss E compared to optimal both cases.
3. The High and Low distributions have the same support and probabilities that differ by 2s.
We note that for welfare maximization, it does not matter whether x1+1 S, because the decision is on whether to accept buyer when V, 1/2.
Finally, a policy has additive error (?s) as long as it has constant probability of setting the wrong price for decision point. Due property 3. above, the policy needs ( relevant observations for given decision point to avoid setting the wrong price for it with constant probability. However, each sample contains relevant observation for given decision point only with probability 1/|S"),
so 22 (5)) samples are necessary for the number of relevant observations to be (2(32) with high probability. Because |S'| Z [لSكب this completes the proof of Theorem
16

---

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 the introduction clearly reflect our contributions.
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
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 other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We discuss in the related work section topics that are not in this paper's 's scope.
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 separate "Limitations" section in 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 a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might 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 faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a 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 an 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]
17

---

Justification:
We clearly state all the assumptions needed for theorems, and all the proofs are either in the body or the appendix.
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 or referenced in the statement of any theorems.
The proof' can either appear in the main paper or the supplemental material, but if 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 proof' 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 the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA]
Justification: This paper does not contain 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 a 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 it clear how to reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it 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 to 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?
18

---

Answer: [NA]
Justification:
This paper does not contain experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (kttps://niis.co cc/
Stgi:dds//ooeetttmmssiiioooooo/ ooliciyy for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" is 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 for more details.
/ //nips httpssccccbbllcgucuccccce wttpiiigggii/////eee Cooeee//doSSubmiiiec seriiisssonpooiiio
The authors should provide instructions on data access and preparation, including how to 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 as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is 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: This paper does not contain experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core 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, 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: This paper does not contain 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 the 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.
19

---

It is OK to report 1-sigma error bars, but 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 errors 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 enror rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures 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 execution) needed reproduce the experiments?
Question:
Answer: [NA]
Justification: This paper does not contain experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as 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:
The research in this paper conforms with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: There is societal impact of the work performed.
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 or 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.
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 improvement in the quality of generative models could be used to
20

---

generate deepfakes for disinformation. On the other hand, it is not needed to point 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 are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
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 poses no such risks.
Guidelines:
The answer NA means that the paper poses no 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 requiring that users adhere to 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. Licenses for existing assets
Question: 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?
Answer: [NA]
Justification: The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset 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 www.whtthcod...o.. 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 has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's ss creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and the documentation provided alongside the assets?
21

---

Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/codc/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing 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 as details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing 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 in the main paper.
According to the NeurlPS 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 equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on 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 NeurlPS Code of Ethics and the
and locations, and we expect authors to adhere
guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
22


Reviews:
[{"review_id": "ERFNfrGEsM", "reviewer": "Reviewer_mFS4", "summary": "The paper considers the problem of statistically estimating the optimal posted price mechanism for selling one item to multiple buyers. Here, it is assumed that the buyers appear sequentially, a price is presented to each of them and the sale is completed if the price posted to them is lower than their valuation. The mechanism aims to optimize one of two targets -- the welfare, defined here as the value of the bidder who wins the auction and revenue of the auctioneer which is the price paid by the winning bidder. It is assumed that the valuations of the bidders are drawn from a distribution and the paper aims to analyze the sample complexity of determining near-optimal posted prices for each of these settings where it is assumed that the learner receives iid samples from the bid distributions. Depending on the degree of dependence between the valuations of the bidders, the paper considers two settings -- firstly, the independent setting where the values are determined independently for each bidder and the dependent setting where the valuations are correlated across the bidders. \n\nIn the independent setting, it is shown that there exists a separation between the sample complexities of welfare and revenue maximization. They show that essentially $1 / \\epsilon^2$ samples suffice for welfare maximization whereas revenue maximization necessarily \\emph{requires} $\\Omega (n / \\epsilon^2)$ samples where $n$ is the number of bidders and $\\epsilon$ an additive error parameter. In this case, they obtain near-optimal characterization of the sample complexity while the upper and lower bounds from prior work are $n / \\epsilon^2$ and $1 / \\epsilon^2$ respectively. In contrast, when the bids are correlated, the paper shows that $\\Omega (n / \\epsilon^2)$ is \\emph{required} for both revenue and welfare maximization. To partially address this pessimistic bound, the paper also considers the setting where the class of possible posted prices is restricted. The particular restriction considered in the paper is by restricting the change points of the price schedule; that is, the price is only allowed to change at $k$ points in the sequence of prices. Here, it is shown that sample complexities independent of $n$ are obtainable and instead only depend on $k$. \n\nThe proof of the upper bound independent of $n$ for welfare maximization in the independent valuation setting is quite interesting. Essentially, the paper analyzes the dynamic programming algorithm for welfare maximization. Observing that the (welfare of the) posted prices have a closed-form solution in terms of the welfare of the next step, the paper proves that the sub-optimality of the posted prices may be bounded by a sum of error terms which satisfy a backwards martingale structure. The use of standard Martingale concentration bounds then yield the required bound. This proof is elegant and appears to be novel. Unfortunately, such martingale structure does not hold in the presence of dependencies between the valuations. Instead, they adopt a classical uniform convergence based approach and show that the statistical complexity may be controlled by the pseudo-dimension of the policy class.\n\nOverall, this is a nice paper that obtains nearly optimal statistical characterizations in several fundamental settings, making several interesting contributions. The proofs of the results, the welfare maximization for independent valuations in particular, are elegant and well-presented. My main concerns are with the assumptions underlying the learning problem. The paper assumes that one obtains independent samples from the \\emph{valuations} of the bidders. It is not clear how such samples are obtained -- it is not clear how one may obtain such samples in practice. More exposition on this point would be helpful. Furthermore, it would be helpful if the authors could comment on alternative settings circumventing the $\\Omega (n / \\epsilon^2)$ sample complexities incurred by the paper -- perhaps, by bounding the degree of dependence between the bidders?", "questions": "See main review", "limitations": "See main review", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "See main review", "weaknesses": "See main review", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful review and comments!\n\n- *The paper assumes that one obtains independent samples from the valuations of the bidders. It is not clear how such samples are obtained -- it is not clear how one may obtain such samples in practice. More exposition on this point would be helpful.*\n\nValuation samples can be obtained in practice through marketing research such as consumer surveys.  We would like to emphasize that this is a standard model; the long line of literature on auction design from samples (e.g. CR16, and other citations in our paper) and pricing from samples (e.g. Huang et al. 2015 below) all generally focus on valuation samples.  Although there are alternate models of information such as the purchase probability at a single price (e.g. Allouah et al. 2023 below), moment ambiguity sets (e.g. Wang et al. 2024 below), a difference is that these models do not consider the randomness caused by sampling.\n\nHuang, Zhiyi, Yishay Mansour, and Tim Roughgarden. \"Making the most of your samples.\" Proceedings of the Sixteenth ACM Conference on Economics and Computation. 2015.\n\nAllouah, Amine, Achraf Bahamou, and Omar Besbes. \"Optimal pricing with a single point.\" Management Science 69.10 (2023): 5866-5882.\n\nWang, Shixin, Shaoxuan Liu, and Jiawei Zhang. \"Minimax regret robust screening with moment information.\" Manufacturing & Service Operations Management 26.3 (2024): 992-1012.\n\n- *Furthermore, it would be helpful if the authors could comment on alternative settings circumventing the Ω(n/ϵ^2) sample complexities incurred by the paper -- perhaps, by bounding the degree of dependence between the bidders?*\n\nThank you for your question. This is indeed a fascinating area for future research. Recent works have explored welfare and revenue maximization under models with bounded correlations, such as linear correlations [Immorlica, Singla, and Waggoner, EC 2020] and graphical correlations of Markov Random Fields [Cai and Oikonomou, EC 2021]. It would be interesting to investigate the sample complexity within these frameworks, as these specific forms of correlations may allow one to circumvent the $\\Omega(n/\\epsilon^2)$ sample complexity lower bound from our Theorem 3.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "79nTjbMXkd", "reviewer": "Reviewer_gD9M", "summary": "The paper studies a setup of a series posted-price auctions that tries to sell a single item up to the first price acceptance. The authors seeking for the number of samples from buyer value distributions (sample complexity) to be able to setup near-optimal posted-price in the auctions. They consider two objectives (social welfare and revenue maximization) and different dependencies of buyer distributions (independent and correlated). The paper contributes proven both upper and lower on the sample complexity for the all four settings: the bounds are close up to logarithmic factors.", "questions": "-\tWhat are the factors (multiplicative constants) in the upper and lower bounds in Theorems 1-4?  What is behind O(...) and \\Omega(...)?", "limitations": "the authors adequately addressed the limitations", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "-\tClear math contribution\n\n-\tWell-structured proofs", "weaknesses": "-\tNo conclusions: the paper does not have a concluding discussion\n\n-\tNo experimental evidence: asymptotic bounds are clear measures for growing (shrinking) parameters, but, for practice, constant factors are more important. It would be nice to understand how they work in practical cases.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful review and comments!\n\n- *What are the factors (multiplicative constants) in the upper and lower bounds in Theorems 1-4? What is behind O(...) and \\Omega(...)?*\n\nWe emphasize that because we have normalized valuations to lie in [0,1], the $O(\\ldots)$ and $\\Omega(\\ldots)$ notation is not hiding any dependencies other than absolute numerical constants.\n\nWe would like to stress that optimizing the constants and coefficients in the sample complexity is not the main focus of our work.  We are interested in whether the sample complexity grows with $n$, which in our mind is a more first-order dependence.  Our main finding is that for product distributions, the sample complexity of welfare maximization does not grow with $n$, whereas the sample complexity of revenue maximization does.\n\n- *No conclusions: the paper does not have a concluding discussion*\n\nA rough, intuitive conclusion from this finding is that the dynamic programming thresholds computed from empirical distributions may be more prone to overfitting for revenue maximization than for welfare maximization.  Put another way, more samples need to be collected for the revenue maximization problem in order to avoid overfitting. We will add a concluding discussion to the next version of the paper.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "5FGgstLMGN", "reviewer": "Reviewer_U8bp", "summary": "This paper studies the problem of learning approximately revenue (welfare) optimal posted-prices single-item auctions from samples. The authors consider the setting where the valuation distributions of the agents are independent and the setting where the distributions are correlated. For both settings and both objectives they derive (almost) matching lower and upper bounds on the sample complexity of the learning task. All the results restrict the valuation distributions to be bounded in $[0,1]$ and consider additive approximations of the optimal posted-prices auctions.", "questions": "-What settings other than single-item auctions can the results be extended to?\n\n-For other types of distributions such as regular/MHR, can you derive optimal bounds?\n\n-For the bound on the pseudo-dimension, can't you use a direct argument like Morgenstern and Roughgarden (2016) for $t$-level auctions? I am not sure I understand the need to go through the dual class.\n\n-Can you comment a bit on the differences of your results/approach and [GHTZ'21]?", "limitations": "Addressed.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "-The problem of learning posted-prices auctions is of interest to the community.\n\n-The results derived are almost tight. \n\n-The technical results require some work (even though, conceptually, the approach relies heavily on prior work).", "weaknesses": "-The conceptual ideas of the work feel a bit incremental, given the long line of work in the setting of learning optimal auctions. \n\n-The results are limited to a very simple setting of single item auctions.\n\n-The running time of the algorithm for correlated distributions is exponential. \n\n-The presentation could be improved a bit. For example, I found the use of the word \"policy\" a bit confusing. Usually, this would imply some dynamic decision process, whereas here there is only a single-shot setting. It would be good to use different symbols for the revenue/welfare objectives. Line 61: instead of $V$ use something that denotes a set of samples. Line 104: what is the value-to-go? The proof sketch of Theorem 5 is a bit confusing. Lines 157-158 \"single item\" is repeated. The notation $r_i, \\hat{r}_i, r^*_i$ in Section 2.1 is a bit confusing. In Section 2.2 you can add a quick comment that choosing a price randomly will not help. In Line 23 \"know\" appears twice. In Line 173 drop \"a\". It might be useful to include the definition of the pseudo-dimension at least in the appendix.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful review and comments!\n\n- *The conceptual ideas of the work feel a bit incremental, given the long line of work in the setting of learning optimal auctions. The results are limited to a very simple setting of single item auctions.*\n\nWe view the simplicity of single item auctions as a major plus of our work, and we were surprised that the sample complexity of welfare/revenue maximization even in this simple setting had not been settled before. For example, our Theorem 1 entirely removes any dependency on the number of bidders in the sample complexity for product distributions (whereas the previous best known bound was linear). In terms of conceptual ideas, we want to highlight that a key difference compared to prior work is that we want to analyze the dynamic program corresponding to the optimal posted-price mechanism. Indeed, our Theorems 1 and 2 (for product distributions) crucially exploit the structure of the dynamic program for our specific problem.\n\n\n- *The running time of the algorithm for correlated distributions is exponential.*\n\nThe runtime is $(Tn(Tn)^{1+|\\mathcal{S}|})$, i.e. exponential in $|\\mathcal{S}|$.  This is because there are $1+|\\mathcal{S}|$ prices to decide, each of which can take $Tn$ possible values (one for each realized value in the $T$ samples of length $n$), and evaluating each combination of prices over each of the $T$ samples takes runtime linear in $n$.\n\nWe had in mind settings where $|\\mathcal{S}|$ is a small constant, in which case the runtime of Empirical Risk Minimization is polynomial in $T$ and $n$, and our sample complexity is also not growing with $n$.  This is well motivated in e.g. business settings where you can only change the price at the start of the month; in fact, there is substantial literature studying pricing policies where you cannot change the price too often (e.g. Cheung et al. 2017 below).\n\nCheung, Wang Chi, David Simchi-Levi, and He Wang. \"Dynamic pricing and demand learning with limited price experimentation.\" Operations Research 65.6 (2017): 1722-1731.\n\n- *For example, I found the use of the word \"policy\" a bit confusing. Usually, this would imply some dynamic decision process, whereas here there is only a single-shot setting.*\n\nThe terminology we adopt is that a policy is a specific prescription of the price to set at each time, and the goal of the (learning) algorithm is to decide on a policy from the samples.  Technically the policy here still needs to be dynamic — once the item is sold, it must change the prices to infinity.  So since the prophet inequality/dynamic pricing problems we study are intrinsically dynamic programming problems, we decided to use the word “policy” for generality, although we agree that we could have used a different word such as “price vector” instead.\n\n- *It would be good to use different symbols for the revenue/welfare objectives ... It might be useful to include the definition of the pseudo-dimension at least in the appendix.*\n\nThanks for catching these typos and suggestions on exposition!  We will definitely incorporate them in the next update.\n\nRegarding line 104, the value-to-go is the expected value of the (optimal) dynamic programming solution, conditional on the item still being unsold at time i.  It is referring to the quantity $r*_i$ in Section 2.2.\n\nRegarding the proof sketch of Theorem 5, sorry for the brevity.  We were trying to communicate the idea that statistically we need $\\Omega(1/\\epsilon^2)$ samples to get an $\\epsilon$-approximation; however, under our construction, only 1/(1+|S|) fraction of the samples would be relevant.  Therefore, in order to get $\\Omega(1/\\epsilon^2)$ relevant samples we now need $\\Omega((1+|S|)/\\epsilon^2)$ samples to begin with, as formally shown in Theorem 5.\n\n- *What settings other than single-item auctions can the results be extended to?*\n\nA natural next question is to extend our results to the problem of posted pricing for selling $k$ identical items (instead of one). We believe that many of our techniques can be extended to this more general setting, but we focus on the single item setting since prior to our work even that was not understood properly.\n\n\n- *For other types of distributions such as regular/MHR, can you derive optimal bounds?*\n\nThanks for the interesting question! Our upper bounds in Theorems 1 and 4 are already tight (up to constants) without needing to make additional assumptions such as MHR.  It is true that our lower bound constructions require distributions that are not MHR, and it is plausible to us that our lower bound construction from Theorem 2 (showing $\\Omega(n/\\epsilon^2)$ for product distributions) would not be possible when restricted to MHR.  Put another way, it is plausible that an $O(1/\\epsilon^2)$ upper bound is possible even for revenue maximization on product distributions under regular/MHR valuations, a question we leave to future work.\n\n- *For the bound on the pseudo-dimension, can't you use a direct argument like Morgenstern and Roughgarden (2016) for t-level auctions? I am not sure I understand the need to go through the dual class.*\n\nThank you for this question! It is indeed possible to directly bound the pseudo-dimension using first principles. In fact, that was our initial approach. However, we later realized we could leverage the existing result of Balcan et al., which resulted in a shorter and cleaner proof. This is why we opted to present it this way in our paper.\n\n- *Can you comment a bit on the differences of your results/approach and [GHTZ'21]?*\n\nThe primary differences are: (1) the bounds in [GHTZ'21] are only applicable to product distributions; (2) even within the context of welfare maximization for product distributions, our work removes the dependency on number of bidders $n$ in their $O(n/\\epsilon^2)$ bound, as shown in Theorem 1.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "6nR8dU74Im", "reviewer": "Reviewer_L1MB", "summary": "This paper studies the sample complexity of posted pricing problems. In such problems, a sequence of $n$ buyers arrive with valuations drawn from fixed distributions, and the goal is to post prices that maximize either the revenue or the welfare. In particular, the item is sold to the first buyer who accepts its proposed price. Notably, in the welfare maximizing case, this is the prophet inequality problem. \n\nGiven access to the distributions of the buyers’ valuations, it is possible to find the optimal online strategy via dynamic programming. This paper studies this problem when the access to the distribution is given via samples. The authors provide matching sample complexity bounds for the revenue and welfare maximization tasks, and for both the independent and correlated setting.", "questions": "None", "limitations": "No potential negative societal impact of this work", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "- Posted pricing is an important problem, vastly studied in both the EC and NeurIPS/ICML communities, with countless applications\n- Studying its sample complexity is well-motivated\n- the paper significantly improves on the state-of-the-art [Guo et al. COLT’21], removing the dependence on $n$\n- The paper is well-written", "weaknesses": "The paper is a strong NeurIPS submission", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful review!", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: Executive Summary

The paper examines the sample complexity of posted-price mechanisms, for both independent (product) distributions and correlated distributions, and both welfare and revenue objectives. The authors assume bounded distributions (normalized in [0,1]), and seek additive approximations to the best posted-price policy. More precisely, they seek approximations of the form "at least OPT - eps with probability at least 1-delta". 

The paper shows that for product distributions, the sample complexity for welfare maximization is O(1/eps^2) (omitting the dependence of delta), matching a known lower bound. Importantly, this is independent of n, the number of buyers. At the same time, for the revenue objective, they establish a lower bound of OmegaTilde(n/eps^2), and thus establish a separation to the welfare case.

The paper also considers the correlated case. For the welfare objective they give a lower bound of OmegaTilde(n/eps^2), matching a upper bound from prior work (and establishing a formal separation from the corresponding independent case). They complement this with postive results for welfare and revenue maximization, when the algorithm is constrained to change prices only a few times.

Recommendation

Overall, this is a very strong NeurIPS submission, which I am very happy to recommend for acceptance (as a spotlight if possible). This positive view of the paper is also reflected in the comments and suggestions from the reviewers, which I encourage the authors to take into account when preparing the final version.

Additional Requests

It appears to me that there is a closely related literature, which would be a natural reference point in the discussion. Namely, prior work on sample-based prophet inequalities, such as the following two papers (and follow-up work). I think the paper would benefit from discussing the differences between the approach taken in this paper, and the approach taken in this prior work (e.g. bounded distributions vs general distributions, prophet benchmark vs optimal online policy, etc.)

Correa, Duetting, Fischer, Schewior. Prophet Inequalities for I.I.D. Random Variables from an Unknown Distribution. EC'19
https://dblp.org/rec/conf/ec/CorreaDFS19.html?view=bibtex

Rubinstein, Weinberg, Wang. Optimal Single-Choice Prophet Inequalities from Samples. ITCS'20
https://dblp.org/rec/conf/innovations/RubinsteinWW20.html?view=bibtex

Another stream of related work that I feel deserves discussion is the one explored in the following paper, which explores the (non-)robustness of algorithms for the prophet inequality problem to inaccuracies in the distributions.

Duetting and Kesselheim. Prophet Inequalities with Inaccurate Priors. EC'19
https://dblp.org/rec/conf/ec/DuttingK19.html?view=bibtex
Decision: Accept (spotlight)