{"id":"e58a3cd9-6597-4bb6-8bfd-eae9f608fc7d","arxiv_id":"2506.02284","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Learning epsilon-optimal posted prices for a unit-demand buyer with independent values takes Theta-tilde(n/epsilon^2) samples, and O-tilde(n^2/epsilon^3) pricing queries suffice, with a matching ex-ante lower bound.","lead":"This paper asks how many samples or price queries a seller needs to learn near-optimal posted prices for a buyer who wants at most one item, assuming item values are independent. It proves the first tight sample-complexity bound for a multi-dimensional revenue maximization problem and initiates a multi-parameter pricing query model.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The sample-complexity lower-bound hard instance is not hard: a 0-sample pricing already achieves expected revenue within ε of optimal, so the Ω(n/ε²) necessity proof in Section A is invalid.","rationale":"The reader's weakest assumption was the Algorithm 2 query-estimator mismatch, which is real but a repairable presentation bug in a secondary theorem. The concern I identify is more load-bearing: it attacks the proof of Theorem 1.1's lower bound, the paper's headline tight sample-complexity claim. On the stated hard instance, the total revenue that can be lost by not knowing the orientation of the qn pairs is bounded by the total undecided mass, ε, and the per-pair constant in Lemma A.3 is only 0.2, so correcting all pairs gains <0.08ε. Thus a 0-sample algorithm that fixes any set of qn items at price 0.5 (the rest at 1) is already ε-optimal in expectation for every realization of the hard instance, contradicting the claimed Ω(n/ε²) sample requirement. The theorem may still be true with a modified construction (e.g., a larger perturbation constant), but the proof as written does not establish it. This warrants a major revision of Section A, so the reader's CONDITIONAL verdict remains appropriate; I therefore keep the verdict UNCHANGED while disagreeing with the reader's identification of the weakest point.","tokens_in":36551,"tokens_out":46885,"duration_ms":504591,"concrete_test":"Analytically evaluate the 0-sample pricing p_S that prices a fixed set S of qn items at 0.5 and all others at 1 on the family of Definition A.2, using the coupling of Lemma A.3 to separate the exchangeable common mass from the undecided zones (total mass ε). Compute sup over orientations of Rev_OPT − Rev(p_S); if this supremum is < ε, the construction cannot prove Theorem A.1 and the lower bound needs a different instance (e.g., per-pair loss cε/n with c·q > 1). A numerical check with n=10^4, ε=10^{-3}, q=ln4−1 would confirm the gap immediately.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The necessity side of the headline Θ(n/ε²) result rests on the hard instance in Section A. In Definition A.2 every item is built from a common distribution (0 w.p. 1−1.5/n, 0.5 w.p. 1/n, 1 w.p. (0.5−ε)/n) plus an 'undecided' ε/n zone that is 1 for G and 0.5 for G_L. Lemma A.3 shows that correcting one misoriented pair increases revenue by at most 0.2ε/n; with qn≤0.39n pairs the total possible gain from correcting all pairs is <0.08ε. Hence the pricing that sets a fixed set of qn items to 0.5 and the rest to 1 — a 0-sample strategy — has expected revenue within <ε of optimal for every orientation, because the common part is exchangeable and the undecided part has total mass ε. The instance is therefore not hard for ε-additive approximation. The proof's inference from 'algorithm fails to identify Ω(n) orientations' (Lemma A.4) to 'revenue loss Ω(ε)' (Theorem A.1) is invalid: the per-pair loss constant is too small, and price vectors that put equal prices on both items in a pair are not covered by Lemma A.3.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies learning optimal item prices for a unit-demand buyer with independent item values, under sample access and under single-item pricing-query access. It claims a nearly tight sample complexity of Θ̃(n/ε²) for learning an ε-optimal posted-price mechanism (Theorem 1.1), an Õ(n²/ε³) pricing-query upper bound (Theorem 1.2), and an Ω(n²/ε³) query lower bound for the ex-ante relaxation (Theorem 1.3). The sample upper bound is proved through an approximate strong revenue-monotonicity lemma combined with a PTAS for the empirical distribution. The sample lower bound uses a paired G/GL hard instance. The query upper bound uses a non-uniform threshold-estimation algorithm whose correctness is delegated to several claims.","tokens_in":36779,"tokens_out":14615,"duration_ms":168087,"significance":"If the sample upper bound is correct, it is a substantial improvement over the previous Õ(n²/ε²) and Õ(n/ε⁴) bounds, and the approximate strong-monotonicity lemma in Section 3.3 is a valuable technical contribution. The query upper bound also introduces an interesting non-uniform query-allocation idea. However, the paper's headline tightness claim rests on a lower-bound construction that does not establish the claimed Ω(n/ε²) bound, and the query upper-bound algorithm as written uses estimators that the stated query model does not provide. The results are therefore not currently established at the claimed level.","major_comments":[{"comment":"Definition A.2, Lemma A.3, and Theorem A.1: the hard instance is not hard for ε-additive approximation. By Lemma A.3, mispricing one pair costs at most 0.2 ε/n. Since the construction has only q* n pairs with q* ≈ 0.386, even mispricing every pair costs less than 0.08 ε. In particular, the fixed 0-sample price vector that sets the first item of each pair to 0.5 and all other items to 1 is within 0.08 ε of optimal for every orientation of the pairs. Therefore no learning algorithm can be forced to incur Ω(ε) revenue loss on this instance. Lemma A.4's conclusion that an algorithm must misorient Ω(n) pairs does not imply a revenue loss Ω(ε), so the proof of Theorem A.1—and hence the necessity side of Theorem 1.1—is unsupported.","section":"Section A"},{"comment":"Algorithm 2, lines 8 and 15, together with Claim 4.5: the estimator F̂_G(m ε²) = (1/N) Σ 1[X_t ≤ m ε²] cannot be formed from the stated pricing queries, which reveal only 1[v_i ≥ p], not 1[v_i ≤ p]. The same issue affects F_H(k_{j+1} ε²) on line 15. A repair is possible in principle by querying the next grid point (m+1)ε² and complementing, and by adjusting the binary-search condition accordingly, but the manuscript never states this conversion or re-analyzes the binary search under it. Since Claim 4.5 is the concentration guarantee behind Lemma 4.4 and Theorem 4.1, the Õ(n²/ε³) query upper bound is not proved as written.","section":"Section 4.3"},{"comment":"The ex-ante query lower bound is presented as evidence for tightness of Theorem 1.2, but Theorem 1.3 is proved only for the ex-ante relaxation. The paper explicitly conjectures that the original problem has the same bound. This is not a technical error, but it means the paper does not provide a query-complexity lower bound for the problem stated in Theorem 1.2; the abstract and introduction should be read accordingly.","section":"Section B"}],"minor_comments":[{"comment":"The derivation of (17) appears to lose a factor of 2. From |F_{D̃_i}(v) − F_{E_i}(v)| ≤ 2ε(1 − F_{D̃_i}(v)) and 1 − F_{D̃_i}(v) ≤ 2(1 − F_{E_i}(v)), one obtains 4ε(1 − F_{E_i}(v)), not 2ε(1 − F_{E_i}(v)). The asymptotic bound is unaffected because constants are absorbed, but the displayed inequality should be corrected.","section":"Section 4.2, Eq. (17)"},{"comment":"The symbol G is used both for the single-dimensional distribution in (21) and for the product distribution in the base instance. This makes Definition A.2 and Lemma A.3 hard to read; a distinct notation for the single-dimensional law would help.","section":"Section A"},{"comment":"The proof contains the apparent typo 'FtDj'; this should be F_{D̃_j} or the corresponding discretized CDF. The notation for the discretized distribution should be used consistently.","section":"Lemma D.1 proof"},{"comment":"The sentence 'We prove this via introduction' should read 'We prove this via induction'.","section":"Claim 3.8 proof"},{"comment":"Line 16 sets F_H(i ε²) = F_H(k_j ε²) for all intermediate grid points, creating a flat CDF segment. The proof should clarify how this is consistent with the right-continuous CDF convention used elsewhere in the paper.","section":"Algorithm 2"}],"recommendation":"reject","confidential_remarks":"The sample lower bound is not a minor gap: the total revenue effect of all O(n) perturbed pairs is O(ε), so a zero-sample pricing is already ε-optimal. Replacing Theorem A.1 with a valid construction would require a substantially new lower-bound argument. The query upper-bound repair (estimating lower-tail probabilities via complements) appears achievable, but it must be written and analyzed before the Õ(n²/ε³) bound can be accepted."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The main result that holds up is the sample-complexity upper bound: O-tilde(n/ε²) for learning optimal posted prices for a unit-demand buyer, improving on the prior O-tilde(n²/ε²) and O-tilde(n/ε⁴) bounds. The approximate strong revenue monotonicity lemma for unit-demand is the core new idea, and that part of the proof looks sound. The non-uniform pricing query algorithm is also a genuine contribution, and the multi-parameter query model is a reasonable first step.\n\nThe trouble is the lower bound in Section A. The hard instance is not hard. A learner who prices the first item of every pair at 0.5 and everything else at 1, using zero samples, gets within about 0.08ε of optimal in expectation over the random orientation. Lemma A.3's per-pair swap gain is only 0.2ε/n, so even if every pair is misoriented, the total loss is below ε. The leap from \"fails to identify Ω(n) orientations\" to \"revenue loss Ω(ε)\" does not work. The Θ(n/ε²) statement in Theorem 1.1 and the abstract is not established by this paper.\n\nThere are also smaller fixable issues. Algorithm 2 uses events 1[X ≤ v] to estimate the CDF, but the query model only releases 1[X ≥ p]; the natural repair is to query the next grid point and complement, but that is not in the text. Inequality (17) in the proof of Theorem 4.1 also loses a constant factor, giving 2ε instead of 4ε. Neither is fatal to the upper bound, but both need editing.\n\nIf you work on sample/query complexity of multi-dimensional mechanism design, this is worth reading for the upper-bound techniques. But the headline tightness claim is currently unsupported. I would still send it to a serious referee—the upper bound and the monotonicity lemma are valuable—but the authors need to fix or remove the lower bound before it is accepted.","headline":"The sample-complexity upper bound is real, but the matching lower bound is invalid: the hard instance is within ε of optimal for a zero-sample strategy, so the Θ(n/ε²) claim doesn't stand.","tokens_in":37348,"tokens_out":10380,"would_cite":true,"duration_ms":104583,"reading_group":"maybe","serious_thinker":"no","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["91B26"],"pacs":[],"model":"deepseek-v4-flash","headline":"For any product distribution over $n$ independent item values, roughly $n/\\epsilon^2$ samples are both necessary and sufficient to learn posted prices whose revenue is within $\\epsilon$ of the optimal item pricing; the paper also gives…","keywords":["posted pricing","unit-demand buyer","sample complexity","pricing queries","threshold queries","revenue maximization","product distributions","ex-ante relaxation"],"falsifier":"Run Algorithm 2 on a distribution with a point mass at a grid point, e.g. $\\Pr[X=0.5]=1/n$, using only the stated signal $\\mathbf{1}[v\\ge p]$. The estimator in Line 8 counts $\\mathbf{1}[X_t\\le m\\epsilon^2]$, but the query at threshold $m\\epsilon^2$ reveals $\\mathbf{1}[X_t\\ge m\\epsilon^2]$; to estimate the CDF one must query the next grid point and complement. If the resulting estimator has bias larger than $0.1(\\epsilon(1-F_G(v))+\\epsilon/n)$ at that point, Claim 4.5 fails and the $\\tilde{O}(n^2/\\epsilon^3)$ upper bound is not established.","tokens_in":36326,"feed_emoji":"🏷️","tokens_out":13555,"duration_ms":142520,"temperature":0.7,"pith_summary":"This paper asks how much information a seller needs before it can price $n$ independent-valued items for a buyer who will take at most one. Its central claim is that the sample complexity is tightly $\\tilde{\\Theta}(n/\\epsilon^2)$: that many full value-vector samples are sufficient to reach expected revenue within $\\epsilon$ of the optimal item pricing, and that any algorithm needs that many for some product distribution. The same problem is then studied under a weaker pricing-query model, where each round reveals only whether one item's sampled value exceeded the asked price; here the paper proves an $\\tilde{O}(n^2/\\epsilon^3)$ upper bound and a matching $\\Omega(n^2/\\epsilon^3)$ lower bound for the ex-ante relaxation, conjecturing tightness for the original problem. A reader should care because this is the first tight sample-complexity result for a revenue-maximization problem in a multi-parameter setting, closing a gap left by earlier polynomial and pseudo-dimension bounds.","feed_headline":"Sample complexity of item pricing is now tight","feed_subtitle":"A unit-demand seller can reach epsilon-optimal posted prices with about n/epsilon^2 samples, and no algorithm needs fewer.","key_machinery":"The load-bearing object is the approximate strong-revenue-monotonicity lemma. It bounds how much revenue of a fixed price vector can drop when each item's distribution is replaced by a stochastically smaller distribution whose CDFs are close, by decomposing expected revenue item by item and controlling the change in the probability that a given item is the buyer's favorite; the key quantity is $S_{G_i}(\\theta)$, the total tail mass of items other than $i$ that can outbid item $i$ at utility level $\\theta$, and the proof splits into cases where this mass is large (win probability is exponentially small) and small (the win-probability difference is controlled by the CDF closeness). For the query upper bound, the additional machinery is a non-uniform key-threshold algorithm: per item, it binary-searches for the $O(1/\\epsilon)$ grid points where the CDF estimate needs refreshing, estimating each with $n/\\epsilon^2$ threshold queries, and uses monotonicity to fill in the grid points in between.","core_discovery":"On the paper's own terms, the discovery is that the unit-demand pricing problem is only approximately strongly revenue-monotone, and that this weaker property is enough to yield the same sample complexity as full strong monotonicity. Specifically, whenever two product distributions on $[0,1]^n$ have coordinate CDFs close in the sense $|F_{D_i}(v)-F_{E_i}(v)| \\le \\sqrt{F_{D_i}(v)(1-F_{D_i}(v))\\cdot 2\\Gamma} + \\Gamma$, the revenue of any fixed price vector under one distribution is within $O(\\log(1/\\Gamma)(\\Gamma n + \\sqrt{\\log(1/\\Gamma)\\Gamma n}))$ of its revenue under the other. From this the paper derives the $\\tilde{\\Theta}(n/\\epsilon^2)$ sample bound. For threshold queries it shows that a non-uniform algorithm estimating the CDF only at $O(1/\\epsilon)$ carefully chosen quantiles per item achieves $\\tilde{O}(n^2/\\epsilon^3)$ queries; a matching $\\Omega(n^2/\\epsilon^3)$ lower bound is proved for the ex-ante relaxation, where the buyer's choice constraint is replaced by an expected-quantity constraint.","pith_inferences":["The paper's query upper bound, as written, uses estimators that count 'value at or below threshold', while the stated query model releases 'value above or equal to price'; a reader implementing Algorithm 2 would need to repair this by querying adjacent grid points and complementing. If such a repair is possible, the $\\tilde{O}(n^2/\\epsilon^3)$ bound likely stands; if not, the upper bound collapses","The approximate strong-revenue-monotonicity proof is not obviously limited to item pricing; the same favorite-item decomposition works whenever a single buyer chooses among $n$ options with independent values, so the sample bound may extend to other simple mechanisms such as sequential posted pricing.","The paper observes that a query model revealing all $n$ threshold signals per round would have complexity $\\tilde{O}(n/\\epsilon^3)$; formalizing this gap between per-item and simultaneous query models would clarify which part of the $n^2$ factor comes from the per-item signal restriction."],"forward_implications":["A seller with access to roughly $n/\\epsilon^2$ independent value-vector samples can set posted prices that lose at most $\\epsilon$ of the optimal item-pricing revenue, with failure probability $1-\\delta$.","No sample-based algorithm can do meaningfully better: the lower-bound construction forces any learner to identify a constant fraction of slightly degraded items, and each misidentified item costs $\\Omega(\\epsilon/n)$ revenue.","Under the weaker threshold-query model, $\\tilde{O}(n^2/\\epsilon^3)$ binary affordability queries are enough to reach the same $\\epsilon$-optimality guarantee, and the ex-ante relaxation requires $\\Omega(n^2/\\epsilon^3)$ queries, so the query complexity of the relaxation is tight.","Because the results hold for arbitrary product distributions on $[0,1]^n$, they settle the sample complexity of item pricing for unit-demand buyers, a problem previously known only through non-tight upper bounds."],"supporting_citations":[{"why":"Supplies the strong-revenue-monotonicity framework and the multi-dimensional Bernstein concentration lemma (Lemma 2.3) used in the sample upper bound.","marker":"[GHTZ21]"},{"why":"Introduces approximate strong revenue monotonicity, the concept the paper proves for unit-demand buyers.","marker":"[CHMY23]"},{"why":"Provides the additive PTAS used to convert a near-optimal pricing on the empirical distribution into a near-optimal pricing on the true distribution.","marker":"[CD15]"},{"why":"Gives the earlier $\\tilde{O}(n^2/\\epsilon^2)$ pseudo-dimension sample bound that Theorem 1.1 improves.","marker":"[MR16]"},{"why":"Earlier learning multi-item auctions result whose pseudo-dimension bound is tightened by Theorem 1.1.","marker":"[CD17]"},{"why":"Defines the pricing/threshold query model and gives the single-dimensional $\\Omega(\\epsilon^{-3})$ lower bound that motivates the multi-dimensional query lower bound.","marker":"[PLSTW23b]"},{"why":"Source of the discretization lemma (Lemma 4.2) that converts a continuous distribution to a grid of step $\\epsilon^2$ with $O(\\epsilon)$ revenue loss.","marker":"[BBHM05]"},{"why":"Co-source of the same discretization and epsilon-IC-to-IC reduction used in the query upper bound.","marker":"[CHK07]"},{"why":"Supplies the Hellinger-distance product formula and total-variation bound used in both lower-bound proofs.","marker":"[GS02]"}],"fun_headline_variants":["Near-tight sample and query bounds for unit-demand pricing","Learning optimal prices for a unit-demand buyer: near-tight bounds","Near-tight complexity for learning unit-demand posted prices","Unit-demand pricing: sample and query complexity nearly optimized"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The main unstated premise is that a learner who only sees whether a sampled value is above a proposed price can estimate the probability that a value is below a threshold, by flipping the answer and querying neighboring prices; the paper's algorithm uses such below-threshold counts without explaining the conversion.","fun_headline_variants_meta":{"raw":{"variants":["Near-tight sample and query bounds for unit-demand pricing","Learning optimal prices for a unit-demand buyer: near-tight bounds","Near-tight complexity for learning unit-demand posted prices","Unit-demand pricing: sample and query complexity nearly optimized"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000765,"raw_usage":{"total_tokens":3363,"prompt_tokens":886,"completion_tokens":2477,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":502,"completion_tokens_details":{"reasoning_tokens":2410}},"tokens_in":502,"tokens_out":2477,"duration_ms":20108,"temperature":1.0,"reasoning_tokens":2410,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T11:30:59.986458+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run Algorithm 2 on a distribution with a point mass at a grid point, e.g. $\\Pr[X=0.5]=1/n$, using only the stated signal $\\mathbf{1}[v\\ge p]$. The estimator in Line 8 counts $\\mathbf{1}[X_t\\le m\\epsilon^2]$, but the query at threshold $m\\epsilon^2$ reveals $\\mathbf{1}[X_t\\ge m\\epsilon^2]$; to estimate the CDF one must query the next grid point and complement. If the resulting estimator has bias larger than $0.1(\\epsilon(1-F_G(v))+\\epsilon/n)$ at that point, Claim 4.5 fails and the $\\tilde{O}(n^2/\\epsilon^3)$ upper bound is not established.","supporting_citations":[],"review_version":1}