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

ปัญหาการแต่งงานที่มีเสถียรภาพ ()  คือปัญหาในวิชาคณิตศาสตร์ เศรษฐศาสตร์ และวิทยาการคอมพิวเตอร์ ที่เกี่ยวข้องกับการจับคู่ที่เสถียรระหว่างสมาชิกของกลุ่มสองกลุ่มที่มีขนาดเท่าๆ กัน โดยที่สมาชิกแต่ละคนมีลำดับความต้องการคู่ของตัวเอง ความเสถียรในที่นี้หมายถึง ในผลของการจับคู่ จะต้องไม่มีสถานการณ์ที่มีสมาชิกคู่หนึ่งจากแต่ละกลุ่ม ต่างฝ่ายต่างต้องการที่จะจับคู่กันเองมากกว่าคู่ที่ได้รับในผลของการจับคู่นั้น

ปัญหานี้เรียกกันทั่วไปว่าปัญหาการแต่งงานที่มีเสถียรภาพ จากวิธีอธิบายปัญหาทางคณิตศาสตร์ที่ใช้ตัวอย่างเป็นการจับคู่แต่งงานระหว่างฝ่ายชายและฝ่ายหญิง ในบทความของเดวิด เกล และ ลอยด์ แชปลีย์

ปัญหาการจับคู่และอัลกอริทึมของเกลและแชปลีย์ ได้รับการนำมาใช้วางระบบจับคู่หลายอย่าง เช่น การรับนักเรียนในสถาบันการศึกษา การจับคู่ระหว่างนักศึกษาแพทย์กับโรงพยาบาล เป็นต้น

ที่มาของปัญหา 
ในค.ศ. 1962 เดวิด เกล และ ลอยด์ แชปลีย์ นักคณิตศาสตร์ และนักเศรษฐศาสตร์ชาวอเมริกัน ได้ทำการพิสูจน์ว่า  ทุกๆ ครั้งที่มีจำนวนของฝ่ายชาย และฝ่ายหญิงเท่ากัน จะสามารถแก้ปัญหาการแต่งงานที่มีเสถียรภาพได้เสมอ  โดยพวกเขาได้ทำการเสนอขั้นตอนวิธี ที่ชื่อว่า ขั้นตอนวิธีของเกล-แชปลีย์เพื่อแก้ปัญหาดังกล่าว

ผลเฉลยของปัญหาที่คิดค้นโดย เดวิด เกล และ ลอยด์ แชปลีย์ 
ขั้นตอนวิธีของเกล-แชพลีย์ จะใช้วงวนสำหรับการดำเนินการตามขั้นตอนวิธี  โดยที่ฝ่ายชายที่ยังไม่ได้ทำ"การหมั้น"กับฝ่ายหญิง ทำการเลือกฝ่ายหญิงที่ตนหมายปองมากที่สุด และเป็นคนที่เขายังไม่ได้เลือกมาก่อน โดยที่ฝ่ายหญิงแต่ละคนนั้นทำการพิจารณาเลือกฝ่ายชายที่ทำการเลือกเธอแต่ละคน  และบอกว่าผู้ใดที่เธอพึงพอใจมากที่สุด  โดยการ ตอบตกลง สำหรับคนที่เธอเลือก และ ปฏิเสธ กับทุกคนที่เธอไม่ได้เลือก  จากนั้นฝ่ายหญิงจะตอบรับ"การหมั้น"จากฝ่ายชายที่ตนเลือกไว้ชั่วคราว  ซึ่งจะสามารถคิดเป็นขั้นตอนวิธีได้ดังนี้

ในการวนซ้ำครั้งแรกนั้น จะประกอบไปด้วยขั้นตอนดังนี้
 ฝ่ายชายที่ยังไม่ได้ทำการหมั้นแต่ละคนเลือกผู้หญิงที่ตนหมายปองมากที่สุด
 ฝ่ายหญิงแต่ะละคน ตอบตกลง กับฝ่ายชายที่เลือกเธอ และเป็นคนที่เธอหมายปองมากที่สุดด้วยการหมั้นชั่วคราว และ ปฏิเสธ กับฝ่ายชายคนอื่น ๆ ที่เธอไม่ได้หมายปอง
