Abstract
There is a growing interest in studying sample-based prophet inequality with the motivation stemming from the connection between the prophet inequalities and the sequential posted pricing mechanisms. Rubinstein, Wang, and Weinberg (ITCS 2021) established the optimal single-choice prophet inequality with only a single sample per each distribution. Our work considers the sample-based prophet inequality with less than one sample per distribution, i.e., scenarios with no prior information about some of the random variables. Specifically, we propose a p-sample model, where a sample from each distribution is revealed with probability \(p \in [0,1]\) independently across all distributions. This model generalizes the single-sample setting of Rubinstein, Wang, and Weinberg (ITCS 2021), and the i.i.d. prophet inequality with a linear number of samples of Correa et al. (EC 2019). Our main result is the optimal \(\frac{p}{1+p}\) prophet inequality for all \(p\in [0,1]\).
This work is supported by Science and Technology Innovation 2030 - “New Generation of Artificial Intelligence” Major Project No. (2018AAA0100903), Innovation Program of Shanghai Municipal Education Commission, Program for Innovative Research Team of Shanghai University of Finance and Economics (IRTSHUFE) and the Fundamental Research Funds for the Central Universities. Zhihao Gavin Tang is supported by NSFC grant 61902233. Nick Gravin is supported by NSFC grant 62150610500.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
E.g., \(w_1=w_2+\varepsilon =\ldots =w_k+(k-1)\varepsilon ,\) for some negligibly small \(\varepsilon >0\).
- 2.
We can assume that once \(w_i\) is set to 0 for \(1<i<k\), it is small enough to not appear in the \(\mathcal {E}_{\ell }\). Indeed, we can add a few dummy cards with both sides having negligibly small numbers in the beginning of the sequence that do not affect performance of Max-Sample, but still bigger than \(w_i\leftarrow 0\).
References
Azar, P.D., Kleinberg, R., Weinberg, S.M.: Prophet inequalities with limited information. In: SODA, pp. 1358–1377. SIAM (2014)
Babaioff, M., Gonczarowski, Y.A., Mansour, Y., Moran, S.: Are two (samples) really better than one? In: EC, p. 175. ACM (2018)
Caramanis, C., et al.: Single-sample prophet inequalities via greedy-ordered selection. In: SODA, pp. 1298–1325. SIAM (2022)
Chawla, S., Hartline, J.D., Malec, D.L., Sivan, B.: Multi-parameter mechanism design and sequential posted pricing. In: STOC, pp. 311–320. ACM (2010)
Correa, J.R., Cristi, A., Epstein, B., Soto, J.A.: The two-sided game of googol and sample-based prophet inequalities. In: SODA, pp. 2066–2081. SIAM (2020)
Correa, J.R., Cristi, A., Feuilloley, L., Oosterwijk, T., Tsigonias-Dimitriadis, A.: The secretary problem with independent sampling. In: SODA, pp. 2047–2058. SIAM (2021)
Correa, J.R., Dütting, P., Fischer, F.A., Schewior, K.: Prophet inequalities for I.I.D. random variables from an unknown distribution. In: EC, pp. 3–17. ACM (2019)
Correa, J.R., Dütting, P., Fischer, F.A., Schewior, K., Ziliotto, B.: Unknown I.I.D. prophets: better bounds, streaming algorithms, and a new impossibility (extended abstract). In: ITCS. LIPIcs, vol. 185, pp. 86:1–86:1. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
Correa, J.R., Foncea, P., Hoeksma, R., Oosterwijk, T., Vredeveld, T.: Posted price mechanisms and optimal threshold strategies for random arrivals. Math. Oper. Res. 46(4), 1452–1478 (2021)
Correa, J.R., Foncea, P., Pizarro, D., Verdugo, V.: From pricing to prophets, and back! Oper. Res. Lett. 47(1), 25–29 (2019)
Daskalakis, C., Zampetakis, M.: More revenue from two samples via factor revealing SDPS. In: EC, pp. 257–272. ACM (2020)
Dhangwatnotai, P., Roughgarden, T., Yan, Q.: Revenue maximization with a single sample. Games Econ. Behav. 91, 318–333 (2015)
Dütting, P., Lattanzi, S., Leme, R.P., Vassilvitskii, S.: Secretaries with advice. In: EC, pp. 409–429. ACM (2021)
Ezra, T., Feldman, M., Gravin, N., Tang, Z.G.: Online stochastic max-weight matching: prophet inequality for vertex and edge arrival models. In: EC, pp. 769–787. ACM (2020)
Feldman, M., Gravin, N., Lucier, B.: Combinatorial auctions via posted prices. In: SODA, pp. 123–135. SIAM (2015)
Feldman, M., Svensson, O., Zenklusen, R.: Online contention resolution schemes. In: SODA, pp. 1014–1033. SIAM (2016)
Fu, H., Immorlica, N., Lucier, B., Strack, P.: Randomization beats second price as a prior-independent auction. In: EC, p. 323. ACM (2015)
Gravin, N., Wang, H.: Prophet inequality for bipartite matching: merits of being simple and non adaptive. In: EC, pp. 93–109. ACM (2019)
Guo, C., Huang, Z., Tang, Z.G., Zhang, X.: Generalizing complex hypotheses on product distributions: auctions, prophet inequalities, and pandora’s problem. In: COLT. Proceedings of Machine Learning Research, vol. 134, pp. 2248–2288. PMLR (2021)
Hajiaghayi, M.T., Kleinberg, R.D., Sandholm, T.: Automated online mechanism design and prophet inequalities. In: AAAI, pp. 58–65. AAAI Press (2007)
Kaplan, H., Naori, D., Raz, D.: Competitive analysis with a sample and the secretary problem. In: SODA, pp. 2082–2095. SIAM (2020)
Kleinberg, R., Weinberg, S.M.: Matroid prophet inequalities. In: STOC, pp. 123–136. ACM (2012)
Krengel, U., Sucheston, L.: Semiamarts and finite values. Bull. Am. Math. Soc. 83(4), 745–747 (1977)
Krengel, U., Sucheston, L.: On semiamarts, amarts, and processes with finite value. In: Probability on Banach Spaces, vol. 4, pp. 197–266 (1978)
Rubinstein, A.: Beyond matroids: secretary problem and prophet inequality with general constraints. In: STOC, pp. 324–332. ACM (2016)
Rubinstein, A., Wang, J.Z., Weinberg, S.M.: Optimal single-choice prophet inequalities from samples. In: ITCS. LIPIcs, vol. 151, pp. 60:1–60:10. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
Samuel-Cahn, E.: Comparison of threshold stop rules and maximum for independent nonnegative random variables. Ann. Probab. 1213–1216 (1984)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Gravin, N., Li, H., Tang, Z.G. (2022). Optimal Prophet Inequality with Less than One Sample. In: Hansen, K.A., Liu, T.X., Malekian, A. (eds) Web and Internet Economics. WINE 2022. Lecture Notes in Computer Science, vol 13778. Springer, Cham. https://doi.org/10.1007/978-3-031-22832-2_7
Download citation
DOI: https://doi.org/10.1007/978-3-031-22832-2_7
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-22831-5
Online ISBN: 978-3-031-22832-2
eBook Packages: Computer ScienceComputer Science (R0)