  We study the problem of finding solutions to the stable matching problem that
are robust to errors in the input and we obtain a polynomial time algorithm for
a special class of errors. In the process, we also initiate work on a new
structural question concerning the stable matching problem, namely finding
relationships between the lattices of solutions of two "nearby" instances.
  Our main algorithmic result is the following: We identify a polynomially
large class of errors, $D$, that can be introduced in a stable matching
instance. Given an instance $A$ of stable matching, let $B$ be the random
variable that represents the instance that results after introducing {\em one}
error from $D$, chosen via a given discrete probability distribution. The
problem is to find a stable matching for $A$ that maximizes the probability of
being stable for $B$ as well. Via new structural properties of the type
described in the question stated above, we give a combinatorial polynomial time
algorithm for this problem.
  We also show that the set of robust stable matchings for instance $A$, under
probability distribution $p$, forms a sublattice of the lattice of stable
matchings for $A$. We give an efficient algorithm for finding a succinct
representation for this set; this representation has the property that any
member of the set can be efficiently retrieved from it.
