Não consigo entender a prova de por que o algoritmo Gale-Shapley casa todas as mulheres com seu esposo PESSIMAL.
Eu sou novo aqui. Este é o meu primeiro post!
Quase todas as provas para este teorema usam prova por contradição e assumem que "deve haver um conjunto estável de casamentos $\mathcal M$ onde uma mulher é casada com um homem de quem ela gosta MENOS do que seu esposo em O Ritual de Acasalamento. "
Minha pergunta é; para fins de contradição, não deveríamos supor que "deve haver um conjunto estável de casamentos$\mathcal M$ onde uma mulher é casada com um homem de quem ela gosta MAIS do que seu esposo em The Mating Ritual. "
Porque na minha cabeça parece que queremos mostrar que toda mulher NÃO é casada com seu esposo ideal. Parece que tudo o que mostramos na prova abaixo é que uma mulher não pode fazer pior do que seu esposo pessimal. Tenho certeza de que estou perdendo algo aqui!
A prova completa para este teorema no livro "Mathematics for Computer Science" do MIT está abaixo (é apenas a parte acima que não está clara para mim, todo o resto faz sentido):
Teorema : O Ritual de Acasalamento casa toda mulher com seu esposo pessimal.
Prova . Por contradição. Suponha que o teorema não seja verdadeiro. Portanto, deve haver um conjunto estável de casamentos$\mathcal M$onde uma mulher (chame-a de Nicole) é casada com um homem (chame-o de Tom) de quem ela gosta menos do que sua esposa no Ritual de Acasalamento (chame-o de Keith). Isso significa que:
Nicole prefere Keith a Tom.
Sabemos que o Ritual de Acasalamento casa todo homem com sua esposa ideal e o fato de Nicole e Keith serem casados no Ritual de Acasalamento, sabemos que
Keith prefere Nicole a sua esposa em $\mathcal M$.
Isso significa que Keith e Nicole formam um casal desonesto em $\mathcal M$, o que contradiz a estabilidade de $\mathcal M$. $\blacksquare$
A ajuda é muito apreciada!
Respostas
Se nossa afirmação for "o algoritmo de Gale-Shapley atribui a cada mulher seu cônjuge pessimal", e queremos provar isso por contradição, então queremos negar essa afirmação.
A negação dessa afirmação é que nem toda mulher é designada a seu esposo pessimal sob Gale-Shapley. Em outras palavras, há uma mulher que não tem seu esposo pessimal (na combinação Gale-Shapley que chamarei$\mathcal G$)
Após a prova, ligue para a mulher a quem não foi designado seu esposo pessimal em $\mathcal G$ "Nicole", e ligue para seu esposo em $\mathcal G$ "Keith".
O que significa que Keith não é seu esposo pessimal? Isso significa que outro homem, chamado de "Tom", é seu esposo pessimal. E o que significa ser um cônjuge pessimal? Isso não significa que Nicole goste de Tom menos do que todos. Isso significa que Nicole gosta de Tom menos do que todos com quem ela poderia se casar em qualquer união estável. Em particular:
- Tem que haver alguma correspondência estável$\mathcal M$que corresponde a Nicole e Tom; é por isso que Tom é um cônjuge em potencial.
- Em qualquer união estável, Nicole se casa com Tom ou com outra pessoa de quem ela gosta mais: é por isso que Tom é o cônjuge pessimal.
- Em particular, em $\mathcal G$ (a combinação estável de Gale-Shapley), Nicole gosta mais da pessoa com quem ela se casa (Keith) do que de Tom.
Isso cobre todas as conclusões feitas no primeiro parágrafo da prova.