ตัวแก้ปัญหาการจับคู่แต่งงานที่เสถียร

เกี่ยวกับ ตัวแก้ปัญหาการจับคู่แต่งงานที่เสถียร

ตัวแก้ปัญหาการจับคู่แต่งงานที่เสถียร เป็นเครื่องมือแบบโต้ตอบที่ใช้ อัลกอริทึม Gale-Shapley (deferred-acceptance) ซึ่งเป็นอัลกอริทึมการจับคู่ปี 1962 ที่ David Gale และ Lloyd Shapley ได้พิสูจน์แล้วว่าสามารถสร้างการจับคู่ที่เสถียรระหว่างกลุ่มสองกลุ่มที่มีขนาดเท่ากันได้เสมอ เมื่อสมาชิกแต่ละคนระบุลำดับความชอบของอีกฝ่ายไว้อย่างครบถ้วน เครื่องมือนี้จะรับรายการความชอบของคุณ รันอัลกอริทึมทีละขั้นตอน และแสดงผลลัพธ์ในรูปแบบการจับคู่ที่เสถียร แอนิเมชันกราฟสองส่วน แผนภูมิความร้อนความชอบ และการพิสูจน์ยืนยันว่าไม่มีคู่ขัดแย้งเกิดขึ้น

ปัญหาการจับคู่แต่งงานที่เสถียรคืออะไร?

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

ตามหลักการ การจับคู่ M จะเสถียรหากไม่มี คู่ขัดแย้ง (Blocking Pair) ซึ่งก็คือคู่ (a, b) ที่ a ถูกจับคู่กับ b' และ b ถูกจับคู่กับ a' โดยที่:

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

อัลกอริทึม Gale-Shapley

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

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

คุณสมบัติทางทฤษฎีที่สำคัญ

การมีอยู่จริงและความเป็นหนึ่งเดียว

การจับคู่ที่เสถียรมีอยู่เสมอ (Gale & Shapley, 1962) แต่อาจไม่ได้มีเพียงชุดเดียว สำหรับรายการความชอบชุดหนึ่งอาจมีรูปแบบการจับคู่ที่เสถียรได้หลายรูปแบบ ซึ่งก่อตัวเป็นโครงสร้างแบบแลตทิซ (Lattice) ตามลำดับความชอบร่วมกัน

ความเป็นที่สุดสำหรับผู้เสนอ (Proposer Optimality)

เมื่อฝ่ายใดฝ่ายหนึ่งเป็นผู้เสนอ Gale-Shapley จะสร้าง การจับคู่ที่เสถียรที่ดีที่สุดสำหรับผู้เสนอ (Proposer-optimal stable matching) หมายความว่าผู้เสนอทุกคนจะได้รับคู่ครองที่ดีที่สุดเท่าที่จะเป็นไปได้ในการจับคู่ที่เสถียรใดๆ และในทางกลับกัน นี่จะเป็นการจับคู่ที่ แย่ที่สุดสำหรับฝ่ายผู้รับ (Receiver-pessimal) การสลับฝ่ายผู้เสนอในเครื่องคำนวณนี้จึงมักจะเปลี่ยนผลลัพธ์

ความปลอดภัยเชิงกลยุทธ์สำหรับผู้เสนอ (Strategy Proofness)

ภายใต้อัลกอริทึม Gale-Shapley ผู้เสนอไม่มีแรงจูงใจที่จะรายงานลำดับความชอบที่เป็นเท็จ เพราะการบอกความจริงเป็นกลยุทธ์ที่ได้เปรียบที่สุด (Dominant Strategy) สำหรับพวกเขา อย่างไรก็ตาม ผู้รับบางครั้งอาจได้ประโยชน์จากการแจ้งลำดับความชอบที่ไม่ตรงตามจริง นี่เป็นเหตุผลหนึ่งที่ตลาดแพทย์ประจำบ้านในสหรัฐฯ ถูกออกแบบมาให้นักศึกษาเป็นฝ่ายเสนอ

Rural Hospitals Theorem

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

รูปแบบข้อมูลขาเข้า

เครื่องคำนวณนี้กำหนดให้ใส่สมาชิกหนึ่งบรรทัดต่อคน โดยระบุชื่อตามด้วยเครื่องหมายโคลอน และรายการลำดับความชอบที่คั่นด้วยจุลภาค:

ข้อกำหนด:

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

วิธีใช้งานเครื่องคำนวณนี้

