kyosek/deferred_acceptance_school_choice

Python implementation of deferred acceptance algorithm for school choice problem

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

Simple DA algorithm

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
    )

DA algorithm with random tie-break lotteries

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,
)

deferred_acceptance_school_choice's Issues

Create an example directory

Create an example directory

Use RL to learn the school choice algorithm

Create an example for tie-break function usage

Add README.md

Improve tie-breaking algorithm

Implement "optimal for" feature to DA function

The "optimal for" argument can choose the algorithm work to optimise their matches for either students or schools.
This can be implemented by choosing which party will make a proposal first.

school capacities / quotas

A couple of suggestions (happy to work on a PR if you're open to it):

• Not enough space: In overcrowded school districts, total capacity can be less than the total number of students. It would be worth it I think to build in some rules for how "excess" students get allocated.
• Eligibility: Some schools may limit which students are eligible to attend (could be based on living within a certain area, test scores, etc.). It would be useful for this model to work if a school's preferences could include only a subset of all students.

This is the error thrown when you try to run the model w/o enough capacity:

---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
[~\AppData\Local\Temp\ipykernel_40444\1300843094.py](https://file+.vscode-resource.vscode-cdn.net/c%3A/webtools_dev/deferred_acceptance_school_choice/examples/~/AppData/Local/Temp/ipykernel_40444/1300843094.py) in 
     13 # Run the algorithm
     14 schools_quota = {"A": 1, "B": 1, "C": 1}
---> 15 matches = deferred_acceptance(
     16     students_df=students_df,
     17     schools_df=strict_school_df,

[c:\webtools_dev\deferred_acceptance_school_choice\examples\..\deferred_acceptance\deferred_acceptance.py](file:///C:/webtools_dev/deferred_acceptance_school_choice/deferred_acceptance/deferred_acceptance.py) in deferred_acceptance(students_df, schools_df, schools_quota, verbose)
     42             if student not in unassigned_students:
     43                 school = available_school[student]
---> 44                 best_choice = students_df.loc[student][
     45                     students_df.loc[student].index.isin(school)
     46                 ].idxmin()

[c:\Users\Raphael.WXYSTUDIO\Anaconda3\lib\site-packages\pandas\core\series.py](file:///C:/Users/Raphael.WXYSTUDIO/Anaconda3/lib/site-packages/pandas/core/series.py) in idxmin(self, axis, skipna, *args, **kwargs)
   2332         nan
   2333         """
-> 2334         i = self.argmin(axis, skipna, *args, **kwargs)
   2335         if i == -1:
   2336             return np.nan

[c:\Users\Raphael.WXYSTUDIO\Anaconda3\lib\site-packages\pandas\core\base.py](file:///C:/Users/Raphael.WXYSTUDIO/Anaconda3/lib/site-packages/pandas/core/base.py) in argmin(self, axis, skipna, *args, **kwargs)
    717             # error: Incompatible return value type (got "Union[int, ndarray]", expected
    718             # "int")
--> 719             return nanops.nanargmin(  # type: ignore[return-value]
    720                 delegate, skipna=skipna
    721             )

[c:\Users\Raphael.WXYSTUDIO\Anaconda3\lib\site-packages\pandas\core\nanops.py](file:///C:/Users/Raphael.WXYSTUDIO/Anaconda3/lib/site-packages/pandas/core/nanops.py) in _f(*args, **kwargs)
     91             try:
     92                 with np.errstate(invalid="ignore"):
---> 93                     return f(*args, **kwargs)
     94             except ValueError as e:
     95                 # we want to transform an object array

[c:\Users\Raphael.WXYSTUDIO\Anaconda3\lib\site-packages\pandas\core\nanops.py](file:///C:/Users/Raphael.WXYSTUDIO/Anaconda3/lib/site-packages/pandas/core/nanops.py) in nanargmin(values, axis, skipna, mask)
   1140     values, mask, _, _, _ = _get_values(values, True, fill_value_typ="+inf", mask=mask)
   1141     # error: Need type annotation for 'result'
-> 1142     result = values.argmin(axis)  # type: ignore[var-annotated]
   1143     result = _maybe_arg_null_out(result, axis, mask, skipna)
   1144     return result

ValueError: attempt to get argmin of an empty sequence

Here's the error when you run the model with school preferences of variable length:

---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
[~\AppData\Local\Temp\ipykernel_40444\2589139436.py](https://file+.vscode-resource.vscode-cdn.net/c%3A/webtools_dev/deferred_acceptance_school_choice/examples/~/AppData/Local/Temp/ipykernel_40444/2589139436.py) in 
      1 schools_preferences = {"A": [1, 1, 1], "B": [1, 3, 3, 1], "C": [2, 2, 2, 2]}
      2 
----> 3 students_df, schools_df = create_dataframes(
      4     students_list=students_list,
      5     students_preferences=students_preferences,

[c:\webtools_dev\deferred_acceptance_school_choice\examples\..\deferred_acceptance\utils.py](file:///C:/webtools_dev/deferred_acceptance_school_choice/deferred_acceptance/utils.py) in create_dataframes(students_list, students_preferences, schools_list, schools_preferences)
     52     students_df.index = schools_list
     53     students_df = students_df.transpose()
---> 54     schools_df = pd.DataFrame(schools_preferences)
     55     schools_df.index = students_list
     56 

[c:\Users\Raphael.WXYSTUDIO\Anaconda3\lib\site-packages\pandas\core\frame.py](file:///C:/Users/Raphael.WXYSTUDIO/Anaconda3/lib/site-packages/pandas/core/frame.py) in __init__(self, data, index, columns, dtype, copy)
    634         elif isinstance(data, dict):
    635             # GH#38939 de facto copy defaults to False only in non-dict cases
--> 636             mgr = dict_to_mgr(data, index, columns, dtype=dtype, copy=copy, typ=manager)
    637         elif isinstance(data, ma.MaskedArray):
    638             import numpy.ma.mrecords as mrecords

[c:\Users\Raphael.WXYSTUDIO\Anaconda3\lib\site-packages\pandas\core\internals\construction.py](file:///C:/Users/Raphael.WXYSTUDIO/Anaconda3/lib/site-packages/pandas/core/internals/construction.py) in dict_to_mgr(data, index, columns, dtype, typ, copy)
    500         # TODO: can we get rid of the dt64tz special case above?
    501 
--> 502     return arrays_to_mgr(arrays, columns, index, dtype=dtype, typ=typ, consolidate=copy)
    503 
    504 

[c:\Users\Raphael.WXYSTUDIO\Anaconda3\lib\site-packages\pandas\core\internals\construction.py](file:///C:/Users/Raphael.WXYSTUDIO/Anaconda3/lib/site-packages/pandas/core/internals/construction.py) in arrays_to_mgr(arrays, columns, index, dtype, verify_integrity, typ, consolidate)
    118         # figure out the index, if necessary
    119         if index is None:
--> 120             index = _extract_index(arrays)
    121         else:
    122             index = ensure_index(index)

[c:\Users\Raphael.WXYSTUDIO\Anaconda3\lib\site-packages\pandas\core\internals\construction.py](file:///C:/Users/Raphael.WXYSTUDIO/Anaconda3/lib/site-packages/pandas/core/internals/construction.py) in _extract_index(data)
    672             lengths = list(set(raw_lengths))
    673             if len(lengths) > 1:
--> 674                 raise ValueError("All arrays must be of the same length")
    675 
    676             if have_dicts:

ValueError: All arrays must be of the same length

Create RL environment

A subtask of Use RL to learn the school choice algorithm #14
Create the following classes:

• "matching" environment
• schools
• students

Add readme

Add readme

Make this into a library

Case where all students and all schools have the same preferences doesn't work

Tried a case with 2 schools and 3 students where quotas were 1 and 2 but each school/student had the same preferences, and it breaks the code. I think the pairs dropped shouldn't be all but the first one, instead it should be based on the school's quota.

Add "strict preference check" to the data construction function

Replace dictionaries in the DA algorithm by __slot__

Replace randrange to randint in the tie-break function

Add requirements.txt

Add config files

Add tie-breaking lottery

Add tie-breaking lottery to the DA algorithm

Develop DA algorithm implementation

Write a DA algorithm implementation

Implement stable improvement cycle algorithm

Implement stable improvement cycle algorithm (Erdil and Ergin, 2008)

Make verbosity feature in DA algorithm

Add function documentation