ในคณิตศาสตร์เศรษฐศาสตร์และวิทยาศาสตร์คอมพิวเตอร์ปัญหาการจับคู่ที่เสถียร^{[ 1 ] [ 2 ] [ 3 ]}คือปัญหาของการค้นหาการจับคู่ที่เสถียรระหว่างเซตขององค์ประกอบสองเซตที่มีขนาดเท่ากัน โดยกำหนดลำดับความชอบสำหรับแต่ละองค์ประกอบ การจับคู่คือการจับคู่แบบหนึ่งต่อหนึ่งจากองค์ประกอบของเซตหนึ่งไปยังองค์ประกอบของอีกเซตหนึ่ง การจับคู่จะไม่เสถียรหาก:

กล่าวอีกนัยหนึ่ง การจับคู่จะมีเสถียรภาพเมื่อไม่มีคู่ใด ( A , B ) ที่ต่างฝ่ายต่างชอบอีกฝ่ายมากกว่าคู่ปัจจุบันของตนภายใต้การจับคู่นั้น

ปัญหาเรื่องการแต่งงานที่ไม่มั่นคงได้ถูกกล่าวไว้ดังนี้:

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

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

อัลกอริทึมสำหรับการค้นหาวิธีแก้ปัญหาการแต่งงานที่มั่นคงมีการประยุกต์ใช้ในสถานการณ์จริงหลากหลายรูปแบบ ซึ่งที่รู้จักกันดีที่สุดอาจเป็นการจัดสรรนักศึกษาแพทย์ที่สำเร็จการศึกษาให้ไปทำงานที่โรงพยาบาลเป็นครั้งแรก^{[ 4 ]}ในปี 2012 รางวัลโนเบลสาขาเศรษฐศาสตร์มอบให้แก่Lloyd S. ShapleyและAlvin E. Roth "สำหรับทฤษฎีการจัดสรรที่มั่นคงและการปฏิบัติการออกแบบตลาด" ^{[ 5 ]}

ส่วนขยายของอัลกอริธึม Gale-Shapley ได้ถูกนำมาใช้ในเครือข่ายการส่งมอบเนื้อหาการเพิ่มประสิทธิภาพจากมุมมองของผู้ใช้และการปรับสมดุลภาระของเซิร์ฟเวอร์จำเป็นต้องมีการจับคู่ที่ดีระหว่างกลุ่มผู้ใช้ที่เข้าถึงเนื้อหาประเภทใดประเภทหนึ่ง (เช่น เว็บเพจหรือวิดีโอ) กับกลุ่มเซิร์ฟเวอร์ที่อยู่ในตำแหน่งที่ดีเพื่อให้บริการเนื้อหาที่ต้องการแก่พวกเขา สิ่งนี้สามารถจำลองได้เป็นกลุ่มผู้ใช้และกลุ่มเซิร์ฟเวอร์ที่มีความชอบ (บางส่วน) เหนือกันและกันโดยอิงจากตัวแปรต่างๆ เช่น โครงสร้างเครือข่ายหรือข้อตกลงตามสัญญากับผู้ให้บริการอินเทอร์เน็ตจากนั้นสามารถแก้ไขได้เป็นปัญหาการจับคู่ที่เสถียร การวางนัยทั่วไปของแนวทาง Gale-Shapley แบบคลาสสิกเป็นสิ่งจำเป็นเนื่องจากมีจำนวนกลุ่มไม่เท่ากันในแต่ละด้าน เนื่องจากความต้องการและความจุอาจแตกต่างกันระหว่างกลุ่ม และเนื่องจากความชอบเป็นเพียงบางส่วนแทนที่จะเป็นทั้งหมด^{[ 6 ]}

อัลกอริทึม Gale–Shapleyสำหรับการจับคู่ที่เสถียรใช้ในการมอบหมายแรบไบที่สำเร็จการศึกษาจากHebrew Union Collegeให้กับประชาคมชาวยิว^{[ 7 ]}

โดยทั่วไป อาจมีการจับคู่ที่เสถียรได้หลายแบบ ตัวอย่างเช่น สมมติว่ามีผู้ชายสามคน (A, B, C) และผู้หญิงสามคน (X, Y, Z) ซึ่งมีความชอบดังนี้:

A: YXZ B: ZYX C: XZY  

X: BAC Y: CBA Z: ACB

มีวิธีแก้ปัญหาที่เสถียรอยู่สามวิธีสำหรับรูปแบบการจับคู่แบบนี้:

• ผู้ชายจะได้เลือกอันดับแรก ส่วนผู้หญิงจะได้เลือกอันดับที่สาม (AY, BZ, CX)
• ผู้เข้าร่วมทุกคนมีสิทธิ์เลือกอันดับสอง (AX, BY, CZ)
• ผู้หญิงมีสิทธิ์เลือกอันดับแรก ส่วนผู้ชายมีสิทธิ์เลือกอันดับที่สาม (AZ, BX, CY)

