Skip to content

Instantly share code, notes, and snippets.

@subpath

subpath/Gale-Shapley.ipynb

Last active November 16, 2023 22:07
Show Gist options
  • Save subpath/fac948b8fa18d0e5a539348231d14915 to your computer and use it in GitHub Desktop.
Save subpath/fac948b8fa18d0e5a539348231d14915 to your computer and use it in GitHub Desktop.
Download ZIP
Gale-Shapley algorithm
Display the source blob
Display the rendered blob
Raw
Gale-Shapley.ipynb
{
"cells": [
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Populating the interactive namespace from numpy and matplotlib\n"
]
}
],
"source": [
"%pylab inline\n",
"import pandas as pd\n",
"import numpy as np\n",
"from collections import Counter\n",
"from copy import copy"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Define men and women data frames"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [],
"source": [
"man_list = ['a', 'b', 'c', 'd']\n",
"women_list = ['A', 'B', 'C', 'D']"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [],
"source": [
"women_df = pd.DataFrame({'A': [3,4,2,1], 'B': [3,1,4,2], 'C':[2,3,4,1], 'D':[3,2,1,4]})\n",
"women_df.index = man_list"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [],
"source": [
"man_df = pd.DataFrame({'A': [1,1,2,4], 'B': [2,4,1,2], 'C':[3,3,3,3], 'D':[4,2,4,1]})\n",
"man_df.index = man_list"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [
{
"data": {
"text/html": [
"<div>\n",
"<style scoped>\n",
" .dataframe tbody tr th:only-of-type {\n",
" vertical-align: middle;\n",
" }\n",
"\n",
" .dataframe tbody tr th {\n",
" vertical-align: top;\n",
" }\n",
"\n",
" .dataframe thead th {\n",
" text-align: right;\n",
" }\n",
"</style>\n",
"<table border=\"1\" class=\"dataframe\">\n",
" <thead>\n",
" <tr style=\"text-align: right;\">\n",
" <th></th>\n",
" <th>A</th>\n",
" <th>B</th>\n",
" <th>C</th>\n",
" <th>D</th>\n",
" </tr>\n",
" </thead>\n",
" <tbody>\n",
" <tr>\n",
" <th>a</th>\n",
" <td>3</td>\n",
" <td>3</td>\n",
" <td>2</td>\n",
" <td>3</td>\n",
" </tr>\n",
" <tr>\n",
" <th>b</th>\n",
" <td>4</td>\n",
" <td>1</td>\n",
" <td>3</td>\n",
" <td>2</td>\n",
" </tr>\n",
" <tr>\n",
" <th>c</th>\n",
" <td>2</td>\n",
" <td>4</td>\n",
" <td>4</td>\n",
" <td>1</td>\n",
" </tr>\n",
" <tr>\n",
" <th>d</th>\n",
" <td>1</td>\n",
" <td>2</td>\n",
" <td>1</td>\n",
" <td>4</td>\n",
" </tr>\n",
" </tbody>\n",
"</table>\n",
"</div>"
],
"text/plain": [
" A B C D\n",
"a 3 3 2 3\n",
"b 4 1 3 2\n",
"c 2 4 4 1\n",
"d 1 2 1 4"
]
},
"execution_count": 5,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"women_df"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {},
"outputs": [
{
"data": {
"text/html": [
"<div>\n",
"<style scoped>\n",
" .dataframe tbody tr th:only-of-type {\n",
" vertical-align: middle;\n",
" }\n",
"\n",
" .dataframe tbody tr th {\n",
" vertical-align: top;\n",
" }\n",
"\n",
" .dataframe thead th {\n",
" text-align: right;\n",
" }\n",
"</style>\n",
"<table border=\"1\" class=\"dataframe\">\n",
" <thead>\n",
" <tr style=\"text-align: right;\">\n",
" <th></th>\n",
" <th>A</th>\n",
" <th>B</th>\n",
" <th>C</th>\n",
" <th>D</th>\n",
" </tr>\n",
" </thead>\n",
" <tbody>\n",
" <tr>\n",
" <th>a</th>\n",
" <td>1</td>\n",
" <td>2</td>\n",
" <td>3</td>\n",
" <td>4</td>\n",
" </tr>\n",
" <tr>\n",
" <th>b</th>\n",
" <td>1</td>\n",
" <td>4</td>\n",
" <td>3</td>\n",
" <td>2</td>\n",
" </tr>\n",
" <tr>\n",
" <th>c</th>\n",
" <td>2</td>\n",
" <td>1</td>\n",
" <td>3</td>\n",
" <td>4</td>\n",
" </tr>\n",
" <tr>\n",
" <th>d</th>\n",
" <td>4</td>\n",
" <td>2</td>\n",
" <td>3</td>\n",
" <td>1</td>\n",
" </tr>\n",
" </tbody>\n",
"</table>\n",
"</div>"
],
"text/plain": [
" A B C D\n",
"a 1 2 3 4\n",
"b 1 4 3 2\n",
"c 2 1 3 4\n",
"d 4 2 3 1"
]
},
"execution_count": 6,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"man_df"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Gale-Shapley algorithm"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {},
"outputs": [],
"source": [
"# dict to control which women each man can make proposals\n",
"women_available = {man:women_list for man in man_list}\n",
"# waiting list of men that were able to create pair on each iteration\n",
"waiting_list = []\n",
"# dict to store created pairs\n",
"proposals = {}\n",
"# variable to count number of iterations\n",
"count = 0"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {},
"outputs": [],
"source": [
"# while not all men have pairs\n",
"while len(waiting_list)<len(man_list):\n",
" # man makes proposals\n",
" for man in man_list:\n",
" if man not in waiting_list:\n",
" # each man make proposal to the top women from it's list\n",
" women = women_available[man]\n",
" best_choice = man_df.loc[man][man_df.loc[man].index.isin(women)].idxmin()\n",
" proposals[(man, best_choice)]=(man_df.loc[man][best_choice],\n",
" women_df.loc[man][best_choice])\n",
" # if women have more than one proposals \n",
" # she will choose the best option\n",
" overlays = Counter([key[1] for key in proposals.keys()])\n",
" # cycle to choose the best options\n",
" for women in overlays.keys():\n",
" if overlays[women]>1:\n",
" # pairs to drop from proposals\n",
" pairs_to_drop = sorted({pair: proposals[pair] for pair in proposals.keys() \n",
" if women in pair}.items(), \n",
" key=lambda x: x[1][1]\n",
" )[1:]\n",
" # if man was rejected by woman\n",
" # there is no pint for him to make proposal \n",
" # second time to the same woman\n",
" for p_to_drop in pairs_to_drop:\n",
" del proposals[p_to_drop[0]]\n",
" _women = copy(women_available[p_to_drop[0][0]])\n",
" _women.remove(p_to_drop[0][1])\n",
" women_available[p_to_drop[0][0]] = _women\n",
" # man who successfully created pairs must be added to the waiting list \n",
" waiting_list = [man[0] for man in proposals.keys()]\n",
" # update counter\n",
" count+=1"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Stable pairs"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"{('b', 'D'): (2, 2),\n",
" ('d', 'B'): (2, 2),\n",
" ('c', 'A'): (2, 2),\n",
" ('a', 'C'): (3, 2)}"
]
},
"execution_count": 9,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"proposals"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"6"
]
},
"execution_count": 10,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"count"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.7.3"
}
},
"nbformat": 4,
"nbformat_minor": 2
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment