  We consider a model for repeated stochastic matching where compatibility is
probabilistic, is realized the first time agents are matched, and persists in
the future. Such a model has applications in the gig economy, kidney exchange,
and mentorship matching.
  We ask whether a $decentralized$ matching process can approximate the optimal
online algorithm. In particular, we consider a decentralized $stable$
$matching$ process where agents match with the most compatible partner who does
not prefer matching with someone else, and known compatible pairs continue
matching in all future rounds. We demonstrate that the above process provides a
0.316-approximation to the optimal online algorithm for matching on general
graphs. We also provide a $\frac{1}{7}$-approximation for many-to-one bipartite
matching, a $\frac{1}{11}$-approximation for capacitated matching on general
graphs, and a $\frac{1}{2k}$-approximation for forming teams of up to $k$
agents. Our results rely on a novel coupling argument that decomposes the
successful edges of the optimal online algorithm in terms of their
round-by-round comparison with stable matching.
