Simplify Your Workflow: Search MiniWebtool.
Add Extension
Home Page > Math > Advanced Math Operations > Stable Marriage Problem Solver

Stable Marriage Problem Solver

Solve the stable marriage / stable matching problem using the Gale-Shapley algorithm. Paste ranked preference lists for two equally-sized groups and get the guaranteed-stable pairing, with an animated proposal-by-proposal trace, satisfaction statistics, blocking-pair verification, and an interactive bipartite visualization.

Stable Marriage Problem Solver
Quick examples:
Classic 3×3 Residency match Textbook P/R 5×5 teams 4×4 (B proposes)
A
One line per member: Name: Pref1, Pref2, ... — list every Group B member in preference order.
B
Same format. Each Group B member ranks all Group A members.
In Gale-Shapley, the proposing side gets their best possible stable partner; the receiving side gets their worst.

Embed Stable Marriage Problem Solver Widget

About Stable Marriage Problem Solver

The Stable Marriage Problem Solver is an interactive implementation of the Gale-Shapley deferred-acceptance algorithm, the 1962 matching algorithm that David Gale and Lloyd Shapley proved always produces a stable pairing between two equally-sized groups given each member's full ranking of the other side. This tool takes your preference lists, runs the algorithm step by step, and shows the result as a stable matching, an animated bipartite visualization, preference heatmaps, and a verified proof that no blocking pair exists.

What Is the Stable Marriage Problem?

Given two disjoint sets of equal size — say n men and n women, or n applicants and n positions — and a complete preference list from every member ranking every member of the other side, a matching is a one-to-one pairing between the two sets. The matching is called stable if no pair (a, b) outside the matching would both rather be together than stay with their assigned partners.

Formally, a matching M is stable if there is no blocking pair — a pair (a, b) with a matched to b' and b matched to a' such that:

a prefers b to b' AND b prefers a to a'

If both conditions hold, both a and b would abandon their current partners, which destabilises the matching. A stable matching is one where no such pair exists.

The Gale-Shapley Algorithm

Gale and Shapley proved — constructively — that a stable matching always exists for any set of preferences, and they gave an efficient algorithm to find one. The algorithm runs in rounds:

  1. Every unengaged proposer proposes to the highest-ranked receiver on their list who has not yet rejected them.
  2. Each receiver who got one or more proposals picks the one they prefer most (compared against any current tentative fiancé) and tentatively accepts; everyone else is rejected.
  3. Rejected proposers become free again and move on to their next choice in the following round.
  4. The algorithm terminates when every proposer is engaged — which is guaranteed to happen in at most n² proposals.
Time complexity: O(n²) Space complexity: O(n²) Proposals before termination: at most n²

Key Theoretical Properties

Existence & Uniqueness

A stable matching always exists (Gale & Shapley, 1962), but is not necessarily unique. For a given preference set there can be multiple stable matchings, and they form a lattice ordered by joint preference.

Proposer Optimality

When one side proposes, Gale-Shapley produces the proposer-optimal stable matching: every proposer receives the best partner they could possibly be paired with in any stable matching. By a symmetric argument, this is also the receiver-pessimal matching — the receiving side gets their worst stable partner. Switching the proposing side in this calculator often changes the result.

Strategy Proofness for Proposers

Under Gale-Shapley, proposers have no incentive to misreport their preferences: telling the truth is a dominant strategy for them. Receivers, however, can sometimes benefit from strategic misreporting — one of the reasons the hospital-residents market in the US is designed with students as the proposing side.

Rural Hospitals Theorem

The set of unmatched agents is identical across all stable matchings. So if your instance has unbalanced sizes (beyond the scope of this classic tool) the same people will be unmatched in every stable solution.

Input Format

This calculator expects one line per member, with name followed by a colon and a full ranked preference list separated by commas:

Name1: first choice, second choice, third choice, ..., last choice Name2: first choice, second choice, ... ...

Requirements:

How to Use This Calculator

  1. Enter preferences for Group A in the left text area — one line per member, full ranked list.
  2. Enter preferences for Group B in the right text area — one line per member, same format.
  3. Pick the proposing side. Choose Group A or Group B. Try both to compare the A-optimal vs B-optimal outcomes.
  4. Click "Solve Stable Matching." The calculator runs Gale-Shapley and produces the stable pairs, statistics, animation, and proof of stability.
  5. Scrub the animation with the play / step / reset controls to see every proposal, acceptance, swap, and rejection in order.
  6. Inspect the heatmap. Each cell shows the ranking; the yellow-outlined cells form the final matching — look at how high or low those cells sit to see how "happy" each side is.

