Static Pricing for Single Sample Multi-unit Prophet Inequalities
<|reference_start|>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, $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 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 then 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 that sets one of the samples as a price.<|reference_end|>
@article{nuti2024static,
    title={Static Pricing for Single Sample Multi-unit Prophet Inequalities},
    author={Pranav Nuti and Peter Westbrook},
    journal={arXiv preprint arXiv:2409.07719},
    year={2024},
    archivePrefix={arXiv},
    eprint={2409.07719},
    primaryClass={cs.GT cs.DS}
}