stability:

$E_{TOT}=\sum_{i=1}^{N}x_{i}+\sum_{i=1}^{N}y_{i}=X+Y\;.$ (76)

The minimum stable total energy can be found by generating all the SMP
solutions and comparing their energies. The problem with this approach is that
the maximum number of SMP solutions grows exponentially with the size $N$ of
the system. In [86], Irving, Leather and Gusfield built an algorithm
$O(N^{4})$ to solve the problem of the minimum of $E_{TOT}$. They took
advantage of the aforementioned rotations theorem which states that in SMP,
stable solutions have a unique correspondence with closed subsets of rotations
and have exploited the result that all rotations can be found in a
time$O(N^{3})$. Later, Feder [87] improved this algorithm arriving at a
$O(N^{3})$ running time.

Regarding the minimum regret stable marriage problem, it concerns the
minimization of the maximum regret $R_{max}$ in a stable matching $M$, where
the regret of the man $m$ (woman $w$) corresponds to the ranking of the woman
(man) married to $m$ ($w$) in $M$ on his (her) preference list:

$R(M)=max_{(i,j)\in M}(max\\{x(i,j),y(j,i)\\})\;.$ (77)

The first to discuss the $R$ minimization was Knuth in [84] where he showed
the solution proposed by Alan Selkow in which an algorithm with a running time
of $O(N^{4})$ is shown. A more efficient solution, instead, was proposed by
Gusfield in [17] in which the breakmarriage operation and its properties are
used to avoid that there are duplicate proposals or rejection in the
algorithm, to increase the speed of execution time to $O(N^{2})$.

###  4.3 NP-Complex Problems in SMP

####  4.3.1 SMP with Incomplete Lists and Ties

In section 7 we will interpret the incompleteness of preference-lists as a
limitation of individuals to process information. Indeed, the concept of
”partial information” was introduced by Zhang in zhang2001happier but the SMP
with incomplete preference-lists has been studied under another interpretation
by mathematicians and computer scientists: the lists of individuals are
incomplete not because of lack of information, but because some individuals
are ”unacceptable” as partners for other individuals. This problem, known in
the literature as SMI (Stable Marriage Incomplete), differs from what we
present in section 7 in that an individual can marry only with the individuals
present in his preference-list. In the SMI the ”unacceptability” is not
symmetrical (the man $m$ might consider the woman $w$ unacceptable but, in
general, the vice versa is not also valid).
The goal of the SMI is therefore to find a stable matching in which
individuals accept each other and therefore individuals may remain single.
However, All the solutions of an SMI have the same number of pairs [88], and
these solutions are found in a polynomial time.

A more complicated extension of SMI is SMTI: the SMP with incomplete list and
ties. The addition of ties implies that two or more individuals may be
indifferent to another individual, that is, they are interchangeable in
his/her preference-list.
In the SMTI it is possible that there are solutions with different numbers of
married couples and the goal of the problem is to find the solution with the
maximum number of married couples. SMTI is NP-hard [89, 90].
Iwama et al [91, 92] have constructed interesting approximation algorithms for
SMTI. Other approximation algorithms are shown in [93, 94, 95, 96].
Another way to approach the solution is to use the local search approach as in
[28, 28, 97, 98] in which the authors exploited GS dynamics and based a search
pattern of the first neighbours to minimize the distance from stability. The
algorithm starts from random matching and at each step, it is moved to the
closest matching which minimizes the distance from stability, measured as the
number of blockingpairs. The algorithm ends when a stable solution is found.

SMTI is an interesting problem since it shows that despite the two separate
problems (only incomplete list or only ties) can be solved in polynomial
times, nevertheless, if put together the problem is no longer so simple, that
is, it becomes NP-hard.

####  4.3.2 Equitable Stable Marriage Problem

In 1989 Gusfield and Irving [25] proposed the ”equitable stable marriage
problem” (ESMP) which requires finding the stable SMP solution that minimizes
”the distance” between the energy of men and of women to avoid discrimination
between the two sides. Since for many real-world applications, ESMP is more
appropriate than the classic SMP, it has attracted a lot of attention [26, 27,
99, 29, 30, 31].
In ESMP we want to minimize is the sex-equality cost $D_{sec}$, defined in
this way:

$D_{sec}(M)=|\sum_{i=1}^{N}x_{i}-\sum_{i=1}^{N}y_{i}|\;,$ (78)

where $x_{i}$ and $y_{i}$ are still the costs of marriages of man $i$ and
woman $i$ in matching $M$ respectively.

Unfortunately, no algorithm solves the $D_{sec}$ search in polynomial time: in
[26] Kato has shown that this problem is strongly NP-hard.
More recent works have used algorithms with approximations and heuristic
methods for this problem [100, 101, 102, 103, 104]: for example in [99] Gelain
et al. have proposed a local search algorithm to find a solution different
from the men-optimal and women-optimal solution for small $N$. Therefore, with
a high probability, this solution is the fairest, without however showing that
it corresponds to the $D_{sec}$. Roth and Vande [101] have shown that starting
from an arbitrary matching and randomly pairing blocking pairs, the result
achieved is a stable matching with probability 1. In this way, it could
transform an unstable matching into a stable one different from the two
extreme solutions men/women optimal and for small $N$ there is a good chance
that such matching is the fairest. Unfortunately, even in this case, there are
no certain guarantees to find a fair solution. In [27] Iwama et al. built an
approximation algorithm with a time $O(n^{3+1/\epsilon})$ to obtain a stable
solution such that $D_{sec}\leq\epsilon\cdot min\\{M_{m},M_{w}\\}$, where
$D(M_{m})$ and $D(M_{w})$ are the distances between the energies of men and
women in the men-optimal and women-optimal solution respectively and
$\epsilon$ is a constant. Later Everaere et al. [30, 31] have built a
heuristic algorithm that manages to achieve a fair solution by allowing both
men and women to make proposals repeatedly. The problem with this algorithm,
however, is that it could proceed for an indefinite number of iterations even
for small $N$.
More recently some improvements have been made in [105]: a heuristic algorithm
has been built based once again on the idea that both parties can propose,
this time however in a controlled manner through a non-state dependent and
non-periodic function.

###  4.4 Algorithms for the Ground State Solution

In section 3 we introduced the analytical methods that have been developed to
study the ground state in the matching problem, here we want to study the
algorithms that allow finding this ground state, given any instance of the
problem.
The main algorithms we will talk about have been developed for the so-called
”assignment problem” which, as we will see, has the same structure as the SMP
if one looks for optimization.
The assignment problem is defined as follows: imagine that there are $N$
workers $i$ and $N$ jobs $j$ and assume that it is given a score for the
skills that each worker has for each job. In this way, each pair $(i,j)$ will
have a certain score. The problem requires finding a matching (each worker is
assigned one and only one job) that maximizes the total score. SMP is
different in that the assignment problem has no preference-lists and requires
no stability whatsoever. However, it is not difficult to rewrite the SMP as
the assignment problem: there are $N$ men $m$ and $N$ women $w$ each with a
preference list on individuals of the opposite sex. In this way each pair
$(m_{i},w_{j})$ will have a certain score given by the sum of the ranking of
the woman $w_{j}$ in the list of $m_{i}$, previously defined as
$x(i,j)=x_{i}$, and of the ranking of man $m_{i}$ in the list of $w_{j}$,
previously defined as $y(j,i)=y_{j}$. Then we ask to minimize
$E_{TOT}^{*}=X+Y$. Note that we did not mention anything about stability.
The two problems are equivalent: returning to the terminology of the
assignment problem, build a matrix $A$ that is $N\times N$ where the rows are
the workers and the columns the jobs. So the element $A_{i,j}$ represents the
score assigned to the worker-job pair $(i,j)$. Finding a matching that
maximizes the total score corresponds to finding $N$ elements of $A$ that are
independent, that is, that there is only one in each row and each column, and
that the sum is the maximum possible. In SMP terminology it is enough to
replace, for example, workers with men, jobs with women and instead of
maximizing the sum of the independent elements of $A$, we must try to minimize
it. It is easy to demonstrate that the maximization and minimization processes
are equivalent: let $p=max\\{A_{ij}\\}$ if you define the matrix $A^{\prime}$
as:

$A_{ij}^{\prime}=p-A_{ij}\;,$

then maximizing $N$ independent elements of $A$ corresponds to minimizing $N$
independent elements of $A^{\prime}$.
To remain consistent with the literature on the subject, in this paragraph we
will refer to the assignment problem and therefore we will talk about
maximizing $N$ independent elements of $A$, keeping in mind that minimizing is
equivalent.

The basis of all algorithms to find the solution to the assignment problem is
the so-called ”Hungarian method” and it is for this reason that in the
following paragraphs we will analyze this algorithm in detail, while its
variants and its most recent improvements will only be mentioned.

####  4.4.1 General Procedure

The most direct approach to solving the assignment problem would be to use a
brute force approach and calculate all possible matching, i.e. all possible
combinations of independent elements of $A$, and choose the one with higher
total score $P_{max}$. This is only feasible for very small $N$, as the number
of possible matches is $N!$ and therefore for large $N$ a brute force approach
is unthinkable.
The first to find an efficient algorithm for the assignment problem was Kuhn
in [6]. His approach is based on two important results [106]: 1) Konig’s
theorem which states that if in an $A$ matrix, $m$ is the maximum number of
independent elements of $A$ equal to 0, then there are $m$ lines (rows or
columns) that contain all elements equal to 0 of $A$; 2) the solution to the
problem does not change if the elements $A_{ij}$ are replaced with the
elements $B_{ij}=A_{ij}-u_{i}-v_{j}$, with $u_{i}$ and $v_{j}$ arbitrary
constants.
The main steps of the Kuhn algorithm, which is called in the literature as the
Hungarian algorithm, can be summarized as follows [107]:

  1. 1.

subtract from each element of $A^{\prime}$ the smallest of its elements,
obtaining a matrix $A_{1}^{\prime}$ which has all non-negative elements and at
least one equal to 0.

  2. 2.

find a minimum set $L_{1}$ of $N_{1}$ lines (rows or columns) containing all
the zeros of $A_{1}^{\prime}$. If $N_{1}=N$, there is a set of $N$ independent
zeros and the elements of $A^{\prime}$ in these $N$ positions correspond to
the solution of the problem.

  3. 3.

if $N_{1}<N$, call $s_{1}>0$ the smallest element of $A_{1}^{\prime}$ which is
not in $L_{1}$. For each line in $L_{1}$ add $s_{1}$ to all elements of that
line and then subtract $s_{1}$ from all elements of $A_{1}^{\prime}$. Call the
new matrix $A_{2}^{\prime}$.

  4. 4.

Repeat steps 2 and 3 using $A_{2}^{\prime}$ instead of $A_{1}^{\prime}$. Since
with each application of the third step the sum of the elements of the matrix
decreases by $N(N-N_{k})s_{k}$, then the algorithm certainly ends after a
finite number of steps.

To complete the algorithm it is necessary to know a procedure for step 2, that
is, to know how to find a minimum set of lines that contains all the zeros and
therefore a maximum set of independent zeros (Konig theorem) .
In the following paragraphs, we will see how the Hungarian method solves this
problem.
For completeness, it is worth knowing that there are several variations of the
Hungarian algorithm and other more recently developed algorithms that solve
the assignment problem, for example in [108, 109, 110].

####  4.4.2 The Hungarian Method

As Kuhn himself wrote in [111], the idea of the Hungarian algorithm came to
him while reading Konig’s book on graph theory in the summer of 1953. If a
matrix is composed only of 0 or 1, then Konig’s theorem states that the
minimum number of rows and columns containing all 1’s is equal to the maximum
number of independent 1’s. The primitive problem for which Konig enunciated
his theorem was a particular version of the assignment problem, called simple
assignment problem (SAP), in which the score that workers receive for a given
job can only be 0 or 1.
In a footnote of the Konig’s book, the author referred to an article by E.
Egervary (written in Hungarian) [112] in which a simple computational method
was provided to reduce the more general assignment problem (which from now on
we will call GAP) to SAP. Kuhn, reading the article in Hungarian, had the idea
which he later gave the name of the Hungarian algorithm.
We now introduce the theoretical bases of the algorithm, studying the
reduction from GAP to SAP.

#### Simple Assignment Problem

The SAP can be formulated as follows: build a $Q$ matrix in which the columns
represent the jobs and the rows the workers. $Q_{ij}=1$ if worker $i$ is
qualified for the job $j$, otherwise $Q_{ij}=0$. The problem requires finding
the maximum number of jobs that can be assigned to qualified workers, i.e. the
maximum number of independent 1’s in $Q$.
Following Kuhn’s terminology in [6] we will call complete any assignment such
that it is no longer possible to assign an unassigned worker to an unassigned
job for which he is qualified. However, an assignment can be improved through
a transfer, namely by moving a worker already assigned to another job for
which he is qualified. Also, we will call all workers involved in a transfer
essential and we will also call all jobs to which a non-essential individual
has been assigned in the same way. It follows that if we conventionally define
the operation of leaving everything unchanged as transfer, then in this case
all jobs will be essential. It is not difficult to prove the following
theorems [6]:

  * •

