  We consider two-sided matching markets, and study the incentives of agents to
circumvent a centralized clearing house by signing binding contracts with one
another. It is well-known that if the clearing house implements a stable match
and preferences are known, then no group of agents can profitably deviate in
this manner.
  We ask whether this property holds even when agents have incomplete
information about their own preferences or the preferences of others. We find
that it does not. In particular, when agents are uncertain about the
preferences of others, every mechanism is susceptible to deviations by groups
of agents. When, in addition, agents are uncertain about their own preferences,
every mechanism is susceptible to deviations in which a single pair of agents
agrees in advance to match to each other.

Computer Science and Game Theory