  The stable marriage problem, as addressed by Gale and Shapely [1] consists of
providing a bipartite matching between n " boys " and n " girls "-each of whom
have a totally ordered preference list over the other set-such that there
exists no " boy " and no " girl " that would prefer each other over their
partner in the matching. In this paper, we analyze the cases of strategic play
by the " boys " in the game directly inspired by this problem. We provide an
O(n^3) algorithm for determining a matching which is not necessarily stable in
the Gale-Shapely sense, but it is coalition-stable, in that no player has a
selfish interest to leave the resulting grand coalition to join any potential
alternative one which might feasibly form, and is also man-optimal. Thus, under
a realistic assumption set, no player has an interest to " destabilize " the
matching, even though he theoretically could. The resulting matching is often
better than the na\"ive Gale-Shapely one for some (not all) of the " boys " ,
being no worse for the rest. This matching is more realistic (stable) than the
one produced by top-trading-cycles method, thus offering a qualitative
improvement over the latter. Furthermore, we analyze the situation when players
are allowed to make strategic threats (i.e. be willing to sacrifice their own
outcome to hurt others), offer a relevant example to illustrate the benefits of
this form of play, and ultimately provide an exponential time algorithm which
tries to determine a good threat-making strategy. We then briefly examine a few
other non-conventional possibilities a player has to affect his outcome. Most
common variations to the game model are also described and analyzed with regard
to applicability of the methods in this paper. Finally, a few examples of
real-life problems which can be modeled and solved with the methods in this
paper are presented.
