mlsanityData to 14 Oct 2026

Learning Optimal Posted Prices for a Unit-Demand Buyer

arXiv 2506.02284 ↗First posted 2 Jun 2025cs.GT cs.DS cs.LGcited by 1

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). Builds on 31 of its 51 references that are in the map. First posted on arXiv 2 Jun 2025.

Builds on

31 of 51 references.

References · 31

  1. 2015The Sample Complexity of Revenue Maximizationcited by 48
  2. 2016Sample Complexity of Automated Mechanism Designcited by 24
  3. 2019Settling the Sample Complexity of Single-parameter Revenue Maximizationcited by 24
  4. 2019Multi-Item Mechanisms without Item-Independence: Learnability via Robustnesscited by 23
  5. 2019Generalizing Complex Hypotheses on Product Distributions: Auctions, Prophet Inequalities, and Pandora's Problemcited by 22
  6. 2015The Sample Complexity of Auctions with Side Informationcited by 20
  7. 2017Learning Multi-item Auctions with (or without) Samplescited by 18
  8. 2018The Sample Complexity of Up-to-varepsilon Multi-Dimensional Revenue Maximizationcited by 17
  9. 2014Making the Most of Your Samplescited by 15
  10. 2021Pricing Query Complexity of Revenue Maximizationcited by 12
  11. 2016Efficient Empirical Revenue Maximization in Single-Parameter Auction Environmentscited by 11
  12. 2017A Sample Complexity Measure with Applications to Learning Optimal Auctionscited by 11
19 more
  1. 2017Generalization Guarantees for Multi-item Profit Maximization: Pricing, Auctions, and Randomized Mechanismscited by 11
  2. 2024Sample Complexity of Posted Pricing for a Single Itemcited by 11
  3. 2014A Simple and Approximately Optimal Mechanism for an Additive Buyercited by 9
  4. 2018A Duality-Based Unified Approach to Bayesian Mechanism Designcited by 9
  5. 2014Sampling and Representation Complexity of Revenue Maximizationcited by 7
  6. 2014An n-to-1 Bidder Reduction for Multi-item Auctions and its Applicationscited by 7
  7. 2015Mechanism Design via Optimal Transportcited by 6
  8. 2023Bandit Sequential Posted Pricing via Half-Concavitycited by 5
  9. 2013Selling Multiple Correlated Goods: Revenue Maximization and Menu-Size Complexity (old title: "The Menu-Size Complexity of Auctions")cited by 4
  10. 2019Learning Reserve Prices in Second-Price Auctionscited by 4
  11. 2021Learning with Comparison Feedback: Online Estimation of Sample Statisticscited by 4
  12. 2021Computing Simple Mechanisms: Lift-and-Round over Marginal Reduced Formscited by 3
  13. 2022Strong Revenue (Non-)Monotonicity of Single-parameter Auctionscited by 3
  14. 2023Description Complexity of Regular Distributionscited by 3
  15. 2023Non-Stochastic CDF Estimation Using Threshold Queriescited by 2
  16. 2015Optimal Pricing is Hardcited by 1
  17. 2018Smoothed Analysis of Multi-Item Auctions with Correlated Valuescited by 1
  18. 2020Menu-size Complexity and Revenue Continuity of Buy-many Mechanismscited by 1
  19. 2023Simultaneous Auctions are Approximately Revenue-Optimal for Subadditive Bidderscited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 1.

1 paper.

  1. 2026Pricing Query Complexity of Multiplicative Revenue Approximationcited by 0