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 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.

1. Introduction

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

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

The MP $\left\{i{i}^{\prime }\right\}$ is called stable if and only if there are no blocking pairs. A blocking pair is composed of a man $i$ and a woman $j^{\hspace{0.17em}}\ne i^{\prime }$ such that both $i$ prefers $j^{\hspace{0.17em}}$ over his assigned woman $i^{\prime }$ and $j^{\hspace{0.17em}}$ prefers $i$ over her assigned man $j$ .

To complete this definition, we have to establish a criterion of preferences over the possible matchings in ${\mathcal{I}}_m\times {\mathcal{I}}_w$ .

Let us consider two extreme cases. The first is the fully transferable (FT) case [1, 2, 3, 4]. Here we assume a utility value ${\theta }_{i{j}^{\hspace{0.17em}}}$ for a potential matching $i{j}^{\hspace{0.17em}}$ . If $i{j}^{\hspace{0.17em}}$ are matched, they can split this reward ${\theta }_{i{j}^{\hspace{0.17em}}}$ 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 $i\in {\mathcal{I}}_m$ , there exists an order relation ${\succ }_i$ on ${\mathcal{I}}_m$ , such that $j^{\hspace{0.17em}}{\succ }_i{k}^{\prime }$ means that the man $i$ will prefer the woman $j^{\hspace{0.17em}}$ over the woman $k^{\prime }$ . Likewise, each woman $i^{\prime }\in {\mathcal{I}}_w$ have its own order relation ${\succ }_{i^{\prime }}$ over ${\mathcal{I}}_m$ .

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 ${\theta }_{i{j}^{\hspace{0.17em}}}^m$ for a man $i$ marrying a woman $j^{\hspace{0.17em}}$ , such that $j^{\hspace{0.17em}}{\succ }_i{k}^{\prime }$ iff ${\theta }_{i{j}^{\hspace{0.17em}}}^m>{\theta }_{i{k}^{\prime }}^m$ . Likewise, ${\theta }_{i{j}^{\hspace{0.17em}}}^w$ quantifies the reward the the woman $j^{\hspace{0.17em}}$ obtains while marrying the man $i$ .

Given a matching $\left\{i{i}^{\prime }\right\}$ , a blocking pair in the FNT case is a pair $i{j}^{\hspace{0.17em}}$ , $j^{\hspace{0.17em}}\ne i^{\prime }$ such that the man $i$ prefers the woman $j^{\hspace{0.17em}}$ over his matched woman $i^{\prime }$ (i.e., $j^{\hspace{0.17em}}{\succ }_i{i}^{\prime }$ , or ${\theta }_{i{j}^{\hspace{0.17em}}}^m>{\theta }_{i{i}^{\prime }}^m$ ) and the woman $j^{\hspace{0.17em}}$ prefers $i$ over her matched man $j$ ( $j{\succ }_{i^{\prime }}i$ , or ${\theta }_{i{j}^{\hspace{0.17em}}}^w>{\theta }_{j{j}^{\hspace{0.17em}}}^w$ ). Thus, a blocking pair $i{j}^{\hspace{0.17em}}$ is defined by

$$\text{min}\left\{{\theta }_{i{j}^{\hspace{0.17em}}}^m-{\theta }_{i{i}^{\prime }}^m,{\theta }_{i{j}^{\hspace{0.17em}}}^w-{\theta }_{j{j}^{\hspace{0.17em}}}^w\right\}>0$$ E1

Definition 1.1. The matching $\left\{{\mathit{ii}}^{;}\right\}$ is stable if and only if

$$\text{min}\left\{{\theta }_{i{j}^{\hspace{0.17em}}}^m-{\theta }_{i{i}^{\prime }}^m,{\theta }_{i{j}^{\hspace{0.17em}}}^w-{\theta }_{j{j}^{\hspace{0.17em}}}^w\right\}\le 0$$

for any $i,j\in {\mathcal{I}}_m$ and $i^{\prime },j^{\hspace{0.17em}}\in {\mathcal{I}}_w$ .

Let

$${\theta }_{i{j}^{\hspace{0.17em}}}≔{\theta }_{i{j}^{\hspace{0.17em}}}^m+{\theta }_{i{j}^{\hspace{0.17em}}}^w.$$ E2

Definition 1.1 implies that the condition

$${\theta }_{i{i}^{\prime }}+{\theta }_{j{j}^{\hspace{0.17em}}}\ge {\theta }_{i{j}^{\hspace{0.17em}}}+{\theta }_{j{i}^{\prime }}$$ E3

is necessary for all $i,j$ for the stability of $\left\{i{i}^{\prime }\right\}$ in the FNT case.

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

$$u_i+v_{j^{\hspace{0.17em}}}<{\theta }_{i{j}^{\hspace{0.17em}}}$$ E4

for some $j^{\hspace{0.17em}}\ne i^{\prime }$ then $i{j}^{\hspace{0.17em}}$ is a blocking pair, since both $i$ and $j^{\hspace{0.17em}}$ can increase their cuts to match the mutual reward ${\theta }_{i{j}^{\hspace{0.17em}}}$ . Hence

