ในคณิตศาสตร์เศรษฐศาสตร์และวิทยาศาสตร์คอมพิวเตอร์อัลกอริทึม Gale–Shapley ( หรือที่รู้จักกันในชื่ออัลกอริทึมการยอมรับแบบเลื่อนออกไป [ ^{1 ] อั}ลกอริทึมเสนอและปฏิเสธ^{[ 2 ]}หรืออัลกอริทึม Boston Pool ^{[ 1 ]} ) เป็นอัลกอริทึมสำหรับการค้นหาวิธีแก้ปัญหาการจับคู่ที่เสถียร อัลกอริทึม นี้ตั้งชื่อตามDavid GaleและLloyd Shapleyซึ่งตีพิมพ์ในปี 1962 แม้ว่าจะมีการใช้งานสำหรับโครงการจับคู่ผู้พักอาศัยแห่งชาติมาตั้งแต่ต้นทศวรรษ 1950 แล้วก็ตาม Shapley และAlvin E. Roth (ผู้ชี้ให้เห็นถึงการใช้งานก่อนหน้านี้) ได้รับรางวัลโนเบลสาขาเศรษฐศาสตร์ ประจำปี 2012 จากผลงานที่รวมถึงอัลกอริทึมนี้

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

ปัญหาการจับคู่ที่เสถียร และอัลกอริทึม Gale–Shapley ที่ใช้แก้ปัญหานี้ มีการประยุกต์ใช้ในโลกแห่งความเป็นจริงอย่างกว้างขวาง รวมถึงการจับคู่ระหว่างนักศึกษาแพทย์ชาวอเมริกันกับตำแหน่งแพทย์ประจำบ้าน และผู้สมัครเข้ามหาวิทยาลัยชาวฝรั่งเศสกับคณะต่างๆ สำหรับข้อมูลเพิ่มเติม โปรดดูที่ปัญหาการจับคู่ที่เสถียร § การประยุกต์ใช้

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

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

ปัญหาการจับคู่ที่เสถียรยังถูกเรียกว่าปัญหาการแต่งงานที่เสถียรโดยใช้คำอุปมาของการแต่งงานระหว่างชายและหญิง และแหล่งข้อมูลหลายแห่งอธิบายอัลกอริทึม Gale–Shapley ในแง่ของข้อเสนอการแต่งงานอย่างไรก็ตาม คำอุปมานี้ถูกวิพากษ์วิจารณ์ว่าเป็นการเหยียดเพศและไม่สมจริง: ขั้นตอนของอัลกอริทึมไม่ได้สะท้อนพฤติกรรมของมนุษย์ทั่วไปหรือแม้แต่พฤติกรรมตามแบบแผนอย่างแม่นยำ^{[ 4 ] [ 5 ]}

ในปี พ.ศ. 2505 เดวิด เกลและลอยด์ แชปลีย์ได้พิสูจน์ว่า สำหรับจำนวนผู้เข้าร่วมที่เท่ากันของแต่ละประเภท จะสามารถหาการจับคู่ที่ทุกคู่มีความเสถียรได้เสมอ พวกเขาได้นำเสนออัลกอริทึมเพื่อทำเช่นนั้น^{[ 6 ] [ 7 ]}ในปี พ.ศ. 2527 อัลวิน อี. รอธสังเกตว่าอัลกอริทึมเดียวกันนี้ได้ถูกนำมาใช้ในทางปฏิบัติแล้วตั้งแต่ต้นทศวรรษ พ.ศ. 2493 ในชื่อ "อัลกอริทึม Boston Pool" ที่ใช้โดยโครงการจับคู่ผู้พักอาศัยแห่งชาติ^{[ 1 ] [ 8 ]}

อัลกอริทึม Gale–Shapley ประกอบด้วย "รอบ" (หรือ " การวนซ้ำ ") จำนวนหนึ่งในแง่ของผู้สมัครงานและนายจ้าง สามารถแสดงได้ดังนี้: ^{[ 9 ]}

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

เพื่อให้การนำอัลกอริทึมไปใช้อย่างมีประสิทธิภาพ นายจ้างแต่ละรายจำเป็นต้องสามารถค้นหาผู้สมัครรายต่อไปได้อย่างรวดเร็ว และผู้สมัครแต่ละรายจำเป็นต้องสามารถเปรียบเทียบนายจ้างได้อย่างรวดเร็ว วิธีหนึ่งในการทำเช่นนี้คือการกำหนดหมายเลขให้กับผู้สมัครและนายจ้างแต่ละรายตั้งแต่ 1 ถึง โดยที่คือจำนวนนายจ้างและผู้สมัคร และจัดเก็บโครงสร้างข้อมูล ต่อไปนี้ : ^{[ 10 ]}${\displaystyle n}$${\displaystyle n}$

