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

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

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

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

ที่มาของปัญหา

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

ผลเฉลยของปัญหาที่คิดค้นโดย เดวิด เกล และ ลอยด์ แชปลีย์

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

ในการวนซ้ำครั้งแรกนั้น จะประกอบไปด้วยขั้นตอนดังนี้

1. ฝ่ายชายที่ยังไม่ได้ทำการหมั้นแต่ละคนเลือกผู้หญิงที่ตนหมายปองมากที่สุด
2. ฝ่ายหญิงแต่ะละคน ตอบตกลง กับฝ่ายชายที่เลือกเธอ และเป็นคนที่เธอหมายปองมากที่สุดด้วยการหมั้นชั่วคราว และ ปฏิเสธ กับฝ่ายชายคนอื่น ๆ ที่เธอไม่ได้หมายปอง

ในการวนซ้ำรอบถัด ๆ มา จะประกอบไปด้วยขั้นตอนดังนี้

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

ขั้นตอนวิธี

ข้อมูลนำเข้า และผลลัพธ์

• ข้อมูลนำเข้า: เซตของผู้ชาย 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 หญิงอันดับ3 หญิงอันดับ4 หนึ่ง เอ ซี ดี บี สอง บี เอ ซี ดี สาม บี ดี ซี เอ สี่ ซี เอ บี ดี หญิง ชายอันดับ1 ชายอันดับ2 ชายอันดับ3 ชายอันดับ4 เอ หนึ่ง สี่ สอง สาม บี สาม หนี่ง สอง สี่ ซี สอง สี่ หนี่ง สาม ดี หนึ่ง สี่ สาม สอง

รอบที่ 1 (รอบแรก) รายชื่อที่หมายปองของฝ่ายชาย รายชื่อที่หมายปองของฝ่ายหญิง ชาย หญิงอันดับ1 หญิงอันดับ2 หญิงอันดับ3 หญิงอันดับ4 หนึ่ง เอ(เลือก) ซี ดี บี สอง บี(เลือก) เอ ซี ดี สาม บี(เลือก) ดี ซี เอ สี่ ซี(เลือก) เอ บี ดี หญิง ชายอันดับ1 ชายอันดับ2 ชายอันดับ3 ชายอันดับ4 เอ หนึ่ง(หมั้น) สี่ สอง สาม บี สาม(หมั้น) หนี่ง สอง สี่ ซี สอง สี่(หมั้น) หนี่ง สาม ดี หนึ่ง สี่ สาม สอง ตารางแสดงความหมายปองรอบปัจจุบัน คำอธิบาย เอ หนึ่ง --- --- --- บี สอง สาม --- --- ซี สี่ --- --- --- ดี --- --- --- --- "หนึ่ง" ขอ "เอ" แต่งงาน และ"เอ"ก็ตอบรับ"หนึ่ง"ด้วยการหมั้นชั่วคราว "สอง" ขอ "บี" แต่งงาน แต่ "บี"ปฏิเสธ"สอง"เนื่องจาก"สาม"ก็ขอ"บี"แต่งงานด้วยเช่นกัน และ"บี"หมายปอง"สาม" มากกว่า "สี่"ขอ"ซี"แต่งงาน และ"ซี"ก็ตอบรับ"สี่"ด้วยการหมั้นชั่วคราว "ดี"ยังไม่มีใครหมายปองในรอบที่ 1

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

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

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

รอบที่ 5 รายชื่อที่หมายปองของฝ่ายชาย รายชื่อที่หมายปองของฝ่ายหญิง ชาย หญิงอันดับ1 หญิงอันดับ2 หญิงอันดับ3 หญิงอันดับ4 หนึ่ง เอ ซี ดี บี สอง บี เอ ซี ดี สาม บี ดี ซี เอ สี่ ซี เอ ดี บี หญิง ชายอันดับ1 ชายอันดับ2 ชายอันดับ3 ชายอันดับ4 เอ หนึ่ง(หมั้น) สี่ สอง สาม บี สาม(หมั้น) หนี่ง สอง สี่ ซี สอง(หมั้น) สี่ หนี่ง สาม ดี หนึ่ง สี่(หมั้น) สาม สอง ตารางแสดงความหมายปองรอบปัจจุบัน คำอธิบาย เอ --- --- --- --- บี --- --- --- --- ซี --- --- --- --- ดี สี่ --- --- --- "สี่" เป็นบุคคลเดียวที่ยังไม่มีคู่หมั้นชั่วคราว "สี่" ทำการเลือกคู่ในรอบที่ 5 โดยเลือก "ดี" "ดี" ตอบรับการขอของ "สี่" ด้วยการหมั้นชั่วคราว

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

ด้วยขั้นตอนวิธีนี้ จะสามารถรับประกันได้ว่า

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

วิเคราะห์ประสิทธิภาพการทำงาน

ใช้พื้นที่ในการเก็บรายชื่อที่หมายปองของทั้งฝ่ายชายและฝ่ายหญิงเป็น ${\displaystyle 2n^{2}}$ 

สมมติฐาน :

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

การแก้ปัญหาแบบถึก (Brute-force) :

• เวลาที่ใช้ในการทำงานในกรณีแย่สุดที่ใช้การตรวจสอบรายชื่อทั้งหมด เป็น ${\displaystyle n!x}$  (เวลาที่ใช้ในการตรวจสอบเสถียรภาพของการจับคู่) เท่ากับ Θ${\displaystyle (n!n^{2})}$ 

การพิสูจน์ความถูกต้อง :

1. ขั้นตอนวิธีนี้จะหยุดการทำงานสำหรับกรณีช้าที่สุดเป็น ${\displaystyle n^{2}}$  จากการทำงานของวงวน

• พิสูจน์: จากรายชื่อที่หมายปองทั้งหมดของฝ่ายชายมีจำนวนรูปแบบที่เป็นไปได้ ${\displaystyle n^{2}}$  รูปแบบ ดังนั้น วงวนจะทำงานเป็นจำนวนครั้งมากที่สุดเท่ากับ ${\displaystyle n^{2}}$  ครั้ง

2. ฝ่ายชายและฝ่ายหญิงทุกคนได้แต่งงานกันทุกคน

• พิสูจน์โดยหาข้อขัดแย้ง

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

3. ไม่มีคู่สมรสใด ที่ขาดเสถียรภาพ

• พิสูจน์โดยหาข้อขัดแย้ง

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

สรุป :

• ขั้นตอนวิธีของเกล-แชปลีย์ รับประกันว่าจะสามารถหาคู่สมรสที่มีเสถียรภาพได้เสมอ ๆ สำหรับฝ่ายชาย และฝ่ายหญิงที่มีจำนวนเท่ากัน
• เวลาและเนื้อที่ที่ใช้สำหรับขั้นตอนวิธีของเกล-แชปลีย์ เป็น Ο${\displaystyle (n^{2})}$ 

ตัวอย่างการประยุกต์ใช้งาน

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

ปัญหาที่เกี่ยวข้อง

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

อ้างอิง

1. Harry Mairson: "The Stable Marriage Problem", The Brandeis Review 12, 1992 (online).
2. Chung-Piaw Teo,Jay Sethuraman, Wee-Peng Tan,Gale-Shapley Stable Marriage Problem Revisited: Strategic Issues and Applications, Management science, 2001 ([1]).
3. D.G. McVITIEɫ̩ and L. B. WILSON, The Application of the Stable Marriage Assignment to University Admissions, Operational Research Quarterly(1970-1977), 1970 ([2]).

แหล่งข้อมูลอื่น

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