ทั้งสามแบบมีความเสถียร เนื่องจากความไม่เสถียรต้องอาศัยผู้เข้าร่วมทั้งสองฝ่ายมีความสุขมากกว่าหากเลือกคู่อื่น การให้กลุ่มหนึ่งเลือกอันดับแรกจะทำให้คู่ที่เลือกมีความเสถียร เพราะพวกเขาจะไม่พอใจกับคู่อื่นที่เสนอมา การให้ทุกคนเลือกอันดับสองจะทำให้คู่อื่นไม่เป็นที่ชื่นชอบของฝ่ายใดฝ่ายหนึ่ง โดยทั่วไปแล้ว ตระกูลของวิธีแก้ปัญหาการแต่งงานที่เสถียรในแต่ละกรณีสามารถกำหนดโครงสร้างของแลตทิซแบบกระจาย จำกัดได้ และโครงสร้างนี้จะนำไปสู่อัลกอริทึมที่มีประสิทธิภาพสำหรับปัญหาการแต่งงานที่เสถียรหลายปัญหา^{[ 8 ]}

ในกรณีสุ่มแบบสม่ำเสมอของปัญหาการแต่งงานที่มั่นคงซึ่งมี ผู้ชาย nคนและ ผู้หญิง nคน จำนวนการจับคู่ที่มั่นคงโดยเฉลี่ยจะเท่ากับ n ในเชิงอะซิมโทติก[ ^{9 ] ใน} กรณีการแต่งงานที่มั่นคงที่เลือกเพื่อเพิ่มจำนวนการจับคู่ที่มั่นคงที่แตกต่างกันให้สูงสุด จำนวนนี้จะเป็นฟังก์ชันเลขชี้กำลังของn ^{[ 10 ]} การนับจำนวนการจับคู่ที่มั่นคงในกรณีใดกรณีหนึ่งนั้นเป็นปัญหา# P- complete ^{[ 11 ]}${\displaystyle e^{-1}n\ln n}$

ในปี พ.ศ. 2505 เดวิด เกลและลอยด์ แชปลีย์ได้พิสูจน์ว่า สำหรับจำนวนที่เท่ากันในกลุ่มต่างๆ ในบริบทของการรับเข้าวิทยาลัยและบุคคลที่ต้องการแต่งงานนั้น เป็นไปได้เสมอที่จะแก้ปัญหาเป็นคู่ที่จับคู่กันเพื่อให้การจับคู่/ปัจจัยที่จับคู่ทั้งหมดมีเสถียรภาพ พวกเขานำเสนออัลกอริทึมเพื่อทำเช่นนั้น^{[ 12 ] [ 13 ]}

อัลกอริทึม Gale –Shapley (หรือที่รู้จักกันในชื่ออัลกอริทึมการยอมรับแบบเลื่อนออกไป) ประกอบด้วย "รอบ" (หรือ " การทำซ้ำ ") จำนวนหนึ่ง :

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

อัลกอริทึมนี้รับประกันว่าจะสร้างการแต่งงานที่มั่นคงสำหรับผู้เข้าร่วมทั้งหมดเมื่อเวลาผ่านไป โดยที่จำนวนผู้ชายหรือผู้หญิงคือ^{[ 14 ]}${\displaystyle O(n^{2})}$${\displaystyle n}$

ในบรรดาการจับคู่ที่เสถียรที่เป็นไปได้ทั้งหมด ผลลัพธ์ที่ได้จะเป็นการจับคู่ที่ดีที่สุดสำหรับผู้ชายทุกคนในบรรดาการจับคู่ที่เสถียรทั้งหมด และแย่ที่สุดสำหรับผู้หญิงทุกคน^{[ 15 ]}

เป็นกลไกที่เที่ยงตรงจากมุมมองของผู้ชาย (ฝ่ายเสนอ) กล่าวคือ ไม่มีผู้ชายคนใดสามารถได้คู่ที่ดีกว่าสำหรับตนเองโดยการบิดเบือนความชอบของตนเอง ยิ่งไปกว่านั้น อัลกอริทึม GS ยังป้องกันกลยุทธ์กลุ่มสำหรับผู้ชายได้อีกด้วย กล่าวคือ ไม่มีกลุ่มผู้ชายกลุ่มใดสามารถประสานงานการบิดเบือนความชอบของตนเองเพื่อให้ผู้ชายทุกคนในกลุ่มได้รับประโยชน์อย่างแท้จริง^{[ 16 ]}อย่างไรก็ตาม เป็นไปได้ที่บางกลุ่มจะบิดเบือนความชอบของตนเองเพื่อให้ผู้ชายบางคนได้รับประโยชน์และผู้ชายคนอื่นๆ ยังคงมีคู่ครองคนเดิม^{[ 17 ]} อัลกอริทึม GS ไม่เที่ยงตรงสำหรับผู้หญิง (ฝ่ายตรวจสอบ): ผู้หญิงแต่ละคนอาจสามารถบิดเบือนความชอบของตนเองและได้คู่ที่ดีกว่า

