gale-shapley-algorithm¶

A Python implementation of the celebrated Gale-Shapley (a.k.a. the Deferred Acceptance) Algorithm.

Time complexity is O(n^2), space complexity is O(n).

GUI with Docker¶

The easiest way to try the algorithm is with the interactive web GUI:

docker pull oedokumaci/gale-shapley-algorithm
docker run --rm -p 8000:8000 oedokumaci/gale-shapley-algorithm

Then open http://localhost:8000 in your browser.

Or build locally for development:

docker build -t gale-shapley-algorithm .
docker run --rm -p 8000:8000 gale-shapley-algorithm

The GUI lets you:

Add and remove people on each side (proposers and responders)
Set preferences by drag-and-drop reordering
Randomize all preferences with one click
Run the matching and see results in a table with stability info
Animate step-by-step to watch proposals, rejections, and tentative matches unfold round by round in an SVG visualization
Upload images for each person to personalize the visualization
Toggle dark/light mode

Installation¶

pip install gale-shapley-algorithm

With CLI support:

pip install "gale-shapley-algorithm[cli]"

With numpy-backed primitives for large-scale / numerical work:

pip install "gale-shapley-algorithm[numeric]"

Quick Start¶

As a Library¶

import gale_shapley_algorithm as gsa

result = gsa.create_matching(
    proposer_preferences={
        "alice": ["bob", "charlie"],
        "dave": ["charlie", "bob"],
    },
    responder_preferences={
        "bob": ["alice", "dave"],
        "charlie": ["dave", "alice"],
    },
)
print(result.matches)  # {'alice': 'bob', 'dave': 'charlie'}

Numerical / large-scale usage¶

For high-throughput work (many random instances, enumerating the stable-matching lattice, using the output in downstream ML/RL pipelines), the numeric subpackage exposes numpy-array APIs:

import numpy as np
from gale_shapley_algorithm.numeric import (
    gale_shapley, gale_shapley_traced, men_optimal_gs, women_optimal_gs,
    men_optimal_traced, women_optimal_traced,
    lifo_selector, fifo_selector, random_selector,
    is_stable, find_blocking_pairs, enumerate_stable_matchings,
    exposed_rotations, apply_rotation,
)

# Rank matrices: men_rank[i, j] is woman j's 1-indexed position on man i's list.
men_rank   = np.array([[1, 2, 3], [3, 1, 2], [2, 3, 1]], dtype=np.int16)
women_rank = np.array([[3, 1, 2], [1, 3, 2], [2, 1, 3]], dtype=np.int16)

mo = men_optimal_gs(men_rank, women_rank)
lattice = enumerate_stable_matchings(men_rank, women_rank)  # (|L|, n) int16

# Step through the lattice manually via rotations:
for rotation in exposed_rotations(men_rank, women_rank, mo):
    next_matching = apply_rotation(mo, rotation)

# Traced variant: returns the matching plus per-proposer proposal counts,
# with a pluggable proposer-selection rule (LIFO, FIFO, random, or custom).
# The match and total proposal count are invariant under selector choice
# (Knuth) — use the hook to drive the loop from a custom policy.
stats = gale_shapley_traced(men_rank, women_rank)
print(stats.proposals, stats.proposals_per_proposer)

rng = np.random.default_rng(0)
_ = gale_shapley_traced(men_rank, women_rank, selector=random_selector(rng))

See examples/numeric_usage.py for a more complete walk-through. enumerate_stable_matchings defaults to the Gusfield-Irving rotation algorithm and scales past n=50; the brute-force method remains available via method="brute" as a correctness oracle for small instances.

As a CLI¶

The CLI uses interactive prompts -- no config files needed:

# Interactive mode: enter names and rank preferences
uvx --from "gale-shapley-algorithm[cli]" python -m gale_shapley_algorithm

# Random mode: auto-generate names and preferences
uvx --from "gale-shapley-algorithm[cli]" python -m gale_shapley_algorithm --random

# Swap proposers and responders
uvx --from "gale-shapley-algorithm[cli]" python -m gale_shapley_algorithm --swap-sides

Interactive mode example:

$ python -m gale_shapley_algorithm

  Gale-Shapley Algorithm

Enter proposer side name [Proposers]: Men
Enter responder side name [Responders]: Women

Enter names for Men (comma-separated): Will, Hampton
Enter names for Women (comma-separated): April, Summer

Ranking preferences for Men...

  Available for Will:
  1. April
  2. Summer
  Enter ranking for Will (e.g. 1,2): 1,2
  -> Will: April > Summer

  Available for Hampton:
  1. April
  2. Summer
  Enter ranking for Hampton (e.g. 1,2): 2,1
  -> Hampton: Summer > April

Ranking preferences for Women...
  ...

┌──────── Matching Result ────────┐
│ Men     │ Women                 │
├─────────┼───────────────────────┤
│ Will    │ April                 │
│ Hampton │ Summer                │
└─────────┴───────────────────────┘
Completed in 1 round. Stable: Yes

Random mode example:

$ python -m gale_shapley_algorithm --random

  Gale-Shapley Algorithm

Enter proposer side name [Proposers]: Cats
Enter responder side name [Responders]: Dogs
Number of Cats [3]: 3
Number of Dogs [3]: 3

  ... (random preferences generated and displayed) ...

Completed in 2 rounds. Stable: Yes

Development¶

This project is managed with uv and uses taskipy for task running.

git clone https://github.com/oedokumaci/gale-shapley-algorithm
cd gale-shapley-algorithm
uvx --from taskipy task setup   # Install dependencies
uvx --from taskipy task run     # Run the application
uvx --from taskipy task fix     # Auto-format + lint fix
uvx --from taskipy task ci      # Run all CI checks
uvx --from taskipy task test    # Run tests
uvx --from taskipy task docs    # Serve docs locally