Skip to content

Latest commit

 

History

History
58 lines (43 loc) · 2.74 KB

README.md

File metadata and controls

58 lines (43 loc) · 2.74 KB
Raw

RoyalMatch

Implementing Nobel Prize winning Gale-Shapley algorithm with Flask & Heroku
Reference: The Creativity Code, Marcus Du Sautoy

In mathematics, economics, and computer science, the Gale–Shapley algorithm (also known as the deferred acceptance algorithm) is an algorithm for finding a solution to the stable matching problem. The stable marriage problem (also stable matching problem or SMP) is the problem of finding a stable matching between two equally sized sets of elements given an ordering of preferences for each element. A matching is a bijection from the elements of one set to the elements of the other set. A matching is not stable if:

  1. There is an element A of the first matched set which prefers some given element B of the second matched set over the element to which A is already matched, and
  2. B also prefers A over the element to which B is already matched.

In other words, a matching is stable when there does not exist any match (A, B) which both prefer each other to their current partner under the matching.

Applications

This algorithm finds application for a variety of real world scenarios, such as:

  • Match children to day-cares, in Denmark
  • Allocate rabbis to synagogues, in New York
  • Match students to universities, in China, Germany and Spain
  • Match patients to organ donations, in UK (National Health Service)

About

This implementation of the Gale–Shapley algorithm aims to find stable matching for the following 4 Kings and 4 Queens given their preferences. The algorithm may be scaled to N pairs of people by simply reassigning the parameter.

INSTRUCTIONS

  • To specify preferences for each King and Queen use the given drop down menu.
  • Ensure that each King or Queen has 4 unique preferences [♣, ♦, ♥, ♠], which may be listed in any order of preference.
  • Please note that the algorithm will not work if the preferences for each Royal are not unique.

RESULTS

  • Stable Matching: The stable matching result for the given preferences is computed and displayed. There may or may not be alternate optimal solutions.
  • Calculation Logs: The verbose calculations for the optimal result produced are also displayed for reference.

SET UP: Local Deployment

To set up and deploy the application locally, follow the steps below:

  • Set up local virtual environment
~$ virtualenv env
  • Activate virtual environment
~$ source env/bin/activate
  • Install dependencies
~$ pip install -r requirements.txt
  • Run server on localhost:5000
~$ python server/app.py