1. กรอกลำดับความชอบของกลุ่ม A ในพื้นที่ข้อความด้านซ้าย — หนึ่งคนต่อหนึ่งบรรทัด เรียงลำดับให้ครบทุกคน
2. กรอกลำดับความชอบของกลุ่ม B ในพื้นที่ข้อความด้านขวา — ใช้รูปแบบเดียวกันและจัดอันดับสมาชิกกลุ่ม A ทุกคน
3. เลือกฝ่ายที่เริ่มเสนอตัว เลือกว่าจะให้กลุ่ม A หรือกลุ่ม B เป็นผู้เริ่ม ลองใช้ทั้งสองแบบเพื่อเปรียบเทียบผลลัพธ์ที่ดีที่สุดสำหรับ A และที่ดีที่สุดสำหรับ B
4. คลิก "คำนวณการจับคู่ที่เสถียร" เครื่องคำนวณจะรัน Gale-Shapley และแสดงคู่ที่เสถียร, สถิติ, แอนิเมชัน และหลักฐานความเสถียร
5. เลื่อนดูแอนิเมชัน ด้วยปุ่ม Play / Step / Reset เพื่อดูการเสนอตัว, การยอมรับ, การสลับ และการปฏิเสธในแต่ละขั้นตอน
6. ตรวจสอบแผนภูมิความร้อน (Heatmap) แต่ละเซลล์แสดงอันดับความชอบ เซลล์ที่มีขอบสีเหลืองคือคู่สุดท้ายที่จับได้จริง — สังเกตว่าเซลล์เหล่านั้นอยู่สูงหรือต่ำแค่ไหนเพื่อดูว่าแต่ละฝ่าย "มีความสุข" เพียงใด

ตัวอย่างการทำงาน — คลาสสิก 3×3

ผู้ชาย: อเล็กซ์, ไบรอัน, คริส ผู้หญิง: บี, แคลร์, ไดอาน่า ความชอบ:

เมื่อรัน Gale-Shapley โดยให้ผู้ชายเสนอตัว จะได้ผลลัพธ์ อเล็กซ์–บี, ไบรอัน–แคลร์, คริส–ไดอาน่า ภายในรอบเดียว (ผู้ชายทุกคนได้ตัวเลือกอันดับหนึ่งที่บังเอิญไปตรงกับผู้หญิงที่มีตัวเลือกอันดับหนึ่งเป็นคนอื่น — ไม่มีการขัดแย้ง) การจับคู่นี้เสถียร: ไม่มีชายหรือหญิงคู่ใดที่ต่างฝ่ายต่างอยากจะสลับคู่ไปหาอีกคนหนึ่ง จึงไม่มีคู่ขัดแย้งเกิดขึ้น

การประยุกต์ใช้ในโลกแห่งความเป็นจริง

เหตุใด Lloyd Shapley จึงได้รับรางวัลโนเบล

ในปี 2012 ราชบัณฑิตยสภาด้านวิทยาศาสตร์แห่งสวีเดนได้มอบ รางวัลโนเบลสาขาเศรษฐศาสตร์ ให้แก่ Lloyd Shapley (สำหรับด้านทฤษฎี ร่วมกับ David Gale ผู้ซึ่งล่วงลับไปแล้วในขณะนั้น) และ Alvin Roth (สำหรับการนำทฤษฎีไปประยุกต์ใช้ในตลาดจริง รวมถึงการออกแบบระบบคัดเลือกแพทย์และการแลกเปลี่ยนไตใหม่) โดยระบุเหตุผลว่า "สำหรับทฤษฎีการจัดสรรที่เสถียรและการปฏิบัติในการออกแบบตลาด"

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

ปัญหาการจับคู่แต่งงานที่เสถียรคืออะไร?

คือโจทย์ที่หาการจับคู่ระหว่างกลุ่มสองกลุ่มที่ขนาดเท่ากัน โดยที่สมาชิกทุกคนจัดอันดับความชอบของอีกฝ่าย และเป้าหมายคือหาการจับคู่ที่ไม่มีใครอยากทิ้งคู่ของตนไปหาคนอื่นที่ก็อยากได้เขาเช่นกัน อัลกอริทึม Gale-Shapley สามารถหาคำตอบนี้ได้เสมอในเวลา O(n²)

อัลกอริทึม Gale-Shapley ทำงานอย่างไร?

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

การจับคู่ที่เสถียรมีเพียงชุดเดียวหรือไม่?

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

คู่ขัดแย้งคืออะไร?

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

การจับคู่ที่เสถียรใช้ทำอะไรได้บ้าง?

ใช้ในการจัดสรรทรัพยากรที่เงินไม่ใช่ปัจจัยหลัก เช่น การเลือกโรงเรียนให้เด็ก การคัดเลือกแพทย์ประจำบ้าน การจับคู่ผู้บริจาคไต หรือแม้แต่การจัดที่นั่งในห้องเรียน

ทั้งสองกลุ่มต้องมีขนาดเท่ากันหรือไม่?

ในทฤษฎีพื้นฐาน ใช่ สำหรับเครื่องมือนี้กำหนดให้เท่ากันเพื่อให้การคำนวณสมบูรณ์ แต่ในทฤษฎีขั้นสูงมีวิธีจัดการกรณีกลุ่มไม่เท่ากันได้

แหล่งข้อมูลเพิ่มเติม

• Stable marriage problem — Wikipedia
• Gale-Shapley algorithm — Wikipedia
• National Resident Matching Program — Wikipedia
• 2012 Nobel Prize in Economic Sciences — Shapley & Roth