  In a dynamic matching market, such as a marriage or job market, how should
agents balance accepting a proposed match with the cost of continuing their
search? We consider this problem in a discrete setting, in which agents have
cardinal values and finite lifetimes, and proposed matches are random.
  We seek to quantify how well the agents can do. We provide upper and lower
bounds on the collective losses of the agents, with a polynomially small
failure probability, where the notion of loss is with respect to a plausible
baseline we define. These bounds are tight up to constant factors.
  We highlight two aspects of this work. First, in our model, agents have a
finite time in which to enjoy their matches, namely the minimum of their
remaining lifetime and that of their partner; this implies that unmatched
agents become less desirable over time, and suggests that their decision rules
should change over time. Second, we use a discrete rather than a continuum
model for the population. The discreteness causes variance which induces
localized imbalances in the two sides of the market. One of the main technical
challenges we face is to bound these imbalances.
  In addition, we present the results of simulations on moderate-sized problems
for both the discrete and continuum versions. For these size problems, there
are substantial ongoing fluctuations in the discrete setting whereas the
continuum version converges reasonably quickly.
