Gale-Shapley-Stable-Marriage.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "9fd98cf7",
   "metadata": {},
   "outputs": [],
   "source": [
    "import time\n",
    "import random"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7492d65b",
   "metadata": {},
   "source": [
    "# Implementation of Gale-Shapley using lists and arrays"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "28d75bfd",
   "metadata": {},
   "outputs": [],
   "source": [
    "men_preferences = [\n",
    "    [0, 1, 2],\n",
    "    [1, 2, 0],\n",
    "    [2, 0, 1]\n",
    "]\n",
    "\n",
    "women_preferences = [\n",
    "    [0, 1, 2],\n",
    "    [1, 0, 2],\n",
    "    [2, 0, 1]\n",
    "]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "902228df",
   "metadata": {},
   "outputs": [],
   "source": [
    "def gale_shapley(men_preferences, women_preferences):\n",
    "    n = len(men_preferences)\n",
    "   \n",
    "    # Initialize empty matching\n",
    "    matching = [-1] * n\n",
    "    free_men = list(range(n))\n",
    "    \n",
    "\n",
    "    preference_rank = [[0]*n for _ in range(n)]\n",
    "    for woman in range(n):\n",
    "        for rank, man in enumerate(women_preferences[woman]):\n",
    "            preference_rank[woman][man] = rank\n",
    "    \n",
    "    while free_men:\n",
    "        man = free_men.pop(0)\n",
    "        man_preferences = men_preferences[man]\n",
    "        \n",
    "        for woman in man_preferences:\n",
    "            # If woman is unmatched, match her with the man\n",
    "            if woman not in matching:\n",
    "                matching[man] = woman\n",
    "                break\n",
    "            else:\n",
    "                # Find the current partner of the woman\n",
    "                current_partner = matching.index(woman)\n",
    "                \n",
    "                # constant time lookup in this way\n",
    "                if preference_rank[woman][man] < preference_rank[woman][current_partner]:\n",
    "                    # Unmatch the current partner\n",
    "                    matching[current_partner] = -1\n",
    "                    free_men.append(current_partner)\n",
    "                    \n",
    "                    # Match the new man\n",
    "                    matching[man] = woman\n",
    "                    break\n",
    "    return matching"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "e15a94ef",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Stable Matching: [0, 1, 2]\n"
     ]
    }
   ],
   "source": [
    "result = gale_shapley(men_preferences, women_preferences)\n",
    "print('Stable Matching:', result)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "708bf52d",
   "metadata": {},
   "source": [
    "Let's test the runtimes and create an average case and worst case input. According to the average case analysis, the while loop of the G-S algorithm requires $O(n \\log n)$ iterations in expectation, compared to the worst case $O(n^2)$. Thus we expect the implementation to run faster on the random input. Let's verify the intuition by setting n=500. You can run the code several times and on larger n values  to see the difference in the runtime."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "a22d377e",
   "metadata": {},
   "outputs": [],
   "source": [
    "def generate_random_permutations(n):\n",
    "    permutations = []\n",
    "    lst = list(range(n))\n",
    "    for _ in range(n):\n",
    "        shuffled_lst = lst.copy()\n",
    "        random.shuffle(shuffled_lst)\n",
    "        permutations.append(shuffled_lst)\n",
    "    return permutations"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "22eab5e6",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Time taken for O(n^2) implementation: 0.0481109619140625 seconds\n"
     ]
    }
   ],
   "source": [
    "n = 500\n",
    "men_preferences  = generate_random_permutations(n)\n",
    "women_preferences  = generate_random_permutations(n)\n",
    " \n",
    "start_time = time.time()\n",
    "result = gale_shapley(men_preferences, women_preferences)\n",
    "end_time = time.time()\n",
    "\n",
    "elapsed_time = end_time - start_time\n",
    "print(f'Time taken for O(n^2) implementation: {elapsed_time} seconds')\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "0981340b",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Time taken for O(n^2) implementation: 158.48829412460327 seconds\n"
     ]
    }
   ],
   "source": [
    "def generate_worst_case_input(n):\n",
    "    men_preferences = [list(range(n)) for _ in range(n)]    \n",
    "    women_preferences = [list(range(n-1, -1, -1)) for _ in range(n)]\n",
    "    return men_preferences, women_preferences\n",
    "\n",
    "n = 500\n",
    "men_preferences, women_preferences = generate_worst_case_input(n)\n",
    "\n",
    "start_time = time.time()\n",
    "result = gale_shapley(men_preferences, women_preferences)\n",
    "end_time = time.time()\n",
    "\n",
    "elapsed_time = end_time - start_time\n",
    "print(f'Time taken for O(n^2) implementation: {elapsed_time} seconds')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3496ba6f",
   "metadata": {},
   "source": [
    "The average case analysis was first performed by Donald Knuth. \n",
    "\n",
    "[1] D. E. KNUTH, [Mariages Stables et leurs relations avec d’autres problemes combinatoires](https://www-cs-faculty.stanford.edu/~knuth/mariages-stables.pdf) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0ad3f0a9",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.9.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}