RESOURCE

Deferred Acceptance and Gale-Shapley Algorithm

Matching Introduction

How to bring different players together in the best possible way is a key problem in economics. Traditional markets use money as a signal of value, and goods or services are allocated to those willing to pay the most. Classical economics says the market will clear at the price at which the willingness to produce (supply) equals the marginal willingness to pay (demand).

But what about markets without money?

These scarce resources are allocated through a “matching process.” In his book, Who Gets What and Why, Al Roth notes that “A market involves matching whenever price isn’t the only determinant of who gets what.”

He goes on to explain, “Matching is economist-speak for how we get the many thing we choose in life that also must choose us. You can’t just inform Yale University that you’re enrolling or Google that you’re showing up for work. You also have to be admitted or hired. Neigher can Yale or Google dictate who will come to them…”

Dating and marriage is an easily understood archetype of a matching market, one which led to one of the most famous thought experiments in economics.

The Stable Marriage Problem

Beginning in the mid-1900s, David Gale and Lloyd Shapley studied different matching methods theoretically and were the first to define an algorithmic approach to optimal allocation. They began with an theoretical approach grounded in an approachable subject - dating.

The problem they proposed is known as the “Stable Marriage Problem,” often generalized as the “Stable matching problem” or “SMP”. They asked if it would be possible to match two equally sized groups of men and women together in a way that no two people would prefer each other over their matched partners. (This problem was devised in the 1950s and is unfortunately heteronormative, our apologies.) They called this property “stability,” which relates closely to the concept of Nash Equilibrium and Pareto Optimality.

In 1963, Gale and 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 Deferred Acceptance Algorithm, now often known as the Gale-Shapley Algorithm. This algorithm is guaranteed to produce a stable marriage for all participants.

The Gale-Shapley Algorithm

Properties

  • Strategy Proof (Truthful Mechanism)

  • Deterministic

  • Transparent and Auditable

  • Efficient - O(n^2), but no training.

Related Problems

The Latest Science on Matching

Nobel Prize.png

Beginning in the 1980s, Al Roth built on their work and explained how markets function in practice. Shapley and Roth won the Nobel Prize for their work in 2012.

Since then, the field has been led by Tayfun Sönmez, Atila Abdulkadiroglu, and our co-founders, Parag Pathak and Josh Angrist. They expanded on the field by applying the science of matching to more complex real world scenarios - everything from medical treatments to school assignments to military deployments to talent placement.

Avela is the only company we know of that is focused on solving matching problems. We offer the only software platform purpose built to solve matching problems, as well as a range of advisory services. And while we’re used the most in education, our tool can be used across industries.

Examples of Matching

We maintain an extensive list of matching markets here.