Abstract
The rich literature on online Bayesian selection problems has long focused on so-called prophet inequalities, which compare the gain of an online algorithm to that of a ``prophet'' who knows the future. An equally-natural, though significantly less well-studied benchmark is the gain of the optimum \emph{online} algorithm, which may be omnipotent (i.e, computationally-unbounded), but not omniscient. What is the computational complexity of the optimum online? How well can a polynomial-time algorithm approximate it?
Motivated by applications in ride hailing, we study the above questions for the online stochastic maximum-weight matching problem under vertex arrivals. This problem was recently introduced by Ezra, Feldman, Gravin and Tang (EC'20), who gave a 1/2-competitive algorithm for it. This is the best possible ratio, as this problem is a generalization of the original single-item prophet inequality.
We present a polynomial-time algorithm which approximates optimal online within a factor of 0.51---beating the best-possible prophet inequality. At the core of our result are a new linear program formulation, an algorithm that tries to match the arriving vertices in two attempts, and an analysis that bounds the correlation resulting from the second attempts. In contrast, we show that it is highly unlikely that one can efficiently approximate the optimum online arbitrarily well, as it is PSPACE-hard to approximate it within some constant alpha < 1.
Based on joint work with Christos Papadimitriou, Tristan Pollner and Amin Saberi.