Ning Chen, Nicole Immorlica, Anna Karlin, Mohammad Mahdian and Atri Rudra

Motivated by applications in online dating and kidney exchange, we
study a stochastic matching problem in which we have a random graph
*G* given by a node set *V* and probabilities *p(i,j)* on all pairs
*i,j* in *V* representing the probability that edge *(i,j)*
exists. Additionally, each node has an integer weight *t(i)* called
its patience parameter. Nodes represent agents in a matching market
with dichotomous preferences, i.e., each agent finds every other agent
either *acceptable* or *unacceptable* and is indifferent
between all acceptable agents. The goal is to maximize the welfare,
or produce a matching between acceptable agents of maximum size.
Preferences must be solicited based on probabilistic information
represented by *p(i,j)*, and agent *i* can be asked at most *t(i)*
questions regarding his or her preferences.

A stochastic matching algorithm iteratively probes pairs of nodes *i*
and *j* with positive patience parameters. With probability *p(i,j)*,
an edge exists and the nodes are irrevocably matched. With
probability *1-p(i,j)*, the edge does not exist and the patience
parameters of the nodes are decremented. We give a simple greedy
strategy for selecting probes which produces a matching whose
cardinality is, in expectation, at least a quarter of the size of this
optimal algorithm's matching. We additionally show that variants of
our algorithm (and our analysis) can handle more complicated
constraints, such as a limit on the maximum number of rounds, or the
number of pairs probed in each round.