ในการวนซ้ำรอบถัด ๆ มา จะประกอบไปด้วยขั้นตอนดังนี้
 ฝ่ายชายที่ยังไม่ได้ทำการหมั้นแต่ละคนเลือกผู้หญิงที่ตนหมายปองมากที่สุด  ที่ยังไม่ได้เลือกมาก่อนในรอบก่อนหน้านี้  โดยไม่ต้องคำนึงถึงว่าฝ่ายหญิงจะมีคู่หมั้นอยู่แล้ว
 ฝ่ายหญิงแต่ะละคน ตอบตกลง กับฝ่ายชายที่เลือกเธอ และเป็นคนที่ที่เธอหมายปองมากที่สุด และปฏิเสธคนที่เหลือ (รวมทั้งฝ่ายชายที่ตนทำการหมั้นไว้ชั่วคราวด้วย ถ้าเธอพึงพอใจฝ่ายชายที่เลือกเธอรอบนี้มากกว่าคู่หมั้นชั่วคราวของเธอ)

ขั้นตอนวิธี

ข้อมูลนำเข้า และผลลัพธ์ 
 ข้อมูลนำเข้า: เซตของผู้ชาย n คน และผู้หญิง n คน โดยที่แต่ละคนมิรายชื่อของบุคคลที่ตนหมายปอง 
 ผลลัพธ์ : เซตของคู่สมรสที่มีเสถียรภาพ ระหว่างฝ่ายชายและฝ่ายหญิง