1: For a given assignment, if all transfers lead to a complete assignment, for
each worker qualified for a job, either the worker or the job is essential, or
possibly both.

  * •

2: There is always an assignment that is complete after every possible
transfer.

A dual aspect of the problem can now be defined. Consider a budget to be given
to the value of an individual assigned to a job for which he is qualified.
This budget consists of a unit or nothing to be delivered to every worker and
every job. A budget is adequate if, for each worker qualified for a job,
either a worker, job or both were given a unit. The following theorems [6] can
be proved:

  * •

3: The total sum of the budget (adequate) delivered is greater than or equal
to the maximum number of jobs that can be assigned to qualified workers.

  * •

4: There is an adequate budget and an assignment such that the total sum of
the budget delivered is equal to the number of jobs assigned to qualified
workers.

Theorem 3 implies that the assignment of theorem 4 is optimal, i.e. it is the
SAP solution. So the maximum number of jobs that can be assigned to qualified
workers is equal to the minimum possible sum of the adequate budget delivered,
and that each assignment is optimal if and only if it is complete after each
possible transfer (theorems 1 and 2).
Let us see now how to reduce the GAP to the SAP just described.

#### General Assignment Problem

We described the GAP previously, so we can directly introduce its dual.
Consider an adequate budget, that is an amount of non-negative integers (for
simplicity) $u_{i}$ to be delivered to each worker and $v_{j}$ to each job,
such that the total amount delivered to worker $i$ and job $j$ is not less
than $A_{ij}$:

$u_{i}+v_{j}\geq A_{ij}\;,$

for every $i,j=1,...,N$. The analogue of Theorem 3 can be stated in this way
[6]:

  * •

Theorem 3’: the total sum of the adequate budget delivered is greater than or
equal to the total score of each assignment.

Therefore, the assignment that has the total sum of the adequate budget
delivered equal to the total score of the assignment is the solution of the
GAP.

A very convenient way to map the GAP to SAP is as follows: worker $i$ is
qualified for the job $j$ if and only if $u_{i}+v_{j}=A_{ij}$. The following
theorems immediately follow [6]:

  * •

5: If all the $N$ workers can be assigned to the jobs for which they are
qualified in the SAP associated with the corresponding GAP with an adequate
budget. Then the sum of the scores is equal to the total budget delivered and
therefore the resulting assignment is the solution of the GAP.

  * •

6: If at most $N_{1}<N$ workers can be assigned to the jobs for which they are
qualified in the SAP associated with the corresponding GAP with an adequate
budget, then a positive integer amount can be subtracted from the total sum of
the budget delivered.

In particular, the subtracted sum to which theorem 6 refers can be deduced in
this way: consider $p$ essential individuals and $q$ essential jobs. Then the
following budget changes can be made:

$u^{\prime}_{1}=u_{1},...,u^{\prime}_{p}=u_{p},u^{\prime}_{p+1}=u_{p+1}-1,...,u^{\prime}_{N}=u_{N}-1\;,$
$v^{\prime}_{1}=v_{1}+1,...,v^{\prime}_{q}=v_{q}+1,v^{\prime}_{q+1}=v_{q+1},...,v^{\prime}_{N}=v_{N}\;.$

Note that the total sum of the budget has decreased, in fact the budget has
increased by $q$ and decreased by $N-p$ and, noting that $p+q=N_{1}$, then the
subtracted sum is $N-p-q=N-N_{1}>0$.
Therefore, starting from any adequate budget, either the assignment is optimal
and therefore theorem 5 is valid, or theorem 6 is applied, and the budget can
be decreased. Since the budget can decrease a finite number of times, then the
highest possible sum of the scores among the possible assignments is equal to
the minimum of the adequate budget delivered. This minimum can be found by
solving a finite SAP associated sequence. Moreover, the maximum number of
steps to find the optimal solution is in the order of $O(N^{3})$ [106].
The proofs of all theorems set out in this paragraph have been omitted but can
all be found in Kuhn’s original article. In the same paper, Kuhn shows a
practical example of this method that can help understand this abstract
framework.

###  4.5 Algorithms for the SMP Generalizations

####  4.5.1 College Admission Problem

The first generalization of the SMP that we will deal with is the ”college
admission problem” (CAP), sometimes also called ”resident hospitals problem”
(RHP). While in SMP the goal is to find one-to-one stable matching, in CAP the
goal is to find many-to-one stable matching. The metaphor that is commonly
used for many-to-one matching is that of students that must apply to various
colleges and each college has a limited number of students that it can accept.
Similarly, one can think of the original problem described in [113] in which
medical students must be assigned to different hospitals.
The original model was first described in [1] by Galey and Shapley and is as
follows: a set of $N$ students must be assigned to $M$ colleges and $q_{i}$ is
the maximum number of students that a college can accept, also called ”quota”.
Each applicant ranks colleges in order of preference, omitting those colleges
they would not accept under any circumstances. Similarly, each college builds
a ranking of students in the system, omitting those who would not be admitted
under any circumstances. For simplicity, in their original article Galey and
Shapley did not consider ties.
The definition of ”instability” is analogous to that of SMP: a matching
between colleges and student is said to be unstable if there are two students
$s_{1}$ and $s_{2}$ who are assigned respectively to colleges $c_{1}$ and
$c_{2}$ despite $s_{1}$ prefers $c_{2}$ and, at the same time, $c_{2}$ prefers
$s_{1}$. So exactly as in the SMP, matching is unstable if it can be disturbed
by a college and a student acting together to both benefits. The objective of
the CAP is to find a stable matching, i.e. that it is not unstable.
Another definition analogous to the case of the classic SMP is that of
optimality: a stable matching is defined as optimal if each student is
accepted by the best college from which they could be accepted in any other
stable matching. This definition of optimality, however, refers only to
students. Indeed it would be more appropriate to define it as ”students-
optimality”. There is also a definition of ”colleges-optimality” even though
the CAP is not symmetric to colleges and students while the SMP was symmetric
(as it consisted of one-to-one matching). We will deal with this issue in the
next paragraphs.
As in the case of SMP, there are several variations of the original model
[114, 115, 116, 117, 118, 119] which, however, we will not describe in detail
in this review.
In this paragraph, we see what are the main algorithms that allow to find a
stable solution to the CAP.

#### Deferred-Acceptance Procedure

In [1] the authors propose a natural extension of the classic GS algorithm
that develops in the following way: for simplicity, it is assumed that if a
college does not accept a certain student in any circumstances then that
student will not be able to apply for that college. At first, all students
apply to colleges that correspond to their first choice. So a college with a
quota $q$ will place their $q$ (or less) best applicants on their waiting list
and will reject the others. The procedure ends when all students are either on
a waiting list or have been rejected by all colleges they are allowed to
apply.
Now, each college will accept all students on its waiting list and the
resulting matching turns out to be stable. Therefore, there is also at least
one stable solution in the CAP. The demonstration of stability is analogous to
the demonstration of stability for SMP.

One can also show that this procedure produces not only stable but also
”student-optimal” matching. The demonstration was first described by Gale and
Shapley in [1] by induction. A college to which a student could be assigned in
a stable matching is called ”possible” for the student. Assume that, at a
certain point in the development of the algorithm, no student has been removed
from a college that is impossible for him. Now assume that college C accepts
students $\\{s_{1},s_{2},...,s_{q}\\}$ and rejects student $s^{\prime}$. We
must show that C is impossible for $s^{\prime}$. The student $s_{i}$ prefers C
to all the other colleges, except those who have already refused him and
therefore are impossible for him by assumption. Consider a hypothetical
matching where $s^{\prime}$ is assigned to C. At least one of the students
$\\{s_{1},s_{2},...,s_{q}\\}$, say $s_{i}$, will be assigned to a less
preferred college than C. But this matching is unstable because $s_{i}$ and C
prefer each other and they would disturb the system. So C is impossible for
$s^{\prime}$. In conclusion, The deferred-acceptance (DA) procedure rejects
only those students from the colleges that are not possible in any stable
matching and therefore the resulting matching is ”student-optimal”.

#### NRMP Algorithm

Actually, there was already a procedure very similar to the DA that was used
in the ”National Residence Matching Program” (NRMP) to assign medical students
to hospitals. The NRMP method is equivalent to the DA procedure but it works
inversely [116]: the matching obtained is ”college-optimal” rather than
”student-optimal”. The algorithm works in the following way: each college with
quota $q$ admits $q$ preferred students. Students who are admitted to multiple
colleges choose only their favourite and therefore are deleted from the list
of colleges that they have not chosen. At this point, colleges that have fewer
students than their quota choose the other preferred students until they reach
their quota or until they have exhausted their preference-lists. Once again,
students accepted into more than one college accept only their favourite
college, and so on. The procedure ends when no college can admit other
students (either because they have reached their quota or because they have
exhausted their preference list). The resulting matching is stable and it is
”college-optimal”.

Based on these two procedures (DA and NRMP), Gale and Sotomayor [116]
demonstrate the following results:

  1. 1.

Although, for students, the NRMP procedure is worse than the DA procedure, it
is true that all students admitted to a college with the DA procedure will
also be admitted to that college in the NRMP procedure. Vice versa, even if-
for colleges- the DA is worse than the NRMP, the number of students $n(C)$
admitted in college C will be the same both in the DA procedure and in the
NRMP procedure.

  2. 2.

If a college extends the list of eligible students, then this will make the
resulting matching (both for DA and NRMP) better for students but worse for
colleges.

  3. 3.

Student-optimal matching is Pareto optimal: that is, there are no matching
(stable or unstable) that are better for all students than student-optimal
matching. But this is not true concerning college-optimal matching.

####  4.5.2 Stable Roommate Problem

So far, we have considered the case in which the elements to be joined belong
to two disjointed sets (men and women). In other words, we have dealt with a
”bipartite matching problem”.
Now let us imagine we have a system of $N$ individuals (no matter if male or
female) that we have to fix in pairs in $N/2$ rooms: this type of problem is
commonly called stable roommates problem (SR) [120, 121]. This problem is the
non-bipartite version of the SMP, it was first described in the papers of
Galey, Shapley and Wilson [81, 1] and is formally defined in this way: there
are $N$ people, each of whom has a preference list of the other $N-1$ people.
The goal is to find a matching in which stability is defined in a similar way
to the case of stable marriage, that is, there must not be two individuals who
are not in the room together but who both would prefer to be (i.e. no blocking
pairs). As for the SMP, the practical applications of this problem are
manifold [122, 123, 124].
The main difference with the SMP is that, while the latter always has at least
one stable solution, the SR may have no solution: as we will see later, Irving
[120] has proposed an algorithm that recognizes whether a stable solution
exists and, if so, how to find it.
Also for this problem, there are several variants: it has been demonstrated,
for example, that finding a matching that is ”almost stable”, that is, that
presents the minimum number of blocking pairs (defined in a similar way to the
SMP), is NP-hard and difficult to approximate [125]; it has been shown that if
ties are admitted in the preference lists, the problems of determining whether
a stable solution exists or not is NP-complete even if complete lists are
admitted [126]; on the other hand, it has been shown that the same problem can
be solved in polynomial times under different stability conditions, such as
super stability or strong stability [127, 128].
There are also extensions similar to those seen for the SMP in which, for
example, the rooms must contain more than two individuals (multi-dimensional
SR [129]).

In the following, we will show in more detail how the Irving algorithm works
to emphasize the main differences with the SMP, in particular showing that
there can be no stable solution.

#### An Algorithm for the Stable Roommates Problems

As already mentioned, if the problem is not bipartite, there may be no stable
solutions. This was first demonstrated by Galey and Shapley. They showed an
example with $N=4$ individuals with the following preference lists:

$m_{1}=\\{2,3,4\\}$ $m_{2}=\\{3,1,4\\}$ $m_{3}=\\{1,2,4\\}$
$m_{4}=\\{any\\}\;,$

and, as it can be easily proved, any individual placed in the room with
individual 4 will constitute a blocking pair for the system.
On the other hand, Knuth [84] showed that, as in the SMP, multiple solutions
can exist; this was shown through an example in which the system was composed
of $N=8$ individuals with 3 possible stable solutions. In the same article,
Knuth requested the need to find a polynomial algorithm (at worst) to generate
a stable solution, in case it exists. We will show how Irving in [120] solved
Knuth’s request by building a $O(N^{2})$ algorithm.

