Now this is the last topic in the graphs course.

So we will consider some practical,

important and tentatively interesting problem which is called Stable matching.

Let me start with some real life example and then explain the mathematical part.

So I took the example which I know personally.

It's about university entrance in Russia.

So after some time,

there was an old system and the old system was that each university organized

its own entrance exams and all is exempt and around the country was at the same time.

There were some small exceptions,

But let's forget for now.

And that's you can participate only in

one exam and you can send

only one application and go to this university and take the exams.

And if you are accepted, you are fine.

But if you fail then it's too late for other universities.

So you have no university this year.

And if you are male,

you risk being taken to the army,

so it was a big deal.

And at some point,

probably with best intentions they changed

the system and this new system was different there was some country-wide tests.

You can participate in this test and get some grades and then you can apply to

different universities and each university gets

your grades and may decide whom to accept.

Then the university makes offer.

And then you decide which offer you want to take if you have several

and maybe you can guess what will the disaster this year.

It was a huge disaster actually because if

applicants choose some university then the other universe do not get them.

So from a university view point you can make several offers,

but if you make more offer than you have

places then you risk that you cannot accept other people.

And if you have this number of offers then of course most of us are not taking.

So if you end with very few students,

so you need a new wave of offers.

And then and it's a short time actually in summer.

So it was a complete complete mess at that moment and it still is.

Still there is no well-thought system how to deal with this.

Now there are some restrictions and things are a bit better,

but still it's a big problem.

Anyway what I want to say here,

is just that this is a very important problem of matching

somehow supply and demand in this kind of situation.

And we will consider a simplified model.

The simplified model is when university have

many positions and we can see the drop but each employer has only one position.

So we have N candidates and we have exactly the same number of positions.

And let's bits a simple situation.

Each candidate knows everything about all the positions and has

a complete list of preferences

of which position is the best of which is the second one and so on.

And at the same time,

the employers also have the full information they need to whom they want if possible,

if not who is the next candidate and so.

And the goal is to find the matching.

So the matching in terms of graphs it's a perfect matching.

So we have n pairs as a candidate a position.

And of course one each candidate should go to

only one position and this position should be filled by one candidate.

So we are looking for a machine and there is a condition in

graph theory of perfect matching and there is

a condition which is called the matching should be stable.

And let me explain,

this is the main thing you should understand it very well.

Because we will develop a graph which guarantee this property.

So what is stable Matching?

So let me show what is unstable matching.

Let this be candidates A and B and jobs P and Q,

so there are some preferences.

So we mentioned that A prefers the job Q.

So the current job is P and the current job is Q for B but

actually A prefers Q but he likes

Q better or she likes you better than P. And

also the employer Q would also prefer A to B.

So there is some kind of reason.

There is unstable, instability here.

Because this pair A-Q is better than the current situation both for A and for Q.

So if it's better for one of them its not enough,

because the other will not agree to this change.

But, now its better for both.

So they have all the reasons to switch to this new pairing.

And then of course,

if we agree that everybody wants to get a job and every position should be filled

then B and P are forced to make a new pair.

So now to our an initial question.

Imagine we have complete list of preferences and the question is,

Is there a stable matching or not?

And of course, if it is, how to find it?

This is the most natural question about this setting.