Non riesco a capire la prova del motivo per cui l'algoritmo Gale - Shapley sposa ogni donna con il suo coniuge PESSIMALE.

Question

Sono nuovo qui. Questo è il mio primo post!

Quasi tutte le prove per questo teorema usano la dimostrazione per contraddizione e assumono che "ci deve essere un insieme stabile di matrimoni $\mathcal M$ dove una donna è sposata con un uomo che le piace MENO del suo coniuge in The Mating Ritual. "

La mia domanda è; ai fini della contraddizione non dovremmo presumere che "ci deve essere un insieme stabile di matrimoni$\mathcal M$ dove una donna è sposata con un uomo che le piace PIÙ del suo coniuge in The Mating Ritual. "

Perché nella mia testa sembra che vogliamo dimostrare che ogni donna NON è sposata con il suo coniuge ottimale. Sembra che tutto ciò che abbiamo mostrato nella prova qui sotto sia che una donna non può fare peggio del suo pessimo coniuge. Sono sicuro che mi manchi qualcosa qui!

La prova completa di questo teorema nel libro di testo "Mathematics for Computer Science" del MIT è di seguito (è solo la parte sopra che non mi è chiara, tutto il resto ha senso):

Teorema : il rituale dell'accoppiamento sposa ogni donna con il suo pessimale coniuge.

Prova . Per contraddizione. Supponiamo che il teorema non sia vero. Quindi ci deve essere un insieme stabile di matrimoni$\mathcal M$dove una donna (chiamala Nicole) è sposata con un uomo (chiamalo Tom) che le piace meno del suo coniuge in The Mating Ritual (chiamalo Keith). Ciò significa che:

Nicole preferisce Keith a Tom.

Sappiamo che The Mating Ritual sposa ogni uomo con il suo coniuge ottimale e il fatto che Nicole e Keith siano sposati nel Mating Ritual, sappiamo che

Keith preferisce Nicole a sua moglie in $\mathcal M$.

Ciò significa che Keith e Nicole formano una coppia canaglia in $\mathcal M$, che contraddice la stabilità di $\mathcal M$. $\blacksquare$

L'aiuto è molto apprezzato!

Answer 1

Se la nostra affermazione è "l'algoritmo Gale-Shapley assegna a ogni donna il suo coniuge pessimale", e vogliamo dimostrarlo per contraddizione, allora vogliamo negare questa affermazione.

La negazione di questa affermazione è che non a tutte le donne viene assegnata la sua sposa pessimale sotto Gale-Shapley. In altre parole, c'è una donna a cui non è stata assegnata la sua sposa pessimale (nell'abbinamento Gale-Shapley che chiamerò$\mathcal G$).

Dopo la prova, chiama la donna a cui non è stato assegnato il suo coniuge pessimale $\mathcal G$ "Nicole", e chiama sua moglie $\mathcal G$ "Keith".

Cosa significa che Keith non è il suo pessimale coniuge? Significa che un altro uomo, chiamalo "Tom", è il suo pessimale coniuge. E cosa significa essere un coniuge pessimale? Non significa che a Nicole piaccia Tom meno di tutti. Significa che a Nicole piace Tom meno di tutti quelli che potrebbe sposare in un abbinamento stabile. In particolare:

• Deve esserci una corrispondenza stabile$\mathcal M$che corrisponde a Nicole e Tom; ecco perché Tom è un potenziale coniuge.
• In ogni abbinamento stabile, Nicole o sposa Tom o qualcun altro che le piace di più: ecco perché Tom è il coniuge pessimale.
• In particolare, in $\mathcal G$ (l'abbinamento stabile Gale-Shapley), Nicole ama la persona che sposa (Keith) più di Tom.

Questo copre tutte le conclusioni tratte nel primo paragrafo della prova.