9
$\begingroup$

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?

$\endgroup$
11
$\begingroup$

There is a humongous literature on "matching with contracts", starting with:

Hatfield, John William, and Paul R. Milgrom. "Matching with contracts." 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.

$\endgroup$
  • 1
    $\begingroup$ It might be also worth pointing out that much of this literature concerns many-to-one matching such as several workers being matched with a firm. The marriage versions tend to be easier. $\endgroup$ – Michael Greinecker Apr 19 '17 at 21:20
  • $\begingroup$ Okay, thanks. I admit that I don't fully understand the model in Hatfield-Milgrom, as the $C_D, C_d, C_H, C_h$ confuse me, but it does seem that Theorem 3 covers my result (matching each hospital with only one doctor should satisfy "contracts are substitutes for the hospitals", right?). $\endgroup$ – darij grinberg Apr 20 '17 at 3:20
  • $\begingroup$ @darijgrinberg Yes, substitutability holds automatically in 1-1 matching. $\endgroup$ – Michael Greinecker Apr 20 '17 at 4:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.