Skip to content

Python implementation of deferred acceptance algorithm for school choice problem

License

Notifications You must be signed in to change notification settings

kyosek/deferred_acceptance_school_choice

Repository files navigation

Deferred Acceptance algorithm for school choice

Python implementation of Deferred Acceptance algorithm (Gale and Shapley, 1962) for school choice.

The medium blog about this repo can be found here.

Introduction

The study of matching investigates stable matchings among people, institutes and goods. Starting with Gale and Shapley (1962)’s deferred acceptance (DA) algorithm, this study has been successfully utilised in the real world, especially in school choice since the early 2000s. This repo covers (so far):

  • DA algorithm for school choice (student optimal)
  • DA algorithm with random tie-break lotteries
  • Examples of above algorithms usage

Usage

After input student and school's preference and schools' quota,

from deferred_acceptance.deferred_acceptance import deferred_acceptance
from deferred_acceptance.utils import create_dataframes


students_df, schools_df = create_dataframes(
        students_list=students_list,
        students_preferences=students_preferences,
        schools_list=schools_list,
        schools_preferences=schools_preferences,
    )
matches = deferred_acceptance(
        students_df=students_df, schools_df=schools_df, schools_quota=schools_quota
    )
from deferred_acceptance.deferred_acceptance import deferred_acceptance
from deferred_acceptance.utils import create_dataframes, tie_break


students_df, schools_df = create_dataframes(
        students_list=students_list,
        students_preferences=students_preferences,
        schools_list=schools_list,
        schools_preferences=schools_preferences,
    )

strict_school_df = tie_break(schools_df)
matches = deferred_acceptance(
    students_df=students_df,
    schools_df=strict_school_df,
    schools_quota=schools_quota,
)

About

Python implementation of deferred acceptance algorithm for school choice problem

Topics

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages