  Mehta and Panigrahi (2012) proposed Online Matching with Stochastic Rewards,
which generalizes the Online Bipartite Matching problem of Karp, Vazirani, and
Vazirani (1990) by associating the edges with success probabilities. This new
feature captures the pay-per-click model in online advertising. Recently, Huang
and Zhang (2020) studied this problem under the online primal dual framework
using the Configuration Linear Program (LP), and got the best known competitive
ratios of the Stochastic Balance algorithm. Their work suggests that the more
expressive Configuration LP is more suitable for this problem than the Matching
LP.
  This paper advances the theory of Configuration LP in two directions. Our
technical contribution includes a characterization of the joint matching
outcome of an offline vertex and \emph{all its neighbors}. This
characterization may be of independent interest, and is aligned with the spirit
of Configuration LP. By contrast, previous analyses of Ranking generally focus
on only one neighbor. Second, we designed a Stochastic Configuration LP that
captures a stochastic benchmark proposed by Goyal and Udwani (2020), who used a
Path-based LP. The Stochastic Configuration LP is smaller and simpler than the
Path-based LP. Moreover, using the new LP we improved the competitive ratio of
Stochastic Balance from $0.596$ to $0.611$ when the success probabilities are
infinitesimal, and to $0.613$ when the success probabilities are further equal.

Data Structures and Algorithms