อัลกอริทึม Gale–Shapley ยังเปิดเผยความขนานเพื่อเร่งความเร็วอินสแตนซ์ SMP ขนาดใหญ่ เนื่องจากผู้ชายที่ไม่ได้มีส่วนร่วมสามารถเสนอข้อเสนอได้อย่างอิสระในแต่ละรอบ การใช้งานแบบขนานสามารถกำหนดผู้ชายให้กับเธรดต่างๆ แก้ไขข้อเสนอพร้อมกันด้วยพรีมิทีฟการซิงโครไนซ์ และใช้การเพิ่มประสิทธิภาพ เช่น การหลีกเลี่ยงคิว รูปแบบข้อมูลที่คำนึงถึงตำแหน่ง และการประมวลผลแบบไฮบริด CPU–GPU เพื่อลดโอเวอร์เฮด^{[ 18 ]}

ทฤษฎีโรงพยาบาลในชนบทเกี่ยวข้องกับรูปแบบทั่วไปของปัญหาการจับคู่ที่เสถียร เช่นเดียวกับที่ใช้ในปัญหาการจับคู่แพทย์กับตำแหน่งในโรงพยาบาล ซึ่งแตกต่างจากรูปแบบพื้นฐานnต่อnของปัญหาการจับคู่ที่เสถียรในประเด็นต่อไปนี้:

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

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

สำหรับปัญหาการจับคู่ที่มีเสถียรภาพประเภทนี้ ทฤษฎีโรงพยาบาลในชนบทกล่าวว่า:

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

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

ปัญหาการอยู่ร่วมห้องอย่างมั่นคงนั้นคล้ายคลึงกับปัญหาการแต่งงานที่มั่นคง แต่แตกต่างตรงที่ผู้เข้าร่วมทั้งหมดอยู่ในกลุ่มเดียวกัน (แทนที่จะแบ่งออกเป็นจำนวน "ชาย" และ "หญิง" ที่เท่ากัน)

ปัญหาโรงพยาบาล/ผู้พักอาศัย – หรือที่รู้จักกันในชื่อปัญหาการรับเข้าวิทยาลัย – แตกต่างจากปัญหาการแต่งงานที่มั่นคงตรงที่โรงพยาบาลสามารถรับผู้พักอาศัยได้หลายคน หรือวิทยาลัยสามารถรับนักเรียนใหม่ได้มากกว่าหนึ่งคน อัลกอริทึมในการแก้ปัญหาโรงพยาบาล/ผู้พักอาศัยสามารถมุ่งเน้นที่โรงพยาบาล (เช่นเดียวกับNRMPก่อนปี 1995) ^{[ 19 ]}หรือมุ่งเน้นที่ผู้พักอาศัยปัญหานี้ได้รับการแก้ไขด้วยอัลกอริทึมในเอกสารต้นฉบับเดียวกันโดย Gale และ Shapley ซึ่งเป็นเอกสารที่แก้ปัญหาการแต่งงานที่มั่นคง^{[ 12 ]}

ปัญหา โรงพยาบาล/ผู้พักอาศัยที่มีคู่รักช่วยให้ชุดผู้พักอาศัยรวมถึงคู่รักที่ต้องได้รับการจัดสรรร่วมกัน ไม่ว่าจะในโรงพยาบาลเดียวกันหรือในโรงพยาบาลคู่ใดคู่หนึ่งที่คู่รักเลือก (เช่น คู่สามีภรรยาต้องการให้แน่ใจว่าพวกเขาจะอยู่ด้วยกันและไม่ติดอยู่ในโปรแกรมที่อยู่ห่างไกลกัน) การเพิ่มคู่รักเข้าไปในปัญหาโรงพยาบาล/ผู้พักอาศัยทำให้ปัญหานี้กลายเป็นNP -complete ^{[ 20 ]}

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

ปัญหา การจับคู่ด้วยสัญญาเป็นการขยายความของปัญหาการจับคู่ ซึ่งผู้เข้าร่วมสามารถจับคู่ด้วยเงื่อนไขสัญญาที่แตกต่างกันได้^{[ 21 ]}กรณีพิเศษที่สำคัญของสัญญาคือการจับคู่ด้วยค่าจ้างที่ยืดหยุ่น^{[ 22 ]}