Irving’s algorithm can be divided into two parts. The first part consists of a
series of proposals that people make in sequence. In particular, if an
individual $m_{x}$ receives a proposal from an individual $m_{y}$, then
$m_{x}$ can reject it if he is already in the room with a partner he prefers,
or he can accept it if he prefers $m_{y}$ to his current partner. As in the
case of the GS algorithm, each individual makes proposals starting from their
first choice until accepted by someone. This phase of the algorithm ends when
each individual has a roommate or if an individual is rejected by all the
other individuals in the system.
It can be demonstrated that if $m_{y}$ refuses $m_{x}$ during the sequence of
proposals, they cannot be partners in stable matching. As a consequence of
this, if an individual $m_{x}$ proposes to $m_{y}$ then $1)$ $m_{x}$ cannot
have a better partner than $m_{y}$ and $2)$ $m_{y}$ cannot have a partner
worse than $m_{x}$.
Furthermore, if this first phase of the algorithm ends with an individual who
has been rejected by all the others, then there is no stable solution.
If, on the other hand, it ends with everyone having partner, then the
preference-list of the individual $m_{y}$ who has accepted the proposal of
$m_{x}$ can be reduced by eliminating from it all those who are under $m_{x}$,
and all those who have a partner they prefer to $m_{y}$. In this way, $m_{y}$
is first in the new list of $m_{x}$ which in turn is last in the new list of
$m_{y}$. Another important result is that if the reduced preference lists
contain only one element then they determine the stable solution.
If the number of items in the reduced preference lists is greater than one,
then the algorithm goes to the second step. In this second phase, the lists
will be further reduced and this procedure will be repeated either until
everyone has a partner specified in their list reduced to a single element, or
until someone is rejected by everyone. In this last case, there is no stable
solution.
The reduction of the lists in this second phase is based on the presence of
cyclical sequences of people $z_{1},...,z_{r}$ defined in this way:

  * •

for $j=1,...,r-1$ the second individual in the reduced list of $z_{j}$ is the
first individual in the reduced list of $z_{j+1}$.

  * •

the second individual on the $z_{r}$’s list is the first individual on the
$z_{1}$’s list.

Once such a cyclic sequence has been identified, preference-lists can be
further reduced with the same rules as in the first phase.
The main theorem that Irving has proved is the following: given a cyclic
sequence defined as above, call $a_{j}$ the first person on the reduced list
of $z_{j}$. Then $1)$ in any stable solution contained in these reduced
preference lists $z_{j}$ and $a_{j}$ either are partners for every $j$ or for
no $j$. $2)$ if there is a stable solution where $z_{j}$ and $a_{j}$ are
partners, then another exists where they are not.
Finally, we have that:

  1. 1.

if the problem admits a stable solution, then this stable solution is
contained in the reduced preference lists.

  2. 2.

if one or more reduced preference lists contain zero elements, then there is
no stable solution.

  3. 3.

if the reduced preference lists contain only one person, then they determine a
stable solution.

In this way, Irving has built an algorithm that in addition to deciding
whether a stable solution exists or not, it finds one in the positive case.
Furthermore, he has shown that at worst this algorithm has a polynomial
execution time $O(N^{2})$.

####  4.5.3 The Family Problem

Throughout most of this review paper, we have considered only ”bipartite
matching like” problems, in which the system was always composed of two
separate sets to be coupled, which were represented, for example, by men and
women, colleges and students or workers and firms. Previously, however, we
dealt with the case in which the system was no longer disjointed but made up
of only one ”type” of individuals: the SR is the monopartite version of the
SMP. We could therefore say that so far we have dealt with the ”1-partite
matching problem” ( such as SR) and the ”2-partite matching problem” (such as
SMP). Here, we introduce the more general ”k-partite matching problem”, in
which the disjointed sets are $k$: when $k=3$ the sets could be called
product-consumer-company, when $k=4$ product-worker-company-machines, and so
on.
The idea of generalizing the SMP to a multi-partite problem derives from Knuth
monography: in this work, as already mentioned, he proposed 12 questions and
one of these asked if the SMP could be generalized to the case of three
separate sets (man, woman and dog). For simplicity, we will often refer to the
3-partite matching problem which we will call ”family problem” (also called 3
genders stable marriage, 3GSM [130]), but most of the results can be easily
generalized for any $k$.

#### The General Family Problem

In the family problem (FP) there are three types of categories of $N$ players:
men, women and children (or, in Knuth’s version: men, women and dogs). Each
agent has a preference list of pairs of agents from the other two sets. The
goal is to compose ”families” of three people (a man, a woman and a child) so
that the final matching is stable. The definition of stability is a direct
generalization of pairwise stability in SMP (that we can call ”triplewise”
stability): a matching is stable if there are not three people (composed by
agents of different sets) who do not form a family but who mutually prefer
each other than to remain in their current family. That is, there must be no
”blocking families”.
In the same way, we can define the ”3-dimensional roommates problem” (also
called ”three persons stable assignment problem” 3PSA [130]) in which the
agents of the system are all of the same ”type”, such as students, and must be
grouped into triple rooms so that there is no triplet of students who are not
in the room together but that would all prefer to stay together than to stay
in their current rooms.
As Knuth posed the problem in his 12 questions, there was no definition of
”ordering preference” or stability. As we shall show studying the many-to-many
matching problem, there can be several ways to define preferences (on couples
or individuals for example) and stability.
To keep everything in close analogy with the SMP for the moment we will keep
the notion of stability defined above and the ordering preference on the pairs
of agents of the other two sets.

As we will see in the next paragraph, when the system is k-partite with $k\geq
3$, the problem becomes computationally more complex. While polynomial
algorithms exist for SMP and SR to find a stable solution (if it exists), this
is not true for FP.
Furthermore, for $k\geq 3$ the theorem of the existence of stability fails:
that is, it is not always true that there is a stable solution, and we will
demonstrate it at the end of section 5. In reality, as we saw before, this
theorem also fails for $k=1$ and therefore is valid only for $k=2$, which
makes the SMP a very particular model.

#### NP-Completeness of Family Problem

The next question we ask ourselves is: is there a polynomial algorithm that
finds, if it exists, a stable solution to FP or 3PSA?
The answer is unfortunately negative as the FP and 3PSA are NP-complete and
therefore an efficient algorithm for these two problems is unlikely. The
firsts to demonstrate this were Ng and Hirschberg in [131] and independently
also Subramanian in [132]. We will not go into the details of the
demonstration but we will show the main steps. The authors in [131] took
advantage of the fact that the ”3D-matching problem” is NP-complete to
construct a polynomial transformation from this problem to the FP.
The definition of 3D-matching problem (3DM) is as follows: given three
disjoint sets $\\{A,B,C\\}$ and given a set of triple $T\subseteq\\{A,B,C\\}$,
one wonders if there exists an $M\subseteq T$ such that $M$ is a complete
matching, meaning that each element of A, B and C appears exactly once in $M$.
This problem turns out to be NP-complete [78]. The two main theorems for the
proof of Ng and Hirschberg are the following:

  1. 1.

Let $I$ be an instance of 3DM (i.e. a set of preference lists). If with such
$I$ there exists a complete matching $M$ of 3DM such that $M\subseteq T$, then
the instance $I_{FP}$ of the FP, constructed starting from an appropriate
polynomial transformation from $I$, contains stable matching $M_{FP}$.

  2. 2.

If the instance $I_{FP}$ has a stable matching, then $T$ contains a complete
matching for instance $I$.

Since the construction of $I_{FP}$ from $I$ can be done in polynomial time and
we know that 3DM is NP-complete, then theorems 1 and 2 together prove that  FP
is NP-complete. Similarly, it can be shown that 3PSA is also NP-complete.
This type of result is not surprising in computer science since the boundary
between P and NP is often marked between the numbers 2 and 3. Indeed, in our
case when $k=1,2$ we saw that the problem is P-complete (we have a polynomial
algorithm $O(N^{2})$), while for $k\geq 3$ the problem is NP-complete.
As with the SMP with incomplete lists and ties, approximation algorithms also
exist for FP and 3PSA, although the complexity of these two problems is even
higher.

However, at the end of the paper of Ng and Hirschberg, the authors mentioned
that their (anonymous) reviewers had pointed out that their conclusions were
valid for ”inconsistent” preference lists, and wondered if they were also
valid for preference lists that are not ”inconsistent”. To understand the
meaning of inconsistent lists, consider the following example: the man $m$
might prefer the pair $(w_{1},c_{1})$ to the pair $(w_{2},c_{1})$, and at the
same time prefer the pair $(w_{2},c_{2})$ to the pair $(w_{1},c_{2})$. This
means that the man $m$ does not consistently prefer the woman $w_{1}$ to the
woman $w_{2}$. The question of the reviewers of Ng and Hirschberg is the
following: if the preference lists are prevented from being inconsistent, then
does the FP (or 3PSA) remain equally NP-complete?
Again the answer is affirmative and was demonstrated by Huang in [133]. The
same author has also shown that the problem remains NP-complete even when
admitting ties in the preference lists.

Having seen that even the most general case of FP is NP-complete, one may
wonder if there is a particular case of FP that can be solved in polynomial
times. Consider a model in which each player has two separate preference lists
for the other two sets. Suppose, for example, that each man first evaluates
the women and then the child; that every woman first evaluates the man and
then the child, and finally that each child first evaluates the man and then
the woman. In this case, one can show that by applying twice the classic GS
algorithm, in which men first propose to women and then to children, a stable
matching is obtained if they join these two matchings (men-women, men-
children) [134]. The problem is that this condition on the preference lists is
weak. A single exchange is enough so that the GS algorithm no longer works: it
is enough for a single woman to choose first based on the child and then on
the man [135].

##  5 SMP and Biology, Mathematics and Other Applications

The SMP is applicable to many real-world situations [136, 137, 138, 139, 140,
141, 142, 143, 144, 145, 146, 147]. Indeed, it appeared to solve a practical
problem such as that of satisfactorily placing medical trainees in various
hospitals, among which there was a high competition to obtain these medical
students.
So, since the mid-1900s, the SMP has been widely studied by economists,
mathematicians, computer scientists and lately also by physicists.
Consequently, the spectrum of applications of this problem has greatly
increased and even in 2012 L.S. Shapley and A.E. Roth were awarded the Nobel
Prize in Economics for the theory of stable allocations and the practice of
market design [148], in which SMP dynamics were exploited.

So this section will be multidisciplinary and we will briefly show the main
results obtained by different scientific fields that are different from the
SMP canonic.
We will start from the most ”out of the box” application of the SMP: the
application to biological systems. In particular, we will see that an ”SMP
style” process manages to account for the evolutionary dynamics of some
communities of microorganisms.
We will then describe another unconventional application of SMP: stable
resource allocation in the wireless network. We will see that an SMP theory
can help solve overloading problems.
Finally, we will briefly study some concepts already seen in the previous
sections and we will deepen them with the magnifying glass of mathematics.
Mathematicians’ studies on the SMP go far beyond what we present in this
review, but these studies go beyond the scope of this work.

###  5.1 SMP and Biology

Here we want to give an example of SMP’s application that goes beyond social,
mathematical or IT fields. We want to show that this model can give us clues
in various areas of science. Indeed, its simplicity and the concept of
”stability” can be useful even in very complex non-social systems: we will
therefore deal with SMP and biology.

####  5.1.1 Microbial Communities Ecosystem

Several works exploit the relationship between SMP and biology [149, 150, 151,
152].
In particular, we want to show the latest works carried out by researchers
from the University of Illinois [150, 151], who developed a mathematical model
based on SMP that could help scientists understanding the particular
characteristics of microbial communities, allowing them to remain stable
despite their strong biodiversity.
Microbial communities are groups of microorganisms that can exist in different
types of environments such as the soil, the oceans or even in the human body
(such as the human gut microbiome). Although these communities involve
different types of microorganisms and can be very complex (thousands of
different species can coexist in a very small volume), it has been shown that
they often exist in multiple stable states that are different from each other
because the proportions of the different coexisting species [153]. By
”stability” we mean how well a community can manage changes: when a community
is stable, for example, it can resist to the modification of one of the
nutrients or the invasion of a new species. These changes can also lead to the
transition from one stable state to another. Understanding better how the
stability of these microorganisms works may be useful to control microbial
ecosystems [154, 155]: it could be possible to change the status of a soil
microbiome by adding microbes or nutrients. At the moment, however, due to its
complexity and diversity, it is impossible to manage a microbial community.
In [150] the authors build a predictive model to measure the stability of
microbial communities based on the SMP.

####  5.1.2 SMP Model of Microbial Community Dynamics

The main assumption of the model is that, as described for the first time in
[156], many microbes tend to use the various nutrients in a specific
sequential order. When they are exposed to a medium containing more nutrients,
the microbes start using their favourite first. Once the first nutrient is
exhausted, they start using their second favourite nutrient until all the
nutrients are depleted. It has been shown experimentally that the most
prevalent genus in the human gut microbiome behaves in this way [157].
The use of the SMP model to describe a dynamic community in which microbes use
one nutrient at a time is a conceptual approach that elegantly justifies the
existence of multiple stable states, the transition between these states and
their resilience.

In this case, marriages are represented by one-to-one matching between
microbial species and nutrients. In the more general version of the model, all
microbes can use all the available nutrients. In the real case, the microbes
can use only a subset of all available nutrients and this fact can be easily
implemented in the model by exploiting the SMP results with incomplete lists
(section 4).
So each species of microbes classifies the nutrients from the most preferred -
such as glucose for E.coli- to the least preferred. Similarly, the ranking of
microbes for nutrients reflects the ability of microbes to use that nutrient.
If the microbe $x$ is the most skilled in using the nutrient $y$, then the
microbe $x$ will be the first in the nutrient $y$ preference list. In this
model, the competitive ability of a microbe for a nutrient is directly
proportional to the rate with which this microbe extracts this nutrient from
the medium.
The final result of the competition between microbes corresponds to a stable
state without ”blocking pairs”, that is, without microbes that can switch to a
nutrient $n$ that they prefer more and, at the same time, be more able to use
$n$ than its current user.
The ecosystem will remain in this stable state until it is disturbed by the
removal of a nutrient or the addition of a new species of microbes.
Another assumption of the model is that the quantity of a certain species of
microbes in a stable ecosystem depends on the ranking of the nutrient it is
using: if it uses its favourite, it will be more abundant than it would be if
it used nutrients with a lower ranking.

