A novel application of the Stable Marriage (Gale-Shapley) algorithm to the real-world problem of optimally matching unemployed individuals to training courses or job positions, maximizing skill overlap and overall satisfaction.
- Overview
- Background & Motivation
- How It Works
- Algorithm
- Repository Structure
- Getting Started
- Example Output
- Extending the Model
- Use Cases
- Citation
- Contributing
- License
This project implements a skill-based stable matching system that:
- Models job seekers/students as employees with skill sets.
- Models training courses or employers as positions with skill requirements.
- Builds preference lists derived from skill-overlap scoring (Jaccard-inspired intersection).
- Runs the Gale-Shapley algorithm to compute a stable, optimal matching.
- Reports a happiness index to quantify the quality of the overall assignment.
The approach guarantees stability — no pair of a job seeker and a position would both prefer each other over their current match — and it is optimal from the proposers' perspective.
Every year, public employment agencies face the challenge of allocating thousands of unemployed individuals into limited training course seats. Ad-hoc or random assignments lead to poor outcomes: candidates drop out when they lack prerequisite skills, and courses fill seats with under-qualified attendees.
This work formalizes the assignment problem as a two-sided matching market:
| Side A (Proposers) | Side B (Reviewers) |
|---|---|
| Job seekers / students | Training courses / employers |
| Ranked by: skill match with available positions | Ranked by: skill match with candidate profiles |
The Gale-Shapley (1962) algorithm — originally designed for the Stable Marriage Problem and awarded the 2012 Nobel Prize in Economics — provides a polynomial-time solution with provably optimal stability guarantees.
[Candidates] [Positions]
Jorge ──────────► Microsoft
Mario ──────────► Apple
Martin ─────────► IBM
Lorena ─────────► Adobe
Step 1 – Skill Profiling: Each candidate has a list of known programming languages / skills.
Step 2 – Preference Computation: For each candidate–position pair, the number of overlapping skills is counted. Preferences are ranked by descending overlap score.
Step 3 – Gale-Shapley Matching: Candidates propose to their most preferred position; positions tentatively accept the best candidate seen so far. Rejected candidates move to their next preference. The process repeats until all are matched.
Step 4 – Happiness Index: The sum of ranking positions in each party's preference list — lower is better, indicating matches closer to everyone's top choices.
The core algorithm is Gale-Shapley (Deferred Acceptance):
While ∃ free candidate who has not proposed to all positions:
candidate c proposes to their top remaining position p
if p is free:
(c, p) become tentatively engaged
else if p prefers c over its current partner c':
(c, p) become tentatively engaged
c' becomes free again
else:
c remains free, p stays with c'
Complexity: O(n²) — runs in quadratic time with respect to the number of agents.
Stability guarantee: The resulting matching is always stable (no blocking pair exists) and optimal for the proposing side.
stable-marriage/
├── Python version/
│ └── app.py # Full Python implementation
├── Java version/
│ └── src/ # Java source files
├── examples/
│ └── demo.py # Standalone runnable demo
├── CONTRIBUTING.md # Guidelines for contributors
├── LICENSE # GNU GPL v3
└── README.md # This file
Requirements: Python 3.7+
No external dependencies — only the Python standard library.
# Clone the repository
git clone https://github.com/jorge-martinez-gil/stable-marriage.git
cd stable-marriage
# Run the Python demo
python "Python version/app.py"Or run the standalone example:
python examples/demo.pyRequirements: Java 8+
# Navigate to Java source
cd "Java version/src"
# Compile
javac *.java
# Run
java Main=== Initial Matching ===
Matches: {'microsoft': 'jorge', 'ibm': 'mario', 'apple': 'martin', 'adobe': 'lorena'}
Happiness Index: 6
=== After Adding Skill 'Julia' to All Candidates ===
Matches: {'microsoft': 'jorge', 'apple': 'martin', 'ibm': 'mario', 'adobe': 'lorena'}
Happiness Index: 6
The happiness index reflects the aggregate rank satisfaction — a lower value means matches are closer to everyone's first choice.
You can easily adapt this codebase to your own domain:
# In app.py, add a new candidate
Stable.skills_alice = ["Python", "Django", "Docker"]
Stable.employees.append("alice")The default scoring counts raw skill intersection. You can replace it with:
- Jaccard similarity:
|A ∩ B| / |A ∪ B| - Weighted overlap: assign weights to in-demand skills
- Cosine similarity on skill vectors
| Original Domain | Alternative Application |
|---|---|
| Job seekers → Employers | Students → Universities |
| Unemployed → Training courses | Doctors → Hospitals |
| Freelancers → Projects | Researchers → Grants |
- 🏛️ Public employment services optimally assigning citizens to upskilling programmes
- 🎓 University admissions matching students to programmes by academic profile
- 🏥 Residency matching (cf. NRMP — the National Resident Matching Program uses the same algorithm)
- 🤝 Talent acquisition platforms ranking candidates against open roles
- 📚 Recommender systems for online learning (MOOCs)
If you use this code or build upon this work, please cite the original paper:
Jorge Martinez-Gil, Bernhard Freudenthaler. Optimal Selection of Training Courses for Unemployed People based on Stable Marriage Model. Proceedings of the 21st International Conference on Information Integration and Web-based Applications & Services (iiWAS 2019), Munich, Germany, December 2–4, 2019. Pages 260–266. ACM.
🔗 DOI: 10.1145/3366030.3366063
@inproceedings{martinez2019stable,
author = {Jorge Martinez-Gil and
Bernhard Freudenthaler},
title = {Optimal Selection of Training Courses for Unemployed People based
on Stable Marriage Model},
booktitle = {Proceedings of the 21st International Conference on Information Integration
and Web-based Applications {\&} Services, iiWAS 2019, Munich,
Germany, December 2-4, 2019},
pages = {260--266},
publisher = {{ACM}},
year = {2019},
url = {https://doi.org/10.1145/3366030.3366063},
doi = {10.1145/3366030.3366063}
}The Stable Marriage / Stable Matching problem has broad applications across computer science and economics:
- Gale, D. & Shapley, L. S. (1962). College Admissions and the Stability of Marriage. American Mathematical Monthly, 69(1), 9–15.
- Roth, A. E. (1984). The evolution of the labor market for medical interns and residents: a case study in game theory. Journal of Political Economy, 92(6), 991–1016.
- Roth, A. E. & Sotomayor, M. (1990). Two-Sided Matching: A Study in Game-Theoretic Modeling and Analysis. Cambridge University Press.
Contributions are welcome! Please read CONTRIBUTING.md for guidelines on how to:
- Report bugs or suggest features via Issues
- Submit a pull request
- Add a new language implementation
- Improve documentation
This project is licensed under the GNU General Public License v3.0 — see the LICENSE file for details.
You are free to use, modify, and distribute this software, provided that derivative works are also distributed under the same license.
Made with ❤️ for research and social good · Read the Paper