Worked Example — The Classic 3×3

Men: Alex, Bryan, Chris. Women: Bea, Claire, Diana. Preferences:

Alex: Bea, Claire, Diana Bryan: Claire, Bea, Diana Chris: Diana, Bea, Claire Bea: Bryan, Alex, Chris Claire: Alex, Bryan, Chris Diana: Chris, Bryan, Alex

Running Gale-Shapley with men proposing yields Alex–Bea, Bryan–Claire, Chris–Diana in a single round (every man's first choice matches a woman whose first choice is someone else — no conflict). The matching is stable: no man-woman pair would both be better off swapping partners, so there is no blocking pair.

Real-World Applications

Application Group A Group B Who proposes
NRMP Residency Match (US) Medical students Hospital programs Students — designed to be student-optimal since 1998
NYC / Boston School Choice Families Public schools Families — replaced a strategic-gaming mechanism in the 2000s
College Admissions Applicants Universities Originally Gale-Shapley's motivating example
Kidney Exchange Donor-recipient pairs Other donor-recipient pairs Specialized cycle-finding extension of matching theory
Dating & Roommate Matching Users Potential partners Consumer apps often use simplified versions of the same idea

Why Lloyd Shapley Won a Nobel Prize

In 2012 the Royal Swedish Academy of Sciences awarded the Nobel Prize in Economics to Lloyd Shapley (for the theory, alongside David Gale who had passed away) and Alvin Roth (for applying the theory to real markets, including redesigning the US medical residency match and kidney exchange networks). The award cited "the theory of stable allocations and the practice of market design."

Frequently Asked Questions

What is the stable marriage problem?

The stable marriage problem asks: given two equally-sized groups where each member ranks all members of the other group from most to least preferred, can we pair everyone up so that no two people would both prefer to leave their current partners for each other? Such a pairing is called a stable matching. The Gale-Shapley algorithm solves this problem in O(n²) time and always finds a stable matching.

How does the Gale-Shapley algorithm work?

The Gale-Shapley deferred-acceptance algorithm proceeds in rounds. In each round, every currently-unengaged proposer proposes to the highest-ranked receiver on their list who has not yet rejected them. Each receiver tentatively accepts the best proposal received so far and rejects the rest; any displaced proposer becomes free again. The algorithm terminates when no proposer is free, which happens in at most n² proposals.

Is the stable matching unique?

No. A stable matching instance can have many stable matchings. However, when one side proposes, Gale-Shapley always produces the proposer-optimal stable matching: every proposer gets the best partner they could possibly get in any stable matching. By symmetry, this is also the receiver-pessimal matching for the other side. Switching the proposing side often yields a different stable matching.

What is a blocking pair?

A blocking pair is a pair (a, b) that is not currently matched where a prefers b to their current partner AND b also prefers a to their current partner. If any blocking pair exists, the matching is unstable because those two would rather pair up with each other. A stable matching has no blocking pairs, which this calculator verifies automatically after each solve.

What are real applications of stable matching?

The Gale-Shapley algorithm powers the National Resident Matching Program that assigns medical students to residencies in the United States, school-choice systems in Boston and New York, college admissions in several countries, organ-donor kidney exchange chains, and roommate-assignment systems. Lloyd Shapley and Alvin Roth won the 2012 Nobel Prize in Economics partly for this work.

Do both groups need to be the same size?

In the classical stable marriage formulation, yes. Both sides must have the same number of members and each must provide a complete ranking of the other side. Unbalanced variants (such as the stable matching with incomplete lists or the hospital-residents problem) exist but require modified algorithms. This calculator enforces equal sizes and complete preference lists.

Further Reading

Reference this content, page, or tool as:

"Stable Marriage Problem Solver" at https://MiniWebtool.com/stable-marriage-problem-solver/ from MiniWebtool, https://MiniWebtool.com/

by miniwebtool team. Updated: Apr 22, 2026

You can also try our AI Math Solver GPT to solve your math problems through natural language question and answer.

Related MiniWebtools:

Adjacency Matrix CalculatorNew
Age Word Problem SolverNew
Angle Between Vectors CalculatorNew
Coin Word Problem SolverNew
Distance Between Two Points Calculator
Factor Calculator
Fraction CalculatorFeatured
Long Division CalculatorNew
Mixture Problem SolverNew
Percentage Calculator

Advanced Math Operations:

Top & Updated:

Random Name PickerRandom PickerInstagram User ID LookupFPS ConverterImage ResizerLine CounterSort NumbersRelative Standard Deviation CalculatorRemove SpacesRandom Truth or Dare GeneratorBatting Average CalculatorMAC Address GeneratorFacebook User ID LookupERA CalculatorFeet and Inches to Cm ConverterWord to Phone Number ConverterMAC Address LookupSun, Moon & Rising Sign Calculator 🌞🌙✨Slope and Grade CalculatorMP3 LooperSum CalculatorRandom Superpower GeneratorPercent Off CalculatorRandom IMEI Generator📷 OCR / Image to TextAudio SplitterRandom Quote GeneratorInvisible Text GeneratorWord Ladder GeneratorBitwise CalculatorNumber of Digits CalculatorVertical Jump CalculatorRoman Numerals ConverterSHA256 Hash GeneratorRandom Credit Card GeneratorAI Text HumanizerMerge VideosRandom Birthday GeneratorLog Base 10 CalculatorWAR CalculatorHalfway Date Calculator⬛ Aspect Ratio CalculatorMaster Number CalculatorCm to Feet and Inches ConverterSalary Conversion CalculatorPhone Number ExtractorRandom Meal GeneratorRandom Activity GeneratorSaturn Return CalculatorRandom Fake Address GeneratorFile Size ConverterOPS CalculatorNumber to Word ConverterIP Subnet CalculatorText FormatterSquare Root (√) CalculatorOn Base Percentage CalculatorRandom Poker Hand GeneratorRandom Writing Prompt GeneratorYouTube Channel StatisticsRandom Movie PickerSlugging Percentage CalculatorCaffeine Overdose CalculatorMercury Retrograde CalendarDecimal to BCD ConverterCompound Growth CalculatorLove Compatibility CalculatorVideo to Image ExtractorBattery Life CalculatorRandom Loadout GeneratorBCD to Decimal ConverterBinary to Gray Code ConverterStair CalculatorLeap Years List🖱️ Click CounterOctal CalculatorDNS LookupAdd Text to Image🎰 Gacha Pity CalculatorCM to Inches ConverterFirst n Digits of PiRandom Time GeneratorConnect the Dots GeneratorCompare Two Strings📅 Date CalculatorWeight Loss CalculatorSHA512 Hash GeneratorRemove AccentNumber ExtractorBingo Card GeneratorVideo CompressorProportion CalculatorImage SplitterAstrological Element Balance CalculatorImage CompressorPercent Growth Rate CalculatorOutlier CalculatorGray Code to Binary ConverterSmall Text Generator ⁽ᶜᵒᵖʸ ⁿ ᵖᵃˢᵗᵉ⁾Lottery Number GeneratorTime Duration CalculatorPER CalculatorCoin FlipperWhat is my Zodiac Sign?Arc Length CalculatorQuotient and Remainder CalculatorRandom Object GeneratorDiff CheckerDay of the Year Calculator - What Day of the Year Is It Today?Word Scramble GeneratorLongest Day of the YearAcreage CalculatorAdd Prefix and Suffix to TextBreak Line by CharactersFlip VideoList of Prime NumbersRandom Emoji GeneratorBolt Torque CalculatorWHIP CalculatorIP Address to Hex ConverterMultiple Fraction CalculatorURL ExtractorAngel Number CalculatorYouTube Tag ExtractorName Number CalculatorMandelbrot Set ExplorerModulo Calculator🔍 Plagiarism CheckerBcrypt Hash Generator / CheckerCone Flat Pattern (Template) GeneratorVideo SplitterPregnancy CalendarBroken Link CheckerMiter Angle CalculatorTessellation GeneratorDay of Year CalendarMD5 Hash GeneratorEmail ExtractorAI Language DetectorRandom Chord GeneratorSteel Weight CalculatorWhat is my Lucky Number?Social Media Username CheckerAntilog CalculatorLong Division CalculatorLunar Calendar ConverterSun Position CalculatorRandom Chess Opening GeneratorRandom Number PickerBinary to BCD ConverterMolarity CalculatorMartingale Strategy CalculatorRandom Line PickerHeight Percentile CalculatorMultiplication CalculatorIs it a Prime Number?Short Selling Profit CalculatorArctan2 CalculatorRandom Tournament Bracket GeneratorDMS to Decimal Degrees ConverterPercentile CalculatorFirst n Digits of eAI Punctuation AdderCollage MakerMorse Code GeneratorRounding CalculatorBonus CalculatorYouTube Earnings EstimatorRandom Name GeneratorRandom User-Agent GeneratorTaco Bar Calculator🔊 Tone GeneratorRemove Leading Trailing SpacesAdjust Video SpeedHypotenuse CalculatorRandom Group GeneratorHTML CompressorBoiling Point CalculatorRandomize NumbersReverse TextAPI TesterFraction CalculatorAI ParaphraserDue Date CalculatorLife Path Number CalculatorJulia Set GeneratorSquare Numbers ListColor InverterPVIF CalculatorPVIFA CalculatorCrossword Puzzle MakerRandom RPG Character GeneratorBirth Day of the Week CalculatorIncome Tax CalculatorHebrew Calendar ConverterGrade CalculatorSum of Positive Integers CalculatorExponential Decay CalculatorSort Lines AlphabeticallyHex to BCD ConverterBCD to Binary ConverterBCD to Hex ConverterMedian CalculatorStandard Error CalculatorList RandomizerAverage CalculatorReverse VideoRemove Audio from VideoActual Cash Value CalculatorScientific Notation to Decimal ConverterLog Base 2 CalculatorRoot Mean Square CalculatorSHA3-256 Hash GeneratorAI Sentence ExpanderLbs to Kg ConverterHex to Decimal ConverterConvolution CalculatorMAC Address AnalyzerRandom String GeneratorAmortization CalculatorMarkup CalculatorDecimal to Hex ConverterInstagram Font GeneratorSocial Media Image Size GuideTikTok Money CalculatorTwitter/X Character CounterTwitter/X Timestamp ConverterYouTube Watch Time CalculatorTwitch Earnings CalculatorYouTube Shorts Monetization CalculatorFacebook Ad Cost CalculatorSocial Media ROI CalculatorSocial Media Post Time OptimizerCTR CalculatorROAS CalculatorInfluencer ROI CalculatorForce CalculatorAcceleration CalculatorVelocity CalculatorMomentum CalculatorProjectile Motion CalculatorKinetic Energy CalculatorPotential Energy CalculatorWork and Power CalculatorDensity CalculatorPressure CalculatorIdeal Gas Law CalculatorFree Fall CalculatorTorque CalculatorHorsepower CalculatorDilution CalculatorChemical Equation BalancerStoichiometry CalculatorPercent Yield CalculatorEmpirical Formula CalculatorTitration CalculatorMole/Gram/Particle ConverterIrregular Polygon Area CalculatorFrustum CalculatorTorus Calculator3D Distance CalculatorGreat Circle Distance CalculatorCircumscribed Circle (Circumcircle) CalculatorInscribed Circle (Incircle) CalculatorAngle Bisector CalculatorTangent Line to Circle CalculatorHeron's Formula CalculatorCoordinate Geometry Distance CalculatorVolume of Revolution CalculatorSurface of Revolution CalculatorParametric Curve GrapherRiemann Sum CalculatorTrapezoidal Rule CalculatorSimpson's Rule CalculatorImproper Integral CalculatorL'Hôpital's Rule CalculatorMaclaurin Series CalculatorPower Series CalculatorSeries Convergence Test CalculatorInfinite Series Sum CalculatorAverage Rate of Change CalculatorInstantaneous Rate of Change CalculatorRelated Rates SolverOptimization Calculator (Calculus)Gradient Calculator (Multivariable)Divergence CalculatorCurl CalculatorLine Integral CalculatorSurface Integral CalculatorJacobian Matrix CalculatorNewton's Method CalculatorRREF Calculator (Row Echelon Form)Matrix Inverse CalculatorMatrix Multiplication CalculatorDot Product CalculatorCross Product CalculatorVector Magnitude CalculatorUnit Vector CalculatorAngle Between Vectors CalculatorNull Space CalculatorColumn Space CalculatorCramer's Rule CalculatorMatrix Diagonalization CalculatorQR Decomposition CalculatorCholesky Decomposition CalculatorMatrix Power CalculatorCharacteristic Polynomial CalculatorBayes' Theorem CalculatorF-Test / F-Distribution CalculatorHypergeometric Distribution CalculatorNegative Binomial Distribution CalculatorGeometric Distribution CalculatorExponential Distribution CalculatorWeibull Distribution CalculatorBeta Distribution CalculatorSpearman Rank Correlation CalculatorFisher's Exact Test CalculatorContingency Table CalculatorOdds Ratio CalculatorROT13 Encoder/DecoderAtbash Cipher ToolVigenère Cipher ToolPronunciation IPA ConverterHemingway-Style Readability EditorSentence Length Variance AnalyzerWord Frequency AnalyzerBusiness Days CalculatorAdd Business Days to DateDate Pattern GeneratorHow Long Until CalculatorHow Long Ago CalculatorBirthday Across Cultures CalculatorHijri Calendar ConverterInsulin Sensitivity Factor CalculatorCarb-to-Insulin Ratio CalculatorLean Body Mass to Strength CalculatorOne-Mile Walk Test (Rockport) CalculatorCooper 12-Minute Run CalculatorFFMI CalculatorAPGAR Score CalculatorGlasgow Coma Scale CalculatorWells Score Calculator (DVT/PE)Tennis Score TrackerSoccer xG (Expected Goals) CalculatorCricket Run Rate CalculatorRugby Points CalculatorBoxing Punch Power CalculatorRace Time PredictorSwimming SWOLF CalculatorYoga Pose Hold TimerFishing Knot Strength CalculatorBike Gear Ratio CalculatorClimbing Grade ConverterWine Pairing SuggesterStandard Drink CalculatorCaffeine Half-Life TrackerSpice Substitution FinderDietary Restriction Recipe FilterMarinade Time CalculatorFermentation Time CalculatorSmoking Wood Pairing GuideFreelance Project Pricing CalculatorSaaS Pricing CalculatorSubscription Cost TrackerSide Hustle ROI CalculatorRemote Work Savings CalculatorCoffee Habit Cost CalculatorGym vs Home Workout Cost CalculatorLunch Cost CalculatorWealth Growth Visualizer1031 Exchange CalculatorRental Yield CalculatorCash-on-Cash Return CalculatorBRRRR Method CalculatorSection 8 Rent CalculatorRoommate Rent SplitterAirbnb Pricing OptimizerStatute of Limitations CalculatorSentence Reduction CalculatorSales Tax Nexus CheckerPatent Filing Fee CalculatorTrademark Class FinderWill Asset Distribution CalculatorWorkers' Compensation CalculatorStopping Distance CalculatorTrip Cost SplitterVehicle Weight Distribution CalculatorTrailer Tongue Weight CalculatorTire Tread Wear CalculatorEngine Compression Ratio CalculatorHeadlight Beam Distance CalculatorCat Litter Box CalculatorAquarium Heater Wattage CalculatorBird Cage Size CalculatorReptile Habitat UVB CalculatorPet Travel Crate Size FinderHorse Hay CalculatorCrochet Hook Size ConverterKnitting Needle Size ConverterKnitting Pattern CalculatorCross-Stitch Floss CalculatorQuilt Binding CalculatorOrigami Paper Size CalculatorPottery Clay Shrinkage CalculatorBeading Pattern CalculatorResin Casting Volume CalculatorEmbroidery Thread Length CalculatorHiking Pace Calculator (Naismith's Rule)Backpacking Food Weight CalculatorTent Footprint Size CalculatorSleeping Bag Temperature Rating GuideKnot Tying Reference ToolStar Visibility CalculatorTide Time CalculatorReynolds Number CalculatorBernoulli Equation CalculatorHeat Transfer CalculatorThermal Expansion CalculatorSpecific Heat Capacity CalculatorGear Ratio Calculator (Mechanical)Pulley System CalculatorHydraulic Cylinder Force CalculatorBelt Length CalculatorCloset Capsule CalculatorStorage Unit Size CalculatorMoving Box Quantity CalculatorGift Card Tip CalculatorGas vs Electric Cost ComparisonPrint Cost CalculatorHair Dye Mixing CalculatorLaundry Detergent Dosage CalculatorDishwasher Load OptimizerTile Grout CalculatorPaint Color Mixing CalculatorFlashcard Spaced Repetition SchedulerLearning Curve CalculatorCornell Notes GeneratorVocabulary Quiz GeneratorLanguage Learning Hours to Fluency CalculatorCollege Cost CalculatorScholarship ROI CalculatorAI Recipe Generator (From Ingredients)AI Gift Idea GeneratorAI Meal Plan GeneratorAI Workout Plan GeneratorAI Reading List Generator