ปัญหาการจับคู่ที่เป็นที่นิยมคือการหาการจับคู่ที่ไม่มีการจับคู่อื่นใดที่มีคนมีความสุขมากกว่าการจับคู่กับการจับคู่อื่น สำหรับอินพุตที่ไม่ใช่แบบสองส่วน การตรวจสอบว่ามีการจับคู่ที่เป็นที่นิยมหรือไม่นั้นเป็นปัญหาNP-complete ^{[ 23 ]}${\displaystyle M^{*}}$${\displaystyle M}$${\displaystyle M}$${\displaystyle M^{*}}$

• การจับคู่ (ทฤษฎีกราฟ) – การจับคู่ระหว่างจุดยอดที่แตกต่างกันของกราฟ โดยปกติจะไม่เกี่ยวข้องกับการจัดลำดับความชอบ
• การจับคู่แบบปราศจากความอิจฉา – การผ่อนคลายการจับคู่แบบเสถียรสำหรับปัญหาการจับคู่แบบหลายต่อหนึ่ง
• การจับคู่สีรุ้งสำหรับกราฟที่มีสีขอบ
• โพลีโทปที่จับคู่ได้อย่างเสถียร
• ปัญหาเลขานุการ (หรือเรียกอีกอย่างว่าปัญหาการแต่งงาน ) – การตัดสินใจว่าจะหยุดเมื่อใดเพื่อให้ได้ผลตอบแทนที่ดีที่สุดในลำดับของตัวเลือกต่างๆ

• Kleinberg, J. และ Tardos, E. (2005) การออกแบบอัลกอริทึมบทที่ 1 หน้า 1–12 ดูเว็บไซต์ประกอบสำหรับข้อความ[1] เก็บถาวรเมื่อ 2011-05-14 ที่Wayback Machine
• Knuth, DE (1996). การแต่งงานที่เสถียรและความสัมพันธ์กับปัญหาเชิงการจัดเรียงอื่นๆ: บทนำสู่การวิเคราะห์ทางคณิตศาสตร์ของอัลกอริทึม CRM Proceedings and Lecture Notes. ฉบับแปลภาษาอังกฤษ สมาคมคณิตศาสตร์อเมริกัน
• Pittel, B. (1992). "เกี่ยวกับวิธีแก้ปัญหาที่เป็นไปได้ของปัญหาการแต่งงานที่มั่นคง"วารสารความน่าจะเป็นประยุกต์ 2 ( 2): 358– 401. doi : 10.1214/aoap/1177005708 . JSTOR  2959755 .
• Roth, AE (1984). "วิวัฒนาการของตลาดแรงงานสำหรับแพทย์ฝึกหัดและแพทย์ประจำบ้าน: กรณีศึกษาในทฤษฎีเกม" (PDF)วารสารเศรษฐศาสตร์การเมือง 92 ( 6): 991– 1016. doi : 10.1086/261272 . S2CID  1360205 .
• Roth, AE; Sotomayor, MAO (1990). การจับคู่แบบสองด้าน: การศึกษาเกี่ยวกับการสร้างแบบจำลองและการวิเคราะห์เชิงทฤษฎีเกมสำนักพิมพ์มหาวิทยาลัยเคมบริดจ์
• Shoham, Yoav; Leyton-Brown, Kevin (2009). ระบบหลายเอเจนต์: รากฐานเชิงอัลกอริทึม ทฤษฎีเกม และตรรกะนิวยอร์ก: สำนักพิมพ์มหาวิทยาลัยเคมบริดจ์ ISBN 978-0-521-89943-7.ดูหัวข้อ 10.6.4; สามารถดาวน์โหลดได้ฟรีทางออนไลน์
• ชูเมอร์ เจ.; โวห์รา อาร์วี (2550) “การออกแบบกลไกโดยไม่ต้องใช้เงิน” (PDF) . ในนิสาน โนอัม; รอฟการ์เดน, ทิม; ทาร์ดอส, เอวา; วาซิรานี, วิเจย์ (บรรณาธิการ). ทฤษฎีเกมอัลกอริทึม หน้า  255– 262. ISBN 978-0521872829.
• Gusfield, D.; Irving, RW (1989). ปัญหาการแต่งงานที่มั่นคง: โครงสร้างและอัลกอริทึมสำนักพิมพ์MIT ISBN 0-262-07118-5.

• การสาธิตแบบโต้ตอบด้วยแฟลชเกี่ยวกับปัญหาการแต่งงานที่มั่นคง
• https://web.archive.org/web/20080512150525/http://kuznets.fas.harvard.edu/~aroth/alroth.html#NRMP
• http://www.dcs.gla.ac.uk/research/algorithms/stable/EGSapplet/EGS.html
• บันทึกการบรรยายเกี่ยวกับปัญหาการแต่งงานที่ไม่มั่นคง