ปัญหาการแต่งงานที่มีเสถียรภาพ

ปัญหาการแต่งงานที่มีเสถียรภาพ  คือปัญหาในวิชาคณิตศาสตร์ เศรษฐศาสตร์ และวิทยาการคอมพิวเตอร์ ที่เกี่ยวข้องกับการจับคู่ที่เสถียรระหว่างสมาชิกของกลุ่มสองกลุ่มที่มีขนาดเท่าๆ กัน โดยที่สมาชิกแต่ละคนมีลำดับความต้องการคู่ของตัวเอง ความเสถียรในที่นี้หมายถึง ในผลของการจับคู่ จะต้องไม่มีสถานการณ์ที่มีสมาชิกคู่หนึ่งจากแต่ละกลุ่ม ต่างฝ่ายต่างต้องการที่จะจับคู่กันเองมากกว่าคู่ที่ได้รับในผลของการจับคู่นั้น
ปัญหานี้เรียกกันทั่วไปว่าปัญหาการแต่งงานที่มีเสถียรภาพ จากวิธีอธิบายปัญหาทางคณิตศาสตร์ที่ใช้ตัวอย่างเป็นการจับคู่แต่งงานระหว่างฝ่ายชายและฝ่ายหญิง ในบทความของเดวิด เกล และ ลอยด์ แชปลีย์
ปัญหาการจับคู่และอัลกอริทึมของเกลและแชปลีย์ ได้รับการนำมาใช้วางระบบจับคู่หลายอย่าง เช่น การรับนักเรียนในสถาบันการศึกษา การจับคู่ระหว่างนักศึกษาแพทย์กับโรงพยาบาล เป็นต้น
ที่มาของปัญหา.
ในค.ศ. 1962 เดวิด เกล และ ลอยด์ แชปลีย์ นักคณิตศาสตร์ และนักเศรษฐศาสตร์ชาวอเมริกัน ได้ทำการพิสูจน์ว่า ทุกๆ ครั้งที่มีจำนวนของฝ่ายชาย และฝ่ายหญิงเท่ากัน จะสามารถแก้ปัญหาการแต่งงานที่มีเสถียรภาพได้เสมอ โดยพวกเขาได้ทำการเสนอขั้นตอนวิธี ที่ชื่อว่า ขั้นตอนวิธีของเกล-แชปลีย์เพื่อแก้ปัญหาดังกล่าว 
ผลเฉลยของปัญหาที่คิดค้นโดย เดวิด เกล และ ลอยด์ แชปลีย์.
ขั้นตอนวิธีของเกล-แชพลีย์ จะใช้วงวนสำหรับการดำเนินการตามขั้นตอนวิธี โดยที่ฝ่ายชายที่ยังไม่ได้ทำ"การหมั้น"กับฝ่ายหญิง ทำการเลือกฝ่ายหญิงที่ตนหมายปองมากที่สุด และเป็นคนที่เขายังไม่ได้เลือกมาก่อน โดยที่ฝ่ายหญิงแต่ละคนนั้นทำการพิจารณาเลือกฝ่ายชายที่ทำการเลือกเธอแต่ละคน และบอกว่าผู้ใดที่เธอพึงพอใจมากที่สุด โดยการ "ตอบตกลง" สำหรับคนที่เธอเลือก และ "ปฏิเสธ" กับทุกคนที่เธอไม่ได้เลือก จากนั้นฝ่ายหญิงจะตอบรับ"การหมั้น"จากฝ่ายชายที่ตนเลือกไว้ชั่วคราว ซึ่งจะสามารถคิดเป็นขั้นตอนวิธีได้ดังนี้
ในการวนซ้ำครั้งแรกนั้น จะประกอบไปด้วยขั้นตอนดังนี้
ในการวนซ้ำรอบถัด ๆ มา จะประกอบไปด้วยขั้นตอนดังนี้
ขั้นตอนวิธี.
รหัสเทียม(Pseudo Code).
 การทำงาน การจับคู่ที่มีเสถียรภาพ
 1: เริ่มต้นให้ ฝ่ายชายทุกคน และฝ่ายหญิงทุกคนเป็นโสด
 2: ขณะที่ มีฝ่ายชายที่ยังเป็นโสด 
 3: เลือกฝ่ายชายที่ยังไม่ได้จับคู่เป็น M และฝ่ายหญิงคนแรกที่อยู่ในรายการของเขาเป็น W
 4: ลบ W จากรายการของเขา เพื่อไม่ให้ถูกเลือกอีกเป็นครั้งที่สอง
 5: ถ้า W หมั้นอยู่แล้ว ให้ทำ
 6: ถ้า W หมายปอง M มากกว่าคู่หมั้นชั่วคราวของตน P ให้ทำ
 7: ตั้งค่าให้ W ถอนหมั้นกับ P และ P เป็นโสด
 8: ตั้งค่าให้ M หมั้นชั่วคราวกับ W 
 9: มิเช่นนั้น ให้ทำ
 10: M ยังคงเป็นโสดเช่นเดิม เนื่องจาก W พอใจที่จะอยู่กับ P มากกว่า
 11: จบการทำงานของเงื่อนไขรอง
 12: มิเช่นนั้น ให้ทำ
 13: ตั้งค่าให้ W หมั้นชั่วคราวกับ M 
 14: จบการทำงานของเงื่อนไขหลัก
 15: จบการทำงานของวงวน
 16: จบการทำงาน
