  Stable matching in a community consisting of men and women is a classical
combinatorial problem that has been the subject of intense theoretical and
empirical study since its introduction in 1962 in a seminal paper by Gale and
Shapley, who designed the celebrated ``deferred acceptance'' algorithm for the
problem.
  In the input, each participant ranks participants of the opposite type, so
the input consists of a collection of permutations, representing the preference
lists. A bipartite matching is unstable if some man-woman pair is blocking:
both strictly prefer each other to their partner in the matching. Stability is
an important economics concept in matching markets from the viewpoint of
manipulability. The unicity of a stable matching implies non-manipulability,
and near-unicity implies limited manipulability, thus these are mathematical
properties related to the quality of stable matching algorithms.
  This paper is a theoretical study of the effect of correlations on
approximate manipulability of stable matching algorithms. Our approach is to go
beyond worst case, assuming that some of the input preference lists are drawn
from a distribution. Our model encompasses a discrete probabilistic process
inspired by a popularity model introduced by Immorlica and Mahdian, that
provides a way to capture correlation between preference lists. Approximate
manipulability is approached from several angles : when all stable partners of
a person have approximately the same rank; or when most persons have a unique
stable partner. Another quantity of interest is a person's number of stable
partners. Our results aim to paint a picture of the manipulability of stable
matchings in a ``beyond worst case'' setting.

Data Structures and Algorithms;Computers and Society;Discrete Mathematics;Computer Science and Game Theory