• กลุ่มนายจ้างที่มีตำแหน่งงานว่าง
• อาร์เรย์หนึ่งมิติที่จัดทำดัชนีโดยนายจ้าง โดยระบุถึงดัชนีลำดับความสำคัญของผู้สมัครรายถัดไปที่นายจ้างจะส่งข้อเสนอให้ โดยเริ่มต้นที่ 1 สำหรับแต่ละนายจ้าง
• อาร์เรย์หนึ่งมิติที่จัดทำดัชนีโดยผู้สมัคร โดยระบุถึงนายจ้างปัจจุบันของพวกเขา โดยค่าเริ่มต้นจะมีค่าบ่งชี้เช่น 0 ซึ่งแสดงว่าพวกเขาว่างงาน
• อาร์เรย์สองมิติที่จัดทำดัชนีโดยผู้สมัครและนายจ้าง โดยระบุตำแหน่งของนายจ้างนั้นในรายการลำดับความสำคัญของผู้สมัคร
• อาร์เรย์สองมิติที่จัดทำดัชนีโดยนายจ้างและตัวเลขตั้งแต่ 1 ถึงn โดยระบุชื่อผู้สมัครที่เป็นลำดับที่ n ของนายจ้างแต่ละราย${\displaystyle i}$${\displaystyle n}$${\displaystyle i}$

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

แม้ว่าขอบเขตเวลาดังกล่าวจะเป็นกำลังสองของจำนวนผู้เข้าร่วม แต่ก็อาจถือได้ว่าเป็นเวลาเชิงเส้นเมื่อวัดตามขนาดของอินพุต ซึ่งเป็นเมทริกซ์ความชอบสองเมทริกซ์ที่มีขนาด^{[ 11 ]}${\displaystyle O(n^{2})}$

อัลกอริทึมนี้รับประกันว่า:

ทุกคนจะได้รับการจับคู่

ในตอนท้าย จะไม่มีผู้สมัครและนายจ้างที่ไม่ได้รับการจับคู่กัน นายจ้างที่ยังไม่ได้รับการจับคู่ในตอนท้ายของกระบวนการจะต้องได้เสนอตำแหน่งงานให้กับผู้สมัครทุกคน แต่ผู้สมัครที่ได้รับข้อเสนอจะยังคงได้รับการจ้างงานต่อไปจนกว่ากระบวนการจะเสร็จสิ้น ดังนั้นจึงไม่มีผู้สมัครที่ว่างงาน เนื่องจากจำนวนผู้สมัครและตำแหน่งงานว่างเท่ากัน จึงไม่มีตำแหน่งงานว่างเหลืออยู่^{[ 9 ]}

ผลการแข่งขันค่อนข้างคงที่

ผู้สมัคร Xและนายจ้างYไม่สามารถเลือกกันและกันเหนือคู่ที่เหมาะสมที่สุดได้ หากYเสนองานให้Xแล้วXจะปฏิเสธY ก็ต่อ เมื่อได้รับข้อเสนอที่ดีกว่าเท่านั้น ดังนั้นX จึง ไม่สามารถเลือกYเหนือคู่ที่เหมาะสมที่สุดได้ และหากYหยุดเสนองานก่อนที่จะถึงXในรายการลำดับความสำคัญYก็ไม่สามารถเลือกXเหนือคู่ที่เหมาะสมที่สุดได้ ไม่ว่าในกรณีใดXและYก็ไม่ก่อให้เกิดคู่ที่ไม่มั่นคง^{[ 9 ]}

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

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

ในอัลกอริธึมทั้งสองรูปแบบ กลุ่มผู้เข้าร่วมกลุ่มหนึ่งจะเสนอการจับคู่ และอีกกลุ่มหนึ่งจะตัดสินใจว่าจะยอมรับหรือปฏิเสธข้อเสนอแต่ละรายการ การจับคู่จะดีที่สุดสำหรับกลุ่มที่เสนอข้อเสนอ และแย่ที่สุดสำหรับกลุ่มที่ตัดสินใจว่าจะจัดการกับข้อเสนอแต่ละรายการอย่างไร^{[ 12 ]}

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

