Pith. sign in

REVIEW 3 major objections 5 minor 56 references

Learning Optimal Posted Prices for a Unit-Demand Buyer

T0 review · 3 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read 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…

desk verdict 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. read the letter →

arxiv 2506.02284 v1 pith:42ZPCXEG submitted 2025-06-02 cs.GT cs.DScs.LG

Yifeng Teng , Yifan Wang This is my paper
classification cs.GTcs.DScs.LG MSC 91B26
keywords postedpricingunit-demandbuyersamplecomplexityqueriesthresholdrevenuemaximizationproductdistributionsex-anterelaxation
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

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.

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 (3)
  1. [Section A] 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.
  2. [Section 4.3] 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.
  3. [Section B] 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.
minor comments (5)
  1. [Section 4.2, Eq. (17)] 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.
  2. [Section A] 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.
  3. [Lemma D.1 proof] 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.
  4. [Claim 3.8 proof] The sentence 'We prove this via introduction' should read 'We prove this via induction'.
  5. [Algorithm 2] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: upper bounds follow from the paper's new approximate strong-revenue-monotonicity lemma plus external concentration results; lower bounds use explicit hard distributions analyzed via Hellinger distance; self-citations like [PLSTW23b] are motivational, not load-bearing.

full rationale

Walking the derivation chain, no load-bearing step reduces to its own inputs. For the sample upper bound (Theorem 3.1), the new content is Lemma 3.6, the approximate strong revenue monotonicity of BUPP, proved as a standalone inequality: the proof decomposes Rev_G(p) − Rev_H(p) into per-item win-probability differences (Equations 7–10), shows the CDF-part (8) is non-positive by integration by parts, and bounds the win-probability part (9) via elementary Claims 3.7–3.9. The CDF-closeness hypothesis feeding this lemma comes from the external concentration Lemma 2.3 [GHTZ21] and the external PTAS [CD15]; the final error bound follows from a standard large-constant choice of N, with no fitted parameter renamed as a prediction. For the query upper bound (Theorem 4.1), Nisan's discretization is Lemma 4.2 (proved in Appendix D.1), the revenue-Lipschitz step is Lemma 4.3 / Lemma D.3 (proved by the same Q_i(θ) machinery), and Algorithm 2's adaptive estimation is analyzed via Bernstein concentration (Claim 4.5) and a multiplicative growth argument bounding the rounds by O(ε^{-1} log(n/ε)). The reader-flagged gap that Algorithm 2 estimates F̂_G(mε²) = (1/N)Σ1[X_t ≤ mε²] while the query model releases 1[X_t ≥ p] is an implementation/correctness issue (the estimator can be implemented by complementing a query at the adjacent grid point), not a circular reduction. The lower bounds (Theorems A.1 and B.1) use explicit hard distributions (G vs G_L; H with a shifted point mass), with hardness argued rather than assumed: Lemma A.3 is a coupling proof over an 'undecided zone', Lemma A.4 computes Hellinger distance between orientations, Lemma B.2 derives the per-item gap from Equation (23), and Lemma B.3 computes Bernoulli Hellinger distances per threshold. The skeptic's objection (total per-pair revenue at stake ≈0.078ε < ε, and equal-price vectors fall outside Lemma A.3's swap analysis) is a quantitative correctness challenge to the hard instance, not circularity: the lower bound is never assumed by definition or self-citation, and if the gap analysis fails, the bound fails on its merits.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The paper introduces no fitted constants. All constants (C, C', C1, C2) are universal and chosen large to satisfy inequalities; they are not tuned to data. No new entities such as particles, forces, or conserved quantities are postulated. The only modeling commitments are the standard Bayesian mechanism design assumptions listed above.

assumptions (5)
  • domain assumption Buyer values are drawn from a product distribution D = D_1 x ... x D_n with support [0,1]^n.
    Core model stated in Section 2.1; all theorems are conditional on this independence assumption.
  • domain assumption Unit-demand buyer with quasi-linear utility chooses the item maximizing v_i - p_i, with ties broken by highest price.
    Behavioral model in Section 2.1; used throughout revenue calculations.
  • domain assumption Each pricing query draws a fresh independent sample v_i ~ D_i and reveals 1[v_i >= p].
    Query model defined in Section 2.2 and used by Algorithm 2 and lower bounds.
  • standard math Bernstein's inequality, Hellinger-to-TV bounds, and GHTZ21 concentration lemmas (Lemma 2.3, Lemma 3.4).
    Used to bound empirical CDF errors and indistinguishability; cited from [GS02, GHTZ21].
  • domain assumption Additive PTAS for BUPP exists and runs in O(n log^3(1/epsilon)/epsilon^4) time (Theorem 2.1 of [CD15]).
    Used as subroutine on empirical distributions; correctness is cited, not reproved.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Learning Optimal Posted Prices for a Unit-Demand Buyer." pith.science (2026). https://pith.science/paper/42ZPCXEG

@misc{pith2026250602284,
  author       = {Pith},
  title        = {Pith review of: Learning Optimal Posted Prices for a Unit-Demand Buyer},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/42ZPCXEG}},
  note         = {Machine review of arXiv:2506.02284}
}
read the original abstract