Figure 14 shows two examples of perturbation of a stable state with two
species of microbes ($M_{1}$ and $M_{2}$) and two nutrients ($N_{1}$ and
$N_{2}$): one in which a third species of microbes is added $M_{3}$, and one
in which a third nutrient is added $N_{3}$. In both examples, there is a
transition between one stable state and another, but both additions ($M_{3}$
in the first case and $N_{3}$ in the second) are rejected by the ecosystem.
The examples in figure 14 show that:

  1. 1.

the invasion of a new microbe increases the competition between the microbes
for the various nutrients and, in general, there is a transition to a less
”optimal” stable state for the microbes (the sum of the rankings of the
”partners” of the various microbes is higher).

  2. 2.

the addition of a nutrient, on the other hand, reduces competition and brings
the system back to a more ”microbes-optimal” stable state.

Figure 14: Microbial community dynamics: the boxes at the top show the
preference lists of microbes and nutrients. In the left panel (A) the system
is in an optimal state for the microbes $M_{1}$ and $M_{2}$ and it is shown
what happens after the addition of the species $M_{3}$: the system translates
into a less optimal state (B) . In the right panel (B) a nutrient $N_{3}$ is
added to the ecosystem in order to return to the microbes-optimal (A) state
[150].

In general, as we have seen, the greater the number of microbes and nutrients
in the ecosystem, the greater the number of stable states (section 3).
Furthermore, the stable states can be ordered starting from the microbes-
optimal (corresponding to the GS state in which ”the microbes propose”) up to
the microbes-pessimal, that is, from the state in which the microbes have the
lowest ”average ranking partner” to the highest one. To move from one state to
another, a ”marriage” should be broken between a microbe and a nutrient.
Likewise, if a nutrient is added into the system, the competition between the
microbes increases and the transition between stable states is in the
direction of the microbes-pessimal state. Removing a microbe, instead, has the
opposite result: the competition decreases and the system shifts to a more
optimal state for the microbes. These results have interesting implications:
the introduction of an antibiotic in the ecosystem could translate the system
towards a more microbes-optimal state and therefore with greater total
biomass. Although this conclusion seems rather counter-intuitive, it has been
experimentally verified [151].

More details and results about this model can be found in [151, 150].
Simplifying, always based on the concepts of the SMP, the authors describe the
properties of the network of the stable states of the ecosystem. The nodes
(the stable states) are connected if a perturbation on the system connects
them. Furthermore, the stable co-existence of large quantities of several
different microorganisms is demonstrated through the complementarity of the
priorities on nutrients, that is, through the complementarity of the
preference lists of the various existing microbes.
The basic model explained above can be expanded to make it more realistic
through the various variants of the SMP explained in sections 3 and 4. One
possibility, for example, is to relax the assumption that there is a one-to-
one matching and incorporate the simultaneous use of multiple nutrients by
different microbes to have many-to-many matching.

###  5.2 SMP in Wireless Network

Smartphones and many other popular handhelds and portable devices today
contribute to increasing traffic in the current wireless network. To overcome
this problem, new systems such as cognitive radio networks or small cell
networks have emerged and, as a consequence, these systems will lead to an
increasingly complex wireless architecture.
In such an environment, where the density of the wireless network is
continuously growing, it becomes important to manage the problem of resource
allocation efficiently. In particular, it is more convenient to focus on the
”self-organization” and ”self-optimization” approach rather than relying on
the traditional centralized mechanism [158]. Therefore self-organizing
systems, in which small cell base stations and various devices can make
resource management decisions quickly, are needed.
We now show how the problems of traditional mathematical methods to optimize
the resource allocation of the wireless network - such as centralized
optimization and game theory - can be solved by applying the fundamental
concepts of SMP (figure 15).

####  5.2.1 SMP Model for Wireless Resources Allocation Problem

In general, the wireless resource management problem can be represented as an
SMP in which men and women are replaced by resources and users. The former can
represent by different elements such as power or time-frequency; the latter,
on the other hand, can represent the various devices or applications for
smartphones.
The matching can be a one-to-one type, a many-to-one type or a many-to-many
type and depending on the type of scenario, each resource and user have a
maximum number of agents with which they can be matched. A matching is simply
an allocation between resources and users. The goal is to pair users and
resources by optimizing the different goals of the players in the system. Each
user and resource builds a preference list of the elements of the opposite
set. A preference can be defined in terms of a utility function that
quantifies the quality of services (QoS) obtained in a given matching [158].
As usual, the matching is stable if there are no blockingpairs. If there is no
user $u$ and resource $r$ that are not coupled together but both would prefer
to be.
The basic algorithm that guarantees a stable solution is the GS algorithm. It
has the advantage of not requiring system agents to know the other agents’
preference lists, but any decision is local (based on the preferences of the
individual). Hence, the GS dynamic does not require a centralized controller.
The GS algorithm has been extended to the case of many-to-many matching by
balancing the role of proposers and receivers in the context of wireless
networks, for example in [159, 160].
There is a great deal of literature in which mathematical methods are proposed
to optimize resource allocation in many wireless systems, in particular,
centralized optimization and game theory [161, 162, 163, 164, 165, 166]. These
approaches have various limitations including an excessively high computing
complexity.
Promising techniques based on the SMP have been developed recently to overcome
the limitations of previous models [167, 168, 169]. Some of the advantages of
the SMP approach are that one can find different solutions in terms of
stability and optimality, reflecting the different purposes of the system and
the possibility of implementing efficient algorithms that favour self-
organization.

Figure 15: Matching game in Wireless local area networks: figure reprinted
from [170].

Following Gu et al. in [158], we can classify three types of matching model in
the context of wireless networks:

  1. 1.

Canonical matching. This is the classic case where an agent’s preferences in
the game depend solely on the information available to the agent. This type of
matching is particularly appropriate for the cognitive radio network (CRN): it
is a two-side system in which licensed primary users PUs (channels) must be
accessible to unlicensed secondary users SUs. In a CRN, a centralized system
would not be suitable, as PUs and SUs often belong to different operators and
cannot be managed centrally. In [164, 163] the CRN is modelled as a one-to-one
SMP between PUs and SUs. The preferences of both parties are based on the same
utility function calibrated on the rate of transmission. The authors in [164,
163], through a modified version of the GS algorithm, found a solution that
compared to the classic random channel allocation scheme, brought significant
improvements for the SUs.

  2. 2.

Matching with exeternalities. In this case, there are externalities in the
system which form interdependencies between the preferences of the agents. An
example concerns small cell networks: when a user is paired with a resource,
the preferences of other users will change accordingly, because that resource
could cause interference to other resources using the same frequency.
Therefore, agent preferences, unlike canonical matching, also depend on the
other matchings in the system.
A classic example of these externalities is the peer effect [144]. The
preferences of users on a resource depend on the type and number of users who
are connected to that resource. In [167] the problem related to resource
allocation in small cell networks is formulated as a one-to-many matching
model in which users can be associated with a single small cell base station
(SCBS). At the same time, each SCBS has a maximum number of users with which
it can connect. User preference-lists are based on the trade-off between error
rate and delay that they can get; while SCBS preference lists are based on
load balancing by pushing users on smaller cells.
The authors in [165, 171] developed a new algorithm to overcome the fact that
the GS algorithm, due to the peer effect, did not achieve a stable solution.
Also in this case, with a matching problem approach, more convenient results
are obtained (in terms of utility) compared to traditional methods based on
the best neighbour scheme.

  3. 3.

Matching with dynamic. Finally, this matching class is appropriate for
situations in which preferences vary with time according to the conditions of
the external environment (time-varying traffic, fast fading or mobility). In
this case, the temporal dimension must be taken into account to solve the
matching. However, at any moment the problem can be interpreted as one of the
two types of matching explained above.

In all types of matching, however, finding a stable solution in the stable
marriage sense guarantees system robustness to possible deviations and this
creates benefits for both resource owners and users. Having many deviations in
the system, that is, many blocking pairs, implies an unstable network
operation.

Despite all the advantages of matching theory, it has some limitations: first
of all, there can be more stable solutions and therefore the problem of which
is better appears; moreover, a stable solution is not necessarily the optimal
solution. In any case, compared to classic models, the stable marriage
approach for the wireless network improves the performance of resource
allocation in many fields of application. For a complete overview about
matching theory in wireless network one can refer to [172].

###  5.3 SMP by Mathematicians

Mathematicians have also contributed a lot to the study of SMP and especially
recently research has been very active. These studies, however, go beyond the
purposes of this review and in the following, we will only deepen two topics
already covered in the previous sections: in the first paragraph we will
deepen some issues concerning the average number of stable solutions in the
classical problem; in the second paragraph we will study some themes on the
generalizations of the classic model.

####  5.3.1 Maximum Number of Stable Solutions in the Standard Problem

As we have seen in section 3.2.1, Pittel through probabilistic arguments has
solved the integral in equation (1) obtaining an asymptotic formula for the
average number of stable solutions in the SMP, i.e. he has obtained the
equation (2).
However, we saw that this formula did not agree well with the numerical
simulations and it was necessary to adopt specific approximations to solve
equation (1), obtaining a more correct solution.

Figure 16: Number of stable solutions with different number of men and women:
average number of solution as a function of (M-W).

Still with regard to the average number of stable solutions, Pittel has
obtained a formula for the case in which the number of women is different from
the number of men. In particular he has shown that, if $M$ is the number of
men and $W$ is the number of women and if we call
$\lambda=log(\frac{M}{M-W})$, the average number of solutions $n$ for
$M>W\to\infty$ goes as [173]:

$n\approx
W\frac{exp(\frac{e^{\lambda}-1-\lambda}{e^{\lambda}-1})}{(M-W)\lambda}\;.$
(79)

Consequently, if $\frac{M}{W}\to\infty$, i.e. for big differences between men
and women, then we have $n\to 1$. In this case, the analytical result is
consistent with the simulation results. We have performed a series of
numerical simulations, shown in Figure 16: it shows the average number of
solutions against the difference between men and women $M-W$ for five
different values of M. Each point in the graph is the average of 100
simulations.

Another interesting question that can be asked about the number of stable
solutions is the following: since at least one stable matching exists, it
becomes natural to ask what the maximum number of stable solutions is, given a
certain size $N$ of the system-which we denote with $f(N)$. In the following
paragraphs, we will expose the main results in recent years regarding the
upper bound and the lower bound of $f(N)$.

####  $f(N)$ Upper Bound

The problem of determining the maximum number of stable matching given a
system of size $N$ is a difficult question both from a theoretical and
computational point of view. This problem appeared first in 1976 in the
Knuth’s monograph. In recent years, mathematicians and computer scientists
have made numerous efforts to solve this problem, but it remains an open
question.
Trivially one could say that the maximum number of stable matchings is $N!$,
as it is the maximum number of matching with $2N$ individuals. In 1976 Knuth
showed an SMP with size $N=4$ in which there were 10 stable solutions.
Subsequently, Eilers showed through an exhaustive computer search that 10 is
the maximum number of stable matches for a system of size 4 ($f(4)=10$) and
that this system is unique, that is, there is only one way of composing the
preference lists to have 10 solutions with $N=4$ [174].
The first real progress regarding the upper bound of $f(N)$ was done by
Stathoupolos in his master’s thesis in 2011, in which he showed that $f(N)$ is
at most of the order $O(N!/C^{N})$, for some constant $c$. More recently, an
article by Drgas-Burchardt and witalski [175] showed a weaker upper bound of
about $3N!/4$. A further step was made in 2018 by Karlin, Gharan and Weber
[176] who have shown that there is a universal constant $c$ such that $f(N)$
is at most $c^{N}$. To arrive at this conclusion, the authors exploited the
theorem previously shown which affirms the existence of a univocal
relationship between stable matches and rotations. The best upper bounds
before this result were of the order $2^{NlogN-O(N)}$.

####  $f(N)$ Lower Bound

The first results about $f(N)$ lower bound were achieved with $N$ being a
power of 2: Irving and Leather [82] have shown that if we denote with $g(N)$
the function that counts the number of stable matching with $N$ power of 2,
then it satisfies the recurrence relation:

$g(N)=3g(N/2)^{2}-2g(N/4)^{4}\;,$ (80)

with $N\geq 4$ and power of 2, and with $g(1)=1$ and $g(2)=2$. Furthermore,
they conjectured $f(N)=g(n)$ for $N$ power of 2. Later on, Knuth showed that
this $f(N)$ contains at least $O(2.28^{N})$ stable matching. More recently
Thurber has extended the work of Irving and Leather to all values of $N$, not
only for powers of 2 [174]. In the case of $N$ power of 2 the results of
Thurber coincide with those of Irving and Leather, while for all other $N$ he
found a lower bound of $O(2.28^{N}/c^{logN})$ for a certain constant $c$.

####  5.3.2 SMP Expansions

