Before revision:  Namely, we consider the following stochastic reward problems: when the stochastic graph is not known and the order of online arrivals is determined uniformly at random (i.e., the ROM model) ; when the stochastic graph is known to the algorithm and the order of arrival of online vertices is determined adversarially; when the stochastic graph is known and the order of arrival of online vertices is determined uniformly at random ; and finally when the online vertices are generated i.i.d. from a known distribution on the vertices of a known stochastic (type)graph .
After revision:  Namely, we consider the following stochastic reward problems: when the stochastic graph is not known and the order of online arrivals is determined uniformly at random (i.e., unlimited) patience. The stochastic matching problem leads to a variety of settings. Our main contribution is to provide a new LP relaxation and a unified approach for establishing new and improved competitive bounds in three different input model settings (namely, adversarial, random order, and known i.i.d. from a known distribution on the vertices of a known stochastic (type)graph .