Skip to content
กลับไปยังผลการค้นหา

อัลกอริทึม 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
  • การเลือกโรงเรียน: การจัดสรรนักเรียนเข้าโรงเรียนรัฐบาลตามความชอบและข้อจำกัดด้านความจุ
  • การแลกเปลี่ยนไต: การจับคู่ผู้บริจาคอวัยวะและผู้รับเพื่อเพิ่มการปลูกถ่ายที่เข้ากันได้
  • การจับคู่ในตลาดงาน: การเชื่อมโยงผู้หางานกับนายจ้างในตลาดแรงงานสองด้าน
  • การนัดพบออนไลน์: การจับคู่ผู้ใช้ในแพลตฟอร์มนัดพบเพื่อเพิ่มความเสถียรของการจับคู่และความพึงพอใจของผู้ใช้

วิธีการทำงาน

วิธีการทำงาน

1

สร้างรายการความชอบ (preference lists) สำหรับบุคคลทั้งหมดในทั้งสองกลุ่ม โดยแสดงการจัดอันดับของอีกฝ่าย

2

ในแต่ละรอบ บุคคลที่ยังไม่ถูกจับคู่ในฝ่ายที่เสนอตัว จะเสนอตัวกับบุคคลที่อยู่ในอันดับสูงสุดของอีกฝ่ายที่ตนเองยังไม่ได้เสนอตัวไป

3

บุคคลในฝ่ายที่รับข้อเสนอจะยอมรับข้อเสนอชั่วคราวหากตนเองยังไม่ถูกจับคู่ หรือหากผู้เสนอตัวมีอันดับสูงกว่าคู่ปัจจุบันของตน ซึ่งในกรณีนี้จะยกเลิกการหมั้นหมายก่อนหน้านี้

4

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

ข้อผิดพลาดที่พบบ่อย

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

คำถามที่พบบ่อย

เหตุใดความเสถียรจึงมีความสำคัญในการจับคู่?

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

อัลกอริทึม Gale-Shapley ให้ผลลัพธ์การจับคู่แบบเดียวกันเสมอหรือไม่?

ไม่ การมีรายการความชอบที่แตกต่างกันหรือลำดับการเสนอตัวที่แตกต่างกันสามารถให้ผลลัพธ์การจับคู่ที่เสถียรที่แตกต่างกันได้ อย่างไรก็ตาม จะมี 'man-optimal' stable matching เสมอ (ดีที่สุดสำหรับผู้เสนอตัวทุกคน) และ 'woman-optimal' stable matching (ดีที่สุดสำหรับผู้ตอบสนองทุกคน)

อัลกอริทึม Gale-Shapley จัดการกับความชอบต่อกลุ่ม (เช่น คู่รัก) ได้อย่างไร?

อัลกอริทึมมาตรฐานไม่ได้จัดการกับคู่รักหรือข้อจำกัดอื่นๆ โดยตรง มีส่วนขยายเช่นอัลกอริทึมสำหรับคู่รัก (couples algorithm) แต่มีความซับซ้อนมากกว่าและอาจไม่รับประกันความเสถียรสำหรับโปรไฟล์ความชอบทั้งหมด

วิธีการที่เกี่ยวข้อง

แหล่งอ้างอิง

  1. Gale, D., & Shapley, L. S. (1962). College admissions and the stability of marriage. The American Mathematical Monthly, 69(1), 9-15.

    เปิดเอกสารอ้างอิง DOI
    คัดลอกแล้ว
  2. Roth, A. E. (1984). The economics of matching: Stability and incentives. Mathematics of Operations Research, 7(4), 617-628.

    เปิดเอกสารอ้างอิง DOI
    คัดลอกแล้ว