No puedo entender la prueba de por qué el algoritmo Gale-Shapley casa a cada mujer con su cónyuge PESIMAL.
Soy nuevo aqui. ¡Esta es mi primera publicación!
Casi todas las pruebas de este teorema utilizan la prueba por contradicción y asumen que "debe haber un conjunto estable de matrimonios $\mathcal M$ donde una mujer está casada con un hombre que le gusta MENOS que a su cónyuge en The Mating Ritual ".
Mi pregunta es; a los efectos de la contradicción, ¿no deberíamos asumir que "debe haber un conjunto estable de matrimonios$\mathcal M$ donde una mujer está casada con un hombre que le gusta MÁS que a su cónyuge en The Mating Ritual ".
Porque en mi cabeza parece que queremos mostrar que toda mujer NO está casada con su cónyuge óptimo. Parece que todo lo que hemos demostrado en la siguiente prueba es que una mujer no puede hacer nada peor que su cónyuge pesimista. ¡Estoy seguro de que me falta algo aquí!
La prueba completa de este teorema en el libro de texto "Matemáticas para la informática" del MIT se encuentra a continuación (es solo la parte anterior la que no me queda clara, todo lo demás tiene sentido):
Teorema : El ritual de apareamiento casa a cada mujer con su cónyuge pesimista.
Prueba . Por contradicción. Suponga que el teorema no es cierto. Por lo tanto, debe haber un conjunto estable de matrimonios.$\mathcal M$donde una mujer (llámala Nicole) está casada con un hombre (llámalo Tom) que le gusta menos que a su cónyuge en The Mating Ritual (llámalo Keith). Esto significa que:
Nicole prefiere a Keith a Tom.
Sabemos que The Mating Ritual casa a cada hombre con su cónyuge óptimo y el hecho de que Nicole y Keith están casados en el Ritual de apareamiento, sabemos que
Keith prefiere a Nicole a su esposa en $\mathcal M$.
Esto significa que Keith y Nicole forman una pareja rebelde en $\mathcal M$, que contradice la estabilidad de $\mathcal M$. $\blacksquare$
¡Se agradece mucho la ayuda!
Respuestas
Si nuestra afirmación es "el algoritmo de Gale-Shapley asigna a cada mujer su cónyuge pesimista", y queremos probarlo por contradicción, entonces queremos negar esta afirmación.
La negación de esta declaración es que no a todas las mujeres se les asigna su cónyuge pesimista bajo Gale-Shapley. En otras palabras, hay una mujer a la que no se le asigna su cónyuge pesimista (en el emparejamiento Gale-Shapley llamaré$\mathcal G$).
Después de la prueba, llame a la mujer a la que no se le asignó su cónyuge pesimal en $\mathcal G$ "Nicole" y llama a su cónyuge $\mathcal G$ "Keith".
¿Qué significa que Keith no es su cónyuge pesimista? Significa que algún otro hombre, llámalo "Tom", es su cónyuge pesimista. ¿Y qué significa ser un cónyuge pesimista? No significa que a Nicole le guste menos Tom. Significa que a Nicole le gusta Tom menos de todas las personas con las que podría casarse en cualquier pareja estable. En particular:
- Tiene que haber alguna coincidencia estable$\mathcal M$que coincide con Nicole y Tom; por eso Tom es un posible cónyuge.
- En cualquier emparejamiento estable, Nicole se casa con Tom o con alguien que le guste más: por eso Tom es el cónyuge pesimista.
- En particular, en $\mathcal G$ (la pareja estable de Gale-Shapley), a Nicole le gusta más la persona con la que se casa (Keith) que a Tom.
Esto cubre todas las conclusiones hechas en el primer párrafo de la prueba.