Open access peer-reviewed chapter

Happy Family of Stable Marriages

By Wolansky Gershon

Submitted: April 10th 2018Reviewed: May 8th 2018Published: November 5th 2018

DOI: 10.5772/intechopen.78406

Downloaded: 657


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
  • core
  • cooperative games
  • Monge-Kantorovich

1. Introduction

Consider two sets Im,Iwof Nelements each. We may think about Imas a set of men and Iwas a set of women. We denote a man in Imby iand a woman in Iwby i.

A marriage plan(MP) is a bijection which assign to each man in Ima unique woman in Iw(and v.v). A matching of a man iImto a woman jIwis denoted by ij. The set of all such matchings is isomorphic to the set of permutations on 1N. Evidently, we can arrange the order according to a given marriage plan and represent this plan as ii;i=1N.

The MP iiis called stableif and only if there are no blocking pairs. A blocking pair is composed of a man iand a woman jisuch that bothiprefers jover his assigned woman iand jprefers iover her assigned man j.

To complete this definition, we have to establish a criterion of preferences over the possible matchings in Im×Iw.

Let us consider two extreme cases. The first is the fully transferable(FT) case [1, 2, 3, 4]. Here we assume a utility valueθijfor a potential matching ij. If ijare matched, they can split this reward θijbetween 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 iIm, there exists an order relation ion Im, such that jikmeans that the man iwill prefer the woman jover the woman k. Likewise, each woman iIwhave its own order relation iover Im.

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 θijmfor a man imarrying a woman j, such that jikiff θijm>θikm. Likewise, θijwquantifies the reward the the woman jobtains while marrying the man i.

Given a matching ii, a blocking pair in the FNT case is a pair ij, jisuch that the man iprefers the woman jover his matched woman i(i.e., jii, or θijm>θiim) andthe woman jprefers iover her matched man j(jii, or θijw>θjjw). Thus, a blocking pair ijis defined by


Definition 1.1.The matchingii;is stable if and only if

for anyi,jImandi,jIw.



Definition 1.1 implies that the condition

is necessaryfor all i,jfor the stability of iiin the FNT case.

Let us consider now the fully transferable (FT) case. Here a married pair iican share the rewards θiifor their marriage. Suppose the man icuts uiand the woman icuts viform their mutual reward θii. Evidently, ui+vi=θii. If

for some jithen ijis a blocking pair, since both iand jcan increase their cuts to match the mutual reward θij. Hence
so (3) is a necessary condition for the stability in the FT case as well.

Evidently, condition (3) is nota sufficient one, unless N=2in the FT case.

A simple example (N=2):


The matching 1122is FNT stable. Indeed θ11m=1>θ12m=0while θ22m=1>θ21m=0, so both men are happy, and this is enough for FNT stability, since that neither 12nor 21is a blocking pair. On the other hand, if the married pairs share their rewards θij=θijm+θijwwe get

thus 2112is the stable marriage in the FT case.

However, we may extend the necessary condition (3) in the FT case as follows:

Consider the couples i1i1,ikik, k2. The sum of the rewards for these couples is l=1kθilil. Suppose they perform a” chain deal” such that man ilmarries woman il+1for 1lk1, and the last man ikmarries the first woman i1. The net reward for the new matching is l=1k1θilil+1+θiki1.

This leads to a definition of a blocking chain:

Definition 1.2.A chaini1i1,ikikof married couples forms a blocking chain iff

whereik+1i1. If there are no blocking chains then the matchingiiis called cyclically monotone[8].

The notion of a blocking chain extends the condition (4) from k=2to k2. It turns that it is also necessary condition for the stability in the fully transferable case:

Proposition 1.1.If a marriageiiis a stable one for the FT case then it is cyclically monotone.

Proof.Let iibe a matching, such that uiis the cut of man imarrying iand vithe cut of the woman imarrying i. Suppose by negation that i1i1ikikis a blocking chain. Since ui+viθiiwe obtain

so, in particular, there exists a pair ilil+1for which θilil+1>uil+vil+1. Hence ilil+1is a blocking pair via (4). ⃞

We shall see later on that cyclical monotonicity is, actually, an equivalent definitionto 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” i1i1ikikby


where, again, ik+1i1. Definition 1.1 is analogs to the statement that that there are no blocking chains of this form. Thus, a marriage iiis stable in the FNT case if and only if

for any chain deal i1i1ikik.

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

This part follows some of the ideas in Galichon et al. and references therein1 [9]. See also [10].

Assume that we can guarantee a cut uifor each married man i, and a cut vjfor each married woman j. 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 ij, a pairwise bargaining setFijR2which contains all possible cuts uivjfor a matching of man iwith woman j.

Assumption 2.1

  1. For each iImand jIw, Fijare closed sets in R2, equal to the closure of their interior. Let F0ijthe interior of Fij.

  2. Fijis monotone in the following sense: If uvFijthen uvFijwhenever uuand vv.

  3. There exist C1,C2Rsuch that


for anyiIm,jIw.

