Now let us start with some basic examples of what is good and what is bad.

And using this marriage terminology.

So first let's consider some cases when there is a unique stable marriage.

For the simplest possible case,

let's repeat the setting.

So we have n men and n women,

and each participant has an ordered list of preferences,

and we are looking for perfect matching or marriages,

but everybody is married.

And the requirement we want to achieve is stability.

And stability, that there is no pair such that both people in

the pair prefer each other to their current partners.

So this is what make an incentive to change, change the marriage.

But so, stability means that no such pair exists.

And of course the simplest case when there is

no problem is where just n=1 and there's no choice,

no problems and so on.

And another case, more interesting case,

is where all the men have the same preferences,

so at least for all men is the same.

Of course you can also speak where the list for all women is the same.

So in this case, I claim that is unique stable marriage and before I got a simple reason,

let's try to see why.

So this is the case of the same ordering.

Here at this ordering,

so all men have the same ordering,

all of them prefer woman one,

and if not then woman two and so on up until the woman n.

And let's look at the woman 1 preferences.

So she prefers somebody we didn't know who, some (mi).

And like all other people,

(mi) prefers also (w1).

So this is a kind of good situation;

one, there is a man and woman which think they are the best mutually.

So in any stable marriage,

they should be married because if they have different partners,

then they will form an unstable pair because they prefer each other to any other partner.

So, in any stable marriage,

we will have this connection,

this period between (mi) and (w1).

And also, what is good,

that they cannot create instability.

So if we find a stable marriage for the rest,

for the remaining n-1, men and women,

then m and we add this pair,

there is no new instability because both of them are completely happier.

They do not want to change the pair.

So they cannot create unstable pair with anybody.

So it remains to find the stable marriage for the rest,

and it can be done of course in the same way we take the look,

what are the preference of woman 2.

And take the best her first choice except for all the used,

(mi) and so on.

So this is a kind of induction or in programmer terms,

it's recursion as easy recursive algorithm

to find the best matching for this special case.

Symmetric case also exists if all as I have said,

if all women have the same preferences for men,

then of course the same symmetric thing happens.

We should look who is the best for first men and then make a pair,

and then apply the algorithm recursive to the rest.

And let's now go to a bit more interesting case where n=2.

So we know that if the preferences are the same for everybody,

for all the men and all the women,

this already we know what happens.

So let's consider a different case.

So now men A and B have different preference,

A prefers P to Q and B prefers Q to P. And the first case with everyone is happy,

when the women have different preferences which match the preference of men.

So A prefers P and P prefers A and then

of course what is happening that is the best thing can happen,

they just follow their preferences,

and this is the only stable marriage.

So in this case, we have unique stable marriage curatives and in good quality.

But another case is possible and in fact in this case,

there are two stable matchings but both are bad.

So imagine that the men have different preferences as women have different preferences,

but now they don't don't match.

So, A prefers P, A would like to marry P,

but P prefers B and B

prefers Q and Q prefers A.

So, there is kind of inconsistency between the desires on both sides.

And in this case,

there are actually two possibilities,

so we can have this matching.

And in this matchings,

you see men are happy but women are not happy.

But this matching is stable because no man wants to change.

So this is a stable matching but it's not good matching.

And also we can take another one which is like this,

and this here everything is symmetric.

So now women are happy and men are not happy,

but there is no instability because no woman would like to change her partner.

So we have two stable but bad matchings unfortunately.

And it's of course,

it's a well known situation,

you can even hear a nice song of lead of Heine and Schumann,

Am leuchtenden sommermorgen, it's called.

So, in the real church you can find a lot of

examples of this type and even of course things.