Again, we return to our main goal is to find a stable matching. There is a very simple approach which is sometimes called with the French name laissez-faire. So the idea is let's start with any matching, and if there is something unstable, let things happen. If there is unstable pair of people who want to marry who prefer to be paired to their current partners, let them do it. Of course the people who are left should also form a pair if they want to have a perfect match. So let's do it, but of course after that, another pair and stable pair can appear. In the beginning, there could be a lot of stable pairs. So we just try to let things happen. This is former partners. We should stop when unstable pairs. So we will repeat this procedure until some stable matching is obtained. And the question is, of course, whether this happens. So is it possible that everything will happen, these changes will happen, happen, and happen and we'll never get a stable matching. So this is a question of stabilization and the answer is negative it's not guaranteed. And let's consider and example, it's taken, probably they are many but this specific example is taken from Donald Knuth book about stable marriages. It's a nice book in French and there is also an English translation and Russian translation. So the example is there are three men, a, b, and c, and we have three women, p, q, and r. And here are the preference which are known, which are important. And for b and for r, any preferences will do because they will not really play any role in this sequence of marriage and sequence of changes. And we will see that there is a loop. So we start with some position, and after some changes, everything returns to the original state, and so it can again happen the same and we can get an infinite sequence. And it's rather you just check that everything is okay. Let's try to follow. I prepared the slides, but let's look how it works. So this is the initial setting. A is paired with p, b with q and c with r. And you can look here and find an unstable pair and it's should be shown in the red in the next slide, yeah. So why it's unstable pair? Because you see that q is better than p here. And also for q, a is better than b. So there all the reasons to to prepare a and q for both sides and spectadium and then b will be paired with p. So this should be showing the next slide, yeah. Yeah, here is the next slide and this is shown. Now we can look for another unstable pair and it should be shown in the red. Yeah, so why is it unstable? So for q, c this new candidate is better than a, here is it, and for c, q should be better than r, here is it. So you see that for both c and q, red line is an improvement. So they form this, that pair, and then r and a are left alone and they form another line. So, and this should be on the next slide, let's see. Yeah, everything is okay. New unstable pair. You can stop the video now and try to find the new unstable pair. But here it is. C prefers p to q, yeah indeed, c prefers p to q. And P should prefer c to b and indeed we prefer c to b. Again unstable pair, again it's appears and the people who are left, b and q, form another pair. And now we are very close to the end of our loop. There is a pair a, p look, a prefers p to r. And people first a to c. So again, c to r for the people who are left form a new pair, and we get this. And it's exactly the thing we started with. So things can repeat and repeat. It's kind of a strange thing, because somehow at each stage, the same argument why it should stabilize, but it's the wrong of course argument. It stabilizes because the situation improves. Improves since in each change, people become more happy. At t least to people who make a new pair become happier. But, of course, this argument doesn't work and probably you guess why it doesn't work so I will not tell you this now. Think a bit, what is wrong with this argument. So we need to look for another algorithm to find the matrix, and it's called algorithm, that's according to the names of the first people, and we will consider it.