We now delve into a topic already covered in section 4 concerning the
generalizations of SMP studied by mathematicians: we will demonstrate that in
the Family problem (FP) the stability theorem is not satisfied, i.e. there may
exist no stable solutions.

#### Stability of $k$-Partite Matching Problem

Figure 17: Alkan’s example: preference-lists of the agents in the Alkan’s
example [177].

The possibility of the non-existence of stable matching in the FP was first
shown by Alkan in 1987 in [177]. He showed through an example that it is not
possible that in the FP there could be no stable matching (as Galey and
Shapely did for Stable Roommate Problem).
Let us analyze Alkan’s example. Consider an FP in which there are three men
$\\{A,B,C\\}$, three women $\\{\alpha,\beta,\gamma\\}$ and three children
$\\{a,b,c\\}$. Each agent builds a preference-list on all possible pairs of
agents from the other sets. The possible pairs for an individual are $N^{2}$
which in our example corresponds to 9 possible pairs to put on one’s
preference-list. The preference-lists of our case are shown in figure 17 (they
are partially specified since it is sufficient for our example).
Consider the $A\alpha a$ family, the scores obtained by the three agents are
$\\{3,1,1\\}$ respectively. To be stable, a matching must assign man $A$ to at
least his third favourite family. Note, however, that any matching that
contains the $A\alpha c$ family, which is the preferred family of $A$, is
blocked by the $C\gamma c$ family. Additionally, any matching that contains
$A\beta c$, which is $A$’s second favourite, is blocked by $B\gamma c$. Hence,
we deduce that all the matchings that do not contain $A\alpha a$ are unstable.
Similarly, it is found that all matchings that do not contain the family
$B\beta b$ are unstable and that all matchings that do not contain the family
$C\gamma c$ are also unstable. So the only possible matching is that which
contains the families $A\alpha a$, $B\beta b$ and $C\gamma c$. However, even
such a matching is unstable because it is blocked by the family $A\beta c$.
It follows that for the FP specified by the preference-lists in figure 17
there is no stable solution and therefore the FP does not guarantee the
existence of a stable matching. The same arguments can be used to generalize
this result when $k>3$ [177].
Although there may not be a stable solution for the FP, it can be shown that
the number of stable solutions goes exponentially with $N$ and this can be
done in a similar way to what was done in the bipartite case [131].

##  6 Stable Marriage Problem and Economics

One of the areas in which the SMP was most successful was the economic field.
Many markets lend themselves very well to being modelled through the stable
matching theory that we have studied so far. Indeed, in 2012 the Nobel prize
for economics was awarded to Shapley and Roth for their theoretical and
experimental contribution to the stable matching theory.
In this section, we shall revisit the main applications of SMP by economists.
After a brief introduction to Game Theory, we will start by telling the story
of the 2012 Nobel Prize and then we will describe the main works that led to
the winning of this award. In particular, we will see in more detail the
famous problem of the allocation of doctors in hospitals, we will study a
specific case, based mainly on Roth’s work, of allocating students in high
schools, we will analyze the SMP applied to the kidney exchange and, finally,
we will describe possible extensions of the SMP to different types of markets.
However, this is not exhaustive: to have a global vision of current economic
research on matching theory, one can look, for example, at [178].

###  6.1 SMP in Game Theory

In the second half of the 20th century, Game Theory was consolidated as a
model of social, biological and economic systems. It was born in 1944 thanks
to the work of John von Neuman [179] and today it is defined as a branch of
applied mathematics focused on the description of systems with many agents
with conflicting interests. Its study led to various Nobel laureates in
economics, for example, that of John Nash, John Harsanyi, and Reinhard Selte
in 1994, that of Thomas Schelling and Robert Aumann in 2005 [180], and more
recently that of Lloyd Shapley and Alvin Roth in 2012.

####  6.1.1 Introduction to Game Theory

A game is intended as a set of players each having a set $S$ of possible
strategies $s$ and an associated cost function $U(s)$ which depends on the
strategy used by the player in question and the one used by the other players.
A state of the game corresponds to the adoption of a certain strategy for each
player. Players are said to be rational in the sense that they will try at all
times to minimize their cost function. As it normally happens in real life,
the final result of the game for a single player depends not only on the
strategy adopted by himself but also on that adopted by all the other players,
over which that player has no decision-making power.
Therefore, in general, players will not have a single optimal strategy but the
best of their actions will vary depending on the decisions made by the other
players. A classic example is the stock market [181, 182] where one has to
decide between buying or selling shares, and the most convenient thing will be
to do what fewer players do.

The fundamental concept of game theory is the so-called Nash equilibrium, from
John Nash [183]. Suppose there is a state
$\prod^{*}=\\{s_{1}^{*},...,s_{N}^{*}\\}$ where the $i$-th player is adopting
the strategy $s^{*}_{i}\in S_{i}$. If that state is such that every agent is
playing the best of his response to the decisions of the others, then
$\prod^{*}$ is a Nash equilibrium. These states persist over time since no
player is tempted to deviate from his behaviour, as $s^{*}_{i}$ is the
strategy that minimizes its cost function, that is, by fixing the strategies
of the other players, we have that

$U_{i}(s_{1}^{*},...,s^{*}_{i},...,s_{N}^{*})\leq
U_{i}(s_{1}^{*},...,s_{i},...,s_{N}^{*})\;.$ (81)

The definition was accompanied by the proof of Nash’s Theorem [183] which
guarantees the existence of these equilibrium states (they can be more than
one) in any game if a broader strategy definition than that given so far is
included. It is important to note that the stability defined according to Nash
is a static concept and does not imply that game dynamics lead to stable
states in the Nash sense [184].

####  6.1.2 SMP and Nash Equilibrium

As described in section 2, an SMP state is unstable if a man $m_{i}$ and a
woman $w_{j}$ are not married in that state, but they would both prefer to be
married rather than stay with their current partner. In real life, this would
be enough for the divorce to occur in the marriages to which mi and $w_{j}$
belong. In this way, they can form a new marriage for themselves, both gaining
happiness.
So unstable couples lead to the reconfiguration of states if the players are
considered acting rationally. A Nash Equilibrium will therefore be a state
that does not contain any unstable pair, as no player will find anything
better to do than stay with his/her current partner. In other words, such a
state will be stable to the individual actions of the players, hence a state
of Nash Equilibrium is also called Stable Marriage. The marriage problem, in
conclusion, studies the existence and properties of Nash equilibrium states,
so it fits very well for economics applications.

###  6.2 Stable Matching: a Nobel Prize History

In the traditional economic analysis, those types of markets in which price
plays a fundamental role are extensively studied. In most markets studied by
economists, the price ”adjusts” to match supply and demand. Indeed, in many
cases, these markets function well enough both in theory and in practice.
In certain situations, however, the ”standard” market mechanisms encounter
some problems and there are cases in which the price is no longer the
fundamental element as it cannot be used to allocate resources. For example,
many schools and universities are prohibited from imposing school fees, or, in
the case of human organ transplants, monetary payments are prevented for
ethical reasons. In these cases and many others, however, an allocation of
resources is required despite the absence of monetary transactions.
The problem for economists was to understand how this type of processes work
in reality and when the outcome of these processes is efficient. The answer to
these questions lies in the theoretical and practical understanding of stable
matching theory. The analysis of the mechanisms for allocating resources can
be, with a certain degree of approximation, addressed to the analysis of the
abstract model of the SMP.

To underline the importance of these types of market, the 2012 Nobel prize was
awarded to Lloyd Shapley and Alvin Roth thanks to their research on matching
theory that extends from abstract models developed in the 1960s, to the
empirical works of the 1980s in which practical solutions are applied to real-
world problems. Examples include, as we will see in the rest of this section,
the assignment of new doctors to hospitals, students to schools or human
organs for transplants to recipients.

Lloyd Shapley is one of the most important researchers in the field of
cooperative game theory. His works not only reinforced the theoretical
foundations in this field but also stimulated practical research applied to
policymaking. Shapley, in collaboration with Gale, Scarf and Shubik, created
the theory of matching markets. In particular with the famous 1962 article
[1], Gale and Shapley expressed the hope that one day their theoretical work
would be finalized in practical applications. So Lloyd Shapley has been
recognized for his early theoretical contribution to the matching market
theory. The clarity and elegance of the Gale-Shapley paper made this article
one of the most important academic ”must-read” for economics students across
the world.
However, the real-world relevance of Shapley’s work was recognized only twenty
years later, in the early 1980s, with Alvin Roth’s work on the market for
newly graduated doctors.
In Roth and Sotomayor’s book (1990) [83] the main practical works on matching
theory are described, including many fundamental results from Roth and
coauthors. Roth’s research has always been aimed at applying game theory to
real situations. In [185] he describes how laboratory experiments and field
observations can connect to game theory and thus make economics a satisfactory
experimental science. Regarding matching theory, Roth’s work has advanced the
understanding of how markets work. Using empirical, experimental and
theoretical methods, Roth and his coauthors studied the institutions that
improve market performance by understanding the fundamental importance of the
concept of stability and therefore encouraging real institutions to create
”compatibility”. Importantly, these contributions led to the redesign of a
large number of real-world markets.

In the following, we will study the main applications of SMP in various two-
sided markets: doctor allocation, student allocation and kidney exchange. A
key feature of these examples is that price is not part of the process.
However, the absence of the in the SMP model does not limit its applicability.
Shapley and co-workers have examined extensions of the original model which
include the price and the salient features of these extensions compared to the
original model.
A direct application of matching with the price is that of auctions, in which
objects must be paired with buyers, and the price is a fundamental element. We
will not go into the details of these models but it is useful to know of their
existence to understand how vast the spectrum of application of the SMP is.

The 2012 Nobel Prize was therefore awarded for contributions to a booming
research field in which experimental theory and evidence interact with each
other. Although Lloyd Shapley and Alvin Roth have worked independently, the
success of their research is due to the combination of Shapley’s theoretical
works and Roth’s practical ones.
As we will see in sections 7 and 8, research in this field continues to grow
and create new insights on the functioning of social and economic relations
(and not only), and it turns out to be a promising field of study for the
future.

###  6.3 Matching Doctors and Hospitals

Here we present the main application of the SMP (not only in the economic
field). The problem of allocation of doctors to hospitals was the first
problem to be studied through matching theory and inspired most of the
subsequent works.
To give a concrete example we will show the main works of Roth and others on
the doctor market in the United States, even if the matching problem theory
has also been applied to other countries such as Canada and Britain [186,
187].

Figure 18: Matching doctors and hospitals: example of Doctor-Optimal and
Hospital-Optimal solutions with the preference-lists in the table

In the United States, medical students are usually hired as interns in
hospitals. At the beginning of the last century, this market was very
decentralized [188]. Competition for scarce medical students in the 1940s
forced hospitals to offer internships to students even many years before
graduation. Hospitals were often assigned well before students could show that
they were qualified enough or even before students chose which branch of
medicine to work in. If an offer was rejected there was a high risk that it
was too late to make offers to other candidates.
A market structured in this way, as we will see later, clearly produces
unstable matching as there is no time to make offers that are beneficial to
both parties. To solve this problem, hospitals imposed deadlines to respond to
an offer, but this forced students to make decisions too early, without having
time to know if they would receive better offers.
To solve this problem, in the middle of the last century, it was decided to
assign the task of creating the matchings to a central organization: the
National Resident Matching Program (NRMP). As we have already seen in section
4, thanks to the work of Roth [119], it was shown that the NRMP algorithm was
no different from the classic GS algorithm. So Roth speculated that the main
reason the NRMP worked so well was that it produced stable matchings. He also
began studying other medical markets to see which matching algorithms produced
stable results and which ones did not and, as can be expected, the algorithms
that produced stable matching were the ones that achieved the most success. In
the following paragraphs, we will develop the tale just presented in more
detail and review the main articles about this topic.

####  6.3.1 Market for New Doctor in the US

The problems concerning the medical market in the United States mentioned
above were studied by Roth in [119]. In particular, before the NRMP was
established, this market suffered from defects in unravelling and congestion
[188]. Unravelling refers to the fact that offers to students were made long
before the students graduated. This did not allow students to show that they
were qualified or the offers were so premature that the students did not even
know in what field of medicine they would like to practice.
As for the congestion problem, it refers to the fact that, when an offer was
rejected, it may be too late to make other offers as other students may
already have accepted offers from other hospitals.
To solve this problem hospitals have imposed deadlines to accept or reject an
offer but this forced students to accept or reject without having the
possibility to know if the next offers would be better or not.
Such unravelling and congestion defects have occurred in many other markets,
most notably Roth found them in the following markets [119, 189]: entry-level
legal, medical market in the US, Canada and UK, business school, Japanese
university graduate, clinical psychology internships, optometry and dental
residencies in the United States.

