In this chapter, we study some aspects of the problem of stable marriage. There are two distinguished marriage plans: the fully transferable case, where money can be transferred between the participants, and the fully nontransferable case where each participant has its own rigid preference list regarding the other gender. We continue to discuss intermediate partial transferable cases. Partial transferable plans can be approached as either special cases of cooperative games using the notion of a core or as a generalization of the cyclical monotonicity property of the fully transferable case (fake promises). We introduce these two approaches and prove the existence of stable marriage for the fully transferable and nontransferable plans. The marriage problem is a special case of more general assignment problems, which has many application in mathematical economy and logistics, in particular, the assignment of employees to hiring firms. The fully cooperative marriage plan is also a special case of the celebrated problem of optimal mass transport, which is also known as Monge-Kantorovich theory. Optimal transport problem has countless applications in many fields of mathematics, physics, computer science and, of course, economy, transportation and traffic control.
- cyclic monotonicity
- cooperative games
Consider two sets of elements each. We may think about as a set of men and as a set of women. We denote a man in by and a woman in by .
A marriage plan (MP) is a bijection which assign to each man in a unique woman in (and v.v). A matching of a man to a woman is denoted by . The set of all such matchings is isomorphic to the set of permutations on . Evidently, we can arrange the order according to a given marriage plan and represent this plan as .
The MP is called stable if and only if there are no blocking pairs. A blocking pair is composed of a man and a woman such that both prefers over his assigned woman and prefers over her assigned man .
To complete this definition, we have to establish a criterion of preferences over the possible matchings in .
Let us consider two extreme cases. The first is the fully transferable (FT) case [1, 2, 3, 4]. Here we assume a utility value for a potential matching . If are matched, they can split this reward between themselves as they wish.
The second case is fully non-transferable (FNT) [5, 6, 7]. This involves no utility value (and no money reward). Each participant (man or woman) lists the set of participants of the other gender according to a preference list: For each man , there exists an order relation on , such that means that the man will prefer the woman over the woman . Likewise, each woman have its own order relation over .
These two notions seem very different, and indeed they are, not only because the first one seems to defines the preference in materialistic terms and the second hints on “true love.” In fact, we can quantify the nontransferable case as well: There may be a reward for a man marrying a woman , such that iff . Likewise, quantifies the reward the the woman obtains while marrying the man .
Given a matching , a blocking pair in the FNT case is a pair , such that the man prefers the woman over his matched woman (i.e., , or ) and the woman prefers over her matched man (, or ). Thus, a blocking pair is defined by
Definition 1.1. The matching is stable if and only if
Definition 1.1 implies that the condition
Let us consider now the fully transferable (FT) case. Here a married pair can share the rewards for their marriage. Suppose the man cuts and the woman cuts form their mutual reward . Evidently, . If
Evidently, condition (3) is not a sufficient one, unless in the FT case.
A simple example ():
The matching is FNT stable. Indeed while , so both men are happy, and this is enough for FNT stability, since that neither nor is a blocking pair. On the other hand, if the married pairs share their rewards we get
However, we may extend the necessary condition (3) in the FT case as follows:
Consider the couples , . The sum of the rewards for these couples is . Suppose they perform a” chain deal” such that man marries woman for , and the last man marries the first woman . The net reward for the new matching is .
This leads to a definition of a blocking chain:
Definition 1.2. A chain of married couples forms a blocking chain iff
The notion of a blocking chain extends the condition (4) from to . It turns that it is also necessary condition for the stability in the fully transferable case:
Proposition 1.1. If a marriage is a stable one for the FT case then it is cyclically monotone.
Proof. Let be a matching, such that is the cut of man marrying and the cut of the woman marrying . Suppose by negation that is a blocking chain. Since we obtain
We shall see later on that cyclical monotonicity is, actually, an equivalent definition to stability in the FT case.
The notion of cyclical monotonicity implies an additional level of cooperation for the marriage game. Not only the married pair share their utility between themselves via (2), but also different couples are ready to share their reward via a chain deal according to Definition 1.2. If the total reward after the chain exchange exceeds their reward prior to this deal, the lucky ones are ready to share their reward with the unlucky and compensate their losses.
What about the FNT case? Of course there is no point talking about a “chain deal” in that case. However, we may define a “FNT blocking chain” by
where, again, . Definition 1.1 is analogs to the statement that that there are no blocking chains of this form. Thus, a marriage is stable in the FNT case if and only if
At the first sight, definition (7) seems redundant, since it provides no further information. However, we can observe the analogy between (5) and (7). In fact, (7) and (5) are obtained from each other by the exchanges
In Section 2.2, we take advantage on this representation.
2. Partial sharing
Here we present two possible definitions of intermediate marriage game which interpolate between the fully transferable and the non transferable case. The first is based on the notion of core of a cooperative game, and the second is based on cyclic monotonicity.
2.1. Stable marriage as a cooperative game
Assume that we can guarantee a cut for each married man , and a cut for each married woman . In order to define a stable marriage we have to impose some conditions which will guarantee that no man or woman can increase his or her cut by marrying a different partner. For this let us define, for each pair , a pairwise bargaining set which contains all possible cuts for a matching of man with woman .
For each and , are closed sets in , equal to the closure of their interior. Let the interior of .
is monotone in the following sense: If then whenever and .
There exist such that
The meaning of the feasibility set is as follows: Any married couple can guarantee the cut for and for , provided .
Any married couple can guarantee the cut for and for , provided .
Definition 2.1. The feasibility set is composed of all vectors which satisfies
The marriage plan is stable if and only if there exists such that for any .
The FNT case is contained in definition 2.1, where
Indeed, if is a stable marriage plan let and . Then satisfies for any . Since there are no blocking pairs if follows that for any , either or , hence so (Figure 1a).
The FT case (Figure 1b) is obtained by
Indeed, if is a stable marriage plan and are the corresponding cuts satisfying , then for each we obtain (otherwise is a blocking pair). This implies that .
There are other sensible models of partial transfers which fit into the formalism of Definition 2.1 and Theorem 3.1. Let us consider several examples:
Transferable marriages restricted to non-negative cuts: In the transferable case, the feasibility sets may contain negative cuts for the man or for the woman (even though not for both, if it is assumed ). To avoid the undesired stable marriages were one of the partners get a negative cut, we may replace the feasibility set (10) bysee Figure 1c. It can be easily verified that if contains negative components, then , obtained by replacing the negative components by , is in as well. Thus, the core of this game contains vectors in of non-negative elements.
In the transferable case (10), we allowed both men and women to transfer money to their partner. Indeed, we assumed that the man’s cut is and the woman’s cut is , where . Suppose we wish to allow only transfer between men to women, so we insist on . In that case, we choose (Figure 1d)
Let us assume that the transfer from man to woman is taxed, and the tax depends on . Thus, if man transfers to a woman he reduces his cut by , but the woman cut is increased by an amount , were . Here is the tax implied for this transfer. It follows that
where . The geometrical description of us as in Figure 1d, where the dashed line is tilted.
2.2. Stability by fake promises
Suppose a man can make a promise to a married woman (which is not his wife), and vice versa. The principle behind it is that each of them does not intend to honor his/her own promise, but, nevertheless, believes that the other party will honor hers/his. It is also based on both partial sharing inside a married pair, as well as some collaboration between the pairs.
where . In particular
The value of represents the level of internal sharing inside the couple. Thus, means there is no sharing whatsoever, and the condition for a blocking pairs implies that both and gains from the exchange, is displayed in (6).
On the other hand, , namely
We now consider an additional parameter and define the real valued function on :
Note that for any if , while for any real . The parameter represents the level of sharing between the pairs.
Definition 2.2. Let . The matching is stable if for any and
Note that implies that for any . If, in addition, then this inequality implies that i′j′ is not a blocking pair in the FNT case.
On the other hand, implies
Let us interpret the meaning of in the context of utility exchange. A man can offer some bribe to any other women he might be interested in (except his own wife, so ). His cut for marrying is now . The cut of the woman should have been . However, the happy woman has to pay some tax for accepting this bribe. Let be the fraction of the bribe she can get (after paying her tax). Her supposed cut for marrying is just . Woman will believe and accept offer from man if two conditions are satisfied: the offer should be both
Competitive, namely .
Trusted, if woman believes that man is motivated. This implies .
The two conditions above can be satisfied, and the offer is acceptable, only if
Symmetrically, man will accept an offer from a woman only if
The utility of the exchange to is, then defined by the minimum of (14, 15) via (12).
To understand the role of , consider the chain of pairs exchanges
Each of the pair exchange yields a utility for the new pair. The lucky new pairs in this chain of couples exchange are those who makes a positive reward. The unfortunate new pairs are those who suffer a loss (negative reward). The lucky pairs, whose interest is to activate this chain, are ready to compensate the unfortunate ones by contributing some of their gained utility. The chain will be activated (and the original marriages will break down) if the mutual contribution of the fortunate pairs is enough to cover at least the part of the mutually loss of utility of the unfortunate pairs. This is the condition
Stability by Definition 2.2 grantees that no such chain is activated.
3. Existence of stable marriage plans
In the general case of Assumption 2.1, the existence of a stable matching follows from the following Theorem:
Theorem 3.1. Let defined as follows:
an injection such that where , Then there exists such that
The set of vectors in satisfying (16) is called the core. Note that the core is identified with the set of vector in which satisfy the condition . Hence Definition 2.1 can be recognized as the nonemptiness of the core, which is equivalent to the existence of a stable matching.
Theorem 3.1 is, in fact, a special case of the celebrated Theorem of Scarf  for cooperative games, tailored to the marriage scenario (see also [12, 13]). As we saw, it can be applied to the fully nontransferable case (9), as well as to the fully transferable case (10).
3.1. Gale-Shapley algorithm in the non-transferable case
Here we describe the celebrated, constructive algorithm due to Gale and Shapley .
At the first stage, each man proposes to the woman at the top of his list. At the end of this stage, some women got proposals (possibly more than one), other women may not get any proposal.
At the second stage, each woman who got more than one proposal binds the man whose proposal is most preferable according to her list (who is now engaged). She releases all the other men who proposed. At the end of this stage, the men’s set is composed of two parts: engaged and released.
At the next stage, each released man makes a proposal to the next woman in his preference list (whenever she is engaged or not).
Back to stage 2.
It is easy to verify that this process must end at a finite number of steps. At the end of this process, all women and men are engaged. This is a stable matching!
Of course, we could reverse the role of men and women in this algorithm. In both cases, we get a stable matching. The algorithm we indicated is the one which is best from the men’s point of view. In the case where the women propose, the result is best for the women. In fact.
Theorem 3.2.  For any NT stable matching , the rank of the woman according to man is at most the rank of the woman matched to by the above, men proposing algorithm.
3.2. Variational formulation in the fully transferable case
There are several equivalent definitions of stable marriage plan in the FT case. Here we introduces two of these.
Recall that if is given by (11) the feasibility set (Definition 2.1) takes the form
Recall also Definition 1.2 for cyclical monotonicity.
Theorem 3.3 is a stable marriage plan in the FT case if and only if one of the following equivalent conditions is satisfied:
Efficiency (or maximal public utility): for any marriage plans .
is cyclically monotone.
Optimality: The minimal sum of cuts in the feasibility set (17) satisfies (i.e., is in the core).
Since the set of all bijections is finite and the maximum on a finite set is always achieved, we obtain from the efficiency characterization.
Corollary 3.1. There always exists a stable marriage plan in the FT case.
Remark 3.1 As far as we know, the fully transferable case (17) is the only case whose stable marriages are obtained by a variational argument.
Proof. (of theorems 3.3) In Proposition 1.1, we obtained that FT stability implies cyclical monotonicity. We now prove that cyclical monotonicity implies efficiency. The proof follows the idea published originally by Afriat  and was introduced recently in a much simpler form by Brezis .
Let and consider a chain realizing
By cyclic monotonicity, . Since ,
Hence, for any
where the last inequality follows by the substitution of the cycle in (18). Since is any number bigger than it follows
Since is a bijection on as well, so . Then, sum (22) over to obtain
To prove that any efficient solution is stable, we define so
Then (21) implies
Finally, the optimality condition follows immediately from the definition of the feasibility set
3.3. On existence and nonexistence of stable fake promises
Theorem 3.4 If the matching is stable, then it is also stable for and .
The proof of this Theorem follows from the definitions (12, 13) and the following.
Lemma 3.1. For any, and ,
Proof. For and define
Observe that . In addition, is monotone not increasing in . A straightforward calculation yields
What can be said about the existence of s stable matching in the general case? Unfortunately, we can prove now only a negative result:
Proposition 3.1. For any , a stable marriage does not exist unconditionally.
Proof. We only need to present a counter-example. So, let . To show that the matching is not stable we have to show
By definition (12) and Lemma 3.1
where . To obtain we just have to exchange man with man , so
All in all, we only have four parameters to play with:
Let us insert . where . So
Conjecture 1 If then there always exists a stable marriage (c.f. Figure 2).
We considered several paradigms of marriage plans between two sets of different genders and the same cardinality. In particular, the extreme cases of completely transferable and completely nontransferable marriage plans. In the completely transferable case, we proved that all stable matching are obtained by an optimization which maximizes the sum of the rewards of the participants. In the completely nontransferable case, the stable marriage plane is obtained as a result of a constructive algorithm due to Gale and Shapley.
We also introduced two paradigms for partially transferable marriage plans. The first paradigm is based on a special case of cooperative coalition games, and quoted (without a proof) the theorem on existence of a stable marriage plan in that setting. The second paradigm is based on extending the notion of cyclical monotonicity which characterizes the fully transferable case. The existence of stable marriage plan in the intermediate cases of the second paradigm is still an open problem.
The marriage problem is a special case of more general assignment problems which has many application in mathematical economy and logistics. In general, the two sets of men and women can be replaced by two sets of any number of agents (e.g., firms and employees), and the 1–1 assignment in the marriage case be replaced by any number to one assignments (e.g., several employees to a given firm), allowing also the possibility of unemployment. Both paradigms introduced in this paper can be extended to include these more general cases.
From another point of view, the fully cooperative marriage plan is also a special case of the celebrated problem of optimal mass transport, also known as Monge-Kantorovich theory, after the French mathematician Monge who lived in Napoleon’s time, and the soviet mathematician Kantorovich who won the Nobel prize in Economics in 1975. Optimal transport problem has countless applications in many fields such as mathematics, physics, computer science and, of course, economy, transportation, and traffic control.
The author wishes to thank the Israel Science foundation grant 988/15.
- which was turned to my attention by R. McCann.