  We study the stable marriage problem in the partial information setting where
the agents, although they have an underlying true strict linear order, are
allowed to specify partial orders. Specifically, we focus on the case where the
agents are allowed to submit strict weak orders and we try to address the
following questions from the perspective of a market-designer: i) How can a
designer generate matchings that are robust? ii) What is the trade-off between
the amount of missing information and the "quality" of solution one can get?
With the goal of resolving these questions through a simple and prior-free
approach, we suggest looking at matchings that minimize the maximum number of
blocking pairs with respect to all the possible underlying true orders as a
measure of "quality", and subsequently provide results on finding such
matchings.
  In particular, we first restrict our attention to matchings that have to be
stable with respect to at least one of the completions and show that in this
case arbitrarily filling-in the missing information and computing the resulting
stable matching can give a non-trivial approximation factor for our problem in
certain cases. We complement this result by showing that, even under severe
restrictions on the preferences of the agents, the factor obtained is
asymptotically tight in many cases. We then investigate a special case, where
only agents on one side provide strict weak orders and all the missing
information is at the bottom of their preference orders, and show that here the
negative result mentioned above can be circumvented in order to get a much
better approximation factor; this result, too, is tight in many cases. Finally,
we move away from the restriction mentioned above and show a general hardness
of approximation result and also discuss one possible approach that can lead us
to a near-tight approximation bound.