When indivisible and heterogeneous goods are traded, as in the labour markets
mentioned above, the offers must be made individually, not to the global
market [188]. The problem of having to coordinate when to propose an offer can
cause market decentralization, unravelling and congestion. In [189, 190], the
authors studied through theoretical models how such defects can emerge.
Due to these failures of the medical US market, the NRMP was established as a
centralized clearinghouse: this institution has the task of creating matching
between hospitals and students and the algorithm used was equivalent to the GS
algorithm (or deferred-acceptance algorithm), therefore it produced stable
matching. As argued by Roth in [119], stability is the main cause of the
success of the NRMP algorithm. Since a stable matching is a Nash equilibrium,
stability means that for no pair of the system it is convenient to change.
Therefore there are no situations in which, for example, a student is assigned
to paediatrics even though he prefers dermatology and, at the same time, that
another student is assigned to dermatology department that, in turn, preferred
the previous student. In this case, a feeling of dissatisfaction would arise
both on the part of the student and on the part of the hospital.
Hence, stability reduces dissatisfaction and has meant that participants in
the NRMP were more and more, creating a virtuous circle in which greater
satisfaction brought more and more participants.

####  6.3.2 New Market Design

In this paragraph, we see how the insights from the previous paragraph can be
exploited to improve the efficiency of labour markets. What we said in the
previous discussion is not enough for real-world situations. Some
complications are absent in theoretical models. Real institutions have to
manage individuals who make mistakes, who do not understand the rules or
voluntarily neglect them and who, in general, are not the perfectly rational
agents of ideal models. Also, institutions must respect ethical and legal
constraints on the transactions that can be executed.
As described by Roth and Peranson in [191], the complexity of the real world
forces the NRMP algorithm to be modified. For example, since 1960 the number
of married couples who both graduated in medicine were increasing and, often,
they both preferred to work in the same geographic region. So they preferred
to contact directly the hospitals rather than undergoing the algorithm.
Therefore, a couple, from a theoretical point of view, is seen as a compound
agent who wants two jobs in the same geographical area violating the
”substitutability” assumption, a concept that we will formally define below.
Roth in [119] has shown that in a market where some agents are couples, a
stable matching may not exist.

Another problem was that the NRMP algorithm was an ”employer-proposing”
algorithm (analogous to the men-oriented GS) and thus favoured hospitals
rather than students.
In 1995 Alvin Roth was hired on the NRMP Board of Directors to build a new
algorithm. The goal of the new design was: ”to construct an algorithm that
would produce stable matchings as favourable as possible to applicants, while
meeting the specific constraints of the medical market” [191]. The new
algorithm designed by Roth and Pernason was an ”applicant-proposing” algorithm
modified to please couples. The instabilities produced by the presence of
couples were resolved sequentially, following the ”instability-chaining”
algorithm of Roth and Vate [101].
Since this new algorithm was adopted in 1997, more than 20,000 doctors have
been employed in hospitals with it [188].

###  6.4 Student-High School Allocation

We now focus on the problem of allocating students in schools. There is a lot
of literature on this type of problem [192, 32, 193, 194, 195, 196, 192].
However, we will see in particular the application of the SMP to the Ministry
of education (MOE) problem in Singapore [197] that is, in turn, mainly based
on the Roth works. The analysis of this problem will allow us to introduce a
topic of which we have not yet talked about in this review: the possibility
for agents in the system (men or women) to act dishonestly (by changing the
preference-lists) to obtain a better matching.
So, before talking about the practical application of SMP in Singapore
schools, following the work of Teo et al. [197] we will introduce the concept
of ”cheating” in SMP and the related algorithms to optimize the problem.

####  6.4.1 Optimal Cheating Model

Consider a two-sided market where a men-oriented GS algorithm is applied. As
already explained in section 2, a men-optimal solution is reached with this
mechanism. However, women can manipulate their preference-lists to achieve
better matching. The goal of this paragraph is to understand under which
conditions and how much women benefit from falsifying preference-lists. In
[147] it has been shown that if one uses the men-oriented GS, no man has the
incentive to falsify his preference-list as nobody would get a better matching
than what they would get with truthful lists. As for women, on the other hand,
Gale and Sotomayor [198] have shown that they can distort their preference-
lists and force the men-oriented GS to reach a women-optimal solution. In this
case, women use their original preference-list but declare ”unacceptable” all
men under their women-optimal partner. In the following paragraph, we explain
what happens if women are forced to use complete preference-lists, that is,
without declaring anyone unacceptable.

Consider again an SMP where the men-oriented GS algorithm is used. Suppose
that the woman $w$ does not know the preference-lists of the other agents in
the game. If you give the woman $w$ the opportunity to reject proposals and
allow her to remain single, a possible algorithm for finding the women-optimal
partner for $w$ is as follows: [197]: $1)$ during the execution of the men-
oriented GS $w$ refuses all proposals so that in the end $w$ and a man $m$
will be single; $2)$ Among all the men who proposed to $w$, call $m^{*}$ the
best proposer. In [197] it is shown that $m^{*}$ is the women-optimal partner
for $w$.
As already mentioned, the above algorithm only works when the woman $w$ is
allowed to remain single. When this is no longer allowed, the situation
becomes more complicated.
Again in [197], the authors build an algorithm to determine the optimal
strategy for $w$ (i.e. the falsified preference-list, permuting men, which
allows her to achieve a better matching) when she is not allowed to remain
single and it is not possible to declare anyone unacceptable:

  1. 1.

Run the men-oriented GS algorithm with the real preference-list $L(m,w)$ for
$w$ (with $m$ the men-optimal partner). Keep track of all the men who proposed
to $w$.

  2. 2.

Suppose that a man $m^{\prime}$ proposes to $w$ during the first step. If you
put $m^{\prime}$ at the top of the $w$’s list and restart the algorithm, you
get a matching where the men-optimal partner of $w$ is $m^{\prime}$. The new
list will be called $L(m^{\prime},w)$ and $m^{\prime}$ will be called
potential partner.

  3. 3.

Repeat the second step to get all the other $L$ lists with all possible
potential partners in the $L(m,w)$ list. It will be said that the man $m$ is
exhausted.

  4. 4.

Repeat steps 1, 2 and 3 until all men are exhausted.

  5. 5.

Call $m^{*}$ the best of $w$ potential partners.

It can be shown that $P(m^{*},w)$ is the optimal strategy for $w$.
Furthermore, it can be shown that $w$ is not guaranteed to reach its women-
optimal partner. Indeed, there is no guarantee that $m^{*}$ is better than its
men-optimal partner. Think, for example, about the case in which each woman is
in the first place exactly for one man, that is, each man has a different
woman at the top of his list. In this way, the men-oriented algorithm ends
with a men-optimal matching regardless of how women falsify their lists.
So, eliminating the possibility for women to declare men unacceptable, makes
it more unlikely for them to behave incorrectly during the game. Teo et al.,
Through simulations, have found that for women the probability of benefiting
by cheating is less than $10\%$ and, therefore, not telling the truth does not
pay enough. Fortunately, this result is quite comforting for practical
applications.

####  6.4.2 Singapore Ministry of Education Exercise

In [197] the authors proposed a mechanism based on the GS algorithm to improve
the mechanism for assigning students to secondary schools in Singapore. The
criticized mechanism worked in this way: before doing the ”Primary School
Leaving Examination” (PSLE), students had to give the Ministry of education
(MOE) a ranking of the 6 schools they preferred; after the PSLE test was run,
a student ranking was built based on the scores obtained on that test; at this
point, the best students were placed in their first choices and the worst
students were left with the last choices or even assigned in schools that are
not on their preference-list.
One of the main features of this mechanism is that schools have a passive
role, that is, students are assigned to schools only based on the PSLE score
and not based on the actual preference of the school. This could not adapt
well to the new rules imposed by the MOE: the schools would have had more
autonomy in the choice of students and the assessment of them would not have
been based only on the PSLE, but also on the grades in the individual subjects
that different schools assessed differently. In other words, schools could
also have had different student preference-lists.
Another problem was that the students had to deliver the school preference-
lists before taking the test: knowing that many good students would apply for
the best schools, it was not convenient for students to build a truthful
preference-list. In fact, with this mechanism, if the students put their first
six ideal choices, they risked being excluded from all six and being assigned
to another school according to criteria decided by the MOE.

At this point, it becomes evident that a matching mechanism based on the GS
algorithm and the above ”cheating model” would be much more convenient for
both schools and students. In particular, the MOE exercise lends itself to
being an SMP cheating model in which men are schools and women are students.
To be more detailed, the model would be a many-to-one matching problem, as
each school can contain more than one student. In [197] the authors easily map
the many-to-one model into a classic one-to-one model.
We list below the main advantages of an SMP model for MOE exercise :

  * •

A general SMP model allows schools to classify students according to different
criteria, according to the areas of excellence in which the schools want to
invest more.

  * •

A general SMP model matches all students to schools according to the true
preferences of the students.

  * •

The SMP cheating model allows students, as we have seen in the previous
paragraph, to deliver their real preference-lists without incentives to say
false, that is, without making strategy based on the results of the PSLE test.

###  6.5 Kidney Matchings

The types of matching described so far involve two parts (doctors and
hospitals, students and schools) who both make active decisions. However,
there are various situations in the real world where one part is active and
the other is passive. An example is the matching of the kidneys or other human
organs to patients who need transplantation. Here we will deal with this
topic.

####  6.5.1 Kidney Matching Market before Matching Theory

Kidney transplantation is a medical treatment that is chosen when kidney
disease reaches its terminal state. However, the main problem may be the
shortage of kidneys that can be transplanted. As Alvin Roth writes in [187],
there are more than 70,000 patients on the waiting list for cadaveric kidneys
in the United States, but in 2006, for example, fewer than 11,000 transplants
of this type had been performed. Also in 2006, approximately 5000 patients
died when they were still on the waiting list or had been removed from the
list because ”too sick to perform the transplant”.
This type of situation is not exclusive to the United States, in fact even in
Great Britain, at the end of 2006, over 6000 people were on the waiting list
for cadaveric kidneys, but only about $20\%$ of these patients performed the
transplant operation.

Figure 19: Kidney matchings: the double-headed arrows indicate that the
connected pairs are compatible, that is, the patient is compatible with the
donor. Couples A1 and A2 are in transplant centre A. Couples B and C are in
different transplant centres. Transplant Center A only knows its patients, so
it can only exchange between them. In (a), transplant centre A also makes
exchanges available with other transplant centres. In (b), there could be an
exchange between A1 and B, leaving A2 with no exchange. If this were the
situation, then transplant centre A could exchange between A1 and A2 without
informing the other centres [187].

Since healthy people have two kidneys and can live on while staying healthy
with just one kidney, an alternative option to having a cadaveric kidney
transplant is to have a healthy person donate one of his kidneys. Furthermore,
in doing so, the patient who undergoes the transplant has a greater chance of
long-term success than someone who receives a cadaveric kidney.
Unfortunately, however, good health and goodwill are not enough for a person
to donate their kidney. The patient and the donor can be biologically
incompatible due to the blood type or because the patient’s immune system
rejects some of the donor’s proteins [187]. In the United States in 2006 there
were about 6500 kidney transplants from living donors, while in Britain there
were about 590. Hence, unfortunately, the supply of transplantable kidneys was
much lower than the demand. Furthermore, in almost all countries it is illegal
to buy or sell organs for transplantation because of ethical issues.

Economists, in addition to having to deal with political issues to relax this
type of law against the sale of organs, must also deal with how to increase
the number of transplants subject to existing constraints (both legislative
and logistical). This will be the issue that we will deal with in the next
paragraph.

####  6.5.2 Matching Theory for Kidney Exchange

As we analyzed in the previous paragraph, the organ transplant market is full
of restrictions. Economic transactions cannot exist and biological
incompatibilities can exist between the voluntary donor and the patient who
needs the transplant. Despite these constraints, there are cases where it is
possible to find a solution for the transplant: consider the case in which the
patient $A$ wants to donate to the patient $a$ but it is incompatible and at
the same time the patient $B$ wants to donate to the patient $b$ but here too
there is incompatibility. If the patient $A$ is compatible with $b$ and $B$
with $a$, then a transplant is possible. However, this type of bilateral
exchange is rare and sometimes impossible for logistical reasons. Roth,
Sonmez, and Unver in [124] have shown that when only bilateral exchanges of
this type are feasible, there are efficient outcomes that can be found
computationally.
As mentioned, some patients could be put on a waiting list in the hope that a
compatible donor would be found as soon as possible. Roth, Sonmez, and Unver
[199] have introduced a very simple algorithm, called top trading-cycle, to
allow the presence of waiting lists in the model: the doctor indicates the
kidney more appropriate for each patient on the waiting list; if there is a
cycle, then the kidneys are exchanged following this cycle.
For example if $A$ wants to donate to $a$, $B$ to $b$ and $C$ to $c$, but
there are incompatibilities, then if possible one can perform the cyclic
exchange $\\{A\to b;B\to c;C\to a\\}$. The algorithm rules allow such a chain,
for example, if $B\to a$ while $b$ is assigned a ”high priority” status in the
waiting list. The same authors of this algorithm have built an efficient
selection rules chain for this type of exchanges [199].

After this type of research on the organ transplant market, several regional
programs have been created in the United States to promote studies towards
more efficient and complex kidney exchanges.
More recently, attention has shifted towards types of exchanges that include
the so-called ”altruistic donors”, i.e. those people who want to donate an
organ but do not have a particular patient in mind [187]. This type of chains
suffers less from logistical problems since transplants do not necessarily
have to be performed simultaneously between two patients [200].

###  6.6 More General Markets