$${\theta }_{i{j}^{\hspace{0.17em}}}+{\theta }_{j{i}^{\prime }}>u_i+v_{j^{\hspace{0.17em}}}+u_j+v_{i^{\prime }}={\theta }_{i{i}^{\prime }}+{\theta }_{j{j}^{\hspace{0.17em}}}$$

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=2$ in the FT case.

A simple example ( $N=2$ ):

$$\begin{array}{lllllll}{\theta }^m& w_1& w_2& & {\theta }^w& w_1& w_2\\ m_1& 1& 0& ;& m_1& 1& 5\\ m_2& 0& 1& & m_2& 0& 1\end{array}$$

The matching $\left\{11^{\prime },22^{\prime }\right\}$ is FNT stable. Indeed ${\theta }_{11^{\prime }}^m=1>{\theta }_{12^{\prime }}^m=0$ while ${\theta }_{22^{\prime }}^m=1>{\theta }_{21^{\prime }}^m=0$ , so both men are happy, and this is enough for FNT stability, since that neither $\left\{12^{\prime }\right\}$ nor $\left\{21^{\prime }\right\}$ is a blocking pair. On the other hand, if the married pairs share their rewards ${\theta }_{i{j}^{\hspace{0.17em}}}={\theta }_{i{j}^{\hspace{0.17em}}}^m+{\theta }_{i{j}^{\hspace{0.17em}}}^w$ we get

$$\begin{array}{lll}\theta & w_1& w_2\\ m_1& 2& 5\\ m_2& 0& 2\end{array}$$

so

$${\theta }_{11^{\prime }}+{\theta }_{22^{\prime }}=4<5={\theta }_{12^{\prime }}+{\theta }_{21^{\prime }},$$

thus $\left\{21^{\prime },12^{\prime }\right\}$ is the stable marriage in the FT case.

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

Consider the couples $i_1{i}_1^{\prime },\dots i_k{i}_k^{\prime }$ , $k\ge 2$ . The sum of the rewards for these couples is ${\sum }_{l=1}^k{\theta }_{i_l{i}_l^{\prime }}$ . Suppose they perform a” chain deal” such that man $i_l$ marries woman $i_{l+1}^{\prime }$ for $1\le l\le k-1$ , and the last man $i_k$ marries the first woman $i_1^{\prime }$ . The net reward for the new matching is ${\sum }_{l=1}^{k-1}{\theta }_{i_l{i}_{l+1}^{\prime }}+{\theta }_{i_k{i}_1^{\prime }}$ .

This leads to a definition of a blocking chain:

Definition 1.2. A chain $i_1{i}_1^{\prime },\dots i_k{i}_k^{\prime }$ of married couples forms a blocking chain iff

$$\sum _{l=1}^k\left({\theta }_{i_l{i}_{l+1}^{\prime }}-{\theta }_{i_l{i}_l^{\prime }}\right)>0$$ E5

where $i_{k+1}^{\prime }≔i_1^{\prime }$ . If there are no blocking chains then the matching $\left\{i{i}^{\prime }\right\}$ is called cyclically monotone [8].

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

Proposition 1.1. If a marriage $\left\{i{i}^{\prime }\right\}$ is a stable one for the FT case then it is cyclically monotone.

Proof. Let $\left\{i{i}^{\prime }\right\}$ be a matching, such that $u_i$ is the cut of man $i$ marrying $i^{\prime }$ and $v_{i^{\prime }}$ the cut of the woman $i^{\prime }$ marrying $i$ . Suppose by negation that $i_1{i}_1^{\prime }\dots i_k{i}_k^{\prime }$ is a blocking chain. Since $u_i+v_{i^{\prime }}\le {\theta }_{i{i}^{\prime }}$ we obtain

$$\sum _{l=1}^k{\theta }_{i_l{i}_{l+1}^{\prime }}>\sum _{l=1}^k{\theta }_{i_l{i}_l^{\prime }}\ge \sum _{l=1}^k\left(u_{i_l}+v_{i_l^{\prime }}\right)=\sum _{l=1}^k\left(u_{i_l}+v_{i_{l+1}^{\prime }}\right)$$

so, in particular, there exists a pair $i_l{i}_{l+1}^{\prime }$ for which ${\theta }_{i_l{i}_{l+1}^{\prime }}>u_{i_l}+v_{i_{l+1}^{\prime }}$ . Hence $i_l{i}_{l+1}^{\prime }$ is 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” $i_1{i}_1^{\prime }\dots i_k{i}_k^{\prime }$ by

$$\underset{1\le l\le k}{\text{max}}\text{min}\left\{{\theta }_{i_l{i}_{l+1}^{\prime }}^m-{\theta }_{i_l{i}_l^{\prime }}^m,{\theta }_{i_l{i}_{l+1}^{\prime }}^w-{\theta }_{i_l{i}_l^{\prime }}^w\right\}>0$$ E6

where, again, $i_{k+1}^{\prime }\equiv i_1^{\prime }$ . Definition 1.1 is analogs to the statement that that there are no blocking chains of this form. Thus, a marriage $\left\{i{i}^{\prime }\right\}$ is stable in the FNT case if and only if

$$\underset{1\le l\le k}{\text{max}}\text{min}\left\{{\theta }_{i_l{i}_{l+1}^{\prime }}^m-{\theta }_{i_l{i}_l^{\prime }}^m,{\theta }_{i_l{i}_{l+1}^{\prime }}^w-{\theta }_{i_l{i}_l^{\prime }}^w\right\}\le 0$$ E7

