Now I'll try to explain why this algorithm is unfair. It's actually double unfair. It treats the men the best possible way. And the women the worst possible way. So let me explain what I mean. Consider some men, and we know that there could be many stable matchings. So in this stable matching, the same man is connected to different women, and so there is some range of possibilities. And actually, what is claimed, that the algorithm gives the best one. So for what the algorithm give is the best one a man can hope in any stable matching, and thus some corollaries first. The non-determinism in the algorithm is not important. Because the best pair for stable matchings is something which is defined independently of any algorithm. So if our algorithm finds this, then this is a case for all possible ways of executing the algorithm. And also you can look at it in different way. So we have some invariantly defined thing, for every man will take the best possible partner. And the claim is that it's indeed a perfect matching which is not obvious. Maybe for the abstractly, we can imagine that for two different men the best possible partner, the same. But still it's not the case, so this is another corollary. And let me reformulate the claim. And in the different way, which is more convenient for proving. So, remember that during the algorithm, our man M tried to make proposals to different women in his list. He was rejected by some of them. Then, he was finally accepted till the end of the algorithm by some woman W. And not Ws, I don't know, accepted by some woman. What I want to say, that if it was rejected by some woman W, then this woman is better than what you finally got in this algorithm. Now this woman cannot appear in a stable matching. So stable matching cannot give any answer which is better than what the algorithm give. So it's just the same claim as was stated. This claim is just repeated in a different way, but this way is more convenient to prove. Let's try. So I gave this claim, and what is important to understand for the proof is there are two pictures in this proof. There is the static picture, which is some stable matching, this stable metric which we consider. And also there is a dynamic picture. It's what is happening due to your algorithm. They are just independent somehow, but we need to prove that some combination of circumferences is not possible. Okay, let's try. It's always difficult to prove, but let's try and see what we can do. The proof is an induction proof. And induction is by the rejection moment. So during the algorithm there are several rejection. So some proposal are rejected, or some pairs are dissolved. And in both cases, some woman rejects some man. And so this is what has happened with m and w. And so there are a sequence of rejections. And we prove induction by induction over this rejection moment. Okay, so assume that the claim is false. And some pair (m,w) appears in a stable matching. But, in the contrary to what we, the claim still w was rejected by m. And what does it mean? That there is some when an objection happens, women gets a better candidate. Either it has at from the moment of rejection, of proposal or a new proposal comes. But in both cases, there is this red line shows that in the algorithm, woman W was connected to some other better candidate than our stable. Okay, but this better candidate M prime, in the stable picture he is also connected to some woman, different one because it is perfect matching, and this woman is W prime. So we have two pairs m m, m w, and and M-prime, W-prime in this stable matching. And this red line means that, due to the algorithm, there was pair and prime W. And now we want to use the matching stable. And what does it mean? Since by construction, and prime was better than m for w, then the only way why this will not be an unstable situation is the viewpoint of m prime. M prime should believe that the stable partner, w prime, is better than w. So we get, we know we have some, this information about ordering. And recall that during the algorithm, this m prime was paired with w. And, So look, w prime is better for m prime. So why if at some point m prime was paired with w, this means that earlier he tried to be paired with W-prime because W-prime is earlier in the list. So he was earlier rejected by W-prime before all this happens, We'll get a contraction with the induction assumption. We see that now, look, M-prime was rejected by W-prime, and on the other hand, we assume that they appear in the stable matching. So this is the thing which cannot happen. We see that this happens for M-prime and W-prime, which is exactly what is forbidden by our claim. This is the inductive proof. It's a bit strange but you can carefully check all the steps, and each step is rather simple. But the problem is that they are not very natural, it is difficult to see all of them together in one algorithm. Anyway, here are the proof.