Sample-Based Matroid Prophet Inequalities
- Jinzhao Wu, Yale University
- Time: 2024-03-25 14:00
- Host: Turing Class Research Committee
- Venue: Room 204, Courtyard No.5, Jingyuan
Abstract
We study matroid prophet inequalities when distributions are unknown and accessible only through samples. While single-sample prophet inequalities for special matroids are known, no constant-factor competitive algorithm with even a sublinear number of samples was known for general matroids. Adding more to the stake, the single-sample version of the question for general matroids has close (two-way) connections with the long-standing matroid secretary conjecture.
Four years ago, we developed an algorithm to address the matroid prophet inequalities problem using $O(\log n)$ samples. Unfortunately, this algorithm was shown to be incorrect. In this work, we finally are able to give a $(\frac14 - \varepsilon)$-competitive matroid prophet inequality with only $O_\varepsilon(\poly \log n)$ samples. Our algorithm consists of two parts: (i) a novel \emph{quantile-based} reduction from matroid prophet inequalities to online contention resolution schemes (OCRSs) with $O_\varepsilon(\log n)$ samples, and (ii) a $(\sfrac14 - \varepsilon)$-selectable matroid OCRS with $O_\varepsilon(\poly \log n)$ samples which carefully addresses an adaptivity challenge.
Biography
Jinzhao Wu is a second-year Ph.D. student in Computer Science at Yale University, where he is advised by Prof. Yang Cai. He has a broad interest in theoretical computer science, with a particular focus on algorithmic game theory and computational problems arising from the field of economics.