We now consider an even broader generalization of the SMP: the many-to-many
matching problem. In this case, the agents of both sides have a quota $q\geq
1$. To remain in the theme of marriage, one can think of the metaphor of
polygamous marriages in which each man can have multiple wives and each woman
can have multiple husbands [201]. More useful is to think of two sets composed
of firms and workers: each firm wants to hire a set of workers and each worker
wants to work for a set of firms [202].
This context, compared to a many-to-one matching market (CAP), is more complex
and has many more pitfalls. Moreover, a many-to-one matching market would seem
more suitable for describing real situations since normally a firm is thought
to contain $q_{f}\geq 1$ workers but one worker works at most for one firm
($q_{w}=1$). However, there are important real-world markets that are many-to-
many [202]: think of the famous example of medical interns in the UK where
doctors could be assigned to multiple hospitals and one hospital hired many
doctors. One can also think about the assignment of teachers to high schools
in some countries such as Argentina where about a third of teachers work in
several different schools. Finally, the many-to-many environment can be
considered as an abstract model of the system of contracts between companies
and suppliers.
Another important reason why it is necessary to have a consistent theory also
for a many-to-many matching market is that most labour markets certainly could
have few many-to-many contracts. For example, in the USA more than half of
workers work in companies with a non-zero percentage of multiple jobholders
[203, 204]. Although this percentage may also be very small, as we will see
later, even a single many-to-many contract would make the model very different
and therefore not at all approximable to a many-to-one model.

####  6.6.1 Many-to-Many Market

The many-to-many matching problem has been extensively studied by
mathematicians, computer scientists and economists. Being very different from
the classic SMP, in this review we will not go into too much detail of the
model but we will try to show the main results as clearly as possible.
We have divided the model into two main variants:

  1. 1.

Reduced many-to-many model (RMM): this version of the model is the most
similar to the classic SMP and is characterized by the concepts of ”stability”
and ”ordering preference” (in the preference-lists) that we have used so far.
For this reason, most of the results of the SMP and the CAP also extend to the
RMM. However, this model is very weak for real-world applications.

  2. 2.

Generalized many-to-many model (GMM): in this case, the definition of
”stability” and that of ”ordering preference” will be modified to make them
more suitable for a many-to-many market. We have already encountered an
example of this adaptation in the case of the CAP concerning ”ordering
preference” when we introduced the concept of ”responsive preference”. As we
will see, in GMM, the results of the classic SMP can only be obtained by
implementing appropriate constraints

In the rest of this paragraph, we will study the main results on the existence
of stability in the two models (RMM and GMM).

#### Reduced Many-to-Many Matching Model

In the reduced many-to-many matching model (RMM) there are two finite sets of
players: N workers $W=\\{w_{1},w_{2},...,w_{N}\\}$ and M firms
$F=\\{f_{1},f_{2}...,f_{M}\\}$. Each agent in the system has a preference-list
of agents from the opposite set which they consider acceptable. In addition,
each player has a quota ($q_{w}$ or $q_{f}$) which represents the maximum
number of players from the opposite set that can be assigned to him. It is
evident that when $q_{w}=1$ and $q_{f}\geq 1$ it is reduced to CAP while if
$q_{w}=q_{f}=1$ it is reduced to the SMP.
So far, we have not made any hypothesis on the preferences to the sets of
players of the opposite set that can be obtained. We are considering, as we
have also done with CAP, preferences on individuals and not on sets of
individuals. This type of ”ordering preference” is called by Mourad Baiou and
Michel Balinski [201] ”Max-Min individual ordering preference” and is defined
by them in terms of sets of individuals as follows:

  * •

”Max-Min individual ordering preference”: a set A of agents is preferred over
a set B if the worst individual in set A is preferred over the worst
individual in set B. If the worst individuals in the two sets are the same
agent, then the preferred set will be the one with more elements.

Furthermore, the definition of stability is the usual one that we have used up
to this point and which in the literature is called ”pairwise stability”
[205]:

  * •

pairwise stability: a matching M is pairwise stable if, for each pair
$\\{w_{i},f_{j}\\}\notin M$, at least one of the two agents ($w_{i}$ or
$f_{j}$) prefers to remain with its partners in M. In other words, M is
pairwise stable if there are no $w_{i}$ and $f_{j}$ agents who are not
partners but if they become partners, dissolving their partnership to remain
in their quota and keeping the other partnerships, would both get a higher
payoff.

With these definitions of ordering preference and stability, it can be
demonstrated in a similar way to that done with SMP and CAP that there is
always at least one stable solution and that there are worker-optimal and
firm-optimal solutions in the usual sense of the SMP. In particular, in [201]
the authors arrive at these conclusions through a ”network approach” in which
workers and firms are placed on a grid where workers are in the rows and firms
in the columns.
The same authors have built an algorithm, called by them ”reduction
algorithm”, which, similarly to the GS algorithm, guarantees the existence of
a pairwise stable solution. The algorithm turns out to be of the order of
$O(n^{2})$ where $n=max\\{N,M\\}$.
There are several variations of the RMM model similar to those existing for
the classic one-to-one SMP [206, 207, 208, 209]. For example, in [208] the
authors find an efficient algorithm to find the minimum egalitarian stable
matching and in [209] the many-to-many matching problem with ties is studied.

#### Generalize Many-to-Many Matching Model

In the generalize many-to-many matching problem the situation is a little more
complex than in RMM. The preferences of each agent are not considered to
individuals, but a set of individuals. We give an example from a real
situation to understand the importance and greater practical utility of
preferences on agent sets rather than on individual agents. Imagine a real
estate company $I$ (with few employees) that has three open positions, i.e.
$q_{I}=3$. There are 6 candidates who, according to their curriculum, are
ranked in order of preference by the company $I$ in the following way:
$\\{a_{1},a_{2},a_{3},l_{4},l_{5},c_{6}\\}$. The first three are architects,
then there are two lawyers and finally a business consultant. If the $I$
company makes its choice according to the Max-Min individual ordering
preference (defined in the previous paragraph) then it is obvious that
$\\{a_{1},a_{2},a_{3}\\}$ would be hired. But if $I$ is a small company, it
does not need three architects, it would be better to diversify and hire three
candidates with three different roles. In this case it would take
$\\{a_{1},l_{4},c_{6}\\}$. So this example shows us that individual-based
ordering preference is not always a good criterion for building the model.
Roth and Sotomayor in [83] demonstrated the following proposition (already
mentioned in the previous paragraph):

  * •

if preferences are assessed on sets of individuals arbitrarily, then there is
no guarantee that a pairwise stable solution exists neither for the many-to-
many matching problem nor for the many-to-one matching problem.

In order for a pairwise stable solution to exist, restrictions must be placed
on the ordering preference. Before seeing what are the constraints on the
ordering preference that have been most adopted in the literature, let us take
another example that shows how much it is disturbing, in this context (i.e.
with preferences on the sets of individuals and not on single individuals),
the presence also of a single ”many-to-many contract” in the system [201]:
let $W=\\{w,w_{1},...w_{2k}\\}$ the workers and $F=\\{f_{1},...f_{k},f\\}$ the
firms. The worker $w$ is the only worker with a share of $q_{w}>1$. The
workers’ preference-lists are:

$P(w_{i},i=1,...,2k)=\\{f_{1},f_{2},...,f_{k},f\\}\;,$
$P(w)=\\{(f_{1},f),f,f_{1}\\}\;.$

The firms’ preference-lists are:

$P(f_{1})=\\{(w,w_{1}),(w_{1},w_{2})\\}\;,$
$P(f)=\\{w,w_{1},w_{2},...,w_{k}\\}\;,$
$P(f_{i},i=2,...,k)=\\{(w_{2i-2},w_{2i-1}),(w_{2i-1},w_{2i}),(w,w_{2i})\\}\;.$

The only possible stable matching in this case is:

$f_{i}\to(w_{2i-2}w_{2i-1})\;,$ $f_{1}\to(w,w_{1})\;,$ $f\to w\;.$

While, if $w$ is allowed to work for only one firm, then we reduce it to the
CAP model and the only stable matching becomes:

$f_{i}\to(w_{2i-1}w_{2i})\;,$ $f\to w\;.$

This example shows that, if even a single worker can have multiple contracts
with different firms, then stability changes for a large number of players in
the system. So even if in a labor market the general rule is one-to-one or
many-to-one contracts, few many-to-many contracts can make a big difference.

####  6.6.2 Substitutability Constraint

We now introduce the concept of ”substitutability” as a constraint in ordering
preference in order to find a structure of stable solutions similar to that of
SMP also for GMM. Let $f$ be a firm, then the ”substitutability” in the
preferences of $f$ is defined in the following way [210, 205]:

  * •

Substitutability: if for firm $f$ assuming the worker $w$ is optimal when the
available workers are $w\cup\\{S\\}$, where $\\{S\\}$ is a set of workers and
$S^{\prime}\subset S$, then $w$ must be optimal for $f$ even when the
available workers are $w\cup\\{S^{\prime}\\}$

In other words, substitutability requires that, if $w$ is chosen by a given
set of workers, then it must also be chosen by a smaller set of workers.
Therefore, under the conditions of substitutability and pairwise stability
Roth in [211] has shown that there is always at least one pairwise stable
solution in the many-to-many matching problem. Furthermore, the same author
has shown that, as in SMP and CAP, there are two particular stable solutions
which are one worker-optimal and the other firm-optimal. These solutions can
be found with the usual GS algorithm procedure adapted, again by Roth to the
case of the many-to-many model. There is also an algorithm for finding all
possible stable solutions of the GMM found for the first time by Martinez et
al. in [212].

Figure 20: Corewise stable solution: $p_{1}$ prefers $(q_{1},q_{2},q_{4})$ to
$(q_{2},q_{3},q_{7})$; $p_{2}$ prefers $(q_{1},q_{4})$ to $(q_{5},q_{6})$;
$q_{1}$ prefers $(p_{1},p_{2})$ to $(p_{3},p_{4})$ and finally $q_{4}$ prefers
$(p_{1},p_{2})$ to $(p_{5},p_{6})$. Here, the matching $x_{3}$ is not setwise
stable because the agents $(p_{1},p_{2},q_{1},q_{4})$ can get a better payoff
for all of them by forming a new partnership only among themselves, like in
the matching $x_{3}^{\prime}$ in the (right) figure. However note that the
agents $(p_{1},p_{2},q_{1},q_{4})$ do not form all their partnership only
among themselves and so $x_{3}$ is corewise stable. Figure adapted from [205],
with permission from Elsevier.

Finally, we now mention two other possible definitions of stability which are
probably more appropriate for a many-to-many labour market. Pairwise
stability, in fact, gives the power to ”block” a matching to individual agents
(worker-firm) and therefore the stability rule required by this definition is
too weak in terms of the duration of the matching [212].
The following two more restrictive definitions of stability have been proposed
in the literature for a many-to-many market [205]:

  * •

Corewise stability: a matching is corewise stable if there are no subgroups of
agents that, by forming all their partnerships only among themselves, can all
get a higher payoff.

  * •

Setwise stability: a matching is called setwise stable if there are no
subgroups of agents who, by forming their partnerships only among themselves,
possibly dissolving some partnerships to remain in their quota and keeping all
the others, can obtain a greater payoff.

Sotomayor has shown that the definition of setwise stability is a strictly
stronger requirement than the other two concepts of stability [205]. He has
indeed shown an example of a case in which a matching is both pairwise stable
and corewise stable, but not setwise stable. Figure 20 shows an example of
matching which is corewise stable but not setwise stable.

##  7 SMP Reinterpretation and the Role of Information

In the above section, we described the wide application of SMP in economics.
Here, from the modern point of view of the new theory of information economy
[213], we see that those models have serious flaws and, in the real world
applications, one of the major features is not recognized: information
deficiency.
Initially, we will provide a reinterpretation of the original model of the
SMP, in particular, we will focus on the Gale-Shapley mechanism and we will
see that, using an information-based point of view, women’s preference lists
are an unnecessary input into the model. This fact has very interesting
consequences if we consider SMP as a metaphor for economic society.
In the second part of this section, we will see quantitatively how the results
of the SMP vary if the concept of partial information is introduced, namely
when the preference-lists of the system agents are not complete but have holes
that represent the lack of information. The fundamental conclusion is that, if
SMP is contextualized as a metaphor for society, the increase in information
in society itself increases global happiness.
Then we briefly introduce the new theory of information economy. In this way,
it will be possible to appreciate how revolutionary the role of information is
in the economic and social sphere. For a more detailed and compelling
description of this theory, one can refer to Zhang’s book [213].
Finally, in the last part, the role of the matchmaker will be described: an
external entity that owns all the information available in the system and
forces the system agents to match in such a way to obtain the global optimal
solution. From a quantitative point of view, we faced this problem at the end
of section 3 where the ground state solution of the SMP was analyzed
analytically and compared with stable solutions (i.e. in the absence of
matchmaker).Here, however, we will place the matchmaker in the context of
information economy theory and see what the implications are for society.

###  7.1 A New Interpretation for the Gale-Shapley Model

