Chapter 10: Stable Matching - The Gale-Shapley Algorithm

import pandas as pd
import copy

def run_gale_shapley():
    # --- SETUP ---
    # 4 Residents (A, B, C, D) and 4 Hospitals (H1, H2, H3, H4)
    
    # Residents' Preferences (Ordered List: 1st choice -> Last choice)
    residents_prefs = {
        'A': ['H1', 'H2', 'H3', 'H4'],
        'B': ['H1', 'H4', 'H3', 'H2'],
        'C': ['H2', 'H1', 'H3', 'H4'],
        'D': ['H4', 'H2', 'H3', 'H1']
    }
    
    # Hospitals' Preferences (Ranking of Residents)
    hospitals_prefs = {
        'H1': ['D', 'C', 'B', 'A'],
        'H2': ['C', 'A', 'D', 'B'],
        'H3': ['A', 'B', 'C', 'D'],
        'H4': ['B', 'A', 'C', 'D']
    }
    
    # TRACKING STATE
    # matches: {'H1': 'A'} means H1 is currently holding A's offer
    matches = {h: None for h in hospitals_prefs.keys()} 
    
    # free_residents: List of residents currently looking for a match
    free_residents = list(residents_prefs.keys())
    
    # proposals_made: Keep track of who has already been asked by whom
    # {'A': 0} means A needs to ask their 0-th index preference next
    proposals_count = {r: 0 for r in residents_prefs.keys()}
    
    print("--- STARTING DEFERRED ACCEPTANCE ALGORITHM ---")
    round_num = 1
    
    while free_residents:
        print(f"\n[Round {round_num}] Free Residents: {free_residents}")
        
        # Take the first free resident
        resident = free_residents.pop(0)
        
        # Who do they want to ask next?
        # Get the index of the next hospital to ask
        pref_index = proposals_count[resident]
        
        # If they ran out of hospitals (shouldn't happen in equal n x n), stop
        if pref_index >= len(residents_prefs[resident]):
            continue
            
        hospital = residents_prefs[resident][pref_index]
        proposals_count[resident] += 1 # Increment for next time
        
        print(f"   -> {resident} proposes to {hospital}...")
        
        # DECISION TIME FOR HOSPITAL
        current_match = matches[hospital]
        
        if current_match is None:
            # Hospital was free, takes the offer (tentatively)
            matches[hospital] = resident
            print(f"      {hospital} accepts {resident} (for now).")
            
        else:
            # Hospital is already matched. Must choose: Current vs New?
            # We look at H's preference list to see who is ranked higher (lower index)
            h_pref_list = hospitals_prefs[hospital]
            
            rank_current = h_pref_list.index(current_match)
            rank_new = h_pref_list.index(resident)
            
            if rank_new < rank_current:
                # New resident is BETTER! Swap.
                print(f"      {hospital} DUMPS {current_match} for {resident}!")
                matches[hospital] = resident
                free_residents.append(current_match) # Old match is free again
            else:
                # New resident is WORSE. Reject.
                print(f"      {hospital} rejects {resident} (prefers current {current_match}).")
                free_residents.append(resident) # Resident stays free
                
        round_num += 1

    # --- FINAL RESULTS ---
    print("\n" + "="*30)
    print("FINAL STABLE MATCHING:")
    for h, r in matches.items():
        print(f"Hospital {h} <---> Resident {r}")
        
    return matches, residents_prefs, hospitals_prefs

final_matches, r_prefs, h_prefs = run_gale_shapley()

import random

def run_stable_marriage():
    # 1. SETUP NAMES
    men = ['Adam', 'Bob', 'Charlie', 'Dave']
    women = ['Alice', 'Beatrice', 'Cindy', 'Diane']
    
    # 2. CREATE PREFERENCES
    # We fix preferences to show the advantage clearly.
    # Men's Preferences: Everyone loves Alice > Beatrice > Cindy > Diane
    men_prefs = {
        'Adam':   ['Alice', 'Beatrice', 'Cindy', 'Diane'],
        'Bob':    ['Alice', 'Beatrice', 'Cindy', 'Diane'],
        'Charlie':['Alice', 'Beatrice', 'Cindy', 'Diane'],
        'Dave':   ['Alice', 'Beatrice', 'Cindy', 'Diane']
    }
    
    # Women's Preferences: Everyone loves Adam > Bob > Charlie > Dave
    women_prefs = {
        'Alice':   ['Charlie', 'Dave', 'Adam', 'Bob'],    # Prefers Charlie/Dave (Low ranked men)
        'Beatrice':['Charlie', 'Dave', 'Adam', 'Bob'],
        'Cindy':   ['Charlie', 'Dave', 'Adam', 'Bob'],
        'Diane':   ['Charlie', 'Dave', 'Adam', 'Bob']
    }
    
    # 3. RUN GALE-SHAPLEY (Men Propose)
    matches = {w: None for w in women} # Women hold the matches
    free_men = list(men)
    proposals_count = {m: 0 for m in men}
    
    print(f"--- STARTING DATING SIMULATION (Men Propose) ---")
    
    while free_men:
        man = free_men.pop(0)
        # Get next woman on his list
        w_index = proposals_count[man]
        
        # If man has been rejected by everyone (Shouldn't happen here), skip
        if w_index >= len(men_prefs[man]):
            continue
            
        woman = men_prefs[man][w_index]
        proposals_count[man] += 1
        
        print(f"{man} proposes to {woman}...")
        
        current_husband = matches[woman]
        
        if current_husband is None:
            matches[woman] = man
            print(f"   -> {woman} says: 'Maybe' (Accepts {man})")
        else:
            # Woman checks her list: Is Man better than Current Husband?
            w_list = women_prefs[woman]
            rank_new = w_list.index(man)
            rank_curr = w_list.index(current_husband)
            
            if rank_new < rank_curr:
                print(f"   -> {woman} DUMPS {current_husband} for {man}!")
                matches[woman] = man
                free_men.append(current_husband) # Husband is single again
            else:
                print(f"   -> {woman} REJECTS {man} (Stays with {current_husband})")
                free_men.append(man) # Man stays single

    print("-" * 30)
    print("FINAL MARRIAGES:")
    for w, m in matches.items():
        # Check rank of husband in woman's list
        rank = women_prefs[w].index(m) + 1
        print(f"{w} is married to {m} (Her #{rank} choice)")
        
run_stable_marriage()