Matching Algorithm Solver
Matching Algorithm Solver visualizes the Gale-Shapley algorithm to find a stable matching between two sets (e.g., men and women). Enter names and preferences to compute and visualize the stable matching.
Methodology Used in Matching Algorithm Solver
The Gale-Shapley algorithm finds a stable matching between two equal-sized sets (e.g., men and women), ensuring no pair prefers each other over their assigned matches:
Algorithm Steps:
1. Initialize all members of Set 1 as free.
2. While there is a free member in Set 1 who hasn’t proposed to everyone:
a. Select the first such member and propose to their highest-ranked unproposed member in Set 2.
b. If the Set 2 member is free, accept the proposal.
c. If the Set 2 member is engaged, compare preference: accept if the new proposer is preferred, reject otherwise.
d. If rejected, the proposer moves to their next preference.
3. Output the final stable matching.
Mathematical Formulation:
\\[ \text{For each free } m \in \text{Set 1}: \\] \\[ \text{Propose to } w \text{ in } m\text{‘s preference list (highest unproposed)} \\] \\[ \text{If } w \text{ is free: } (m, w) \text{ become engaged} \\] \\[ \text{Else if } w \text{ prefers } m \text{ over current match } m’: \\] \\[ \text{Disengage } (m’, w), \text{ engage } (m, w), \text{ set } m’ \text{ free} \\] \\[ \text{Else: } w \text{ rejects } m \\]Example Calculation
Sample Input
Set 1: M1,M2; Set 2: W1,W2; M1: W1-W2, M2: W2-W1; W1: M2-M1, W2: M1-M2
Step 1: M1 proposes to W1 (top preference):
\\[ W1 \text{ is free, so } (M1, W1) \text{ engage} \\]Step 2: M2 proposes to W2 (top preference):
\\[ W2 \text{ is free, so } (M2, W2) \text{ engage} \\]Result: Stable matching: \\( M1 \leftrightarrow W1, M2 \leftrightarrow W2 \\)