for any chain deal $i_1{i}_1^{\prime }\dots i_k{i}_k^{\prime }$ .

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

$${\theta }_{i_l{i}_{l+1}^{\prime }}-{\theta }_{i_l{i}_l^{\prime }}\iff \text{min}\left\{{\theta }_{i_l{i}_{l+1}^{\prime }}^m-{\theta }_{i_l{i}_l^{\prime }}^m,{\theta }_{i_l{i}_{l+1}^{\prime }}^w-{\theta }_{i_l{i}_l^{\prime }}^w\right\}\text{and}\sum _1^k\iff \underset{1\le i\le k}{\text{max}}$$ E8

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 therein¹ [9]. See also [10].

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

Assumption 2.1

1. For each $i\in {\mathcal{I}}_m$ and $j^{\hspace{0.17em}}\in {\mathcal{I}}_w$ , $\mathcal{F}\left(i{j}^{\hspace{0.17em}}\right)$ are closed sets in ${\mathbb{R}}^2$ , equal to the closure of their interior. Let ${\mathcal{F}}_0\left(i{j}^{\hspace{0.17em}}\right)$ the interior of $\mathcal{F}\left(i{j}^{\hspace{0.17em}}\right)$ .

2. $\mathcal{F}\left(i{j}^{\hspace{0.17em}}\right)$ is monotone in the following sense: If $\left(u,v\right)\in \mathcal{F}\left(i{j}^{\hspace{0.17em}}\right)$ then $\left(u^{\prime },v^{\prime }\right)\in \mathcal{F}\left(i{j}^{\hspace{0.17em}}\right)$ whenever $u^{\prime }\le u$ and $v^{\prime }\le v$ .

3. There exist $C_1,C_2\in \mathbb{R}$ such that

   $$\left\{\left(u,v\right);\text{max}(u,v)\le C_2\right\}\subset \mathcal{F}\left(i{j}^{\hspace{0.17em}}\right)\subset \left\{\left(u,v\right);u+v\le C_1\right\}$$

for any $i\in {\mathcal{I}}_m,j\in {\mathcal{I}}_w$ .

The meaning of the feasibility set is as follows:

Any married couple $i{j}^{\hspace{0.17em}}\in {\mathcal{I}}_m\times {\mathcal{I}}_w$ can guarantee the cut $u$ for $i$ and $v$ for $j^{\hspace{0.17em}}$ , provided $\left(u,v\right)\in \mathcal{F}\left(i{j}^{\hspace{0.17em}}\right)$ .

Definition 2.1. The feasibility set $V\left(\mathcal{F}\right)\subset {\mathbb{R}}^{2N}$ is composed of all vectors $\left(u_1,\dots u_N,v_1,\dots v_N\right)$ which satisfies

$$\left(u_i,v_{j^{\hspace{0.17em}}}\right)\in {\mathbb{R}}^2-{\mathcal{F}}_0\left(i{j}^{\hspace{0.17em}}\right)$$

for any $i{j}^{\hspace{0.17em}}\in {\mathcal{I}}_m\times {\mathcal{I}}_w$

The marriage plan $\left\{i{i}^{\prime }\right\}$ is stable if and only if there exists $\left(u_1,\dots v_N\right)\in V\left(\mathcal{F}\right)$ such that $\left(u_i,v_{i^{\prime }}\right)\in \mathcal{F}\left(i{i}^{\prime }\right)$ for any $i\in \left\{1,\dots N\right\}$ .

The FNT case is contained in definition 2.1, where

$$\mathcal{F}\left(i{j}^{\hspace{0.17em}}\right)≔\left\{u\le {\theta }_{i{j}^{\hspace{0.17em}}}^m;v\le {\theta }_{i{j}^{\hspace{0.17em}}}^w\right\}.$$ E9

Indeed, if $\left\{i{i}^{\prime }\right\}$ is a stable marriage plan let $u_i={\theta }_{i{i}^{\prime }}^m$ and $v_{i^{\prime }}={\theta }_{i{i}^{\prime }}^w$ . Then $\left(u_1,\dots v_N\right)$ satisfies $\left(u_i,v_{i^{\prime }}\right)\in \mathcal{F}$ for any $i\in \left\{1\dots N\right\}$ . Since there are no blocking pairs if follows that for any $j^{\hspace{0.17em}}\ne i^{\prime }$ , either ${\theta }_{i{j}^{\hspace{0.17em}}}^m>{\theta }_{i{i}^{\prime }}=u_i$ or ${\theta }_{i{j}^{\hspace{0.17em}}}^w>{\theta }_{j{j}^{\hspace{0.17em}}}^w=v_{j^{\hspace{0.17em}}}$ , hence $\left(u_i,v_{j^{\hspace{0.17em}}}\right)\in {\mathbb{R}}^2-{\mathcal{F}}_0\left(i{j}^{\hspace{0.17em}}\right)$ so $\left(u_1\dots v_N\right)\in V\left(\mathcal{F}\right)$ (Figure 1a).

Figure 1.

Pairwise bargaining sets.

