Static Pricing for Single Sample Multi-unit Prophet Inequalities
This work addresses algorithmic pricing challenges in online resource allocation for sellers with limited distributional information, providing optimal static pricing strategies that are incremental improvements over prior results for specific k values.
The paper tackles the problem of maximizing social welfare in single sample multi-unit prophet inequalities by proposing static pricing strategies for selling k identical items, proving that setting the price to the k-th largest sample achieves a competitive ratio of 1/2 for k ≥ 3, and for large k, using the (k - √(2k log k))-th largest sample achieves an optimal ratio of 1 - √(2 log k / k) - o(√(log k / k)).
In this paper, we study $k$-unit single sample prophet inequalities. A seller has $k$ identical, indivisible items to sell. A sequence of buyers arrive one-by-one, with each buyer's private value for the item, $X_i$, revealed to the seller when they arrive. While the seller is unaware of the distribution from which $X_i$ is drawn, they have access to a single sample, $Y_i$ drawn from the same distribution as $X_i$. What strategies can the seller adopt for selling items so as to maximize social welfare? Previous work has demonstrated that when $k = 1$, if the seller sets a price equal to the maximum of the samples, they can achieve a competitive ratio of $\frac{1}{2}$ of the social welfare, and recently Pashkovich and Sayutina established an analogous result for $k = 2$. In this paper, we prove that for $k \geq 3$, setting a (static) price equal to the $k^{\text{th}}$ largest sample also obtains a competitive ratio of $\frac{1}{2}$, resolving a conjecture Pashkovich and Sayutina pose. We also consider the situation where $k$ is large. We demonstrate that setting a price equal to the $(k-\sqrt{2k\log k})^{\text{th}}$ largest sample obtains a competitive ratio of $1 - \sqrt{\frac{2\log k}{k}} - o\left(\sqrt{\frac{\log k}{k}}\right)$, and that this is the optimal possible ratio achievable with a static pricing scheme with access to a single sample. This should be compared against a competitive ratio $1 - \sqrt{\frac{\log k}{k}} - o\left(\sqrt{\frac{\log k}{k}}\right)$, which is the optimal possible ratio achievable with a static pricing scheme with knowledge of the distributions of the values.