Static Pricing for Single Sample Multi-unit Prophet Inequalities

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, Xi, revealed to the seller when they arrive. While the seller is unaware of the distribution from which Xi is drawn, they have access to a single sample, Yi drawn from the same distribution as Xi. 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 frac12 of the social welfare, and recently Pashkovich and Sayutina established an analogous result for k = 2. In this paper, we prove that for k ≥ 3, setting a (static) price equal to the kth largest sample also obtains a competitive ratio of frac12, 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-√2klog k)th largest sample obtains a competitive ratio of 1 - √frac2log kk - oleft(√fraclog kkright), 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 - √fraclog kk - oleft(√fraclog kkright), which is the optimal possible ratio achievable with a static pricing scheme with knowledge of the distributions of the values.