What is a stable matching?

A matching is considered stable if there is no pair of participants who would both prefer each other over their current assigned partners.

Is this implementation proposer-optimal or acceptor-optimal?

The provided Gale-Shapley algorithm is proposer-optimal, meaning the side initiating the proposals receives the best possible partner they can get in any stable matching.

Can this be used for one-sided assignments?

No, this skill is specifically for two-sided markets. For one-sided assignments, such as assigning tasks to workers, the Hungarian algorithm is typically more appropriate.

What is the time complexity of the match-stable-pairs skill?

The implementation follows an O(n^2) time complexity, where each proposer proposes to each acceptor at most once, making it efficient for most real-world matching scenarios.

Stable Matching & Gale-Shapley

Name: Stable Matching & Gale-Shapley
Author: jimmc414

byjimmc414

•

Data Science & ML

Implements the Gale-Shapley algorithm to solve stable matching problems for two-sided markets like residency and admissions.

This skill provides specialized implementation patterns for the Gale-Shapley algorithm, the gold standard for solving stable marriage and two-sided matching problems. It allows Claude to generate robust, stable matching logic where no two entities would prefer to be paired with each other over their current assignments. Based on Peter Norvig's algorithmic patterns, it is ideal for building systems for hospital-resident matching, college admissions, and automated recruitment platforms where preference-based stability is critical.

Key Features

01Proposer-optimal Gale-Shapley implementation

02Efficient O(n^2) time complexity patterns

03Support for strict preference ordering

04Optimized preference lookup via pre-sorting

05Guaranteed stable matching with no blocking pairs

061 GitHub stars

Use Cases

01Implementing automated college admissions and school choice placements

02Designing medical residency and hospital-resident matching systems

03Building job candidate matching platforms for two-sided recruitment markets

What are Skills?·How to Install

Install with 🐟 Skill.Fish

npx skillfish add jimmc414/claude-code-plugin-marketplace match-stable-pairs

For use in Claude.ai and ChatGPT

Download Skill