# From Stream to Pool: Pricing Under the Law of Diminishing Marginal Utility

arXiv: https://arxiv.org/abs/2310.19220 · HTML: https://mlsanity.com/paper/2310.19220/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 8 of its 74 references that are in the map.
- First posted on arXiv 30 Oct 2023.

## Builds on (most cited first, 8 of 8)

- [Provably efficient RL with Rich Observations via Latent State Decoding](https://mlsanity.com/paper/1901.09018/) (2019)
- [The Complexity of Constrained Min-Max Optimization](https://mlsanity.com/paper/2009.09623/) (2020)
- [Beyond IID: data-driven decision-making in heterogeneous environments](https://mlsanity.com/paper/2206.09642/) (2022)
- [Learning and Optimization with Seasonal Patterns](https://mlsanity.com/paper/2005.08088/) (2020)
- [Multi-armed Bandit Requiring Monotone Arm Sequences](https://mlsanity.com/paper/2106.03790/) (2021)
- [Learning to Price Against a Moving Target](https://mlsanity.com/paper/2106.04689/) (2021)
- [Algorithmic Challenges in Ensuring Fairness at the Time of Decision](https://mlsanity.com/paper/2103.09287/) (2021)
- [The Power of Simple Menus in Robust Selling Mechanisms](https://mlsanity.com/paper/2310.17392/) (2023)

## Abstract (arXiv)

Dynamic pricing models often posit that a stream of customer interactions occur sequentially, where customers' valuations are drawn independently. However, this model is not entirely reflective of the real world, as it overlooks a critical aspect, the law of diminishing marginal utility, which states that a customer's marginal utility from each additional unit declines. This causes the valuation distribution to shift towards the lower end, which is not captured by the stream model. This motivates us to study a pool-based model, where a pool of customers repeatedly interacts with a monopolist seller, each of whose valuation diminishes in the number of purchases made according to a discount function. In particular, when the discount function is constant, our pool model recovers the stream model. We focus on the most fundamental special case, where a customer's valuation becomes zero once a purchase is made. Given k prices, we present a non-adaptive, detail-free (i.e., does not "know" the valuations) policy that achieves a 1/k competitive ratio, which is optimal among non-adaptive policies. Furthermore, based on a novel debiasing technique, we propose an adaptive learn-then-earn policy with a tilde O(k2/3 n2/3) regret.