  We study the problem of vertex-weighted online bipartite matching with
stochastic rewards where matches may fail with some known probability and the
decision maker has to adapt to the sequential realization of these outcomes.
Recent works have studied several special cases of this problem and it was
known that the (randomized) Perturbed Greedy algorithm due to Aggarwal et al.
(SODA, 2011) achieves the best possible competitive ratio guarantee of
$(1-1/e)$ in some cases. We give a simple proof of these results by reducing
(special cases of) the stochastic rewards problem to the deterministic setting
of online bipartite matching (Karp, Vazirani, Vazirani (STOC, 1990)). More
broadly, our approach gives conditions under which it suffices to analyze the
competitive ratio of an algorithm for the simpler setting of deterministic
rewards in order to obtain a competitive ratio guarantee for stochastic
rewards. The simplicity of our approach reveals that the Perturbed Greedy
algorithm has a competitive ratio of $(1-1/e)$ even in certain settings with
correlated rewards, where no results were previously known. Finally, we show
that without any special assumptions, the Perturbed Greedy algorithm has a
competitive ratio strictly less than $(1-1/e)$ for vertex-weighted online
matching with stochastic rewards.
