ไม่เข้าใจข้อพิสูจน์ว่าเหตุใด Gale - Shapley Algorithm จึงแต่งงานกับผู้หญิงทุกคนกับคู่สมรส PESSIMAL ของเธอ

Question

ฉันมาใหม่ที่นี่ นี่เป็นกระทู้แรกของฉัน!

การพิสูจน์เกือบทั้งหมดสำหรับทฤษฎีบทนี้ใช้การพิสูจน์โดยความขัดแย้งและพวกเขาคิดว่า "ต้องมีชุดแต่งงานที่มั่นคง $\mathcal M$ ที่ผู้หญิงบางคนแต่งงานกับผู้ชายที่เธอชอบน้อยกว่าคู่ครองใน The Mating Ritual "

คำถามของฉันคือ; ด้วยจุดประสงค์ของความขัดแย้งเราไม่ควรคิดว่า "ต้องมีการแต่งงานที่มั่นคง$\mathcal M$ ที่ผู้หญิงบางคนแต่งงานกับผู้ชายที่เธอชอบมากกว่าคู่ครองของเธอใน The Mating Ritual "

เพราะในหัวของฉันดูเหมือนว่าเราต้องการแสดงให้เห็นว่าผู้หญิงทุกคนไม่ได้แต่งงานกับคู่ครองที่ดีที่สุดของเธอ ดูเหมือนว่าทั้งหมดที่เราได้แสดงไว้ในบทพิสูจน์ด้านล่างนี้ก็คือผู้หญิงจะไม่เลวร้ายไปกว่าคู่ครองที่น่ารังเกียจของเธอ ฉันแน่ใจว่าฉันพลาดอะไรบางอย่างที่นี่!

ข้อพิสูจน์ฉบับสมบูรณ์สำหรับทฤษฎีบทนี้ในหนังสือเรียน "คณิตศาสตร์สำหรับวิทยาการคอมพิวเตอร์" ของ MIT อยู่ด้านล่าง (เป็นเพียงส่วนข้างต้นที่ไม่ชัดเจนสำหรับฉันทุกอย่างก็สมเหตุสมผล):

ทฤษฎีบท : พิธีกรรมการผสมพันธุ์แต่งงานกับผู้หญิงทุกคนกับคู่สมรสที่ไม่ดีของเธอ

หลักฐาน . โดยความขัดแย้ง สมมติว่าทฤษฎีบทไม่เป็นความจริง ดังนั้นจึงต้องมีการแต่งงานที่มั่นคง$\mathcal M$ที่ผู้หญิงบางคน (เรียกเธอว่านิโคล) แต่งงานกับผู้ชาย (เรียกเขาว่าทอม) ที่เธอชอบน้อยกว่าคู่ครองของเธอในพิธีกรรมการผสมพันธุ์ (เรียกเขาว่าคี ธ ) ซึ่งหมายความว่า:

นิโคลชอบคี ธ กับทอม

เรารู้ว่า The Mating Ritual แต่งงานกับผู้ชายทุกคนกับคู่ครองที่ดีที่สุดของเขาและการที่นิโคลและคี ธ แต่งงานกันในพิธีกรรมการผสมพันธุ์เรารู้ดีว่า

Keith ชอบ Nicole กับคู่สมรสของเขาใน $\mathcal M$.

ซึ่งหมายความว่าคี ธ และนิโคลสร้างคู่โกงใน $\mathcal M$ซึ่งขัดแย้งกับเสถียรภาพของ $\mathcal M$. $\blacksquare$

ช่วยชื่นชมมาก!

Answer 1

หากคำกล่าวอ้างของเราคือ "อัลกอริทึม Gale-Shapley กำหนดให้ผู้หญิงทุกคนเป็นคู่ครองที่น่ารังเกียจของเธอ" และเราต้องการพิสูจน์ด้วยความขัดแย้งเราก็ต้องการลบล้างคำพูดนี้

การปฏิเสธของคำแถลงนี้คือไม่ใช่ว่าผู้หญิงทุกคนจะได้รับมอบหมายให้เป็นคู่สมรสที่ไม่ดีของเธอภายใต้ Gale-Shapley กล่าวอีกนัยหนึ่งก็คือมีผู้หญิงบางคนที่ไม่ได้กำหนดคู่ครองที่แย่ที่สุดของเธอ (ในการจับคู่ Gale-Shapley ฉันจะเรียก$\mathcal G$).

หลังจากพิสูจน์แล้วให้โทรหาผู้หญิงที่ไม่ได้กำหนดคู่สมรสที่ไม่ดีของเธอเข้ามา $\mathcal G$ "นิโคล" และเรียกคู่สมรสของเธอเข้ามา $\mathcal G$ "คี ธ ".

หมายความว่าอย่างไรที่คี ธ ไม่ใช่คู่สมรสที่น่ารังเกียจของเธอ? หมายความว่าผู้ชายคนอื่น ๆ เรียกเขาว่า "ทอม" เป็นคู่สมรสที่ไม่ดีของเธอ และการเป็นคู่สมรสที่ไม่ดีหมายถึงอะไร? ไม่ได้หมายความว่านิโคลชอบทอมน้อยที่สุดของทุกคน หมายความว่านิโคลชอบทอมน้อยที่สุดในบรรดาทุกคนที่เธออาจจะแต่งงานด้วยการจับคู่ที่มั่นคง โดยเฉพาะอย่างยิ่ง:

• จะต้องมีมีบางการจับคู่ที่มั่นคง$\mathcal M$ซึ่งตรงกับนิโคลและทอม; นั่นเป็นเหตุผลที่ทอมเป็นคู่ครองที่มีศักยภาพ
• ในการจับคู่ที่มั่นคงนิโคลอาจแต่งงานกับทอมหรือคนอื่นที่เธอชอบมากกว่านั่นคือเหตุผลที่ทอมเป็นคู่สมรสที่น่ารังเกียจ
• โดยเฉพาะอย่างยิ่งใน $\mathcal G$ (การจับคู่ที่มั่นคงของ Gale-Shapley) นิโคลชอบคนที่เธอแต่งงานกับ (คี ธ ) มากกว่าทอม

ซึ่งครอบคลุมข้อสรุปทั้งหมดที่เกิดขึ้นในย่อหน้าแรกของการพิสูจน์