WisFaq!

De digitale vraagbaak voor het wiskundeonderwijs

HOME

samengevat

\require{AMSmath}

Re: Slechtste partner in Gale Shapley

Dit is een reactie op vraag 93366

Bedankt voor uw antwoord. In het boek wordt een bewijs gegeven uit het ongerijmde, met de volgende definitie: We say that m is the worst valid partner of w if m is a valid partner of w, and no man whom w ranks lower than m is a valid partner of hers. Dus: stel dat er een vrouw wordt gepaard met een man M die niet de slechtst mogelijke partner is. Dan geldt per definitie een van de volgende twee gevallen (of allebei, omdat we een negatie zetten voor de conjunctie in de definitie van worst valid partner):
1) M is geen geldige partner van de vrouw
2) Er is een man M' die de vrouw lager beoordeeld dan M, en M' is een geldige partner.

In het bewijs wordt echter alleen geval 2 (of allebei) aangenomen, maar zouden we niet ook het geval moeten bewijzen dat alleen geval 1 geldt? Waarom volstaat het om alleen geval 2 aan te nemen in het bewijs, en geval 1 te negeren?
Nico
Student universiteit - vrijdag 11 februari 2022

Antwoord

Die stelling gaat over de matching $S^*$ en die is stable, dus $m$ is een geldige partner van $w$.

kphart

Vragen naar aanleiding van dit antwoord? Klik rechts..!
vrijdag 11 februari 2022