รหัสเทียม(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:  จบการทำงาน

ตัวอย่างการอธิบายขั้นตอนวิธี 

ด้วยขั้นตอนวิธีนี้ จะสามารถรับประกันได้ว่า
 ทุกคนจะได้ทำการสมรส เนื่องจาก ฝ่ายชายแต่ละคนจะมีรายชื่อของฝ่ายหญิงที่ตนหมายปองครบทุกคน ดังนั้นจะไม่มีฝ่ายหญิงคนใดเลยที่ไม่ถูกเลือก  โดยฝ่ายชาย  จึงเป็นไปไม่ได้ที่จะทั้งฝ่ายหญิงและฝ่ายชายเป็นโสดพร้อมกันในที่สุด
 การสมรสมีเสถียรภาพ เนื่องจากการที่ฝ่ายหญิงมีสิทธิ์ที่จะเลือกฝ่ายชายที่ตนเองหมายปองด้วยเช่นกัน  สมมติเช่น ถ้าหากเกิดสถานการณ์ที่ฝ่ายหญิงมีคู่หมั้นชั่วคราวอยู่แล้ว  แต่ว่ามีฝ่ายชายที่หมายปองตนและตนนั้นก็พึงพอใจฝ่ายชายคนนั้นมากกว่าคู่หมั้นชั่วคราวของตน  ฝ่ายหญิงมีสิทธิ์ที่จะถอนหมั้น และทำการหมั้นกับฝ่ายชายคนใหม่ที่ตนพึงพอใจมากกว่าได้  ดังนั้นจึงรับประกันได้ว่าฝ่ายหญิงจะได้แต่งงานกับฝ่ายชายที่ตนพึงพอใจมากที่สุด จึงทำให้การสมรสมีเสภียรภาพ

วิเคราะห์ประสิทธิภาพการทำงาน 
ใช้พื้นที่ในการเก็บรายชื่อที่หมายปองของทั้งฝ่ายชายและฝ่ายหญิงเป็น

สมมติฐาน : 
 สมมติฐานที่ 1: ฝ่ายชายขอแต่งงานกับฝ่ายหญิงด้วยลำดับความพึงพอใจที่ลดลงจากมากไปน้อย
 สมมติฐานที่ 2: ฝ่ายหญิงที่ทำการหมั้นไปแล้วครั้งหนึ่ง จะไม่มีทางที่จะไร้คู่สมรสเพราะเธอจะไม่ถอนหมั้นก็ต่อเมื่อไม่เจอฝ่ายชายที่เลือกตนและตนพึงพอใจฝ่ายชายคนนั้นมากกว่าคู่หมั้นชั่วคราว

การแก้ปัญหาแบบถึก (Brute-force) : 
 เวลาที่ใช้ในการทำงานในกรณีแย่สุดที่ใช้การตรวจสอบรายชื่อทั้งหมด เป็น  (เวลาที่ใช้ในการตรวจสอบเสถียรภาพของการจับคู่) เท่ากับ Θ

การพิสูจน์ความถูกต้อง : 
1. ขั้นตอนวิธีนี้จะหยุดการทำงานสำหรับกรณีช้าที่สุดเป็น  จากการทำงานของวงวน
 พิสูจน์: จากรายชื่อที่หมายปองทั้งหมดของฝ่ายชายมีจำนวนรูปแบบที่เป็นไปได้  รูปแบบ ดังนั้น วงวนจะทำงานเป็นจำนวนครั้งมากที่สุดเท่ากับ  ครั้ง
2. ฝ่ายชายและฝ่ายหญิงทุกคนได้แต่งงานกันทุกคน
พิสูจน์โดยหาข้อขัดแย้ง
สมมติให้นายหนึ่ง ไม่มีคู่เลยแม้ว่าการทำงานของขั้นตอนวิธีจะจบลงแล้ว
จะพบ มีนางสาวเอ ไม่มีคู่เช่นกันแม้ว่าการทำงานของขั้นตอนวิธีจะจบลงแล้ว
จากสมมติฐานที่ 2 แสดงว่านางสาวเอ ไม่มีฝ่ายชายคนไหนเลยที่ปรารถนาจะแต่งงานด้วยเลย
แต่จากปัญหานี้ ฝ่ายชายทุกคนจะทำการเลือกฝ่ายหญิงทุกคน ตามลำดับความพึงพอใจ ดังนั้น นายหนึ่ง ทำการเลือกนางสาวเอ แล้ว
ดังนั้นจึงเป็นไปไม่ได้ที่จะมีฝ่ายชายหรือฝ่ายหญิงคนใด ไม่มีคู่
3. ไม่มีคู่สมรสใด ที่ขาดเสถียรภาพ
พิสูจน์โดยหาข้อขัดแย้ง
 สมมติให้ การจับคู่คู่หนึ่งระหว่างนายหนึ่ง กับนางสาวเอ ขาดเสถียรภาพ ในขณะที่พวกเขาเสนอรายชื่อของกันและกันในรายชื่อที่หมายปอง
 กรณีที่ 1:  นายหนึ่งไม่เคยขอแต่งงานกับนางสาวเอ 
 นายหนึ่งขอแต่งานกับนางสาวเอในที่สุด (จากการลดลำดับความพึงพอใจในรายชื่อที่หมายปองของฝ่ายชาย)
 การจับคู่ระหว่าง นายหนึ่ง กับ นางสาวเอ มีเสถียรภาพ
 กรณีที่ 2:  นายหนึ่งขอแต่งงานกับนางสาวเอไปแล้ว
 นางสาวเอ ปฏิเสธการขอแต่งงานของนายหนึ่ง (ทั้งกรณีที่นายหนึ่งไม่ดีกว่าคู่หมั้นชั่วคราวของนาวสาวเอ และกรณีที่เลือกนายหนึ่ง ไปแล้ว แต่เจอคนที่ดีกว่าในภายหลัง)
 แสดงว่านางสาวเอก็เสนอรายชื่อของนายหนึ่ง ในรายชื่อที่หมายปองไว้แล้ว เพียงแต่ต้องการคนที่ดีกว่าเท่านั้น
การจับคู่ระหว่างนายหนึ่ง กับ นางสาวเอ มีเสถียรภาพ

สรุป : 
 ขั้นตอนวิธีของเกล-แชปลีย์ รับประกันว่าจะสามารถหาคู่สมรสที่มีเสถียรภาพได้เสมอ ๆ สำหรับฝ่ายชาย และฝ่ายหญิงที่มีจำนวนเท่ากัน
 เวลาและเนื้อที่ที่ใช้สำหรับขั้นตอนวิธีของเกล-แชปลีย์ เป็น Ο

ตัวอย่างการประยุกต์ใช้งาน 
มีการนำขั้นตอนวิธีของ เกล-แชปลีย์ ไปประยุกต์ใช้อย่างกว้างขวาง ยกตัวอย่างเช่น การคัดเลือกนักเรียนชั้นประถมศึกษาเพื่อเข้าศึกษาต่อในโรงเรียนระดับมัธยมศึกษาของประเทศสิงคโปร์  การคัดเลือกนักเรียนชั้นมัธยมศึกษาเพื่อเข้าศึกษาต่อในมหาวิทยาลัยของประเทศอังกฤษ 
ตัวอย่างอื่น ๆ เช่น การเลือกโรงพยาบาลที่จะฝึกงานสำหรับนักศึกษาแพทย์  การเลือกเพื่อนร่วมห้องในหอพักนิสิตนักศึกษาในมหาวิทยาลัย  เป็นต้น

ปัญหาที่เกี่ยวข้อง 
 การจับคู่กราฟสองส่วน (Bipartite matching) กล่าวคือ ปัญหาการแต่งงานที่มีเสถียรภาพนี้เป็นตัวอย่างหนึ่งของการจับคู่กราฟสองส่วนโดยทั่วไปในเรื่องของทฤษฏีกราฟ
 ปัญหาการจัดตารางช่วงเวลา (Interval scheduling problem) เป็นตัวอย่างหนึ่งของขั้นตอนวิธีแบบละโมภ  
 การจัดตาราช่วงเวลาแบบถ่วงน้ำหนัก (Weighted interval scheduling) ซึ่งเป็นตัวอย่างหนึ่งของปัญหาการจัดตารางช่วงเวลา โดยให้มีหอประชุมขนาดใหญ่ และมีการจัดกิจกรรมต่าง ๆ ที่จะต้องจัดตารางเวลาในการใช้หอประชุมแห่งนี้  โดยกิจกรรมต่าง ๆ นั้นมีเวลาที่เริ่มของกิจกรม และเวลาที่จบของกิจกรรมนั้น ๆ ซึ่งปัญหานี้เกี่ยวข้องกันโดยที่เราจะต้องจัดการตารางเวลาให้มีกิจกรรมจัดขึ้นมากที่สุดในช่วงเวลาที่กำหนด 
 เซตอิสระ (Independent Set) โดยให้มีกราฟ G ที่มีปมเป็น V และเส้นเชื่อมเป็น E โดยเราจะสามารถบอกได้ว่า เซตของปม S จะเป็นเซตอิสระ ถ้าไม่มีสองปอมใด ๆ ที่มีเส้นเชื่อมซึ่งกันและกัน ซึ่งการหาเซตอิสระที่ใหญ่ที่สุดในกราฟ G จะเป็นส่วนหนึ่งของปัญหาเอ็นพีบริบูรณ์ (NP-Complete)
 การแข่งขันหาทำเลที่ตั้งสิ่งอำนวยความสะดวก (Competitive Facility Location) เป็นเกมที่มีผู้เล่นตั้งแต่ 2 คนขึ้นไป ทำการเดินและเลือกที่ตั้งที่ทำให้ตนมีคะแนนมากที่สุด โดยกลยุทธ์ที่จะสามารถทำให้ชนะในเกมนี้คือการเลือกจุดเริ่มต้นของที่ตั้ง และการตัดสินใจในการเลือกเดินของผู้เล่นในตาก่อนหน้านี้ ซึ่งเกมนี้เป็นตัวอย่างหนึ่งของปัญหาพีเสปซบริบูรณ์

อ้างอิง

แหล่งข้อมูลอื่น 
 เอกสารประกอบการสอนของ SMP
 โค้ดของโรเซตต้า
 การออกแบบขั้นตอนวิธี 
 บทนำของปัญหาการแต่งงานที่มีเสถียรภาพ 
 โปรแกรมแสดงการแก้ปัญหาการแต่งงานที่มีเสถียรภาพ
 โปรแกรมจำลองสถานการณ์แสดงการแก้ปัญหาการแต่งงานที่มีเสถียรภาพแบบมีฝ่ายชาย 4 คน และฝ่ายหญิง 4 คน
 โปรแกรมจำลองสถานการณ์แสดงการแก้ปัญหาการแต่งงานที่มีเสถียรภาพแบบมีฝ่ายชาย 15 คน และฝ่ายหญิง 15 คน
 ปัญหาที่เกี่ยวข้องกับปัญหาการแต่งงานที่มีเสถียรภาพ

ทฤษฎีเกม
ปัญหาทางคณิตศาสตร์