Consider the following generalization of the classical Stable Marriage Problem. The rough idea is that instead of merely specifying who marries whom, a matching now chooses a set of "marriage contracts" (out of a given set, which may be large since a man and a woman can choose between several different contracts for marrying each other); correspondingly the men and the women rank not their potential partners but rather the potential contracts available to them (e.g., a given man $m$ can prefer marrying a woman $w_1$ via a contract $c_1$ to marrying a woman $w_2$ via a contract $c_2$, but at the same time prefer marrying $w_2$ via $c_2$ to marrying $w_1$ via a different contract $c_3$). In detail, the generalized problem is stated as follows:
Contracted Stable Marriage Problem. Suppose that we have a population of $k$ men and $k$ women
(for some $k \in \mathbb{N}$).
Assume furthermore that a finite set $C$ of "contracts" is given.
Each contract involves exactly one man and exactly
one woman.
(Think of the contracts as marriage contracts, each prepared for some man and some woman, but not signed.)Assume that, for each pair $\left(m, w\right)$ consisting of a man $m$
and a woman $w$, there is at least one contract
that involves $m$ and $w$.Suppose that each person has a preference list of all the
contracts that involve him/her; i.e., he/she ranks
all contracts that involve him/her in the order of
preferability.
(No ties are allowed.)A matching shall mean a subset $K$ of $C$ such
that each man is involved in exactly one contract in $K$,
and such that each woman is involved in exactly one
contract in $K$.
Thus, visually speaking, a matching is a way to marry off
all $k$ men and all $k$ women to each other (in the
classical meaning of the word — i.e., heterosexual and
monogamous)
by having them sign some of the contracts in $C$
(of course, each person signs exactly one contract).If $p$ is a person and $K$ is a matching, then the
unique contract $c \in K$ that involves $p$ will be called
the $K$-marriage contract of $p$.If $K$ is a matching and $c \in C$ is a contract, then
the contract $c$ is said to be rogue (for $K$) if
this contract $c$ is not in $K$,
the man involved in $c$ prefers $c$ to his
$K$-marriage contract, andthe woman involved in $c$ prefers $c$ to her
$K$-marriage contract.Thus, roughly speaking, a rogue contract is a contract
$c$ that has not been signed in the matching $K$, but that
would make both persons involved in $c$ happier than
whatever contracts they did sign in $K$.A matching $K$ is called stable if there exist
no rogue contracts for $K$.The problem now asks you to find a stable matching.
Theorem. A stable matching always exists.
The proof of the above theorem is a fairly straightforward modification of the classical proof of the Gale-Shapley Stable Marriage Theorem (which is discussed in several places, the most readable one perhaps being Section 6.4 of Eric Lehman, F. Thomson Leighton, Albert R. Meyer, Mathematics for Computer Science, revised 16th April 2017). In generalizing it, I was motivated by an elegant solution of a graph-theoretical exercise suggested by Alex Postnikov (Exercise 3 on UMN Spring 2017 Math 5707 midterm #2; see its Second Solution for Postnikov's argument).
But I am left wondering: Is the above Theorem, and the problem it answers, known? I suspect it has further applications, which the (standard) Stable Marriage Theorem is a tad too narrow to handle, as the latter treats a marriage as uniquely determined by the two partners involved.
One thing the added generality seems well-equipped to model is "matching with dowry"; i.e., a marriage should come with a payment from one partner to the other, and the preferability of the marriage depends on this payment. (At least if the set of all possible payments is finite, this is easily obtained as a particular case of the Contracted Stable Marriage Problem by formulating a contract for each possible payment.) This rather unromantic modification appears suited for various real-life applications of the Stable Marriage Problem, given that few of them involve actual marriages. At least this case is probably known?
Best Answer
There is a humongous literature on "matching with contracts", starting with:
The existence result of that paper is actually a special case of the earlier, even up to the basic proof approach (via Tarski's fixed point theorem).
It was also shown in
that the model of Hatfield and Milgrom is equivalent to the model in
There exists also generalizations that are genuinely new and the matching with contracts model is pretty much the state of the art of stable matching theory in economics. There is also a large and even older literature on matching with transferable utility or imperfect transferable utility, which covers the "dowry case". This material can even be found in the classic textbook
where you can find further references.