อัลกอริทึม Gale-Shapley
- ผู้เสนอ
- David Gale, Lloyd Shapley
- ปี
- 1962
- ประเภท
- algorithm
- กลุ่มวิธี
- Game-theoretic
ข้อความนี้เป็นการแปลด้วยเครื่องและยังไม่ได้รับการตรวจทาน อ่านต้นฉบับภาษาอังกฤษ
ใช้ทำอะไร?
อัลกอริทึม Gale-Shapley ใช้แก้ปัญหาการจับคู่ที่เสถียร (stable marriage problem): วิธีการจับคู่ระหว่างสองกลุ่ม (เช่น แพทย์ประจำบ้านกับโรงพยาบาล, นักเรียนกับโรงเรียน) โดยที่ไม่มีคู่ใดคู่หนึ่งชอบกันและกันมากกว่าคู่ที่ตนเองได้รับมอบหมาย อัลกอริทึมนี้ถูกนำเสนอโดย David Gale และ Lloyd Shapley ในปี 1962 โดยรับประกันการจับคู่ที่เสถียรในเวลาพหุนาม (polynomial time) ผ่านกระบวนการยอมรับแบบเลื่อนเวลา (deferred acceptance) ซึ่งฝ่ายหนึ่งเสนอตัวตามลำดับ และอีกฝ่ายหนึ่งตอบสนอง โดยปรับปรุงการเลือกเมื่อมีตัวเลือกที่ดีกว่าเข้ามา
แนวคิดเบื้องหลังวิธีการ
ลองนึกภาพการจับคู่แพทย์กับโรงพยาบาล อัลกอริทึมทำงานเหมือนเกมเก้าอี้ดนตรี: แพทย์แต่ละคนเสนอตัวกับโรงพยาบาลที่ตนเองชอบมากที่สุด; โรงพยาบาลแต่ละแห่งยอมรับแพทย์ที่ดีที่สุดที่มีอยู่ชั่วคราว เมื่อโรงพยาบาลได้รับข้อเสนอที่ดีกว่า พวกเขาจะปรับปรุงการเลือก ซึ่งอาจส่งผลให้ปฏิเสธการยอมรับก่อนหน้านี้ แพทย์ที่ถูกปฏิเสธจะเสนอตัวกับโรงพยาบาลที่ชอบลำดับถัดไป กระบวนการนี้ดำเนินต่อไปจนกว่าจะไม่มีแพทย์คนใดต้องการเสนอตัวอีกต่อไป และไม่มีโรงพยาบาลใดต้องการแลกเปลี่ยนคู่ที่ตนเองมีอยู่ ผลลัพธ์ที่ได้คือความเสถียร: ไม่มีคู่แพทย์-โรงพยาบาลใดที่จะชอบที่จะจับคู่กันเองมากกว่าคู่ที่ได้รับมอบหมาย
ประวัติศาสตร์
David Gale และ Lloyd Shapley ได้ตีพิมพ์วิธีแก้ปัญหาการจับคู่ที่เสถียรในปี 1962 โดยพิสูจน์ว่าการจับคู่ที่เสถียรมีอยู่เสมอสำหรับตลาดสองด้าน อัลกอริทึมของพวกเขาได้ก่อให้เกิดวรรณกรรมจำนวนมากเกี่ยวกับทฤษฎีการจับคู่กับการประยุกต์ใช้ในด้านการแพทย์ การศึกษา และตลาดแรงงาน ในปี 2012 Alvin Roth ได้รับรางวัลโนเบลสาขาเศรษฐศาสตร์จากการทำงานเชิงทดลองและเชิงทฤษฎีในการประยุกต์ใช้ทฤษฎีการจับคู่กับการออกแบบตลาดจริง ซึ่งเป็นการยืนยันความสำคัญในทางปฏิบัติของกรอบงาน Gale-Shapley
ควรใช้เมื่อใด
นำอัลกอริทึม Gale-Shapley ไปใช้เมื่อทำการจับคู่ในตลาดสองด้าน (two-sided markets) ที่ความเสถียรมีความสำคัญ: การจัดสรรแพทย์ประจำบ้าน, การจัดสรรนักเรียนเข้าโรงเรียน, การแลกเปลี่ยนไต, การจับคู่ในตลาดแรงงาน, หรือตลาดนัดพบออนไลน์ ใช้เมื่อมีความเสี่ยงที่การจับคู่จะไม่เสถียร (blocking pairs) ซึ่งอาจทำให้การจับคู่ล่มสลายหลังจากการมอบหมาย อัลกอริทึมนี้เหมาะสมอย่างยิ่งเมื่อฝ่ายหนึ่งสามารถดำเนินการก่อนโดยมีข้อได้เปรียบเชิงกลยุทธ์
ข้อจำกัดและข้อควรพิจารณา
- ไม่ใช่ Pareto optimal: การจับคู่อาจไม่สามารถเพิ่มสวัสดิการรวมได้; อาจมี blocking pairs ที่ทุกฝ่ายจะได้รับประโยชน์จากการแลกเปลี่ยนคู่
- ความอ่อนแอเชิงกลยุทธ์: ฝ่ายที่เสนอตัวสามารถได้รับประโยชน์จากการแสดงความชอบที่ไม่ถูกต้อง ในขณะที่ฝ่ายที่ตอบสนองจะแสดงความชอบอย่างตรงไปตรงมา
- ความไม่สมมาตร: ผลลัพธ์ขึ้นอยู่กับว่าฝ่ายใดเสนอตัวก่อนเป็นอย่างมาก
- ไม่สามารถจัดการกับข้อจำกัดได้: ยากที่จะรวมความชอบที่ซับซ้อน (เช่น คู่รัก, ความชอบตามภูมิภาค) โดยไม่มีการปรับเปลี่ยนอัลกอริทึม
เงื่อนไขจากแหล่งที่มาไม่สามารถใช้แทนการทบทวนทางวิทยาศาสตร์ที่เป็นอิสระหรือการตรวจสอบโดยเอนจินวิเคราะห์ได้
จุดแข็ง
- ความเสถียรที่รับประกัน: ไม่มี blocking pairs ในการจับคู่สุดท้าย
- เวลาพหุนาม: ความซับซ้อน O(n^2) ทำให้มีประสิทธิภาพสำหรับประชากรจำนวนมาก
- การนำไปใช้ที่ง่าย: ดำเนินการได้ง่ายในทางปฏิบัติด้วยการรวบรวมความชอบที่โปร่งใส
- แรงจูงใจเชิงกลยุทธ์: ฝ่ายที่เสนอตัวมีข้อได้เปรียบเชิงกลยุทธ์ โดยชอบการเสนอตัวในช่วงต้นมากกว่าช่วงหลัง
- การประยุกต์ใช้ได้ทั่วไป: ใช้ได้กับโปรไฟล์ความชอบใดๆ โดยไม่ต้องสมมติเรื่อง convexity หรือ transitivity
การประยุกต์ใช้
- การจัดสรรแพทย์ประจำบ้าน: การจับคู่ผู้สำเร็จการศึกษาจากโรงเรียนแพทย์กับโปรแกรมการฝึกอบรมแพทย์ประจำบ้านผ่าน NRMP
- การเลือกโรงเรียน: การจัดสรรนักเรียนเข้าโรงเรียนรัฐบาลตามความชอบและข้อจำกัดด้านความจุ
- การแลกเปลี่ยนไต: การจับคู่ผู้บริจาคอวัยวะและผู้รับเพื่อเพิ่มการปลูกถ่ายที่เข้ากันได้
- การจับคู่ในตลาดงาน: การเชื่อมโยงผู้หางานกับนายจ้างในตลาดแรงงานสองด้าน
- การนัดพบออนไลน์: การจับคู่ผู้ใช้ในแพลตฟอร์มนัดพบเพื่อเพิ่มความเสถียรของการจับคู่และความพึงพอใจของผู้ใช้
วิธีการทำงาน
วิธีการทำงาน
สร้างรายการความชอบ (preference lists) สำหรับบุคคลทั้งหมดในทั้งสองกลุ่ม โดยแสดงการจัดอันดับของอีกฝ่าย
ในแต่ละรอบ บุคคลที่ยังไม่ถูกจับคู่ในฝ่ายที่เสนอตัว จะเสนอตัวกับบุคคลที่อยู่ในอันดับสูงสุดของอีกฝ่ายที่ตนเองยังไม่ได้เสนอตัวไป
บุคคลในฝ่ายที่รับข้อเสนอจะยอมรับข้อเสนอชั่วคราวหากตนเองยังไม่ถูกจับคู่ หรือหากผู้เสนอตัวมีอันดับสูงกว่าคู่ปัจจุบันของตน ซึ่งในกรณีนี้จะยกเลิกการหมั้นหมายก่อนหน้านี้
อัลกอริทึมจะหยุดทำงานเมื่อทุกคนถูกจับคู่และไม่มีการเสนอตัวเพิ่มเติมเกิดขึ้น ซึ่งจะให้ผลลัพธ์การจับคู่ที่เสถียร
ข้อผิดพลาดที่พบบ่อย
- การสมมติว่าความเสถียรเพียงอย่างเดียวเพียงพอสำหรับความเป็นธรรมหรือสวัสดิการ; การจับคู่ที่เสถียรอาจเอนเอียงอย่างมากไปทางฝ่ายใดฝ่ายหนึ่ง
- การสับสนระหว่างความเสถียรกับความเป็นเลิศ (optimality); การจับคู่ที่เสถียรไม่จำเป็นต้องเป็นการเพิ่มสวัสดิการสูงสุด
- การมองข้ามข้อได้เปรียบเชิงกลยุทธ์ของฝ่ายที่เสนอตัว: สมาชิกของฝ่ายที่เสนอตัวมักจะจับคู่กับคู่ที่มีอันดับสูงกว่า
- การลืมว่าอัลกอริทึมสมมติว่ามีรายการความชอบที่สมบูรณ์; ความชอบที่ไม่สมบูรณ์ต้องมีการปรับเปลี่ยน
คำถามที่พบบ่อย
เหตุใดความเสถียรจึงมีความสำคัญในการจับคู่?
หากปราศจากความเสถียร คู่ที่ถูกจับคู่อาจค้นพบในภายหลังว่าพวกเขาชอบกันและกันมากกว่าคู่ที่ได้รับมอบหมาย ซึ่งสร้างแรงจูงใจในการยกเลิกการจับคู่ การจับคู่ที่เสถียรจะป้องกัน blocking pairs ดังกล่าว ทำให้มั่นใจได้ว่าการจับคู่จะคงอยู่โดยไม่ต้องมีการเจรจาต่อรองใหม่
อัลกอริทึม Gale-Shapley ให้ผลลัพธ์การจับคู่แบบเดียวกันเสมอหรือไม่?
ไม่ การมีรายการความชอบที่แตกต่างกันหรือลำดับการเสนอตัวที่แตกต่างกันสามารถให้ผลลัพธ์การจับคู่ที่เสถียรที่แตกต่างกันได้ อย่างไรก็ตาม จะมี 'man-optimal' stable matching เสมอ (ดีที่สุดสำหรับผู้เสนอตัวทุกคน) และ 'woman-optimal' stable matching (ดีที่สุดสำหรับผู้ตอบสนองทุกคน)
อัลกอริทึม Gale-Shapley จัดการกับความชอบต่อกลุ่ม (เช่น คู่รัก) ได้อย่างไร?
อัลกอริทึมมาตรฐานไม่ได้จัดการกับคู่รักหรือข้อจำกัดอื่นๆ โดยตรง มีส่วนขยายเช่นอัลกอริทึมสำหรับคู่รัก (couples algorithm) แต่มีความซับซ้อนมากกว่าและอาจไม่รับประกันความเสถียรสำหรับโปรไฟล์ความชอบทั้งหมด
วิธีการที่เกี่ยวข้อง
แหล่งอ้างอิง
Gale, D., & Shapley, L. S. (1962). College admissions and the stability of marriage. The American Mathematical Monthly, 69(1), 9-15.
เปิดเอกสารอ้างอิง DOIคัดลอกแล้วRoth, A. E. (1984). The economics of matching: Stability and incentives. Mathematics of Operations Research, 7(4), 617-628.
เปิดเอกสารอ้างอิง DOIคัดลอกแล้ว