  The stable marriage problem and its extensions have been extensively studied,
with much of the work in the literature assuming that agents fully know their
own preferences over alternatives. This assumption however is not always
practical (especially in large markets) and agents usually need to go through
some costly deliberation process in order to learn their preferences. In this
paper we assume that such deliberations are carried out via interviews, where
an interview involves a man and a woman, each of whom learns information about
the other as a consequence. If everybody interviews everyone else, then clearly
agents can fully learn their preferences. But interviews are costly, and we may
wish to minimize their use. It is often the case, especially in practical
settings, that due to correlation between agents' preferences, it is
unnecessary for all potential interviews to be carried out in order to obtain a
stable matching. Thus the problem is to find a good strategy for interviews to
be carried out in order to minimize their use, whilst leading to a stable
matching. One way to evaluate the performance of an interview strategy is to
compare it against a naive algorithm that conducts all interviews. We argue
however that a more meaningful comparison would be against an optimal offline
algorithm that has access to agents' preference orderings under complete
information. We show that, unless P=NP, no offline algorithm can compute the
optimal interview strategy in polynomial time. If we are additionally aiming
for a particular stable matching (perhaps one with certain desirable
properties), we provide restricted settings under which efficient optimal
offline algorithms exist.