อัลกอริทึม Gale–Shapley ไม่ซื่อสัตย์สำหรับผู้เข้าร่วมที่ไม่เสนอ แต่ละคนอาจบิดเบือนความชอบของตนและได้รับการจับคู่ที่ดีกว่า^{[ 15 ]}รูปแบบเฉพาะของการบิดเบือนคือการตัดทอน : การนำเสนอเฉพาะทางเลือกสูงสุดเท่านั้น ซึ่งหมายความว่าทางเลือกด้านล่างไม่เป็นที่ยอมรับเลย ภายใต้ข้อมูลที่สมบูรณ์ การพิจารณาการบิดเบือนในรูปแบบของกลยุทธ์การตัดทอนก็เพียงพอแล้ว อย่างไรก็ตาม การบิดเบือนที่ประสบความสำเร็จต้องอาศัยความรู้เกี่ยวกับความชอบของตัวแทนอื่น ๆ หากไม่มีความรู้ดังกล่าว การบิดเบือนอาจทำให้ตัวแทนได้รับการมอบหมายที่แย่ลง ยิ่งไปกว่านั้น แม้หลังจากที่ตัวแทนเห็นการจับคู่ขั้นสุดท้ายแล้ว พวกเขาก็ไม่สามารถสรุปกลยุทธ์ที่จะรับประกันผลลัพธ์ที่ดีกว่าในภายหลังได้ สิ่งนี้ทำให้อัลกอริทึม Gale–Shapley เป็นกลไกการบอกความจริงที่ปราศจากความเสียใจ ยิ่ง ไปกว่านั้น ในอัลกอริทึม Gale–Shapley การบอกความจริงเป็นกลยุทธ์เดียวที่รับประกันว่าจะไม่มีความเสียใจ อัลกอริทึม Gale–Shapley เป็นกลไกเดียวที่ปราศจากความเสียใจในกลุ่มกลไกการจับคู่ที่เสถียรตามควอนไทล์^{[ 16 ]}

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

ตั้งแต่ปี 2018 เป็นต้นมา มีการใช้รูปแบบหนึ่งของอัลกอริทึม Gale–Shapley ในการประสานงานการรับเข้าศึกษาต่อในระดับอุดมศึกษาในประเทศฝรั่งเศส ผ่าน ระบบ Parcoursupโดยกระบวนการนี้จะเกิดขึ้นในช่วงฤดูร้อนก่อนเริ่มภาคการศึกษา ผู้สมัครจะได้รับข้อเสนอการรับเข้าศึกษา และต้องเลือกในแต่ละรอบว่าจะยอมรับข้อเสนอใหม่หรือไม่ (และหากยอมรับ ก็ต้องปฏิเสธข้อเสนอเดิมที่เคยยอมรับไปแล้ว) วิธีนี้มีความซับซ้อนมากขึ้นเนื่องจากมีข้อจำกัดเพิ่มเติมที่ทำให้ปัญหาที่แก้ไขไม่ใช่ปัญหาการจับคู่ที่เสถียรอย่างแท้จริง ข้อดีคือ นักเรียนไม่จำเป็นต้องตัดสินใจเลือกตั้งแต่เริ่มต้น แต่สามารถกำหนดความชอบของตนเองได้เมื่ออัลกอริทึมดำเนินไป โดยพิจารณาจากการเปรียบเทียบข้อเสนอที่ได้รับโดยตรง สิ่งสำคัญคือ กระบวนการนี้ต้องดำเนินการเพียงไม่กี่รอบ เพื่อให้สิ้นสุดก่อนวันเริ่มภาคการศึกษา แต่ถึงแม้ว่าในทางทฤษฎีแล้วสามารถดำเนินการได้หลายรอบ แต่ในทางปฏิบัติมักจะไม่เกิดขึ้น^{[ 17 ]}ได้มีการแสดงให้เห็นในทางทฤษฎีแล้วว่า หากจำเป็นต้องยุติอัลกอริธึม Gale–Shapley ก่อนกำหนด หลังจากจำนวนรอบเล็กน้อยที่ตำแหน่งว่างทุกตำแหน่งเสนอข้อเสนอใหม่ อัลกอริธึมนี้ก็ยังคงสร้างการจับคู่ที่มีอัตราส่วนของผู้เข้าร่วมที่จับคู่กับคู่ที่ไม่เสถียรสูง^{[ 18 ]}

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

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

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

Shapley และ Roth ได้รับรางวัลโนเบลสาขาเศรษฐศาสตร์ประจำ ปี 2012 "สำหรับทฤษฎีการจัดสรรที่มีเสถียรภาพและการปฏิบัติการออกแบบตลาด " Gale เสียชีวิตในปี 2008 ทำให้เขาไม่มีสิทธิ์ได้รับรางวัล^{[ 21 ]}

• การประมูลแบบยอมรับภายหลัง
• ปัญหาเพื่อนร่วมห้องที่มั่นคง
• ปัญหาร้านอาหารโกลกาตา Paise