The meaning of the feasibility set is as follows:

Any married couple ijIm×Iwcan guarantee the cut ufor iand vfor j, provided uvFij.

Definition 2.1.Thefeasibility set VFR2Nis composed of all vectorsu1uNv1vNwhich satisfies

for anyijIm×Iw

The marriage planiiis stable if and only if there existsu1vNVFsuch thatuiviFiifor anyi1N.

The FNT case is contained in definition 2.1, where


Indeed, if iiis a stable marriage plan let ui=θiimand vi=θiiw. Then u1vNsatisfies uiviFfor any i1N. Since there are no blocking pairs if follows that for any ji, either θijm>θii=uior θijw>θjjw=vj, hence uivjR2F0ijso u1vNVF(Figure 1a).

Figure 1.

Pairwise bargaining sets.

The FT case (Figure 1b) is obtained by


Indeed, if iiis a stable marriage plan and u1vNare the corresponding cuts satisfying ui+vj=θij, then for each jiwe obtain ui+vjθij(otherwise ijis a blocking pair). This implies that uivjR2F0ij.

There are other sensible models of partial transferswhich fit into the formalism of Definition 2.1 and Theorem 3.1. Let us consider several examples:

  1. Transferable marriages restricted to non-negative cuts: In the transferable case, the feasibility sets may contain negative cuts for the man uor for the woman v(even though not for both, if it is assumed θij>0). To avoid the undesired stable marriages were one of the partners get a negative cut, we may replace the feasibility set (10) by

    see Figure 1c. It can be easily verified that if u1vNVFcontains negative components, then u1+vN+, obtained by replacing the negative components by 0, is in VFas well. Thus, the core of this game contains vectors in VFof 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 icut is θijmwand the woman’s jcut is θijw+w, where wR. Suppose we wish to allow only transfer between men to women, so we insist on w0. In that case, we choose (Figure 1d)

  • FijuvR2u+vθijuθijm.E11
    1. Let us assume that the transfer wfrom man ito woman jis taxed, and the tax depends on i,j. Thus, if man itransfers w>0to a woman jhe reduces his cut by w, but the woman cut is increased by an amount βi,jw, were βi,j01. Here 1βi,jis the tax implied for this transfer. It follows that




      where θijβθijm+βi,j1θijw. The geometrical description of Fus 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 0q1. In particular


    The value of qrepresents the level of internal sharinginside the couple. Thus, q=0means there is no sharing whatsoever, and the condition Δ0ij>0for a blocking pairs implies that both iand jgains from the exchange, is displayed in (6).

    On the other hand, Δ1ij+Δ1ji>0, namely

    is, as we argued, a necessary condition for a blocking pair in FT case, where θrepresents the sum of the rewards to of the pair via (2).

    We now consider an additional parameter p01and define the real valued function on R:


    Note that xp=xfor any pif x0, while x1=xfor any real x. The parameter prepresents the level of sharing between the pairs.

    Definition 2.2.Let0p,q1. The matchingiiispqstable if for anykNandi1,i2,ik1N


    Note that p=0implies that Δqij0for anyji. If, in addition, q=0then this inequality implies that i′j′ is not a blocking pair in the FNT case.

    On the other hand, p=1implies

    which is reduced to (5) if q=1as well.

    Let us interpret the meaning of q,pin the context of utility exchange. A man iImcan offer some bribe wto any other women jhe might be interested in (except his own wife, so ji). His cut for marrying jis now θijmw. The cut of the woman jshould have been θijw+w. However, the happy woman has to pay some tax for accepting this bribe. Let q01be the fraction of the bribe she can get (after paying her tax). Her supposed cut for marrying iis just θijw+qw. Woman jwill believe and accept offer from man iif two conditions are satisfied: the offer should be both

    1. Competitive, namely θijw+qwθjjw.

    2. Trusted, if woman jbelieves that man iis motivated. This implies θijmwθiim.

    The two conditions above can be satisfied, and the offer is acceptable, only if


    Symmetrically, man iwill accept an offer from a woman jionly if


    The utilityof the exchange iito ijis, then defined by the minimum Δqijof (14, 15) via (12).

    To understand the role of p, consider the chain of pairs exchanges


    Each of the pair exchange ilililil+1yields a utility Δqilil+1for 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 leastthe ppart 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.LetWFR2Ndefined as follows:


    an injection τ:ImIwsuch that uiviFiiwhere i=τi, iIm.Then there exists u1uNv1vNWFsuch that

    for any ijIm×Iw.

    The set of vectors in WFsatisfying (16) is called the core. Note that the core is identified with the set of R2Nvector in VFwhich satisfy the condition uiviFii. 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 [11] 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).

    Theorem 3.1 implies, in particular, the existence of stable marriage in the FNT case corresponding to p=q=0or (9), as well as for the FT case corresponding to p=q=1or (10).

    3.1. Gale-Shapley algorithm in the non-transferable case

    Here we describe the celebrated, constructive algorithm due to Gale and Shapley [5].

    1. At the first stage, each man iImproposes to the woman jIwat 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.

    2. 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 Imis composed of two parts: engaged and released.

    3. At the next stage, each releasedman makes a proposal to the nextwoman in his preference list (whenever she is engaged or not).

    4. 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.[14] For any NT stable matchingii, the rank of the womaniaccording to maniis at most the rank of the woman matched toiby 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 Fis given by (11) the feasibility set VF(Definition 2.1) takes the form


    Recall also Definition 1.2 for cyclical monotonicity.

    Theorem 3.3iiis 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): i=1Nθiii=1Nθifor any marriage plans σ:ImIw.

    • iiis cyclically monotone.

    • Optimality: The minimal sum 1Nui0+vi0of cuts in the feasibility set (17) satisfies ui0+vi0=θii(i.e., u10vN0is in the core).

    The efficiency characterization of stable marriage connects this notion with optimal transport and the celebrated Monge Kantorovichtheory [15, 16, 17]. See also [18].

    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.1As 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 [19] and was introduced recently in a much simpler form by Brezis [20].



    Let α>ui0and consider a kchain realizing


    By cyclic monotonicity, l=1kθililθilil+10. Since ik+1=i1,

    so (19) implies
    in particular ui0<.

    Hence, for any jIm


    where the last inequality follows by the substitution of the k+1cycle i1=i,i2,,ik,ik+1=iin (18). Since αis any number bigger than ui0it follows

    for any pair i,jIm. Now, let σbe any permutation in Imand let j=σi. Then

    Since σis a bijection on Imas well, so Σi=1Nui0=i=1Nuσi0. Then, sum (22) over 1iNto obtain

    so iiis an efficient marriage plan.

    To prove that any efficient solution is stable, we define vj0θjjuj0so


    Then (21) implies

    for any i,j. Thus, (23, 24) establish that iiis a stable marriage via Definition 2.1.

    Finally, the optimality condition follows immediately from the definition of the feasibility set

    for any bijection σ:ImIwand from (23).⃞

    3.3. On existence and nonexistence of stable fake promises

    Theorem 3.4If the matchingiiispqstable, then it is alsopqstable forppandqq.

    The proof of this Theorem follows from the definitions (12, 13) and the following.

    Lemma 3.1.For any,ijand1q>q0,


    Proof.For a,bRand r01define


    Observe that Δ1abminab. In addition, rΔrabis monotone not increasing in r. A straightforward calculation yields

    and the Lemma follows from the above observation, upon inserting a=θmijθmiiand b=θwijθwjj. ⃞

    What can be said about the existence of s pqstable matching in the general case? Unfortunately, we can prove now only a negative result:

    Proposition 3.1.For any1q>p0, a stable marriage does not exist unconditionally.

    Proof.We only need to present a counter-example. So, let N=2. To show that the matching 11,22is not stable we have to show

    while, to show that 12,21is not stable we have to show

    By definition (12) and Lemma 3.1


    where r=1q1+q. To obtain Δq11,Δq22we just have to exchange man 1with man 2, so


    All in all, we only have four parameters to play with:

    so the two conditions to be verified are

    Let us insert a1=a2a>0. b1=b2bwhere b>0. So

    while Δra1b2=Δrb1a2=ba2r2a+b. In particular, the condition ab<1r1+rimplies Δra1b2p=Δrb1a2p>0which verifies (26). On the other hand, if apb>0then (25) is verified. Both conditions can be verified if 1r1+r>p. Recalling q=1r1+rwe obtain the result.

    Conjecture 1If0<p<q<1then there always exists apqstable marriage(c.f. Figure 2).

    Figure 2.

    Conjecture: Is there an unconditional existence of stable marriages in the gray area?.


    4. Conclusions

    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.

    © 2018 The Author(s). Licensee IntechOpen. This chapter is distributed under the terms of the Creative Commons Attribution 3.0 License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

    How to cite and reference

    Link to this chapter Copy to clipboard

    Cite this chapter Copy to clipboard

    Wolansky Gershon (November 5th 2018). Happy Family of Stable Marriages, Game Theory - Applications in Logistics and Economy, Danijela Tuljak-Suban, IntechOpen, DOI: 10.5772/intechopen.78406. Available from:

    chapter statistics

    657total chapter downloads

    More statistics for editors and authors

    Login to your personal dashboard for more detailed statistics on your publications.

    Access personal reporting

    Related Content

    This Book

    Next chapter

    Stochastic Leader-Follower Differential Game with Asymmetric Information

    By Jingtao Shi

    Related Book

    First chapter

    The Neumann-Morgenstern Project – Game Theory as a Formal Language for the Social Sciences

    By Hardy Hanappi

    We are IntechOpen, the world's leading publisher of Open Access books. Built by scientists, for scientists. Our readership spans scientists, professors, researchers, librarians, and students, as well as business professionals. We share our knowledge and peer-reveiwed research papers with libraries, scientific and engineering societies, and also work with corporate R&D departments and government entities.

    More About Us