game_theory.md

Game theory

Table of contents

• Stable marriage problem
  • Gale–Shapley algorithm

---

Stable marriage problem

Problem: given n men and n women, where each person has ranked all members of the opposite sex in order of preference, marry the men and women together such that there are no two people of opposite sex who would both rather have each other than their current partners.

📝

• This problem is also known as the stable matching problem.

🔗

• Stable marriage problem – Wikipedia

🎥

• Stable marriage problem. Part I, Part II – Numberphile (2014)
• The stable matching algorithm: Examples and implementation – The Simple Engineer (2017)

📖

• D.E.Knuth. Stable marriage and its relation to other combinatorial problems: An introduction to the mathematical analysis of algorithms (1996)

📄

• H.Mairson. The stable marriage problem – The Brandeis Review 12, 38 (1992)

Gale–Shapley algorithm

🔗

• D.Austin. The stable marriage problem and school choice – AMS Feature column (2015)
• Stable marriage problem – Rosetta Code

📄

• D.Gale, L.S.Shapley. College admissions and the stability of marriage – American Mathematical Monthly 69, 9 (1962)