We study the problem of learning the optimal item pricing for a unit-demand buyer with independent item values, and the learner has query access to the buyer's value distributions. We consider two common query models in the literature: the sample access model where the learner can obtain a sample of each item value, and the pricing query model where the learner can set a price for an item and obtain a binary signal on whether the sampled value of the item is greater than our proposed price. In this work, we give nearly tight sample complexity and pricing query complexity of the unit-demand pricing problem.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

56 extracted references · 54 canonical work pages

  1. [1]

    Hartline, and Yishay Mansour

    Maria - Florina Balcan, Avrim Blum, Jason D. Hartline, and Yishay Mansour. Mechanism design via machine learning. In 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 23-25 October 2005, Pittsburgh, PA, USA, Proceedings , pages 605--614. IEEE Computer Society, 2005

    work page 2005

  2. [2]

    Multi-item mechanisms without item-independence: Learnability via robustness

    Johannes Brustle, Yang Cai, and Constantinos Daskalakis. Multi-item mechanisms without item-independence: Learnability via robustness. In Proceedings of the 21st ACM Conference on Economics and Computation , pages 715--761, 2020

    work page 2020

  3. [3]

    Pricing lotteries

    Patrick Briest, Shuchi Chawla, Robert Kleinberg, and S Matthew Weinberg. Pricing lotteries. Journal of Economic Theory , 156:144--174, 2015

    work page 2015

  4. [4]

    How much data is sufficient to learn high-performing algorithms? generalization guarantees for data-driven algorithm design

    Maria-Florina Balcan, Dan DeBlasio, Travis Dick, Carl Kingsford, Tuomas Sandholm, and Ellen Vitercik. How much data is sufficient to learn high-performing algorithms? generalization guarantees for data-driven algorithm design. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing , pages 919--932, 2021

    work page 2021

  5. [5]

    A simple and approximately optimal mechanism for an additive buyer

    Moshe Babaioff, Nicole Immorlica, Brendan Lucier, and S Matthew Weinberg. A simple and approximately optimal mechanism for an additive buyer. Journal of the ACM (JACM) , 67(4):1--40, 2020

    work page 2020

  6. [6]

    Sample complexity of automated mechanism design

    Maria-Florina F Balcan, Tuomas Sandholm, and Ellen Vitercik. Sample complexity of automated mechanism design. Advances in Neural Information Processing Systems , 29, 2016

    work page 2016

  7. [7]

    Generalization guarantees for multi-item profit maximization: Pricing, auctions, and randomized mechanisms

    Maria-Florina Balcan, Tuomas Sandholm, and Ellen Vitercik. Generalization guarantees for multi-item profit maximization: Pricing, auctions, and randomized mechanisms. Operations Research , 2023

    work page 2023

  8. [8]

    A constant factor prophet inequality for online combinatorial auctions

    Jos \'e Correa and Andr \'e s Cristi. A constant factor prophet inequality for online combinatorial auctions. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing , pages 686--697, 2023

    work page 2023

