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: 253

Abstract

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.

Keywords

  • 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 stable if and only if there are no blocking pairs. A blocking pair is composed of a man iand a woman jisuch that both iprefers 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) and the woman jprefers iover her matched man j(jii, or θijw>θjjw). Thus, a blocking pair ijis defined by

minθijmθiimθijwθjjw>0E1

Definition 1.1. The matching ii;is stable if and only if

minθijmθiimθijwθjjw0
for any i,jImand i,jIw.

Let

θijθijm+θijw.E2

Definition 1.1 implies that the condition

θii+θjjθij+θjiE3
is necessary for 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

ui+vj<θijE4
for some jithen ijis a blocking pair, since both iand jcan increase their cuts to match the mutual reward θij. Hence
θij+θji>ui+vj+uj+vi=θii+θjj
so (3) is a necessary condition for the stability in the FT case as well.

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

A simple example (N=2):

θmw1w2θww1w2m110;m115m201m201

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

θw1w2m125m202
so
θ11+θ22=4<5=θ12+θ21,
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 chain i1i1,ikikof married couples forms a blocking chain iff

l=1kθilil+1θilil>0E5
where ik+1i1. If there are no blocking chains then the matching iiis 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 marriage iiis 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

l=1kθilil+1>l=1kθilill=1kuil+vil=l=1kuil+vil+1
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 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” i1i1ikikby

max1lkminθilil+1mθililmθilil+1wθililw>0E6

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

max1lkminθilil+1mθililmθilil+1wθililw0E7
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

θilil+1θililminθilil+1mθililmθilil+1wθililwand1kmax1ikE8

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 set FijR2which 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

    uvmax(uv)C2Fijuvu+vC1

for any iIm,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. The feasibility set VFR2Nis composed of all vectors u1uNv1vNwhich satisfies

uivjR2F0ij
for any ijIm×Iw

The marriage plan iiis stable if and only if there exists u1vNVFsuch that uiviFiifor any i1N.

The FNT case is contained in definition 2.1, where

Fijuθijmvθijw.E9

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

Fijuvu+vθij.E10

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 transfers which 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

    FijuvR2u+vθijmaxuvθij,
    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

      uiθijmw;vjθijw+βi,jw,w0

      Hence

      FijuvR2ui+βi,j1vjθijβuiθijm,

      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.

    Define

    Δqijminqθijmθiim+θijwθjjwq(θijwθjjw+θijmθiim,E12

    where 0q1. In particular

    Δ0ijminθijmθiimθijwθjjwΔ1ijθijmθiim+θijwθiiwθijθii.

    The value of qrepresents the level of internal sharing inside 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

    θii+θjj<θij+θji
    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:

    xxpx+pxE13

    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. Let 0p,q1. The matching iiis pqstable if for any kNand i1,i2,ik1N

    l=1kΔqilil+1p0whereik+1=i1
    where ik+1i1.

    Note that p=0implies that Δqij0for any ji. 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

    l=1kΔqilil+10where
    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

    qθijmθiim+θijwθjjw>0.E14

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

    qθijwθiiw+θijmθjjm>0.E15

    The utility of 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

    i1i1i1i2,ik1ik1ik1ik,ikikiki1.

    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 least the ppart of the mutually loss of utility of the unfortunate pairs. This is the condition

    Δqilil+1>0Δqilil+1+pΔqilil+1<0Δqilil+1l=1kΔqilil+1p>0.

    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 WFR2Ndefined as follows:

    u1uNv1vNWF,

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

    uivjR2F0ijE16
    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 released man makes a proposal to the next woman 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 matching ii, the rank of the woman iaccording to man iis at most the rank of the woman matched to iby 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

    VFu1vNR2Nui+vjθijijIm×Iw.E17

    Recall also Definition 1.2 for cyclical monotonicity.

    Theorem 3.3 iiis 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 Kantorovich theory [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.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 [19] and was introduced recently in a much simpler form by Brezis [20].

    Let

    ui0infkchains,kNl=1k1θililθilil+1+θikikθiki.E18

    Let α>ui0and consider a kchain realizing

    α>l=1k1θililθilil+1+θikikθikiE19

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

    l=1k1θililθilil+1θiki1θikik
    so (19) implies
    α>θik,i1θik,i0,
    in particular ui0<.

    Hence, for any jIm

    α+θiiθij>l=1k1θil,ilθil,il+1+θikikθiki+θiiθijuj0E20

    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

    ui0+θiiθijuj0,E21
    for any pair i,jIm. Now, let σbe any permutation in Imand let j=σi. Then
    ui0+θiiθiuσi0.E22

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

    i=1Nθiii=1Nθi,
    so iiis an efficient marriage plan.

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

    uj0+vj0=θjj.E23

    Then (21) implies

    ui0+vj0=ui0+θjjuj0ui0ui0+θij=θijE24
    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

    1Nui+vi=1Nui+vσi1Nθi
    for any bijection σ:ImIwand from (23).⃞

    3.3. On existence and nonexistence of stable fake promises

    Theorem 3.4 If the matching iiis pqstable, then it is also pqstable for ppand qq.

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

    Lemma 3.1. For any, ijand 1q>q0,

    1+q1Δqij>1+q1Δqij.

    Proof. For a,bRand r01define

    Δrab12a+br2ab.

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

    minqa+bqb+a=Δ1qa+bqb+a=q+1Δ1q1+qab,
    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 any 1q>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

    Δq12p+Δq21p>0E25
    while, to show that 12,21is not stable we have to show
    Δq11p+Δq22p>0.E26

    By definition (12) and Lemma 3.1

    Δq12=q+1Δrθ12mθ11mθ12wθ22wΔq21=q+1Δrθ21mθ22mθ21wθ11w

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

    Δq22=q+1Δrθ22mθ21mθ22wθ12wΔq11=q+1Δrθ11mθ12mθ11wθ21w.

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

    a1θ12mθ11m,a2=θ12wθ22w,b1=θ21mθ22m,b2=θ21wθ11w,
    so the two conditions to be verified are
    Δra1a2p+Δrb1b2p>0;Δra1b2p+Δrb1a2p>0.

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

    Δra1a1p=a,Δrb1b2p=pb,
    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 1 If 0<p<q<1then there always exists a pqstable 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.

    Acknowledgments

    The author wishes to thank the Israel Science foundation grant 988/15.

    Notes

    • 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

    253total 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