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

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

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

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

## ที่มาของปัญหา
ในค.ศ. 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:  **จบการทำงาน**

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

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

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

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

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

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

## สรุป :
* ขั้นตอนวิธีของเกล-แชปลีย์ รับประกันว่าจะสามารถหาคู่สมรสที่มีเสถียรภาพได้เสมอ ๆ สำหรับฝ่ายชาย และฝ่ายหญิงที่มีจำนวนเท่ากัน
* เวลาและเนื้อที่ที่ใช้สำหรับขั้นตอนวิธีของเกล-แชปลีย์ เป็น Ο(n^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 คน
* ปัญหาที่เกี่ยวข้องกับปัญหาการแต่งงานที่มีเสถียรภาพ

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