Now, we want to show that the algorithm is double unfair.

So it's not only treats the men in the most favorable way,

it also treats women in the most unfavorable way.

So let's explain what does it mean.

Again, it's just the same setting.

So if we have a view of some women in different stable matches,

this woman can have different partners.

And the algorithm will give one of these partners.

And what we claim that the algorithm will give the worst one.

So there are many possibilities but our algorithm is somehow maximally mean.

It will give the worst possibility for every woman.

So why it happens.

Again we can try to reform you later in a more specific way.

So imagine we say that,

we want to say that if MW is in some stable matching,

then our algorithm cannot provide something better.

So if we take the first stable matching our algorithm will provide this partner.

So it cannot pair W with some better candidate

M. If there is even some stable metric that will use pair it with them.

Okay, again we need to rewrite,

to see the start or prove by repeating the claim.

Just the same claim.

Now, let's look what does it mean.

So M we assume here this is in the picture MW,

appears in some stable matching.

So the stable matching is a static picture and it's shown in black.

And so here are the connection and there is dynamic picture.

Imagine that the claim is false which means that our algorithm pairs

W with M prime which is better than

M. This red thing is what our algorithm gives at the end.

And then of course this M prime in the stable matching,

M prime is also involved.

So it's paired with some W prime.

Again, the same reasoning.

So we know that for W,

M prime is better than M. So why this red line doesn't destroy the stability.

The only reason why it happens is just the opinion of M prime.

So for M prime,

W prime should be better than W. Otherwise

this black connection is not stable because the red line will destroy, make it unstable.

Okay, and let's look what happens for M prime.

We see that in some stable matching,

he's paired with W prime.

And our algorithm paired it with W which is worse than W prime here.

W is worse for M prime than W. W prime is better than W for M prime.

So we see that the algorithm, the red line,

is worse than the stable marching and we know it's just the first part of our statement.

That for men, for all men including M prime the algorithm should give the best result.

So the best result is at least W prime and now the algorithm that

gives W and this is not possible according to our assumption.

So the second part is just we do not make now an induction we just use

the statement we had from the first part.

Okay, so we are almost finished.

Let me make some general remarks about what is happening.

So first I will say that somehow it's a bit counter-intuitive.

Why this algorithm favors men over women.

Somehow you can see that men are more restricted.

They never allowed to leave their partners by their own will,

so they can exist,

a pair is broken only if the woman wants this.

And the women are allowed to do this if the woman gets

a better proposal than the current partner then she accepts it.

So somehow there is more freedom for women and still strangely the algorithm favors men.

But here the men is in quotes because of

course I should repeat again and very strongly what I have said before.

That just when we speak about men and women

in our discussion they are not real men and women.

They are just some entities,

some names for algorithmic entities and there is no claim

of any similarity between

the conclusions about the algorithm and anything about the real life.

So there are real important,

there are cases when this model is really relevant for

these admissions for donors from other cases.

But the manage problem is not modeled by this.

It's Just a way of saying things to make the proofs

more easy to remember or easier to understand and so on.

So don't take it serious at any rate.

So what if you want to apply this in practice,

then we need to extend the model in different ways.

So first like in admissions and university it's not one to one correspondence of course.

University corresponds to many applicants.

So we need to extend the algorithm to this case.

Also sometimes there are no preferences so

there are a group of people which are equally good for some job or

some student doesn't know much about

several universities and treat them as essentially of the same level.

So there is qualities is also possible.

And also there are cases when for some candidates

some job are completely unacceptable or or vice versa.

So it's better not to have a job at all than to have this job.

So this is also not in our simple case it was not allowed also.

And that is a more subtle thing which

is there's a protocol the question is whether it's truthful.

What does it mean?

Imagine that people, for example students,

imagine they sent the list of preferences for university to

some central committee which may process all the data and provide the matching.

But of course they are not interested in sending the truth.

It's not, they are not obliged to send real preferences.

Maybe if they sent something wrong this will finally,

this will force the Central Committee to

the central processing unit provide better outcome for them.

So it's a general,

any economic mechanism should be asked whether it's truthful or not,

whether it's encouraged telling the real preferences or

just whether telling the real preferences is the best strategy.

It's a very important economic things but it's beyond

our computer science and discrete mathematics topic.

But I just want to say that if you like the setting,

if you like this type of question you should think

about taking some course in mathematical economics.

It's a very interesting course, very interesting topic.

And also you see that

it's not difficult to get a Nobel Prize for such a simple algorithm. Just kidding.

But anyway economics is really really interesting.

So if you get a feeling,

a bit of feeling what is economics then you can

decide whether you want to study it more seriously and it's recommended.