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

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

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

อัลกอริทึม Gale-Shapley ถูกใช้ในโครงการ National Resident Matching Program เพื่อจัดสรรนักศึกษาแพทย์เข้าฝึกงานในสหรัฐอเมริกา, ระบบเลือกโรงเรียนในบอสตันและนิวยอร์ก, การรับเข้ามหาวิทยาลัยในหลายประเทศ, เครือข่ายแลกเปลี่ยนไตของผู้บริจาคอวัยวะ และระบบจัดห้องพักรูมเมท Lloyd Shapley และ Alvin Roth ได้รับรางวัลโนเบลสาขาเศรษฐศาสตร์ปี 2012 ส่วนหนึ่งมาจากผลงานชิ้นนี้

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

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

stable marriage problem คืออะไร?

(ดูคำตอบด้านบนเรื่อง ปัญหาการจับคู่แต่งงานที่เสถียร)

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

แก้ปัญหาการจับคู่แต่งงานที่เสถียร (Stable Marriage / Stable Matching Problem) โดยใช้อัลกอริทึม Gale-Shapley เพียงวางรายการลำดับความพึงพอใจสำหรับสองกลุ่มที่มีขนาดเท่ากัน เพื่อหาการจับคู่ที่รับประกันความเสถียร พร้อมการแสดงขั้นตอนการเสนอตัวแบบแอนิเมชัน สถิติความพึงพอใจ การตรวจสอบคู่ขัดแย้ง (Blocking Pair) และการสร้างภาพกราฟสองส่วน (Bipartite Visualization) แบบโต้ตอบได้

ตัวอย่างด่วน:

คลาสสิก 3×3 การคัดเลือกแพทย์ประจำบ้าน บทเรียน P/R ทีม 5×5 4×4 (B เสนอตัว)

หนึ่งบรรทัดต่อคน: ชื่อ: ลำดับ 1, ลำดับ 2, ... — ระบุสมาชิกกลุ่ม B ทุกคน ตามลำดับความชอบ

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

ฝ่ายใดเริ่มเสนอตัว?

ใน Gale-Shapley ฝ่ายที่เสนอตัวจะได้คู่ครองที่ดีที่สุดเท่าที่เป็นไปได้ ส่วนฝ่ายรับจะได้คู่ครองที่แย่ที่สุด

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

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

ตัวแก้ปัญหาการจับคู่แต่งงานที่เสถียร เป็นเครื่องมือแบบโต้ตอบที่ใช้ อัลกอริทึม 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 มากกว่า b' และ b ชอบ a มากกว่า a'

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

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

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

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

Time complexity: O(n²) Space complexity: O(n²) จำนวนการเสนอตัวก่อนจบ: สูงสุด n²

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

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

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

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

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

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

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

Rural Hospitals Theorem

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

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

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

ชื่อ1: ตัวเลือกอันดับหนึ่ง, ตัวเลือกอันดับสอง, ตัวเลือกอันดับสาม, ..., ตัวเลือกสุดท้าย ชื่อ2: ตัวเลือกอันดับหนึ่ง, ตัวเลือกอันดับสอง, ... ...

ข้อกำหนด:

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

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

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

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

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

อเล็กซ์: บี, แคลร์, ไดอาน่า ไบรอัน: แคลร์, บี, ไดอาน่า คริส: ไดอาน่า, บี, แคลร์ บี: ไบรอัน, อเล็กซ์, คริส แคลร์: อเล็กซ์, ไบรอัน, คริส ไดอาน่า: คริส, ไบรอัน, อเล็กซ์

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

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

การใช้งาน	กลุ่ม A	กลุ่ม B	ฝ่ายที่เสนอตัว
NRMP Residency Match (สหรัฐฯ)	นักศึกษาแพทย์	โครงการของโรงพยาบาล	นักศึกษา — ออกแบบให้ดีที่สุดสำหรับนักศึกษาตั้งแต่ปี 1998
การเลือกโรงเรียนใน NYC / บอสตัน	ครอบครัว/นักเรียน	โรงเรียนรัฐบาล	ครอบครัว — เข้ามาแทนที่ระบบเดิมที่เกิดการเล่นแง่เชิงกลยุทธ์ในช่วงปี 2000
การรับเข้ามหาวิทยาลัย	ผู้สมัคร	มหาวิทยาลัย	เป็นตัวอย่างเริ่มแรกที่เป็นแรงจูงใจให้ Gale-Shapley
การแลกเปลี่ยนไต	คู่ผู้บริจาค-ผู้รับ	คู่ผู้บริจาค-ผู้รับคู่อื่น	ใช้ทฤษฎีการจับคู่ในรูปแบบการหาวัฏจักรแบบพิเศษ
แอปหาคู่และรูมเมท	ผู้ใช้งาน	คู่ครองที่มีศักยภาพ	แอปพลิเคชันสำหรับผู้บริโภคมักใช้แนวคิดที่ลดทอนมาจากทฤษฎีนี้

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

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

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

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

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

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

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

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

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

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

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

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

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