ตัวอย่างการอธิบายขั้นตอนวิธี.
ด้วยขั้นตอนวิธีนี้ จะสามารถรับประกันได้ว่า
วิเคราะห์ประสิทธิภาพการทำงาน.
ใช้พื้นที่ในการเก็บรายชื่อที่หมายปองของทั้งฝ่ายชายและฝ่ายหญิงเป็น <math> 2n^2 </math>
การพิสูจน์ความถูกต้อง :.
1. ขั้นตอนวิธีนี้จะหยุดการทำงานสำหรับกรณีช้าที่สุดเป็น <math> n^2 </math> จากการทำงานของวงวน
2. ฝ่ายชายและฝ่ายหญิงทุกคนได้แต่งงานกันทุกคน
*พิสูจน์โดยหาข้อขัดแย้ง
*สมมติให้นายหนึ่ง ไม่มีคู่เลยแม้ว่าการทำงานของขั้นตอนวิธีจะจบลงแล้ว
**จะพบ มีนางสาวเอ ไม่มีคู่เช่นกันแม้ว่าการทำงานของขั้นตอนวิธีจะจบลงแล้ว
**จากสมมติฐานที่ 2 แสดงว่านางสาวเอ ไม่มีฝ่ายชายคนไหนเลยที่ปรารถนาจะแต่งงานด้วยเลย
**แต่จากปัญหานี้ ฝ่ายชายทุกคนจะทำการเลือกฝ่ายหญิงทุกคน ตามลำดับความพึงพอใจ ดังนั้น นายหนึ่ง ทำการเลือกนางสาวเอ แล้ว
**ดังนั้นจึงเป็นไปไม่ได้ที่จะมีฝ่ายชายหรือฝ่ายหญิงคนใด ไม่มีคู่
3. ไม่มีคู่สมรสใด ที่ขาดเสถียรภาพ
*พิสูจน์โดยหาข้อขัดแย้ง
* สมมติให้ การจับคู่คู่หนึ่งระหว่างนายหนึ่ง กับนางสาวเอ ขาดเสถียรภาพ ในขณะที่พวกเขาเสนอรายชื่อของกันและกันในรายชื่อที่หมายปอง
** กรณีที่ 1: นายหนึ่งไม่เคยขอแต่งงานกับนางสาวเอ 
*** นายหนึ่งขอแต่งานกับนางสาวเอในที่สุด (จากการลดลำดับความพึงพอใจในรายชื่อที่หมายปองของฝ่ายชาย)
*** การจับคู่ระหว่าง นายหนึ่ง กับ นางสาวเอ มีเสถียรภาพ
** กรณีที่ 2: นายหนึ่งขอแต่งงานกับนางสาวเอไปแล้ว
*** นางสาวเอ ปฏิเสธการขอแต่งงานของนายหนึ่ง (ทั้งกรณีที่นายหนึ่งไม่ดีกว่าคู่หมั้นชั่วคราวของนาวสาวเอ และกรณีที่เลือกนายหนึ่ง ไปแล้ว แต่เจอคนที่ดีกว่าในภายหลัง)
*** แสดงว่านางสาวเอก็เสนอรายชื่อของนายหนึ่ง ในรายชื่อที่หมายปองไว้แล้ว เพียงแต่ต้องการคนที่ดีกว่าเท่านั้น
***การจับคู่ระหว่างนายหนึ่ง กับ นางสาวเอ มีเสถียรภาพ
ตัวอย่างการประยุกต์ใช้งาน.
มีการนำขั้นตอนวิธีของ เกล-แชปลีย์ ไปประยุกต์ใช้อย่างกว้างขวาง ยกตัวอย่างเช่น การคัดเลือกนักเรียนชั้นประถมศึกษาเพื่อเข้าศึกษาต่อในโรงเรียนระดับมัธยมศึกษาของประเทศสิงคโปร์ การคัดเลือกนักเรียนชั้นมัธยมศึกษาเพื่อเข้าศึกษาต่อในมหาวิทยาลัยของประเทศอังกฤษ 
ตัวอย่างอื่น ๆ เช่น การเลือกโรงพยาบาลที่จะฝึกงานสำหรับนักศึกษาแพทย์ การเลือกเพื่อนร่วมห้องในหอพักนิสิตนักศึกษาในมหาวิทยาลัย เป็นต้น