The FT case (Figure 1b) is obtained by

$$\mathcal{F}\left(i{j}^{\hspace{0.17em}}\right)≔\left\{\left(u,v\right);u+v\le {\theta }_{i{j}^{\hspace{0.17em}}}\right\}.$$ E10

Indeed, if $\left\{i{i}^{\prime }\right\}$ is a stable marriage plan and $\left(u_1,\dots v_N\right)$ are the corresponding cuts satisfying $u_i+v_{j^{\hspace{0.17em}}}={\theta }_{i{j}^{\hspace{0.17em}}}$ , then for each $j^{\hspace{0.17em}}\ne i^{\prime }$ we obtain $u_i+v_{j^{\hspace{0.17em}}}\ge {\theta }_{i{j}^{\hspace{0.17em}}}$ (otherwise $i{j}^{\hspace{0.17em}}$ is a blocking pair). This implies that $\left(u_i,v_{j^{\hspace{0.17em}}}\right)\in {\mathbb{R}}^2-{\mathcal{F}}_0\left(i{j}^{\hspace{0.17em}}\right)$ .

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 $u$ or for the woman $v$ (even though not for both, if it is assumed ${\theta }_{i{j}^{\hspace{0.17em}}}>0$ ). To avoid the undesired stable marriages were one of the partners get a negative cut, we may replace the feasibility set (10) by

   $$\mathcal{F}\left(i{j}^{\hspace{0.17em}}\right)≔\left\{\left(u,v\right)\in {\mathbb{R}}^2;u+v\le {\theta }_{i{j}^{\hspace{0.17em}}},\text{max}\left(u,v\right)\le {\theta }_{i{j}^{\hspace{0.17em}}}\right\},$$
   see Figure 1c. It can be easily verified that if $\left(u_1,\dots v_N\right)\in V\left(\mathcal{F}\right)$ contains negative components, then $\left({\left[u_1\right]}_{+},\dots {\left[v_N\right]}_{+}\right)$ , obtained by replacing the negative components by $0$ , is in $V\left(\mathcal{F}\right)$ as well. Thus, the core of this game contains vectors in $V\left(\mathcal{F}\right)$ of non-negative elements.

2. In the transferable case (10), we allowed both men and women to transfer money to their partner. Indeed, we assumed that the man’s $i$ cut is ${\theta }_{i{j}^{\hspace{0.17em}}}^m-w$ and the woman’s $j$ cut is ${\theta }_{i{j}^{\hspace{0.17em}}}^w+w$ , where $w\in \mathbb{R}$ . Suppose we wish to allow only transfer between men to women, so we insist on $w\ge 0$ . In that case, we choose (Figure 1d)

$$\mathcal{F}\left(i{j}^{\hspace{0.17em}}\right)≔\left\{\left(u,v\right)\in {\mathbb{R}}^2;u+v\le {\theta }_{i{j}^{\hspace{0.17em}}};u\le {\theta }_{i{j}^{\hspace{0.17em}}}^m\right\}.$$ E11

1. Let us assume that the transfer $w$ from man $i$ to woman $j^{\hspace{0.17em}}$ is taxed, and the tax depends on $i,j^{\hspace{0.17em}}$ . Thus, if man $i$ transfers $w>0$ to a woman $j^{\hspace{0.17em}}$ he reduces his cut by $w$ , but the woman cut is increased by an amount ${\beta }_{i,j}w$ , were ${\beta }_{i,j}\in \left[0,1\right]$ . Here $1-{\beta }_{i,j}$ is the tax implied for this transfer. It follows that

   $$u_i\le {\theta }_{i{j}^{\hspace{0.17em}}}^m-w;v_{j^{\hspace{0.17em}}}\le {\theta }_{i{j}^{\hspace{0.17em}}}^w+{\beta }_{i,j}w,w\ge 0$$

   Hence

   $$\mathcal{F}\left(i{j}^{\hspace{0.17em}}\right)≔\left\{\left(u,v\right)\in {\mathbb{R}}^2;u_i+{\beta }_{i,j}^{-1}{v}_{j^{\hspace{0.17em}}}\le {\theta }_{i{j}^{\hspace{0.17em}}}^{\beta },u_i\le {\theta }_{i{j}^{\hspace{0.17em}}}^m\right\},$$

   where ${\theta }_{i{j}^{\hspace{0.17em}}}^{\beta }≔{\theta }_{i{j}^{\hspace{0.17em}}}^m+{\beta }_{i,j}^{-1}{\theta }_{i{j}^{\hspace{0.17em}}}^w$ . The geometrical description of $\mathcal{F}$ 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.

Define

