Gale-Shapley (Deferred-Acceptance) Algorithm Initially all men and women are free while there is a man m who is free and hasn't proposed to every woman choose such a man m arbitrarily 0 let w be the highest ranked woman in m's preference list to whom m hasn't proposed yet ▣∥next:m proposes to w a if w is free,then (m,w)become engaged 口 else,suppose w is currently engaged to m' if w prefers m'to m,then m remains free if w prefers m to m',then (m,w)becomes engaged and m' becomes free Return the set of engaged pairs as a matching 17Gale-Shapley (Deferred-Acceptance) Algorithm ◼ Initially all men and women are free ◼ while there is a man 𝑚 who is free and hasn’t proposed to every woman ❑ choose such a man 𝑚 arbitrarily ❑ let 𝑤 be the highest ranked woman in 𝑚’s preference list to whom 𝑚 hasn’t proposed yet ❑ // next: 𝑚 proposes to 𝑤 ❑ if 𝑤 is free, then (𝑚, 𝑤) become engaged ❑ else, suppose 𝑤 is currently engaged to 𝑚′ ◼ if 𝑤 prefers 𝑚′ to 𝑚, then 𝑚 remains free ◼ if 𝑤 prefers 𝑚 to 𝑚′ , then (𝑚, 𝑤) becomes engaged and 𝑚′ becomes free ◼ Return the set of engaged pairs as a matching 17