Static Pricing for Multi-unit Prophet Inequalities

• 成果类型: Article
• 署名作者: Chawla, Shuchi; Devanur, Nikhil; Lykouris, Thodoris
• 署名单位: University of Texas System; University of Texas Austin; Amazon.com; Massachusetts Institute of Technology (MIT)
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2023.0031
• 发表日期: 2024
• 页码: 1388-1399

摘要

We study a pricing problem where a seller has k identical copies of a product, buyers arrive sequentially, and the seller prices the items aiming to maximize social welfare. When k =1, this is the so-called prophet inequality problem for which there is a simple pricing scheme achieving a competitive ratio of 1/2. On the other end of the spectrum, as k goes to infinity, the asymptotic performance of both static and adaptive pricing is well understood. We provide a static pricing scheme for the small-supply regime: where k is small but larger than one. Prior to our work, the best competitive ratio known for this setting was the 1/2 that follows from the single-unit prophet inequality. Our pricing scheme is easy to describe as well as practical; it is anonymous, nonadaptive, and order oblivious. We pick a single price that equalizes the expected fraction of items sold and the probability that the supply does not sell out before all customers are served; this price is then offered to each customer while supply lasts. This extends an approach introduced by Samuel-Cahn for the case of k =1. This pricing scheme achieves a competitive ratio that increases gradually with the supply. Subsequent work shows that our pricing scheme is the optimal static pricing for every value of k.