Abstract:
In this work, we study the single-choice prophet inequality problem, where a gambler faces a sequence of n online i.i.d. random variables drawn from an unknown distribution. When a variable reveals its value, the gambler needs to decide irrevocably whether or not to accept the value. The goal is to maximize the competitive ratio between the expected gain of the gambler and that of the maximum variable. It is shown by Correa et al. (EC 2019) that when the distribution is unknown or only o(n) uniform samples from the distribution are given, the best an algorithm can do is 1/e-competitive. In contrast, when the distribution is known (Correa et al. EC 2017) or \Omega(n) uniform samples are given (Rubinstein et al. ITCS 2020), the optimal competitive ratio of 0.7451 can be achieved. In this work, we introduce a new model in which the algorithm has access to an oracle that answers quantile queries about the distribution and investigate to what extent we can use a small number of queries to achieve good competitive ratios. We first use the answers from the queries to implement the threshold-based algorithms and show that with two thresholds our algorithm achieves a competitive ratio of 0.6786. We further introduce the observe-and-accept algorithm that requires only a single query. This algorithm sets a threshold in the early stage of the algorithm by making a query and uses the maximum realization from one phase as the threshold for the next phase. It can be viewed as a natural combination and generalization of the single-threshold algorithm and the algorithm for the secretary problem. By properly choosing the quantile to query and the break-points of phases, we achieve a competitive ratio of 0.6861.
The talk is based on joint works with Yilong Feng, Bo Li, Haolong Li and Yutong Wu.
About the speaker:
Xiaowei Wu is an Assistant Professor in the Department of Computer and Information Science with the State Key Laboratory of Internet of Things for Smart City at the University of Macau. He received his Ph.D. degree from the University of Hong Kong and his B.Eng. degree from University of Science and Technology of China. His research interests span various topics in online approximation algorithms, algorithmic game theory, computational social choice, and data mining. He has published more than 50 papers in top theory and artificial intelligence conferences and journals including JACM, SICOMP, AIJ, STOC, FOCS, SODA, AAAI and IJCAI. He has served as the PC chair and local organizing chairs of several international conferences, including IJTCS-FAW 2023, MCSCT 2022, 2023 and 2024.