Happy family of stable marriages

Happy family of stable marriages

\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 non transferable 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 shall introduced these two approaches, and prove the existence of stable marriage for the fully transferable and non-transferable plans. } \vskip .2in Keywords: Cyclic monotonicity, core, cooperative games, Monge-Kantorovich

Introduction

Consider two sets ${\cal I}_m,{\cal I}_w$ of $N$ elements each. We may think about ${\cal I}_m$ as a set of men and ${\cal I}_w$ as a set of women. We denote a man in ${\cal I}_m$ by $i$ and a woman in ${\cal I}_w$ by $i^{'}$.

A {\em marriage plan} (MP) is a bijection which assign to each man in ${\cal I}_m$ a unique woman in ${\cal I}_w$ (and v.v). A matching of a man $i\in{\cal I}_m$ to a woman $j^{'}\in{\cal I}_w$ is denoted by $ij^{'}$. The set of all such matchings is isomorphic to the set of permutations on $\{1, \ldots N\}$. Evidently, we can arrange the order according to a given marriage plan and represent this plan as $ \{ii^{'}\}; i=1\ldots N$.

The MP $\{ii^{'}\}$ is called {\em stable} if and only if there are no {\em blocking pairs}. A blocking pair is composed of a man $i$ and a woman $j^{'}\not=i^{'}$ such that {\em both} $i$ prefers $j^{'}$ over his assigned woman $i^{'}$ and $j^{'}$ prefers $i$ over her assigned man $j$.

In order to complete this definition we have to establish a criterion of preferences over the possible matchings in ${\cal I}_m\times {\cal I}_w$. Let us consider two extreme cases. The first is the {\em fully transferable} (FT) case shap1, SS, Bec1,Bec2. Here we assume a {\em utility value} $\theta_{ij^{'}}$ for a potential matching $ij^{'}$. If $ij^{'}$ are matched, they can split this reward $\theta_{ij^{'}}$ between themselves as they wish.

The second case is fully non-transferable (FNT) GSH, knu, Dub. This involves no utility value (and no money reward). Each participant (man or woman) list the set of participants of the other gender according to a preference list: For each man $i\in{\cal I}_m$ there exist an order relation $\succ_i$ on ${\cal I}_m$, such that $j^{'}\succ_i k^{'}$ means that the man $i$ will prefer the woman $j^{'}$ over the woman $k^{'}$. Likewise, each woman $i^{'}\in{\cal I}_w$ have its own order relation $\succ_{i^{'}}$ over ${\cal I}_m$.

These two notions seems 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 non-transferable case as well: There may be a reward $\theta^m_{i j^{'}}$ for a man $i$ marrying a woman $j{'}$, such that $j^{'}\succ_ik^{'}$ iff $\theta^m_{ij^{'}}>\theta^m_{ik^{'}}$. Likewise, $\theta^w_{ij^{'}}$ quantifies the reward the the woman $j^{'}$ obtains while marrying the man $i$.

Given a matching $\{ii^{'}\}$, a blocking pair in the FNT case is a pair $ij^{'}$, $j^{'}\not =i^{'}$ such that the man $i$ prefers the woman $j^{'}$ over his matched woman $i^{'}$ (i.e $j^{'}\succ_ii^{'}$, or $\theta^m_{ij^{'}}>\theta^m_{ii^{'}}$ ) {\em and} the woman $j^{'}$ prefers $i$ over her matched man $j$ ($j\succ_{i^{'}}i$, or $\theta^w_{ij^{'}}>\theta^w_{jj^{'}}$ ). Thus, a blocking pair $ij^{'}$ is defined by

Let

Definition (ref) implies that the condition

is {\em necessary} for all $i,j$ for the stability of $\{ii^{'}\}$ in the FNT case.

Let us consider now the fully transferable (FT) case. Here a married pair $ii^{'}$ can share the rewards $\theta_{ii^{'}}$ for their marriage. Suppose the man $i$ cuts $u_i$ and the woman $i^{'}$ cuts $v_{i^{'}}$ form their mutual reward $\theta_{ii^{'}}$. Evidently, $u_i+v_{i^{'}}= \theta_{ii^{'}}$. If

for some $j^{'}\not= i^{'}$ then $ij^{'}$ is a blocking pair, since both $i$ and $j^{'}$ can increase their cuts to match the mutual reward $\theta_{ij^{'}}$. Hence $$ \theta_{ij^{'}}+\theta_{ji^{'}} > u_i+v_{j^{'}}+u_j+v_{i^{'}} = \theta_{ii^{'}}+\theta_{jj^{'}}$$ so ((ref)) is a necessary condition for the stability in the FT case as well.

Evidently, condition ((ref)) is {\em not} a sufficient one, unless $N=2$ in the FT case.

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

Consider the couples $i_1i_1^{'}, \ldots i_ki_k^{'}$, $k\geq 2$ . The sum of the rewards for these couples is $\sum_{l=1}^k\theta_{i_li^{'}_l}$. Suppose they perform a "chain deal" such that man $i_l$ marries woman $i^{'}_{l+1}$ for $1\leq l\leq k-1$, and the last man $i_k$ marries the first woman $i^{'}_1$. The net reward for the new matching is $\sum_{l=1}^{k-1}\theta_{i_li^{'}_{l+1}}+ \theta_{i_ki^{'}_1}$.

This leads to a definition of a {\em blocking chain}:

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

We shall see later on that cyclical monotonicity is, actually, an {\em 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 ((ref)), but also different couples are ready to share their reward via a chain deal according to Definition (ref). 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 loss

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" $i_1i^{'}_1\ldots i_{k}i^{'}_k$ by

where, again, $i^{'}_{k+1}\equiv i^{'}_1$. Definition (ref) is analogs to the statement that that there are no blocking chains of this form. Thus, a marriage $\{ii^{'}\}$ is stable in the FNT case if and only if

for any chain deal $i_1i^{'}_1\ldots i_{k}i^{'}_k$.

At the first sight definition ((ref)) seems redundant, since it provides no further information. However, we can observe the analogy between ((ref)) and ((ref)). In fact, ((ref)) and ((ref)) are obtained from each other by the exchanges

In section (ref) below we will take advantage on this representation.

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.

Stable marriage as a cooperative game

This part follows some of the ideas in Galichon et.all and references therein\footnote{which was turned to my attention by R. McCann} GASD. See also ECA.

Assume that we can guarantee a cut $u_i$ for each married man $i$, and a cut $v_{j^{'}}$ for 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 {\em pairwise bargaining set} ${\cal F}(ij^{'})\subset \mathbb R^2$ which contains all possible cuts $(u_i,v_{j^{'}})$ for a matching of man $i$ with woman $j^{'}$.

The meaning of the feasibility set is as follows:

The FNT case is contained in definition (ref), where

Indeed, if $\{ii^{'}\}$ is a stable marriage plan let $u_i=\theta^m_{ii^{'}}$ and $v_{i^{'}}=\theta^w_{ii^{'}}$. Then $(u_1, \ldots v_N)$ satisfies $(u_i,v_{i^{'}})\in{\cal F}$ for any $i\in\{1\ldots N\}$. Since there are no blocking pairs if follows that for any $j^{'}\not= i^{'}$, either $\theta^m_{ij^{'}}>\theta_{ii^{'}}=u_i$ or $\theta^w_{ij^{'}}>\theta^w_{jj^{'}}=v_{j^{'}}$, hence $(u_i, v_{j^{'}})\in\mathbb R^2-{\cal F}_0(ij^{'})$ so $(u_1\ldots v_N)\in V({\cal F})$ (Fig. [1a]).

The FT case (Fig. [1b]) is obtained by

Indeed, if $\{ii^{'}\}$ is a stable marriage plan and $(u_1, \ldots v_N)$ are the corresponding cuts satisfying $u_i+v_{j^{'}}=\theta_{ij^{'}}$, then for each $j^{'}\not= i^{'}$ we obtain $u_i+v_{j^{'}}\geq \theta_{ij^{'}}$ (otherwise $ij^{'}$ is a blocking pair). This implies that $(u_i,v_{j^{'}})\in \mathbb R^2-{\cal F}_0(ij^{'})$.

There are other, sensible models of {\em partial transfers} which fit into the formalism of Definition (ref) and Theorem (ref). Let us consider several examples:

Stability by fake promises

Suppose a man can make a promise to a married woman (which is not his wife), and v.v. The principle behind it is that each of them does not intend to honor his/her own promise, but, nevertheless, believes that the other parti 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

where $0\leq q\leq 1$. In particular $$ \Delta^{(0)}(i,j^{'}):=\min\{ \theta^m_{ij^{'}}-\theta^m_{ii^{'}}, \theta^w_{ij^{'}}-\theta^w_{j^{'}j^{'}}\} $$ $$ \Delta^{(1)}(i,j^{'}):= \theta^m_{ij^{'}}-\theta^m_{ii^{'}}+ \theta^w_{ij^{'}}-\theta^w_{ii^{'}}\equiv \theta_{ij^{'}}-\theta_{ii^{'}} . $$ The value of $q$ represents the level of {\em internal sharing} inside the couple. Thus, $q=0$ means there is no sharing whatsoever, and the condition $\Delta^{(0)}(i,j^{'})>0$ for a blocking pairs implies that both $i$ and $j^{'}$ gains from the exchange, is displayed in ((ref)) .

On the other hand, $\Delta^{(1)}(i, j^{'})+\Delta^{(1)}(j,i^{'})>0$, namely $$\theta_{ii^{'}}+ \theta_{jj^{'}}< \theta_{ij^{'}}+\theta_{ji^{'}}$$ is, as we argued, a necessary condition for a blocking pair in FT case, where $\theta$ represents the sum of the rewards to of the pair via ((ref)).

We now consider an additional parameter $p\in[0,1]$ and define the real valued function on $\mathbb R$:

Note that $[x]_p=x$ for any $p$ if $x\geq 0$, while $[x]_1=x$ for any real $x$. The parameter $p$ represents the level of sharing {\em between the pairs}.

Note that $p=0$ implies that $\Delta^{(q)}(i, j^{'})\leq 0$ for {\em any} $j^{'}\not= i^{'}$. If, in addition, $q=0$ then this is just the statement that there are no blocking pairs in the FNT case.

On the other hand, $p=1$ implies $$ \sum_{l=1}^k \Delta^{(q)}(i_l, i^{'}_{l+1}) \leq 0 \ \text{where} \ \ $$ which is reduced to ((ref)) if $q=1$ as well.

Let us interpret the meaning of $q,p$ in the context of utility exchange. A man $i\in{\cal I}_m$ can offer some bribe $w$ to any other women $j^{'}$ he might be interested in (except his own wife, so $j^{'}\not=i^{'}$). His cut for marrying $j^{'}$ is now $\theta^m_{ij^{'}}-w$. The cut of the woman $j^{'}$ should have been $\theta^w_{ij^{'}}+w$. However, the happy woman have to pay some tax for accepting this bribe. Let $q\in[0,1]$ be the fraction of the bribe she can get (after paying her tax). Her supposed cut for marrying $i$ is just $\theta^w_{ij^{'}}+qw$. Woman $j^{'}$ will believe and accept offer from man $i$ if two conditions are satisfied: the offer should be both

The two conditions above can be satisfied, and the offer is {\em acceptable}, only if

Symmetrically, man $i$ will accept an offer from a woman $j^{'}\not=i^{'}$ only if

The {\em utility} of the exchange $ii^{'}$ to $ij^{'}$ is, then defined by the minimum $\Delta^{(q)}(i, j^{'})$ of ((ref), (ref)) via ((ref)).

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

Each of the pair exchange $(i_l,i_l)\rightarrow (i_l,i_{l+1})$ yields a utility \\ $\Delta^{(q)}(i_l, i^{'}_{l+1})$ 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 {\it at least} the $p-$ part of the mutually loss of utility of the unfortunate pairs. This is the condition $$ \sum_{\Delta^{(q)}(i_l, i^{'}_{l+1})>0} \Delta^{(q)}(i_l, i^{'}_{l+1}) + p\sum_{\Delta^{(q)}(i_l, i^{'}_{l+1})<0} \Delta^{(q)}(i_l, i^{'}_{l+1}) \equiv \sum_{l=1}^k\left[ \Delta^{(q)}(i_l, i^{'}_{l+1})\right]_p > 0 \ \ . $$ \vskip .3in

Existence of stable marriage plans

In the general case of Assumption (ref), the existence of a stable matching follows from the following Theorem:

The set of vectors in $W({\cal F})$ satisfying ((ref)) is called {\em the core}. Note that the core is identified with the set of $\mathbb R^{2N}$ vector in $V({\cal F})$ which satisfy the condition $(u_i, v_{i^{'}})\in{\cal F}(ii^{'})$. Hence Definition (ref) can be recognized as the non-emptiness of the core, which is equivalent to the existence of a stable matching. Theorem (ref) is, in fact, a special case the celebrated Theorem of Scarf Sc for cooperative games, tailored to the marriage scenario (see also Gi, bon). As we saw, it can be applied to the fully non-transferable case ((ref)), as well as to the fully transferable case ((ref)).

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

Gale-Shapley algorithm in the non-transferable case

Here we describe the celebrated, constructive algorithm due to Gale and Shapley GSH, is describe below:

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

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 ${\cal F}$ is given by ((ref)) the feasibility set $V({\cal F})$ (Definition (ref)) takes the form

Recall also Definition (ref) for cyclical monotonicity.

The efficiency characterization of stable marriage connects this notion with optimal transport and the celebrated {\em Monge Kantorovich} theory Mo, Ka, Vil. See also Gal.

Since the set of all bijections is finite and the maximum on a finite set is always achieved we obtain from the efficiency characterization.

On existence and non-existence of stable fake promises

The proof of this Theorem follows from the definitions ((ref), (ref)) and the following

What can be said about the existence of s $(p,q)-$ stable matching in the general case? Unfortunately, we can prove now only a negative result: