Gale–Shapley algorithm

==Recognition==

==Recognition==

Shapley and Roth were awarded the 2012 [[Nobel Memorial Prize in Economic Sciences]] "for the theory of stable allocations and the practice of [[market design]]". Gale had died in 2008, making him ineligible for the prize.{{r|nobel}}

Shapley and Roth were awarded the 2012 [[Nobel Memorial Prize in Economic Sciences]] "for the theory of stable allocations and the practice of [[market design]]". Gale had died in 2008, making him ineligible for the prize.{{r|nobel}}

==Parallelization==

The Gale–Shapley algorithm has a natural source of parallelism that makes it suitable for parallel hardware such as multicore CPUs and graphics processing units (GPUs). In each round, all employers with unfilled positions can independently advance along their preference lists and make offers concurrently. A parallel implementation can assign threads to independent employers so that many offers are made simultaneously. When multiple employers make offers to the same applicant, synchronization primitives are used to resolve the competing offers, ensuring that only the applicant’s most-preferred employer is tentatively accepted while the rejected employers continue to their next choices.{{r|manne-greedy|liu-bamboo}}

To reduce synchronization overhead, it is advantageous to avoid repeatedly returning rejected employers to the shared set of employers with unfilled positions, since concurrent updates to this set require synchronization. Instead, a rejected employer immediately continues to the next applicant on its preference list. If an applicant accepts a new offer, the displaced employer likewise continues from its next preference.{{r|manne-greedy|liu-bamboo}}

Other optimization techniques include locality-aware data structures, which combine the employer preference array with the applicant rank array to reduce random memory accesses and improve cache efficiency, and advanced synchronization primitives, which resolve contention among simultaneous offers more efficiently. Heterogeneous approaches further improve performance by using the GPU for highly parallel stages and switching to the CPU when few employers remain unmatched, avoiding GPU underutilization during mostly sequential work.{{r|liu-bamboo}}

==See also==

==See also==

| hdl-access = free

| hdl-access = free

}}

}}

| last1 = Manne | first1 = Fredrik

| last2 = Naim | first2 = Md.

| last3 = Lerring | first3 = Håkon

| last4 = Halappanavar | first4 = Mahantesh

| title = On Stable Marriages and Greedy Matchings

| book-title = 2016 Proceedings of the Seventh SIAM Workshop on Combinatorial Scientific Computing

| pages = 92–101

| publisher = SIAM

| year = 2016

| doi = 10.1137/1.9781611974690.ch10

}}

| last1 = Liu | first1 = Jiaxin

| last2 = Lee | first2 = Rubao

| last3 = Xia | first3 = Cathy H.

| last4 = Zhang | first4 = Xiaodong

| title = A Stable Marriage Requires a Shared Residence with Low Contention and Mutual Complementarity

| book-title = 2025 34th International Conference on Parallel Architectures and Compilation Techniques (PACT)

| year = 2025

| publisher = IEEE

| url = https://xiaodongzhang1911.github.io/Zhang-papers/TR-25-4.pdf

}}