Prophet Inequalities for Matching with a Single Sample
share
We consider the prophet inequality problem for (not necessarily bipartite) matching problems with independent edge values, under both edge arrivals and vertex arrivals. We show constant-factor prophet inequalities for the case where the online algorithm has only limited access to the value distributions through samples. First, we give a 16-approximate prophet inequality for matching in general graphs under edge arrivals that uses only a single sample from each value distribution as prior information. Then, for bipartite matching and (one-sided) vertex arrivals, we show an improved bound of 8 that also uses just a single sample from each distribution. Finally, we show how to turn our 16-approximate single-sample prophet inequality into a truthful single-sample mechanism for online bipartite matching with vertex arrivals.
READ FULL TEXT