Show all 56 references
  1. [9]

    Simultaneous auctions are approximately revenue-optimal for subadditive bidders

    Yang Cai, Ziyun Chen, and Jinzhao Wu. Simultaneous auctions are approximately revenue-optimal for subadditive bidders. In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS) , pages 134--147. IEEE, 2023

    2023

  2. [10]

    Extreme value theorems for optimal multidimensional pricing

    Yang Cai and Constantinos Daskalakis. Extreme value theorems for optimal multidimensional pricing. Games and Economic Behavior , 92:266--305, 2015

    2015

  3. [11]

    Learning multi-item auctions with (or without) samples

    Yang Cai and Constantinos Daskalakis. Learning multi-item auctions with (or without) samples. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS) , pages 516--527. IEEE, 2017

    2017

  4. [12]

    On the complexity of optimal lottery pricing and randomized mechanisms

    Xi Chen, Ilias Diakonikolas, Anthi Orfanou, Dimitris Paparas, Xiaorui Sun, and Mihalis Yannakakis. On the complexity of optimal lottery pricing and randomized mechanisms. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science , pages 1464--1479. IEEE, 2015

    2015

  5. [13]

    The complexity of optimal multidimensional pricing for a unit-demand buyer

    Xi Chen, Ilias Diakonikolas, Dimitris Paparas, Xiaorui Sun, and Mihalis Yannakakis. The complexity of optimal multidimensional pricing for a unit-demand buyer. Games and Economic Behavior , 110:139--164, 2018

    2018

  6. [14]

    Devanur, and S

    Yang Cai, Nikhil R. Devanur, and S. Matthew Weinberg. A duality-based unified approach to bayesian mechanism design. SIAM Journal on Computing , 50(3):STOC16--160--STOC16--200, 2021

    2021

  7. [15]

    Hartline, and Robert D

    Shuchi Chawla, Jason D. Hartline, and Robert D. Kleinberg. Algorithmic pricing via virtual valuations. In Jeffrey K. MacKie - Mason, David C. Parkes, and Paul Resnick, editors, Proceedings 8th ACM Conference on Electronic Commerce (EC-2007), San Diego, California, USA, June 11...

    2007

  8. [16]

    Multi-parameter mechanism design and sequential posted pricing

    Shuchi Chawla, Jason D Hartline, David L Malec, and Balasubramanian Sivan. Multi-parameter mechanism design and sequential posted pricing. In Proceedings of the forty-second ACM symposium on Theory of computing , pages 311--320, 2010

    2010

  9. [17]

    Strong revenue (non-)monotonicity of single-parameter auctions

    Ziyun Chen, Zhiyi Huang, Dorsa Majdi, and Zipeng Yan. Strong revenue (non-)monotonicity of single-parameter auctions. In Kevin Leyton - Brown, Jason D. Hartline, and Larry Samuelson, editors, Proceedings of the 24th ACM Conference on Economics and Computation, EC 2023, London,...

    2023

  10. [18]

    Mechanism design for subadditive agents via an ex ante relaxation

    Shuchi Chawla and J Benjamin Miller. Mechanism design for subadditive agents via an ex ante relaxation. In Proceedings of the 2016 ACM Conference on Economics and Computation , pages 579--596, 2016

    2016

  11. [19]

    The power of randomness in bayesian optimal mechanism design

    Shuchi Chawla, David Malec, and Balasubramanian Sivan. The power of randomness in bayesian optimal mechanism design. Games and Economic Behavior , 91:297--317, 2015

    2015

  12. [20]

    Computing simple mechanisms: Lift-and-round over marginal reduced forms

    Yang Cai, Argyris Oikonomou, and Mingfei Zhao. Computing simple mechanisms: Lift-and-round over marginal reduced forms. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing , pages 704--717, 2022

    2022

  13. [21]

    The sample complexity of revenue maximization

    Richard Cole and Tim Roughgarden. The sample complexity of revenue maximization. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing , pages 243--252, 2014

    2014

  14. [22]

    Menu-size complexity and revenue continuity of buy-many mechanisms

    Shuchi Chawla, Yifeng Teng, and Christos Tzamos. Menu-size complexity and revenue continuity of buy-many mechanisms. In Proceedings of the 21st ACM Conference on Economics and Computation , pages 475--476, 2020

    2020

  15. [23]

    Optimal pricing is hard

    Constantinos Daskalakis, Alan Deckelbaum, and Christos Tzamos. Optimal pricing is hard. In International Workshop on Internet and Network Economics , pages 298--308. Springer, 2012

    2012

  16. [24]

    Mechanism design via optimal transport

    Constantinos Daskalakis, Alan Deckelbaum, and Christos Tzamos. Mechanism design via optimal transport. In Proceedings of the fourteenth ACM conference on Electronic commerce , pages 269--286, 2013

    2013

  17. [25]

    The complexity of optimal mechanism design

    Constantinos Daskalakis, Alan Deckelbaum, and Christos Tzamos. The complexity of optimal mechanism design. In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms , pages 1302--1318. SIAM, 2014

    2014

  18. [26]

    Sampling and representation complexity of revenue maximization

    Shaddin Dughmi, Li Han, and Noam Nisan. Sampling and representation complexity of revenue maximization. In International Conference on Web and Internet Economics , pages 277--291. Springer, 2014

    2014

  19. [27]

    Devanur, Zhiyi Huang, and Christos - Alexandros Psomas

    Nikhil R. Devanur, Zhiyi Huang, and Christos - Alexandros Psomas. The sample complexity of auctions with side information. In Daniel Wichs and Yishay Mansour, editors, Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, Ju...

    2016

  20. [28]

    The sample complexity of auctions with side information

    Nikhil R Devanur, Zhiyi Huang, and Christos-Alexandros Psomas. The sample complexity of auctions with side information. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing , pages 426--439, 2016

    2016

  21. [29]

    Revenue maximization with a single sample

    Peerapong Dhangwatnotai, Tim Roughgarden, and Qiqi Yan. Revenue maximization with a single sample. In Proceedings of the 11th ACM conference on Electronic commerce , pages 129--138, 2010

    2010

  22. [30]

    Designing and learning optimal finite support auctions

    Edith Elkind. Designing and learning optimal finite support auctions. In Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms , pages 736--745, 2007

    2007

  23. [31]

    Generalizing complex hypotheses on product distributions: Auctions, prophet inequalities, and pandora's problem

    Chenghao Guo, Zhiyi Huang, Zhihao Gavin Tang, and Xinzhi Zhang. Generalizing complex hypotheses on product distributions: Auctions, prophet inequalities, and pandora's problem. In Conference on Learning Theory, COLT , pages 2248--2288, 2021

    2021

  24. [32]

    Settling the sample complexity of single-parameter revenue maximization

    Chenghao Guo, Zhiyi Huang, and Xinzhi Zhang. Settling the sample complexity of single-parameter revenue maximization. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing , pages 662--673, 2019

    2019

  25. [33]

    Efficient empirical revenue maximization in single-parameter auction environments

    Yannai A Gonczarowski and Noam Nisan. Efficient empirical revenue maximization in single-parameter auction environments. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing , pages 856--868, 2017

    2017

  26. [34]

    On choosing and bounding probability metrics

    Alison L Gibbs and Francis Edward Su. On choosing and bounding probability metrics. International statistical review , 70(3):419--435, 2002

    2002

  27. [35]

    The sample complexity of up-to- multi-dimensional revenue maximization

    Yannai A Gonczarowski and S Matthew Weinberg. The sample complexity of up-to- multi-dimensional revenue maximization. Journal of the ACM (JACM) , 68(3):1--28, 2021

    2021

  28. [36]

    Making the most of your samples

    Zhiyi Huang, Yishay Mansour, and Tim Roughgarden. Making the most of your samples. In Proceedings of the Sixteenth ACM Conference on Economics and Computation , pages 45--60, 2015

    2015

  29. [37]

    Selling multiple correlated goods: Revenue maximization and menu-size complexity

    Sergiu Hart and Noam Nisan. Selling multiple correlated goods: Revenue maximization and menu-size complexity. Journal of Economic Theory , 183:991--1029, 2019

    2019

  30. [38]

    Maximal revenue with multiple goods: Nonmonotonicity and other observations

    Sergiu Hart and Philip J Reny. Maximal revenue with multiple goods: Nonmonotonicity and other observations. Theoretical Economics , 10(3):893--922, 2015

    2015

  31. [39]

    Sample complexity for non-truthful mechanisms

    Jason Hartline and Samuel Taggart. Sample complexity for non-truthful mechanisms. In Proceedings of the 2019 ACM Conference on Economics and Computation , pages 399--416, 2019

    2019

  32. [40]

    Sample complexity of posted pricing for a single item

    Billy Jin, Thomas Kesselheim, Will Ma, and Sahil Singla. Sample complexity of posted pricing for a single item. arXiv preprint arXiv:2406.00819 , 2024

    2024 arXiv

  33. [41]

    Benchmark-tight approximation ratio of simple mechanism for a unit-demand buyer

    Yaonan Jin and Pinyan Lu. Benchmark-tight approximation ratio of simple mechanism for a unit-demand buyer. In 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS) , pages 1251--1259, 2024

    2024

  34. [42]

    Learning reserve prices in second-price auctions

    Yaonan Jin, Pinyan Lu, and Tao Xiao. Learning reserve prices in second-price auctions. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023) . Schloss Dagstuhl--Leibniz-Zentrum f \"u r Informatik, 2023

    2023

  35. [43]

    The value of knowing a demand curve: Bounds on regret for online posted-price auctions

    Robert Kleinberg and Tom Leighton. The value of knowing a demand curve: Bounds on regret for online posted-price auctions. In 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings. , pages 594--605. IEEE, 2003

    2003

  36. [44]

    Learning with comparison feedback: Online estimation of sample statistics

    Michela Meister and Sloan Nietert. Learning with comparison feedback: Online estimation of sample statistics. In Algorithmic Learning Theory , pages 983--1001. PMLR, 2021

    2021

  37. [45]

    On the pseudo-dimension of nearly optimal auctions

    Jamie H Morgenstern and Tim Roughgarden. On the pseudo-dimension of nearly optimal auctions. Advances in Neural Information Processing Systems , 28, 2015

    2015

  38. [46]

    Learning simple auctions

    Jamie Morgenstern and Tim Roughgarden. Learning simple auctions. In Conference on Learning Theory , pages 1298--1318. PMLR, 2016

    2016

  39. [47]

    Non-stochastic cdf estimation using threshold queries

    Princewill Okoroafor, Vaishnavi Gupta, Robert Kleinberg, and Eleanor Goh. Non-stochastic cdf estimation using threshold queries. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 3551--3572. SIAM, 2023

    2023

  40. [48]

    Description complexity of regular distributions

    Renato Paes Leme, Balasubramanian Sivan, Yifeng Teng, and Pratik Worah. Description complexity of regular distributions. In Proceedings of the 24th ACM Conference on Economics and Computation , pages 959--959, 2023

    2023

  41. [49]

    Pricing query complexity of revenue maximization

    Renato Paes Leme, Balasubramanian Sivan, Yifeng Teng, and Pratik Worah. Pricing query complexity of revenue maximization. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 399--415. SIAM, 2023

    2023

  42. [50]

    Smoothed analysis of multi-item auctions with correlated values

    Alexandros Psomas, Ariel Schvartzman, and S Matthew Weinberg. Smoothed analysis of multi-item auctions with correlated values. In Proceedings of the 2019 ACM Conference on Economics and Computation , pages 417--418, 2019

    2019

  43. [51]

    Simple mechanisms for a subadditive buyer and applications to revenue monotonicity

    Aviad Rubinstein and S Matthew Weinberg. Simple mechanisms for a subadditive buyer and applications to revenue monotonicity. ACM Transactions on Economics and Computation (TEAC) , 6(3-4):1--25, 2018

    2018

  44. [52]

    Bandit sequential posted pricing via half-concavity

    Sahil Singla and Yifan Wang. Bandit sequential posted pricing via half-concavity. In Dirk Bergemann, Robert Kleinberg, and Daniela Sab \' a n, editors, Proceedings of the 25th ACM Conference on Economics and Computation, EC 2024, New Haven, CT, USA, July 8-11, 2024 , pages 922...

    2024

  45. [53]

    A sample complexity measure with applications to learning optimal auctions

    Vasilis Syrgkanis. A sample complexity measure with applications to learning optimal auctions. Advances in Neural Information Processing Systems , 30, 2017

    2017

  46. [54]

    Haggling over substitutes

    John Thanassoulis. Haggling over substitutes. Journal of Economic theory , 117(2):217--245, 2004

    2004

  47. [55]

    An n-to-1 bidder reduction for multi-item auctions and its applications

    Andrew Chi-Chih Yao. An n-to-1 bidder reduction for multi-item auctions and its applications. In Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms , pages 92--109. SIAM, 2014

    2014

  48. [56]

    On revenue monotonicity in combinatorial auctions

    Andrew Chi-chih Yao. On revenue monotonicity in combinatorial auctions. In Xiaotie Deng, editor, Algorithmic Game Theory , pages 1--11, Cham, 2018. Springer International Publishing

    2018

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.