De digitale vraagbaak voor het wiskundeonderwijs

home |  vandaag |  gisteren |  bijzonder |  gastenboek |  wie is wie? |  verhalen |  contact

HOME

samengevat
vragen bekijken
een vraag stellen
hulpjes
zoeken
FAQ
links
twitter
boeken
help

inloggen

colofon

  \require{AMSmath} Printen

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



home |  vandaag |  bijzonder |  gastenboek |  statistieken |  wie is wie? |  verhalen |  colofon

©2001-2024 WisFaq - versie 3