Je ne peux pas comprendre la preuve de la raison pour laquelle l'algorithme Gale-Shapley marie chaque femme à son conjoint PESSIMAL.

Question

Je suis nouveau ici. Ceci est mon premier message posté!

Presque toutes les preuves de ce théorème utilisent la preuve par contradiction et supposent qu '"il doit y avoir un ensemble stable de mariages $\mathcal M$ où une femme est mariée à un homme qu'elle aime MOINS que son conjoint dans The Mating Ritual. "

Ma question est; à des fins de contradiction, ne devrions-nous pas supposer qu '"il doit y avoir un ensemble stable de mariages$\mathcal M$ où une femme est mariée à un homme qu'elle aime PLUS que son conjoint dans The Mating Ritual. "

Parce que dans ma tête, il semble que nous voulons montrer que chaque femme n'est PAS mariée à son conjoint optimal. Il semble que tout ce que nous avons montré dans la preuve ci-dessous, c'est qu'une femme ne peut pas faire pire que son conjoint pessimal. Je suis sûr qu'il me manque quelque chose ici!

La preuve complète de ce théorème dans le manuel "Mathematics for Computer Science" du MIT est ci-dessous (c'est juste la partie ci-dessus qui n'est pas claire pour moi, tout le reste a du sens):

Théorème : Le rituel d'accouplement marie chaque femme à son conjoint pessimal.

Preuve . Par contradiction. Supposons que le théorème n'est pas vrai. Par conséquent, il doit y avoir un ensemble stable de mariages$\mathcal M$où une femme (appelez-la Nicole) est mariée à un homme (appelez-le Tom) qu'elle aime moins que son conjoint dans The Mating Ritual (appelez-le Keith). Cela signifie que:

Nicole préfère Keith à Tom.

Nous savons que le rituel d'accouplement marie chaque homme à son épouse optimale et le fait que Nicole et Keith sont mariés dans le rituel d'accouplement, nous savons que

Keith préfère Nicole à son épouse en $\mathcal M$.

Cela signifie que Keith et Nicole forment un couple de voyous $\mathcal M$, ce qui contredit la stabilité de $\mathcal M$. $\blacksquare$

L'aide est très appréciée!

Answer 1

Si notre affirmation est «l'algorithme Gale-Shapley attribue à chaque femme son conjoint pessimal», et que nous voulons le prouver par contradiction, alors nous voulons nier cette affirmation.

La négation de cette affirmation est que toutes les femmes ne se voient pas attribuer leur conjoint pessimal sous Gale-Shapley. En d'autres termes, il y a une femme à qui son conjoint pessimal n'est pas attribué (dans le match Gale-Shapley, je vais appeler$\mathcal G$).

Suite à la preuve, appelez la femme à qui son conjoint pessimal $\mathcal G$ "Nicole", et appelle son épouse $\mathcal G$ «Keith».

Qu'est-ce que cela signifie que Keith n'est pas son époux pessimal? Cela signifie qu'un autre homme, appelez-le "Tom", est son époux pessimal. Et que signifie être un conjoint pessimal? Cela ne veut pas dire que Nicole aime le moins Tom de tout le monde. Cela signifie que Nicole aime le moins Tom de tous ceux qu'elle pourrait épouser dans n'importe quel match stable. En particulier:

• Il doit y avoir une correspondance stable$\mathcal M$qui correspond à Nicole et Tom; c'est pourquoi Tom est un conjoint potentiel.
• Dans tout jumelage stable, Nicole épouse soit Tom ou quelqu'un d'autre qu'elle aime plus: c'est pourquoi Tom est le conjoint pessimal.
• En particulier, dans $\mathcal G$ (l'appariement stable Gale-Shapley), Nicole aime plus la personne qu'elle épouse (Keith) que Tom.

Cela couvre toutes les conclusions faites dans le premier paragraphe de la preuve.