Let us refer to the original Gale-Shapley algorithm where one side takes the
initiative and the other side evaluates whether accepting or rejecting; this
was just the choice of a mathematical model, nothing wrong here. But, as an
economic model, this raises an important question. Whoever takes the
initiative to propose, as we saw, statistically gets much better results than
the other side that just sits and waits. Then one may ask: why does the
passive side choose to be passive? Why do not they also play the active role,
i.e. both sides propose to each other ?
But from this point of view, the original GS model can be re-interpreted as
follows. Men and women have to be matched, one side has complete information
on the other side (let us say men), whereas the other side (women) has no
information on the opposite side. So they just store the information regarding
the people that have already proposed to them.
Those with information can proceed to rank the other side according to their
preference, just like in the GS algorithm. But the women must wait as they do
not have any information over men. The women have the same cognitive
capability than men but they do not have information so they cannot propose
(otherwise these proposals would be completely random). Once a woman receives
a proposal, she temporarily keeps him as a candidate, but if she receives two
or more candidates, even without any prior knowledge, she is capable to
evaluate making a comparison between the two, choosing the best one and
rejecting the other. In this way, everything proceeds just like in the GS
model. It is important to note that a woman does not have a rank list, but,
whenever she receives proposals, she is capable of choosing the best for her
so, actually, she never needs the full ranking list as in the original model.
Of course, mathematically speaking, the results would be the same as in the
original GS model, hence we call the above description as a reinterpretation.
Nevertheless, it is useful for a generalization of SMP, i.e. information
deficiency problem.
The re-interpretation sheds lights on the original GS mechanism: here it is
clear, missing information impede women to make proposals and hence their
passive stance is not a choice, but they could not do better otherwise.
Now, we may ask: if, in the original GS mechanism, women would have the full
information, why do not they use it to their advantage? In our opinion, this
is contrary to the fundamental principle of rationality.

The indirect lesson we learn from the above is that prior information over the
other side brings advantages, and missing information puts you at a
disadvantage.
The real-world applications are full of these circumstances. For example, what
happens if both sides have partial information? Following our previous
interpretation, each side would choose a hybrid approach, both making and
evaluating proposals. Everyone would use as much as possible their information
edge to propose, but since he or she misses a substantial part of the
information available, they must at the same time evaluate ex post the other
side proposals. This means that a person may lack prior knowledge about the
other side, but upon receiving a concrete proposal, is capable of evaluating,
and comparing (if more than one proposal comes to his/her attention). The best
strategy would be to always keep the current best proposal, dropping all the
others, and keeping to propose until the current best proposal received is
better than the one he/her is about to propose. Similarly, the game will end
if the other side accepts his proposal.

This modification of the standard SMP has profound consequences: while in
mainstream economics, each player is rational but limited by his constraints,
here the constraints are the limited prior knowledge on the other side. But
rational players must use all the information they have with maximum
efficiency. In this light, the original GS model is not rational: if the women
have the full information, why should they choose to sit and passively wait
for the proposals? This is clearly a bad option from the rationality
criterion.
Of course, one may reinterpret the GS algorithm so that the women, for
whichever reason, do not have prior knowledge about the men, but are as
intelligent as the men if a proposal or more come to their attention.
Acquiring prior knowledge must cost some resources and, if these needed
resources are high, one may say that one of the cost-saving measures would be
not to evaluate all the men beforehand, but only when the men make proposals,
to spend (relatively) much fewer evaluation efforts to check the proposals.
But one of the main conclusions is that prior information begets advantages,
more prior information begets more advantages, no prior information puts you
at a much more disadvantageous position. Nevertheless, the heavily penalized
player (from the lack of information) can still get the best he can, even if
it would be an optimization under severe limitation to achieve a limited
optimization.

The lesson learned is the following: ”taking initiatives” vs ”passively
waiting”, the former brings more advantages. But it is the amount of
information that plays the most important role: if you have the information
like the women in the original GS model, they had the full information and not
using it is a huge waste of resources (valuable information) that is not
condoned by any rationality criterium. On the other hand, with null or
inadequate information, taking the initiative to propose is worse off than
passively waiting. This is especially true if the quality of information is
taken into account (for example the information is not reliable). This latter
may induce a player to be overly confident, thinking that he has enough
information for taking the initiative to propose. The conclusion is that the
degree of initiative-taking should be commensurate with our true information.

The case of the GS mechanism is an extreme case in which information is all on
the side of men. In the following, we will quantitatively analyze, through a
mean-field approximation, what happens to the energies of the agents when the
information is partial on both sides. In particular, we will focus on a
mechanism in which both parties act as both proposers and judger, meaning that
both men and women take the initiative.

###  7.2 Stable Marriage Problem with Partial Information

Computational power is continuously growing with time. According to Moore’s
law, it is set to double every eighteen months. This increase in computational
power will allow for predictions on many systems such as long term weather
forecast, financial market predictions and DNA decoding [214]. All of this can
be summed up in one sentence: information in society is improving. This will
have extraordinary implications in our society and in particular, the increase
in information will be the main driving force of economic growth.
However, no individual can ever be perfectly informed and it is useful to
exploit the metaphor of the SMP to see what happens when each individual has a
limited capacity of information.

In most of the classic economic models, it is assumed that agents have an
infinite availability of information, the same is assumed in the classic SMP.
Indeed, all individuals in the system build preference lists by evaluating all
individuals of the opposite sex. In real-world, however, it would be very
complicated to establish a preference-list for a large number of possible
partners because it would be necessary to analyze all the people one by one
and the amount of information to be processed would be prohibitive for a
normal person.
Here we want to modify the classic SMP model so that to include limited
information processing power: each man or woman will not be able to build a
complete preference-list. Hence, not all individuals will know each other, but
the preference-lists will have holes.
We will therefore see how the increase (or decrease) of information in the
system, defined as the number of individuals present in the preference-lists,
modifies the total and individual energy of the agents. There are two extreme
cases: one in which both men and women have complete information, and
therefore both sides have a motivation to take the initiative, and another in
which women do not have their preference-list, i.e. the GS model, and
therefore only men benefit from taking the initiative. We will focus on the
latter in the next paragraph.

####  7.2.1 GS Energy of the Agent with Costly Information

We now focus on the energies of men and women in the GS (men-oriented) dynamic
when the agents have limited information. First of all, we note that,
according to the reasoning made above, since women are passive agents in the
GS dynamic, then their preference-lists are superfluous. In fact, at each
step, they only have to judge between two men and do not need to know what
ranking these two men have on their preference-list. So, once again, the same
GS algorithm can be interpreted in such a way that women do not have to waste
information processing power.

To calculate the energies of men and women in GS dynamics we can follow the
reasonings of Caldarelli, Capocci and Laureti in [215]. They assume that
system agents have limited ability to process information and therefore cannot
know all individuals in the system. To limit this information capacity, they
consider individuals arranged on a $k$ -dimensional lattice and assume that
everyone can only know individuals at a certain Euclidean distance $d$. So the
”unreachable” partners will be represented as holes in the preference-lists
and, under these assumptions, everyone will know only a fraction
$\gamma\sim(d/N)^{k}$ of the total agents in the system. So the energy of men
is equal to the number of proposals divided by $\gamma$, that is, with the
same calculations made in section 3.2.2, we have:

$x\approx\frac{1}{\gamma}(logN+0.5772)\;.$ (82)

Still following the calculations in section 3.2.2 we find that the
relationship between the energy of men and women is [215]:

$x\approx\frac{\gamma y}{N[1-(1-\frac{y}{N})^{\gamma}]^{2}}\;.$ (83)

So when the agents have more information, although the competition between
them is greater, their energy is lower.

So far, we have dealt with the problem using the GS mechanism and we have seen
that the benefit to society (of both sides) decreases when the information is
less ($\gamma$ greater). In the following we will see that, as one might
imagine, the GS model is not an exception: even when we make both men and
women take the initiative, an information deficit harms the whole society and
also the side better-informed benefits the most, even if, as we shall see, it
is not a zero-sum game.

####  7.2.2 Mean-Field Energy with Partial Information

Let us assume that men only know $U<N$ women and that women know $D<N$ men.
For the moment we assume that $U>D$. The subsets $U$ and $D$ are randomly
chosen from the total number of individuals of the opposite sex. These
hypotheses are more realistic than the classic model since, in reality, no one
can know all the people.
Our goal is to calculate the average energy of men $x=X/N$ and women $y=Y/N$
(where we still consider that each person’s energy corresponds to the ranking
of the partner on their list). To do this we will use a mean-field approach in
the same way as Y.C. Zhang in [214].
Imagine that both men and women are active agents (as they are called in
[214]): they are both proposers and, at each step, they make a proposal and
evaluate another at the same time. We legitimately consider that the $U$ women
are uniformly distributed in the hypothetical complete list composed of $N$
women. The list of each man will therefore be ”sparse” with an average
interval equal to $N/U$ between a woman and the other. Similar considerations
are made for women.
So the game begins with every man and woman who propose to someone and
evaluate the proposals received at each step. Since the women’s lists are
sparser ($D<U$), they will scroll faster and, when the game ends, the men and
women have travelled a distance $x$ and $y$ respectively in their lists (in
general it will be $y>x$). So on average, every man will make $xU/N$ before
getting married and, since every proposal from a man has a probability $y/N$
to be accepted, the total probability that a man’s proposal is accepted is
equal at $xyU/N^{2}$. Similarly, one finds that the total probability that a
woman’s proposal is accepted is $xyD/N^{2}$.
At the end of the trial, there are three types of marriages: those in which
only the man has proposed, those in which only the woman has proposed and
those in which both have taken the initiative. In the first two cases we mean
the man (woman) proposes to a woman (man) who accepts but he (she) is not
present in her (his) preference-list.
For the matching to exist, it must be that the total probability is equal to
1, therefore we have:

$\frac{xyU}{N^{2}}+\frac{xyD}{N^{2}}(1-\frac{U}{N})=1\;,$ (84)

where the first term contains the sum of the probabilities of marriages in
which only the man takes the initiative and in which both take the initiative;
the second term, instead, represents only the marriages in which the woman
takes the initiative.
In addition to this normalization condition, we must add the fact that both
men and women scroll their list one step each and that the number of proposals
is the same between men and women. So we have to add the condition:

$xU=yD\;.$ (85)

Solving for $x$ and $y$ the system, we obtain:

$x=\frac{N\sqrt{U}}{\sqrt{(U+D-\frac{UD}{N})D}}\;,$ (86)
$y=\frac{N\sqrt{D}}{\sqrt{(U+D-\frac{UD}{N})U}}\;.$ (87)

First of all, it should be noted that in the case where $U=D=N$, the standard
SMP theory apply.

Figure 21: Average partner’s rankings as a function of $D$: the most up curve
from the left correspond to the man’s partner ranking, the lowest curve is for
the women, and the middle curve is the sum of the two rankings. Here is
$U=100$ fixed and $N=1000$. Figure reprinted from [214], with permission from
Elsevier.

When $U>D$ equations (86) and (87) tell us that $x<y$. In other words, those
who have more information also have more benefits. Figure 21 shows the trends
of $x$, $y$ and $x+y$ as a function of $D$, keeping $U$ fixed. Note that, when
$U>D$, women are much more unhappy than men. By increasing $D$, the benefit of
women increases and that of men decreases. However this decrease does not
offset the growth of women’s happiness and therefore the total benefits,
$x+y$, grow monotonically with $D$.
All this has important consequences if it is considered the role of
information in society [214, 216, 217], as these results show that the greater
the information, the greater the global benefits for society .

Another interesting aspect to investigate is whether an initial information
difference ca dilate the inequality (in happiness) between the two sides if
the information with the same velocity for both men and women is increased
[214].
The benefit for men can be defined as $N-x$, similarly, for women, the benefit
is equal to $N-y$. Now let us grow the amount of information of the same
factor for both sides, that is we have that the information of men is $\xi U$
and that of women is $\xi D$, where $\xi>1$, and we do increase this
parameter. The relative benefit $R$ can be written as:

$R=\frac{N-y}{N-x}\;.$ (88)

If, as before, we assume that $U>D$ we have that R grows monotonically with
$\xi$. So the benefits of the part with less initial information grow faster
and this is a socially good result since it means that initial differences do
not expand with the uniform growth of information.

###  7.3 Beyond Marriages: the New Theory of Information Economy

As one can imagine, the information paradigm goes far beyond marriage, as it
turns out to be a very important concept in many other areas of social
interaction. Indeed, the SMP model serves as a metaphor for other
applications.
Among the most important social relationships is the commercial one. Consider
for example the relationship between firms and consumers. It is generally
assumed that a transaction between a firm that sells a product and a consumer
who needs this product benefits both parties. In the standard economy, it is
assumed that the benefit is equal for both parties and the so-called economic
pie is the largest. But modern products are much more complex than those of
the past, and consumer needs are also more diversified and complicated: the
simple law of supply and demand based solely on the price of products is no
longer adequate [214]. In today’s world, finding compatibility between the
products sold by firms and consumers takes time and efforts. Consumers cannot
know all the potentially useful products and services in the world. Similarly,
a firm cannot know all the wishes of all consumers in the world. Therefore, an
essential skill in commercial relations is knowing how to find the right
counterpart.
In this section, we have shown how, through the metaphor of the SMP, the
economic pie is as large as possible when the information is the same on both
sides, but it is easy to understand that in the real world, in most of the