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, and
the 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?
