It is commonly stated as:

In 1962, David Gale and Lloyd Shapley proved that, for any equal number of men and women, it is always possible to solve the SMP and make all marriages stable. They presented an algorithm to do so.

The Gale-Shapley algorithm involves a number of "rounds" (or "iterations") where each unengaged man "proposes" to the most-preferred woman to whom he has not yet proposed. Each woman then considers all her suitors and tells the one she most prefers "Maybe" and all the rest of them "No". She is then provisionally "engaged". In each subsequent round, each unengaged man proposes to the most-preferred woman to whom he has not yet proposed (the woman may or may not already be engaged), and the women once again reply with one "maybe" to the most-preferred suitor and reject the rest (including for consideration her current partner). This may mean that already-engaged women can "trade up", and already-engaged men can be "jilted".

This algorithm guarantees that:

While the solution is stable, it is not necessarily optimal from all individuals' points of view. The traditional form of the algorithm is optimal for the initiator of the proposals and the stable, suitor-optimal solution may or may not be optimal for the reviewer of the proposals. An informal proof by example is as follows:

There are three suitors (A,B,C) and three reviewers (X,Y,Z) which have preferences of:

There are 3 stable solutions to this matching arrangement:

All three are stable because instability requires both participants to be happier with an alternative match. Giving one group their first choices ensures that the matches are stable because they would be unhappy with any other proposed match. Giving everyone their second choice ensures that any other match would be disliked by one of the parties. The algorithm converges in a single round on the suitor-optimal solution because each reviewer receives exactly one proposal, and therefore selects that proposal as its best choice, ensuring that each suitor has an accepted offer, ending the match. This asymmetry of optimality is driven by the fact that the suitors have the entire set to choose from, but reviewers choose between a limited subset of the suitors at any one time.

There are a number of real world applications for the Gale-Shapley solution. For example, their algorithm has been used to pair graduating medical students with hospital jobs.

The weighted matching problem seeks to find a matching in a weighted bipartite graph that has maximum weight. Maximum weighted matchings do not have to be stable, but in some applications a maximum weighted matching is better than a stable one.