กาลครั้งหนึ่งนานมาแล้ว มีปัญหาข้อหนึ่ง เรียกว่าปัญหาคู่แต่งงานเสถียรภาพ: ลองจินตนาการว่า คุณเป็นพ่อสื่อแม่ชัก และมีสาวร้อยคน กับหนุ่มร้อยนาย เดินเข้ามาขอให้คุณช่วยจับคู่ให้ หลังจากที่หนุ่มสาวทั้งร้อยคู่พบหน้ากันแล้ว สาวแต่ละคนจะเรียงลำดับหนุ่มตามสเป็คของเธอไว้ เช่นเดียวกับฝ่ายชาย ก็เรียงลำดับสาวในฝันของเขาไว้เช่นกัน
โจทย์มีอยู่ว่า คุณจะสามารถจับคู่แต่งงานทั้งหนึ่งร้อยคู่ได้หรือไม่?
มันคงเห็นได้ทันทีว่า ทุกคนไม่มีทางได้ตามสเป็คแรกของตัวเอง : ถ้าหนุ่มดิจิเดี้ยงฮอตจัดเป็นที่พึงใจของสาวๆมากกว่าหนึ่งราย มันก็จะมีสาวเพียงรายเดียวที่ได้หนุ่มดิจิไปครอง ความท้าทายของโจทย์นี้คือ เราสามารถทำให้การแต่งงานนี้ เสถียรได้หรือไม่ - ในที่นี้หมายความว่า เมื่อการจับคู่เกิดขึ้นแล้ว จะต้องไม่มีคู่ไหนเปลี่ยนคู่ เพราะเจอคนที่ดีกว่า (นั่นหมายถึง ต้องไม่มีหนุ่มดาร์ธเกิดปิ๊งปั๊งขึ้นมากับสาวโอ้ละหนอ [ที่หนุ่มดาร์ธเห็นว่างามกว่าสาวที่ถูกจับคู่ด้วยแต่แรก] แล้วเกิดตัดสินใจหนีตามกัน โดยฝ่ายหญิงยินยอมพร้อมใจว่า เออ เธอก็ดูดีกว่าคนที่ชั้นโดนจับยัดมาในถุงเหมือนกัน) ในทางกลับกัน ถ้าสาวปิ๊งก่อน เราก็คาดหวังว่าหนุ่มๆจะตอบว่า "ขออภัยแม่หญิง แต่นงคราญที่บ้านข้างามล้ำกว่ายิ่งนัก ข้าขอปฏิเสธ"
คำถามก็คือ เราสามารถยืนยันได้หรือไม่ว่า พ่อสื่อจะสามารถจัดคู่แต่งงานที่เสถียรได้เสมอ? และ ถ้ายืนยันได้ จะทำอย่างไร?
ปัญหาข้อนี้ได้ชื่อว่า Stable Marriage Problem หรือ SMP และในปี 1962 David Gale และ Lloyd Shapley ประสบความสำเร็จในการพิสูจน์ว่า ไม่ว่าจำนวน ผช / ผญ จะเป็นเท่าไรก็ตาม ขอแค่จำนวนคนเท่ากัน (และไม่มีเกย์ หรือ เลสเบี้ยน) จะสามารถจับคู่แต่งงานที่เสถียรให้กับทุกคนได้เสมอ กระบวนการนี้ ถูกเรียกว่า Gale–Shapley algorithm.
Gale–Shapley algorithm ยืนยันว่า
1. ทุกคนจะได้แต่งงาน
2. คู่แต่งงานจะเสถียร
โดยการดำเนินการ จะทำเป็นรอบ โดยในรอบแรก
a) หนุ่มทุกคน จะถือดอกกุหลาบไปสารภาพรักกับสาวที่เขาพอใจที่สุด
b) สาวๆ จะรับดอกกุหลาบ จากหนุ่มที่เธอพอใจที่สุด เพียงดอกเดียว
ในรอบถัดๆไปจะคล้ายๆกัน แต่มีปรับเปลี่ยนเล็กน้อย
c) หนุ่มที่ยังไม่มีคู่ จะไปสารภาพรักกับสาวคนที่เขาชอบที่สุดที่ยังไม่เคยสารภาพรักมาก่อน(สาวมีคู่แล้วก็ไม่เป็นไร)d) สาวๆต้องเลือกว่าจะรับหนุ่มคนใหม่เป็นแฟน(กรณีที่มีอยู่แล้ว - แฟนเก่า ก็กลายเป็นคนโดนทิ้ง ไปหาสาวคนใหม่) หรือ จะพอใจกับคนเดิม(คนที่กินแห้วก็ต้องแสวงหาต่อไป)
เมื่อกระบวนการนี้ดำเนินต่อไป การจับคู่ก็จะจบลงโดยทุกคนมีคู่ และไม่สามารถหาคู่ที่ดีกว่านี้ได้
หวังว่าข้อพิสูจน์นี้ จะให้กำลังใจบรรดาหนุ่มโสด-สาวโสดแห่งหว้ากอทั้งหลาย ว่าชีวิตยังไม่สิ้น ก็ดิ้นหาคู่ไปเถิด หนุ่มๆก็หมั่นหาดอกกุหลาบไปเสนอสาวๆหน่อย แม้ว่าจะดอกละห้าร้อยในวันนี้ก็ตาม
ปล. ในปี 1984 Alvin E. Roth ได้นำ Algorithm นี้ไปปรับปรุงระบบการจับคู่นักศึกษาแพทย์เรสสิเดนท์ของอเมริกา กับ โรงพยาบาล ซึ่งทำให้มีระดับความพึงพอใจของทั้งโรงพยาบาล และนักศึกษาแพทย์เพิ่มขึ้นมาก ผลจากการประยุกต์ใช้นี้ ทำให้ ในปี 2012 Alvin E. Roth และ Lloyd Shapley ได้รางวัลโนเบลร่วมกัน สำหรับผลงานที่โดดเด่นในด้านทฤษฎีการจัดสรรที่เสถียรและการออกแบบระบบตลาด ("the theory of stable allocations and the practice of market design")
http://en.wikipedia.org/wiki/Stable_marriage_problem
http://www.dcs.gla.ac.uk/research/algorithms/stable/
http://en.wikipedia.org/wiki/Lloyd_Shapley
http://en.wikipedia.org/wiki/List_of_Nobel_laureates_in_Economics
http://en.wikipedia.org/wiki/David_Gale
http://scimath.unl.edu/MIM/files/MATExamFiles/PremerJennie_Final_071511_LA.pdf
http://www.meconomics.net/content/456 
กระทู้รับวาเลนไทน์ - ปัญหาคู่แต่งงานเสถียร(SMP)
โจทย์มีอยู่ว่า คุณจะสามารถจับคู่แต่งงานทั้งหนึ่งร้อยคู่ได้หรือไม่?
มันคงเห็นได้ทันทีว่า ทุกคนไม่มีทางได้ตามสเป็คแรกของตัวเอง : ถ้าหนุ่มดิจิเดี้ยงฮอตจัดเป็นที่พึงใจของสาวๆมากกว่าหนึ่งราย มันก็จะมีสาวเพียงรายเดียวที่ได้หนุ่มดิจิไปครอง ความท้าทายของโจทย์นี้คือ เราสามารถทำให้การแต่งงานนี้ เสถียรได้หรือไม่ - ในที่นี้หมายความว่า เมื่อการจับคู่เกิดขึ้นแล้ว จะต้องไม่มีคู่ไหนเปลี่ยนคู่ เพราะเจอคนที่ดีกว่า (นั่นหมายถึง ต้องไม่มีหนุ่มดาร์ธเกิดปิ๊งปั๊งขึ้นมากับสาวโอ้ละหนอ [ที่หนุ่มดาร์ธเห็นว่างามกว่าสาวที่ถูกจับคู่ด้วยแต่แรก] แล้วเกิดตัดสินใจหนีตามกัน โดยฝ่ายหญิงยินยอมพร้อมใจว่า เออ เธอก็ดูดีกว่าคนที่ชั้นโดนจับยัดมาในถุงเหมือนกัน) ในทางกลับกัน ถ้าสาวปิ๊งก่อน เราก็คาดหวังว่าหนุ่มๆจะตอบว่า "ขออภัยแม่หญิง แต่นงคราญที่บ้านข้างามล้ำกว่ายิ่งนัก ข้าขอปฏิเสธ"
คำถามก็คือ เราสามารถยืนยันได้หรือไม่ว่า พ่อสื่อจะสามารถจัดคู่แต่งงานที่เสถียรได้เสมอ? และ ถ้ายืนยันได้ จะทำอย่างไร?
ปัญหาข้อนี้ได้ชื่อว่า Stable Marriage Problem หรือ SMP และในปี 1962 David Gale และ Lloyd Shapley ประสบความสำเร็จในการพิสูจน์ว่า ไม่ว่าจำนวน ผช / ผญ จะเป็นเท่าไรก็ตาม ขอแค่จำนวนคนเท่ากัน (และไม่มีเกย์ หรือ เลสเบี้ยน) จะสามารถจับคู่แต่งงานที่เสถียรให้กับทุกคนได้เสมอ กระบวนการนี้ ถูกเรียกว่า Gale–Shapley algorithm.
Gale–Shapley algorithm ยืนยันว่า
1. ทุกคนจะได้แต่งงาน
2. คู่แต่งงานจะเสถียร
โดยการดำเนินการ จะทำเป็นรอบ โดยในรอบแรก
a) หนุ่มทุกคน จะถือดอกกุหลาบไปสารภาพรักกับสาวที่เขาพอใจที่สุด
b) สาวๆ จะรับดอกกุหลาบ จากหนุ่มที่เธอพอใจที่สุด เพียงดอกเดียว
ในรอบถัดๆไปจะคล้ายๆกัน แต่มีปรับเปลี่ยนเล็กน้อย
c) หนุ่มที่ยังไม่มีคู่ จะไปสารภาพรักกับสาวคนที่เขาชอบที่สุดที่ยังไม่เคยสารภาพรักมาก่อน(สาวมีคู่แล้วก็ไม่เป็นไร)d) สาวๆต้องเลือกว่าจะรับหนุ่มคนใหม่เป็นแฟน(กรณีที่มีอยู่แล้ว - แฟนเก่า ก็กลายเป็นคนโดนทิ้ง ไปหาสาวคนใหม่) หรือ จะพอใจกับคนเดิม(คนที่กินแห้วก็ต้องแสวงหาต่อไป)
เมื่อกระบวนการนี้ดำเนินต่อไป การจับคู่ก็จะจบลงโดยทุกคนมีคู่ และไม่สามารถหาคู่ที่ดีกว่านี้ได้
หวังว่าข้อพิสูจน์นี้ จะให้กำลังใจบรรดาหนุ่มโสด-สาวโสดแห่งหว้ากอทั้งหลาย ว่าชีวิตยังไม่สิ้น ก็ดิ้นหาคู่ไปเถิด หนุ่มๆก็หมั่นหาดอกกุหลาบไปเสนอสาวๆหน่อย แม้ว่าจะดอกละห้าร้อยในวันนี้ก็ตาม
ปล. ในปี 1984 Alvin E. Roth ได้นำ Algorithm นี้ไปปรับปรุงระบบการจับคู่นักศึกษาแพทย์เรสสิเดนท์ของอเมริกา กับ โรงพยาบาล ซึ่งทำให้มีระดับความพึงพอใจของทั้งโรงพยาบาล และนักศึกษาแพทย์เพิ่มขึ้นมาก ผลจากการประยุกต์ใช้นี้ ทำให้ ในปี 2012 Alvin E. Roth และ Lloyd Shapley ได้รางวัลโนเบลร่วมกัน สำหรับผลงานที่โดดเด่นในด้านทฤษฎีการจัดสรรที่เสถียรและการออกแบบระบบตลาด ("the theory of stable allocations and the practice of market design")
http://en.wikipedia.org/wiki/Stable_marriage_problem
http://www.dcs.gla.ac.uk/research/algorithms/stable/
http://en.wikipedia.org/wiki/Lloyd_Shapley
http://en.wikipedia.org/wiki/List_of_Nobel_laureates_in_Economics
http://en.wikipedia.org/wiki/David_Gale
http://scimath.unl.edu/MIM/files/MATExamFiles/PremerJennie_Final_071511_LA.pdf
http://www.meconomics.net/content/456