Deferred Acceptance (Gale-Shapley) Algorithm

This package implements the deferred acceptance algorithm (also known as the Gale-Shapley algorithm) in Rust with Python bindings. It can be used to solve matching problems like student-school assignments, worker-firm matching, or any other two-sided matching market.

Setup

1. Clone the repository:

git clone <repository-url>
cd deferred-acceptance

2. Set up a Python environment (Python 3.7 or higher required):

conda create -n da python=3.11
pip install maturin pytest

3. Build and install the package:

maturin develop

Quick Start

from gale_shapley import match_students_to_schools

# Simple example with 2 students and 2 schools
student_preferences = [
    [0, 1],  # Student 0 prefers School 0 over School 1
    [1]      # Student 1 only wants School 1
]

school_preferences = [
    [0],     # School 0 only wants Student 0
    [1, 0]   # School 1 ranks both students
]

school_capacities = [1, 1]  # Each school can accept 1 student

matches = match_students_to_schools(student_preferences, school_preferences, school_capacities)
print(matches)  # Output: {0: 0, 1: 1}  # {student_id: school_id}

Running Tests

pytest test_matching.py -v

Input Format

Student Preferences (student_preferences)

• Type: List of lists of integers
• Each inner list represents one student's preferences
• Schools are identified by integers starting from 0
• Order matters: earlier positions indicate higher preference
• Lists can be empty or partial (don't need to include all schools)
• Example:

  student_preferences = [
      [2, 0, 1],  # Student 0 ranks all schools
      [0],        # Student 1 only wants School 0
      [],         # Student 2 has no preferences
      [1, 2]      # Student 3 only ranks Schools 1 and 2
  ]

School Preferences (school_preferences)

• Type: List of lists of integers
• Each inner list represents one school's preferences
• Students are identified by integers starting from 0
• Order matters: earlier positions indicate higher preference
• Lists can be partial (don't need to include all students)
• Example:

  school_preferences = [
      [0, 2, 1],  # School 0 ranks all students
      [1],        # School 1 only wants Student 1
      [2, 1]      # School 2 only ranks Students 2 and 1
  ]

School Capacities (school_capacities)

• Type: List of integers
• Each integer represents the maximum number of students a school can accept
• Must be positive integers
• Length must match the number of schools
• Example:

  school_capacities = [
      2,  # School 0 can accept 2 students
      1,  # School 1 can accept 1 student
      3   # School 2 can accept 3 students
  ]

Output Format

The function returns a dictionary where:

• Keys are student IDs (integers)
• Values are school IDs (integers)
• Only matched students appear in the dictionary
• Students with empty preference lists won't be matched
• Students not ranked by their preferred schools won't be matched
• Example:

  {
      0: 2,  # Student 0 is matched with School 2
      1: 0,  # Student 1 is matched with School 0
      3: 1   # Student 3 is matched with School 1
      # Student 2 is unmatched (not in dictionary)
  }

Preference List Handling

The algorithm supports flexible preference lists:

1. Empty Preferences

   # Student with no preferences
   student_preferences = [
       [0, 1],  # Student 0 has preferences
       []       # Student 1 has no preferences (will remain unmatched)
   ]

2. Partial Preferences

   # Students only listing their top choices
   student_preferences = [
       [0],     # Student 0 only wants School 0
       [1, 0],  # Student 1 ranks two schools
       [2]      # Student 2 only wants School 2
   ]

3. Asymmetric Preferences

   # Schools can rank different numbers of students
   school_preferences = [
       [0, 1, 2],  # School 0 ranks all students
       [1],        # School 1 only ranks Student 1
       [2, 0]      # School 2 ranks two students
   ]

Important Notes

1. All IDs must be consecutive integers starting from 0
2. Preference lists cannot contain duplicates
3. A student will not be matched if:
   • They submit an empty preference list
   • Their preferred schools are full with higher-ranked students
   • They are not ranked by any of their preferred schools
4. The algorithm guarantees:
   • The matching is stable (no blocking pairs)
   • School capacity constraints are respected
   • The matching is student-optimal among all stable matchings

Error Handling

The function will raise a ValueError if:

1. Preference lists contain duplicate entries
2. IDs are invalid (not in range)
3. School capacities are not positive
4. Input lists have inconsistent sizes

Common Patterns

1. Students applying only to top choices:

   # Students only list schools they would actually attend
   student_preferences = [
       [0],        # Only wants top choice
       [0, 1],     # Lists top two choices
       [0, 1, 2]   # Lists all options
   ]

2. Schools with tiered preferences:

   # Schools only rank students meeting certain criteria
   school_preferences = [
       [0, 1],     # Only ranks top students
       [0, 1, 2],  # Ranks all students
       [2]         # Only ranks one student
   ]

3. Mixed participation:

   student_preferences = [
       [0, 1, 2],  # Full participation
       [],         # Opts out of matching
       [1]         # Partial participation
   ]

Development

To rebuild after making changes to the Rust code:

maturin develop

To run tests:

pytest test_matching.py -v

Made with help from Claude 3.5 Sonnet