Gale-Shapley Algorithm이 모든 여성을 PESSIMAL 배우자와 결혼하는 이유에 대한 증거를 이해할 수 없습니다.
나는 신입이다. 이것은 내 첫 번째 게시물입니다!
이 정리에 대한 거의 모든 증명은 모순에 의한 증명을 사용하며 그들은 "안정적인 결혼 세트가 있어야한다"고 가정합니다. $\mathcal M$ 어떤 여성이 The Mating Ritual에서 배우자보다 덜 좋아하는 남자와 결혼했습니다. "
내 질문은; 모순의 목적으로 우리는 "안정적인 결혼이 있어야한다"고 가정해서는 안됩니다.$\mathcal M$ 어떤 여성이 The Mating Ritual에서 배우자보다 더 좋아하는 남성과 결혼했습니다. "
내 머릿속에서는 모든 여성이 최적의 배우자와 결혼하지 않았 음을 보여주고 싶은 것 같기 때문입니다. 우리가 아래 증명에서 보여준 모든 것은 여성이 비관적 인 배우자보다 더 나쁜 일을 할 수 없다는 것입니다. 여기에 뭔가 빠진 것 같아요!
MIT의 "컴퓨터 과학을위한 수학"교과서에있는이 정리에 대한 완전한 증거는 다음과 같습니다.
정리 : 짝짓기 의식은 모든 여성을 비관적 인 배우자와 결혼합니다.
증거 . 모순으로. 정리가 사실이 아니라고 가정합니다. 그러므로 안정적인 결혼이 있어야합니다$\mathcal M$어떤 여성 (Nicole이라고 부름)이 The Mating Ritual (Keith라고 부름)에서 배우자보다 덜 좋아하는 남자 (톰이라고 부름)와 결혼했습니다. 이는 다음을 의미합니다.
Nicole은 Tom보다 Keith를 선호합니다.
우리는 The Mating Ritual이 모든 남자를 최적의 배우자와 결혼하고 Nicole과 Keith가 Mating Ritual에서 결혼했다는 사실을 알고 있습니다.
Keith는 그의 배우자보다 Nicole을 선호합니다. $\mathcal M$.
이것은 Keith와 Nicole이 $\mathcal M$의 안정성에 모순되는 $\mathcal M$. $\blacksquare$
도움을 많이 주시면 감사하겠습니다!
답변
우리의 주장이 "Gale-Shapley 알고리즘은 모든 여성에게 비관적 인 배우자를 할당합니다"이고 모순으로 증명하고 싶다면이 진술을 부정하고 싶습니다.
이 진술의 부정은 모든 여성이 Gale-Shapley 아래에서 비관적 인 배우자로 지정 되는 것은 아니라는 것 입니다. 즉, 일부가 내가 전화 할게 일치하는 강풍 - 샤플리 그녀의 pessimal 배우자를 할당되지 않은 여자 ($\mathcal G$).
증거에 따라 비관적 배우자가 배정되지 않은 여성을 $\mathcal G$ "Nicole", 그리고 그녀의 배우자를 $\mathcal G$ "키스".
Keith가 그녀의 비관적 인 배우자가 아니라는 것은 무엇을 의미합니까? 그것은 그를 "톰"이라고 부르는 다른 남자 가 그녀의 비관적 인 배우자 라는 것을 의미합니다 . 그리고 비관적 인 배우자가된다는 것은 무엇을 의미합니까? 니콜이 톰을 가장 좋아한다는 의미는 아닙니다. 니콜은 안정적인 매칭에서 결혼 할 수있는 모든 사람 중에서 톰을 가장 좋아한다는 것을 의미합니다. 특히:
- 있을가 일부 안정 매칭$\mathcal M$Nicole과 Tom과 일치합니다. 이것이 Tom이 잠재적 인 배우자 인 이유입니다.
- 에서 어떤 안정적인 매칭, 니콜 중이 결혼하고 톰 또는 다른 사람이 그녀가 더 좋아 : 톰이 pessimal 배우자 인 이유가.
- 특히 $\mathcal G$ (게일-샤플리 안정적인 매칭) 니콜은 톰보다 결혼 한 사람 (키스)을 더 좋아한다.
이것은 증명의 첫 번째 단락에서 내린 모든 결론을 다룹니다.