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

By Robert D. Kleinberg, Frank Thomson Leighton. 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings., 2003

440 citations recorded by the source corpus.

Subfields: Computer Science Applications, Management Science and Operations Research

View Paper: https://www.semanticscholar.org/paper/a35100e8954261d4802ef70b690ff7724653806f

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Science Applications

In Management Science and Operations Research

Citations in the corpus

Dynamic Pricing with an Unknown Demand Model: Asymptotically Optimal Semi-Myopic Policies (2014, methodology): “Kleinberg and Leighton (2003) employ a multi-armed bandit approach in a dynamic pricing context by allowing the seller to use only a discrete grid of prices within the continuum of feasible prices.”
The sample complexity of revenue maximization (2014, background): “ly with the papers most closely related to the present work. For previously studied models about revenue-maximization with an unknown distribution, which dier in various respects from our model, see [4, 29]. For other uses of samples in auction design that dier from ours, see Fu et al. [21], who use”
Multi-parameter mechanism design and sequential posted pricing (2010, background): “Several papers study revenue maxi mization through online posted pricings in the context of adversarial values, albeit in the simpler context of multin t auctions [6, 15, 5].”
ARMDN: Associative and Recurrent Mixture Density Networks for eRetail Demand Forecasting (2018, background): “In the retail industry, accurate sales forecasts are essential for timely buying and replenishment of inventory, top-line demand planning and effective supply-chain utilization [15, 19].”
Truthful incentives in crowdsourcing tasks using regret minimization mechanisms (2013, methodology): “However, the mechanisms of [25] [6] are not directly applicable as they optimize a different objective, which leads to a substantially different mathematical analysis.”
Introduction to Multi-Armed Bandits (2019, neutral): “• for dynamic pricing (Kleinberg and Leighton, 2003; Babaioff et al., 2015a).”
Dynamic Pricing and Learning: Historical Origins, Current Research, and New Directions (2013, positive): “This changes with the work of Kleinberg and Leighton (2003), who quantify the performance of a pricing policy by Regret(T ): the expected loss in T time periods incurred by not choosing optimal prices.”
Nearly Tight Bounds for the Continuum-Armed Bandit Problem (2004, methodology): “For a one-dimensional strategy space, the first algorithm with sublinear regret appeared in [1], while the first polynomial lower bound on regret appeared in [15].”
Bandits with Knapsacks (2013, methodology): “This generic approach has been successfully used in past work on dynamic pricing (e.g., [13], [12], [10], [11]) to provide worst-case optimal regret bounds.”
Mechanism Design via Differential Privacy (2007, neutral): “The online variant of this problem has also been extensively studied [7, 11, 25, 10].”
Partial Monitoring - Classification, Regret Bounds, and Algorithms (2014, background): “Various problems of interest can be modeled as partial monitoring instances, such as learning with expert advice [20], the multi-armed bandit problem [6], dynamic pricing [19], the dark pool problem [3], label efficient prediction [14], and linear and convex optimization with full or bandit feedback”
Towards Sharp Inapproximability For Any 2-CSP (2007, neutral): “The online variant of this problem has also been extensively studied [7, 11, 25, 10].”
Stochastic Multi-Armed-Bandit Problem with Non-stationary Rewards (2014, background): “Since their inception, MAB problems with various modifications have been studied extensively in Statistics, Economics, Operations Research, and Computer Science, and are used to model a plethora of dynamic optimization problems under uncertainty; examples include clinical trials ([3]), strategic pri”
Dynamic Pricing Without Knowing the Demand Function: Risk Bounds and Near-Optimal Algorithms (2009, positive): “Related studies in the computer science literature include Auer et al. (2002) who study an adversarial version of a multi-armed bandit problem, and Kleinberg and Leighton (2003) who provide an analysis of an on-line posted-price auction using these tools.”