Consider the following generalization of the classical [Stable Marriage Problem](https://en.wikipedia.org/wiki/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](https://courses.csail.mit.edu/6.042/spring17/mcs.pdf)). 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](http://www-users.math.umn.edu/~dgrinber/5707s17/mt2s.pdf); 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?



Stable marriage with contracts: is it known?
There is a humongous literature on "matching with contracts", starting with:



> 
> Hatfield, John William, and Paul R. Milgrom. "[Matching with
>  contracts](https://web.stanford.edu/~milgrom/publishedarticles/Matching%20with%20Contracts-AER.pdf)." The American Economic Review 95.4 (2005): 913-935.
> 
> 
> 


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).



> 
> Fleiner, Tamás. "A fixed-point approach to stable matchings and some
>  applications." Mathematics of Operations Research 28.1 (2003):
>  103-126.
> 
> 
> 


It was also shown in



> 
> Echenique, Federico. "Contracts versus salaries in matching." The
>  American Economic Review 102.1 (2012): 594-601.
> 
> 
> 


that the model of Hatfield and Milgrom is equivalent to the model in



> 
> Kelso Jr, Alexander S., and Vincent P. Crawford. "Job matching,
>  coalition formation, and gross substitutes." Econometrica: Journal of
>  the Econometric Society (1982): 1483-1504.
> 
> 
> 


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



> 
> Roth, Alvin E., and Marilda A. Oliveira Sotomayor. "Two-sided
>  matching, volume 18 of Econometric Society Monographs." (1990),
> 
> 
> 


where you can find further references.