$${\mathrm{\Delta }}^{\left(q\right)}\left(i,j^{\hspace{0.17em}}\right)≔\text{min}\left\{\begin{array}{l}q\left({\theta }_{i{j}^{\hspace{0.17em}}}^m-{\theta }_{i{i}^{\prime }}^m\right)+{\theta }_{i{j}^{\hspace{0.17em}}}^w-{\theta }_{j{j}^{\hspace{0.17em}}}^w\\ q({\theta }_{i{j}^{\hspace{0.17em}}}^w-{\theta }_{j{j}^{\hspace{0.17em}}}^w+{\theta }_{i{j}^{\hspace{0.17em}}}^m-{\theta }_{i{i}^{\prime }}^m\end{array}\right\},$$ E12

where $0\le q\le 1$ . In particular

$$\begin{array}{l}{\mathrm{\Delta }}^{\left(0\right)}\left(i,j^{\hspace{0.17em}}\right)≔\text{min}\left\{{\theta }_{i{j}^{\hspace{0.17em}}}^m-{\theta }_{i{i}^{\prime }}^m,{\theta }_{i{j}^{\hspace{0.17em}}}^w-{\theta }_{j^{\hspace{0.17em}}{j}^{\hspace{0.17em}}}^w\right\}\\ {\mathrm{\Delta }}^{\left(1\right)}\left(i,j^{\hspace{0.17em}}\right)≔{\theta }_{i{j}^{\hspace{0.17em}}}^m-{\theta }_{i{i}^{\prime }}^m+{\theta }_{i{j}^{\hspace{0.17em}}}^w-{\theta }_{i{i}^{\prime }}^w\equiv {\theta }_{i{j}^{\hspace{0.17em}}}-{\theta }_{i{i}^{\prime }}.\end{array}$$

The value of $q$ represents the level of internal sharing inside the couple. Thus, $q=0$ means there is no sharing whatsoever, and the condition ${\mathrm{\Delta }}^{\left(0\right)}\left(i,j^{\hspace{0.17em}}\right)>0$ for a blocking pairs implies that both $i$ and $j^{\hspace{0.17em}}$ gains from the exchange, is displayed in (6).

On the other hand, ${\mathrm{\Delta }}^{\left(1\right)}\left(i,j^{\hspace{0.17em}}\right)+{\mathrm{\Delta }}^{\left(1\right)}\left(j,i^{\prime }\right)>0$ , namely

$${\theta }_{i{i}^{\prime }}+{\theta }_{j{j}^{\hspace{0.17em}}}<{\theta }_{i{j}^{\hspace{0.17em}}}+{\theta }_{j{i}^{\prime }}$$

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 (2).

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

$$x\mapsto {\left[x\right]}_p≔{\left[x\right]}_{+}-p{\left[x\right]}_{-}$$ E13

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

Definition 2.2. Let $0\le p,q\le 1$ . The matching $\left\{i{i}^{\prime }\right\}$ is $\left(p,q\right)-$ stable if for any $k\in \mathbb{N}$ and $i_1,i_2,\dots i_k\in \left\{1,\dots N\right\}$

$$\sum _{l=1}^k{\left[{\mathrm{\Delta }}^{\left(q\right)}\left(i_l,i_{l+1}^{\prime }\right)\right]}_p\le 0\mathit{\text{where}}{i}_{k+1}=i_1$$

where $i_{k+1}≔i_1$ .

Note that $p=0$ implies that ${\mathrm{\Delta }}^{\left(q\right)}\left(i,j^{\hspace{0.17em}}\right)\le 0$ for any $j^{\hspace{0.17em}}\ne i^{\prime }$ . If, in addition, $q=0$ then this inequality implies that i′j′ is not a blocking pair in the FNT case.

On the other hand, $p=1$ implies

$$\sum _{l=1}^k{\mathrm{\Delta }}^{\left(q\right)}\left(i_l,i_{l+1}^{\prime }\right)\le 0\text{where}$$

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

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

1. Competitive, namely ${\theta }_{i{j}^{\hspace{0.17em}}}^w+\mathit{qw}\ge {\theta }_{j^{\hspace{0.17em}}{j}^{\hspace{0.17em}}}^w$ .

2. Trusted, if woman $j^{\hspace{0.17em}}$ believes that man $i$ is motivated. This implies ${\theta }_{i{j}^{\hspace{0.17em}}}^m-w\ge {\theta }_{i{i}^{\prime }}^m$ .

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

$$q\left({\theta }_{i{j}^{\hspace{0.17em}}}^m-{\theta }_{i{i}^{\prime }}^m\right)+{\theta }_{i{j}^{\hspace{0.17em}}}^w-{\theta }_{j{j}^{\hspace{0.17em}}}^w>0.$$ E14

Symmetrically, man $i$ will accept an offer from a woman $j^{\hspace{0.17em}}\ne i^{\prime }$ only if

$$q\left({\theta }_{i{j}^{\hspace{0.17em}}}^w-{\theta }_{i{i}^{\prime }}^w\right)+{\theta }_{i{j}^{\hspace{0.17em}}}^m-{\theta }_{j{j}^{\hspace{0.17em}}}^m>0.$$ E15

The utility of the exchange $i{i}^{\prime }$ to $i{j}^{\hspace{0.17em}}$ is, then defined by the minimum ${\mathrm{\Delta }}^{\left(q\right)}\left(i,j^{\hspace{0.17em}}\right)$ of (14, 15) via (12).

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

$$\left(i_1{i}_1^{\prime }\to i_1{i}_2^{\prime }\right),\dots \left(i_{k-1}{i}_{k-1}^{\prime }\to i_{k-1}{i}_k^{\prime }\right),\left(i_k{i}_k^{\prime }\right)\to \left(i_k{i}_1^{\prime }\right).$$

Each of the pair exchange $\left(i_l,i_l\right)\to \left(i_l,i_{l+1}\right)$ yields a utility ${\mathrm{\Delta }}^{\left(q\right)}\left(i_l,i_{l+1}^{\prime }\right)$ 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 $p-$ part of the mutually loss of utility of the unfortunate pairs. This is the condition

$$\sum _{{\mathrm{\Delta }}^{\left(q\right)}\left(i_l,i_{l+1}^{\prime }\right)>0}{\mathrm{\Delta }}^{\left(q\right)}\left(i_l,i_{l+1}^{\prime }\right)+p\sum _{{\mathrm{\Delta }}^{\left(q\right)}\left(i_l,i_{l+1}^{\prime }\right)<0}{\mathrm{\Delta }}^{\left(q\right)}\left(i_l,i_{l+1}^{\prime }\right)\equiv \sum _{l=1}^k{\left[{\mathrm{\Delta }}^{\left(q\right)}\left(i_l,i_{l+1}^{\prime }\right)\right]}_p>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 $W\left(\mathcal{F}\right)\subset {\mathbb{R}}^{2N}$ defined as follows:

$$\left(u_1,\dots u_N,v_1,\dots v_N\right)\in W\left(\mathcal{F}\right),$$

$\iff \exists$ an injection $\tau :{\mathcal{I}}_m\to {\mathcal{I}}_w$ such that $\left(u_i,v_{i^{\prime }}\right)\in \mathcal{F}\left(i{i}^{\prime }\right)$ where $i^{\prime }=\tau \left(i\right)$ , $\forall i\in {\mathcal{I}}_m.$ Then there exists $\left(u_1,\dots u_N,v_1,\dots v_N\right)\in W\left(\mathcal{F}\right)$ such that

$$\left(u_i,v_{j^{\hspace{0.17em}}}\right)\in {\mathbb{R}}^2-{\mathcal{F}}_0\left(i{j}^{\hspace{0.17em}}\right)$$ E16

for any $\left(i,j^{\hspace{0.17em}}\right)\in {\mathcal{I}}_m\times {\mathcal{I}}_w$ .

The set of vectors in $W\left(\mathcal{F}\right)$ satisfying (16) is called the core. Note that the core is identified with the set of ${\mathbb{R}}^{2N}$ vector in $V\left(\mathcal{F}\right)$ which satisfy the condition $\left(u_i,v_{i^{\prime }}\right)\in \mathcal{F}\left(i{i}^{\prime }\right)$ . 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=0$ or (9), as well as for the FT case corresponding to $p=q=1$ or (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 $i\in {\mathcal{I}}_m$ proposes to the woman $j\in {\mathcal{I}}_w$ 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.

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 ${\mathcal{I}}_m$ is 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 $\left\{i{i}^{\prime }\right\}$ , the rank of the woman $i^{\prime }$ according to man $i$ is at most the rank of the woman matched to $i$ 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 $\mathcal{F}$ is given by (11) the feasibility set $V\left(\mathcal{F}\right)$ (Definition 2.1) takes the form

$$V\left(\mathcal{F}\right)≔\left\{\left(u_1,\dots v_N\right)\in {\mathbb{R}}^{2N};u_i+v_{j^{\hspace{0.17em}}}\ge {\theta }_{i{j}^{\hspace{0.17em}}}\forall i{j}^{\hspace{0.17em}}\in {\mathcal{I}}_m\times {\mathcal{I}}_w\right\}.$$ E17

Recall also Definition 1.2 for cyclical monotonicity.

Theorem 3.3 $\left\{i{i}^{\prime }\right\}$ 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): ${\sum }_{i=1}^N{\theta }_{i{i}^{\prime }}\ge {\sum }_{i=1}^N{\theta }_{\mathit{i\sigma }\left(i\right)}$ for any marriage plans $\sigma :{\mathcal{I}}_m\to {\mathcal{I}}_w$ .

• $\left\{i{i}^{\prime }\right\}$ is cyclically monotone.

• Optimality: The minimal sum ${\sum }_1^N{u}_i^0+v_i^0$ of cuts in the feasibility set (17) satisfies $u_i^0+v_{i^{\prime }}^0={\theta }_{i{i}^{\prime }}$ (i.e., $\left\{u_1^0,\dots v_N^0\right\}$ is 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

$$-u_i^0≔\underset{k-\mathit{\text{chains}},k\in \mathbb{N}}{\text{inf}}\left(\sum _{l=1}^{k-1}{\theta }_{i_l{i}_l^{\prime }}-{\theta }_{i_l{i}_{l+1}^{\prime }}\right)+{\theta }_{i_k{i}_k^{\prime }}-{\theta }_{i_k{i}^{\prime }}.$$ E18

Let $\alpha >-u_i^0$ and consider a $k-$ chain realizing

$$\alpha >\left(\sum _{l=1}^{k-1}{\theta }_{i_l{i}_l^{\prime }}-{\theta }_{i_l{i}_{l+1}^{\prime }}\right)+{\theta }_{i_k{i}_k^{\prime }}-{\theta }_{i_k{i}^{\prime }}$$ E19

By cyclic monotonicity, ${\sum }_{l=1}^k{\theta }_{i_l{i}_l^{\prime }}-{\theta }_{i_l{i}_{l+1}^{\prime }}\ge 0$ . Since $i_{k+1}^{\prime }=i_1^{\prime }$ ,

$$\sum _{l=1}^{k-1}{\theta }_{i_l{i}_l^{\prime }}-{\theta }_{i_l{i}_{l+1}^{\prime }}\ge {\theta }_{i_k{i}_1^{\prime }}-{\theta }_{i_k{i}_k^{\prime }}$$

so (19) implies

$$\alpha >{\theta }_{i_k,i_1^{\prime }}-{\theta }_{i_k,i^{\prime }}\ge 0,$$

in particular $u_i^0<\infty$ .

Hence, for any $j\in {\mathcal{I}}_m$

$$\begin{array}{l}\alpha +{\theta }_{i{i}^{\prime }}-{\theta }_{i{j}^{\hspace{0.17em}}}>\left(\sum _{l=1}^{k-1}{\theta }_{i_l,i_l^{\prime }}-{\theta }_{i_l,i_{l+1}^{\prime }}\right)\\ +{\theta }_{i_k{i}_k^{\prime }}-{\theta }_{i_k{i}^{\prime }}+{\theta }_{i{i}^{\prime }}-{\theta }_{i{j}^{\hspace{0.17em}}}\ge -u_j^0\end{array}$$ E20

where the last inequality follows by the substitution of the $k+1-$ cycle $i_1=i,i_2,\dots ,i_k,i_{k+1}=i$ in (18). Since $\alpha$ is any number bigger than $-u_i^0$ it follows

$$-u_i^0+{\theta }_{i{i}^{\prime }}-{\theta }_{i{j}^{\hspace{0.17em}}}\ge -u_j^0,$$ E21

for any pair $i,j\in {\mathcal{I}}_m$ . Now, let $\sigma$ be any permutation in ${\mathcal{I}}_m$ and let $j=\sigma \left(i\right)$ . Then

$$-u_i^0+{\theta }_{i{i}^{\prime }}-{\theta }_{\mathit{i\sigma }\left(i^{\prime }\right)}\ge -u_{\sigma \left(i\right)}^0.$$ E22

Since $\sigma$ is a bijection on ${\mathcal{I}}_m$ as well, so ${\mathrm{\Sigma }}_{i=1}^N{u}_i^0={\sum }_{i=1}^N{u}_{\sigma \left(i\right)}^0$ . Then, sum (22) over $1\le i\le N$ to obtain

$$\sum _{i=1}^N{\theta }_{i{i}^{\prime }}\ge \sum _{i=1}^N{\theta }_{\mathit{i\sigma }\left(i^{\prime }\right)},$$

so $\left\{i{i}^{\prime }\right\}$ is an efficient marriage plan.

To prove that any efficient solution is stable, we define $v_j^0≔{\theta }_{j{j}^{\hspace{0.17em}}}-u_j^0$ so

$$u_j^0+v_{j^{\hspace{0.17em}}}^0={\theta }_{j{j}^{\hspace{0.17em}}}.$$ E23

Then (21) implies

$$u_i^0+v_{j^{\hspace{0.17em}}}^0=u_i^0+{\theta }_{j{j}^{\hspace{0.17em}}}-u_j^0\ge u_i^0-u_i^0+{\theta }_{i{j}^{\hspace{0.17em}}}={\theta }_{i{j}^{\hspace{0.17em}}}$$ E24

for any $i,j$ . Thus, (23, 24) establish that $\left\{i{i}^{\prime }\right\}$ is a stable marriage via Definition 2.1.

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

$$\sum _1^N{u}_i+v_{i^{\prime }}=\sum _1^N{u}_i+v_{\sigma \left(i\right)}\ge \sum _1^N{\theta }_{\mathit{i\sigma }\left(i\right)}$$

for any bijection $\sigma :{\mathcal{I}}_m\to {\mathcal{I}}_w$ and from (23).⃞

3.3. On existence and nonexistence of stable fake promises

Theorem 3.4 If the matching $\left\{i{i}^{\hspace{0.17em}}\right\}$ is $\left(p,q\right)-$ stable, then it is also $\left(p^{\prime },q^{\prime }\right)-$ stable for $p^{\prime }\ge p$ and $q^{\prime }\le q$ .

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

Lemma 3.1. For any, $i\ne j$ and $1\ge q>q^{\prime }\ge 0$ ,

$${\left(1+q\right)}^{-1}{\mathrm{\Delta }}^{\left(q\right)}\left(i,j\right)>{\left(1+q^{\prime }\right)}^{-1}{\mathrm{\Delta }}^{\left(q^{\prime }\right)}\left(i,j\right).$$

Proof. For $a,b\in \mathbb{R}$ and $r\in \left[0,1\right]$ define

$${\mathrm{\Delta }}_r\left(a,b\right)≔\frac{1}{2}\left(a+b\right)-\frac{r}{2}\mid a-b\mid .$$

Observe that ${\mathrm{\Delta }}_1\left(a,b\right)\equiv \text{min}\left(a,b\right)$ . In addition, $r\mapsto {\mathrm{\Delta }}_r\left(a,b\right)$ is monotone not increasing in $r$ . A straightforward calculation yields

$$\text{min}\left(\mathit{qa}+b,\mathit{qb}+a\right)={\mathrm{\Delta }}_1\left(\mathit{qa}+b,\mathit{qb}+a\right)=\left(q+1\right){\mathrm{\Delta }}_{\frac{1-q}{1+q}}\left(a,b\right),$$

and the Lemma follows from the above observation, upon inserting $a={\theta }_m\left(i,j\right)-{\theta }_m\left(i,i\right)$ and $b={\theta }_w\left(i,j\right)-{\theta }_w\left(j,j\right)$ . ⃞

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

Proposition 3.1. For any $1\ge q>p\ge 0$ , 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^{\prime },22^{\prime }$ is not stable we have to show

$${\left[{\mathrm{\Delta }}^{\left(q\right)}\left(1,2^{\prime }\right)\right]}_p+{\left[{\mathrm{\Delta }}^{\left(q\right)}\left(2,1^{\prime }\right)\right]}_p>0$$ E25

while, to show that $12^{\prime },21^{\prime }$ is not stable we have to show

$${\left[{\mathrm{\Delta }}^{\left(q\right)}\left(1,1^{\prime }\right)\right]}_p+{\left[{\mathrm{\Delta }}^{\left(q\right)}\left(2,2^{\prime }\right)\right]}_p>0.$$ E26

By definition (12) and Lemma 3.1

$$\begin{array}{l}{\mathrm{\Delta }}^{\left(q\right)}\left(1,2^{\prime }\right)=\left(q+1\right){\mathrm{\Delta }}_r\left({\theta }_{12^{\prime }}^m-{\theta }_{11^{\prime }}^m,{\theta }_{12^{\prime }}^w-{\theta }_{22^{\prime }}^w\right)\\ {\mathrm{\Delta }}^{\left(q\right)}\left(2,1^{\prime }\right)=\left(q+1\right){\mathrm{\Delta }}_r\left({\theta }_{21^{\prime }}^m-{\theta }_{22^{\prime }}^m,{\theta }_{21^{\prime }}^w-{\theta }_{11^{\prime }}^w\right)\end{array}$$

where $r=\frac{1-q}{1+q}$ . To obtain ${\mathrm{\Delta }}^{\left(q\right)}\left(1,1^{\prime }\right),{\mathrm{\Delta }}^{\left(q\right)}\left(2,2^{\prime }\right)$ we just have to exchange man $1$ with man $2$ , so

$$\begin{array}{l}{\mathrm{\Delta }}^{\left(q\right)}\left(2,2^{\prime }\right)=\left(q+1\right){\mathrm{\Delta }}_r\left({\theta }_{22^{\prime }}^m-{\theta }_{21^{\prime }}^m,{\theta }_{22^{\prime }}^w-{\theta }_{12^{\prime }}^w\right)\\ {\mathrm{\Delta }}^{\left(q\right)}\left(1,1^{\prime }\right)=\left(q+1\right){\mathrm{\Delta }}_r\left({\theta }_{11^{\prime }}^m-{\theta }_{12^{\prime }}^m,{\theta }_{11^{\prime }}^w-{\theta }_{21^{\prime }}^w\right).\end{array}$$

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

$$\begin{array}{l}{a}_1≔{\theta }_{12^{\prime }}^m-{\theta }_{11^{\prime }}^m,a_2={\theta }_{12^{\prime }}^w-{\theta }_{22^{\prime }}^w,\\ b_1={\theta }_{21^{\prime }}^m-{\theta }_{22^{\prime }}^m,b_2={\theta }_{21^{\prime }}^w-{\theta }_{11^{\prime }}^w,\end{array}$$

so the two conditions to be verified are

$${\left[{\mathrm{\Delta }}_r\left(a_1,a_2\right)\right]}_p+{\left[{\mathrm{\Delta }}_r\left(b_1,b_2\right)\right]}_p>0;{\left[{\mathrm{\Delta }}_r\left(-a_1,-b_2\right)\right]}_p+{\left[{\mathrm{\Delta }}_r\left(-b_1,-a_2\right)\right]}_p>0.$$

Let us insert $a_1=a_2≔a>0$ . $b_1=b_2≔-b$ where $b>0$ . So

$${\left[{\mathrm{\Delta }}_r\left(a_1,a_1\right)\right]}_p=a,{\left[{\mathrm{\Delta }}_r\left(b_1,b_2\right)\right]}_p=-\mathit{pb},$$

while ${\mathrm{\Delta }}_r\left(-a_1,-b_2\right)={\mathrm{\Delta }}_r\left(-b_1,-a_2\right)=\frac{b-a}{2}-\frac{r}{2}\left(a+b\right)$ . In particular, the condition $\frac{a}{b}<\frac{1-r}{1+r}$ implies ${\left[{\mathrm{\Delta }}_r\left(-a_1,-b_2\right)\right]}_p={\left[{\mathrm{\Delta }}_r\left(-b_1,-a_2\right)\right]}_p>0$ which verifies (26). On the other hand, if $a-\mathit{pb}>0$ then (25) is verified. Both conditions can be verified if $\frac{1-r}{1+r}>p$ . Recalling $q=\frac{1-r}{1+r}$ we obtain the result.

Conjecture 1 If $0<p<q<1$ then there always exists a $\left(p,q\right)$ stable 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.