Hexo

The Gale Shapley Algorithm (Deferred Acceptance Algorithm or DAA)

The DAA algorithm for one to one matching is a stable matching algorithm that is guaranteed to find a stable matching for any set of preferences.
While the one to one matching is well known, the many to many matching is not as well known.
The many to many matching is a generalization of the one to one matching, where each agent can be matched to multiple agents.

Code

Blair matching and DAA matching notebooks at:
https://github.com/FranciscoRMendes/matching-algorithms

Fixed Points of Many to Many matching

Define the rejection functions

Define the map
This map is a
recursive function on the underlying sets, like so .
Example of iteration,

Claim : The fixed points of are a stable matching.

Worked Out Example Many to Many DAA Matching

Workers



Firms



Step 1:






Step 2:






Step 3:





\