2 papers
cs.GT2023
Single Sample Prophet Inequality for Uniform Matroids of Rank 2
Kanstantsin Pashkovich, Alice Sayutina
We study the prophet inequality when the gambler has an access only to a single sample from each distribution. Rubinstein, Wang and Weinberg showed that an optimal guarantee of 1/2…
cs.GT2023
Non-Adaptive Prophet Inequalities for Minor-Closed Classes of Matroids
Kanstantsin Pashkovich, Alice Sayutina
We consider the matroid prophet inequality problem. This problem has been extensively studied in the case of adaptive mechanisms. In particular, there is a tight -competitive me…