Skip to content

gale_shapley_algorithm

gale-shapley-algorithm: A Python implementation of the Gale-Shapley algorithm.

Modules:

  • algorithm –

    Algorithm module.

  • matching –

    Convenience function for creating matchings.

  • person –

    Person module.

  • result –

    Result types for the Gale-Shapley algorithm.

  • stability –

    Stability analysis for matchings.

Classes:

  • Algorithm –

    Gale-Shapley Algorithm class.

  • MatchingResult –

    Result of running the Gale-Shapley algorithm.

  • Person –

    Person class, base class for Proposer and Responder.

  • Proposer –

    Proposer class, subclass of Person.

  • Responder –

    Responder class, subclass of Person.

  • StabilityResult –

    Result of a stability check on a matching.

Functions:

Algorithm dataclass 

Algorithm(proposers: list[Proposer], responders: list[Responder], round: int = 0)

Gale-Shapley Algorithm class.

Uses slots for memory efficiency.

Methods:

  • execute –

    Run the algorithm and return structured results.

  • format_all_preferences –

    Format preferences of all proposers and responders as a string.

  • format_matches –

    Format all matches as a string.

  • proposers_propose –

    Makes all unmatched proposers propose to their next choice.

  • responders_respond –

    Makes all responders that are awaiting to respond respond.

  • terminate –

    Returns True if all proposers are matched, False otherwise.

Attributes:

awaiting_to_respond_responders property 

awaiting_to_respond_responders: list[Responder]

Returns responders that are awaiting to respond.

persons property 

persons: list[Proposer | Responder]

Returns all proposers and responders.

unmatched_proposers property 

unmatched_proposers: list[Proposer]

Returns unmatched proposers, excludes self matches.

execute 

execute() -> MatchingResult

Run the algorithm and return structured results.

Returns:

  • MatchingResult –

    MatchingResult with rounds, matches, unmatched, self_matches, all_matched.

Source code in src/gale_shapley_algorithm/algorithm.py 
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
def execute(self) -> MatchingResult:
    """Run the algorithm and return structured results.

    Returns:
        MatchingResult with rounds, matches, unmatched, self_matches, all_matched.
    """
    while not self.terminate():
        self.proposers_propose()
        self.responders_respond()
        self.round += 1

    # Change None to self matches for unmatched responders
    for responder in self.responders:
        if not responder.is_matched:
            responder.match = responder

    matches: dict[str, str] = {}
    unmatched: list[str] = []
    self_matches: list[str] = []

    for proposer in self.proposers:
        match proposer.match:
            case None:
                unmatched.append(proposer.name)
            case m if m.name == proposer.name:
                self_matches.append(proposer.name)
            case m:
                matches[proposer.name] = m.name

    for responder in self.responders:
        match responder.match:
            case m if m == responder:
                self_matches.append(responder.name)
            case None:
                unmatched.append(responder.name)

    return MatchingResult(
        rounds=self.round,
        matches=matches,
        unmatched=unmatched,
        self_matches=self_matches,
        all_matched=len(unmatched) == 0 and len(self_matches) == 0,
    )

format_all_preferences 

format_all_preferences(compact: bool = True) -> str

Format preferences of all proposers and responders as a string.

Parameters:

  • compact

    (bool, default: True ) –

    If True formats all in one table. Defaults to True.

Source code in src/gale_shapley_algorithm/algorithm.py 
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
def format_all_preferences(self, compact: bool = True) -> str:
    """Format preferences of all proposers and responders as a string.

    Args:
        compact: If True formats all in one table. Defaults to True.
    """
    lines: list[str] = []
    if compact:
        lines.append("Preferences in compact format, only showing acceptables:")
        header: Final[list[str]] = [p.name for p in self.persons]
        first_column: Final[list[str]] = [
            f"{i}." for i in range(1, max(len(self.proposers), len(self.responders)) + 2)
        ]
        data: list[list[str]] = []
        for i in range(len(first_column)):
            data.append(
                [
                    (
                        person.preferences[i].name
                        if bool(person.preferences)
                        and i < len(person.preferences)
                        and person.is_acceptable(person.preferences[i])
                        else ""
                    )
                    for person in self.persons
                ]
            )
        format_row: Final[str] = "{:8}" * (len(header) + 1)
        lines.append(format_row.format("", *header))
        lines.append(format_row.format("", *["-" * len(h) for h in header]))
        for pref, row in zip(first_column, data, strict=False):
            lines.append(format_row.format(pref, *row))
    else:
        lines.append("Preferences for each person separately:")
        for person in self.persons:
            lines.append(person.format_preferences())
            if person != self.persons[-1]:
                lines.append("")

    return "\n".join(lines)

format_matches 

format_matches() -> str

Format all matches as a string.

Source code in src/gale_shapley_algorithm/algorithm.py 
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
def format_matches(self) -> str:
    """Format all matches as a string."""
    lines: list[str] = ["Matching:"]
    for proposer in self.proposers:
        match proposer.match:
            case None:
                lines.append(f"{proposer.name} is unmatched.")
            case m if m.name == proposer.name:
                lines.append(f"{proposer.name} is matched to self.")
            case m:
                lines.append(f"{proposer.name} is matched to {m.name}.")

    for responder in self.responders:
        match responder.match:
            case m if m == responder:
                lines.append(f"{responder.name} is matched to self.")
            case None:
                lines.append(f"{responder.name} is unmatched.")

    return "\n".join(lines)

proposers_propose 

proposers_propose() -> None

Makes all unmatched proposers propose to their next choice.

Source code in src/gale_shapley_algorithm/algorithm.py 
36
37
38
39
def proposers_propose(self) -> None:
    """Makes all unmatched proposers propose to their next choice."""
    for proposer in self.unmatched_proposers:
        proposer.propose()

responders_respond 

responders_respond() -> None

Makes all responders that are awaiting to respond respond.

Source code in src/gale_shapley_algorithm/algorithm.py 
41
42
43
44
def responders_respond(self) -> None:
    """Makes all responders that are awaiting to respond respond."""
    for responder in self.awaiting_to_respond_responders:
        responder.respond()

terminate 

terminate() -> bool

Returns True if all proposers are matched, False otherwise.

Source code in src/gale_shapley_algorithm/algorithm.py 
46
47
48
def terminate(self) -> bool:
    """Returns True if all proposers are matched, False otherwise."""
    return all(proposer.is_matched for proposer in self.proposers)

MatchingResult dataclass 

MatchingResult(rounds: int, matches: dict[str, str], unmatched: list[str], self_matches: list[str], all_matched: bool)

Result of running the Gale-Shapley algorithm.

Person 

Person(name: str, side: str)

Person class, base class for Proposer and Responder.

Methods:

  • format_preferences –

    Format the preferences of the person as a string, * indicates acceptable.

  • is_acceptable –

    Check if person is acceptable (ranked at or above self in preferences).

Attributes:

  • is_matched (bool) –

    Returns True if the person is matched to someone or self, False if match is None.

Source code in src/gale_shapley_algorithm/person.py 
13
14
15
16
17
def __init__(self, name: str, side: str) -> None:
    self.name = name
    self.side = side
    self.preferences: tuple[Proposer | Responder, ...] = ()
    self.match: Proposer | Responder | None = None

is_matched property writable 

is_matched: bool

Returns True if the person is matched to someone or self, False if match is None.

format_preferences 

format_preferences() -> str

Format the preferences of the person as a string, * indicates acceptable.

Source code in src/gale_shapley_algorithm/person.py 
42
43
44
45
46
47
48
49
50
def format_preferences(self) -> str:
    """Format the preferences of the person as a string, * indicates acceptable."""
    lines = [f"{self.name} has the following preferences, * indicates acceptable:"]
    offset_one: int = len(str(len(self.preferences)))
    offset_two: int = max(len(person.name) for person in self.preferences)
    for i, person in enumerate(self.preferences, start=1):
        acceptable = "*" if self.is_acceptable(person) else ""
        lines.append(f"{i}.{'':{offset_one - len(str(i)) + 1}}{person.name:<{offset_two + 1}}{acceptable}")
    return "\n".join(lines)

is_acceptable 

is_acceptable(person: Proposer | Responder) -> bool

Check if person is acceptable (ranked at or above self in preferences).

Parameters:

Raises:

Returns:

  • bool –

    True if person is acceptable, False otherwise.

Source code in src/gale_shapley_algorithm/person.py 
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
def is_acceptable(self, person: Proposer | Responder) -> bool:
    """Check if person is acceptable (ranked at or above self in preferences).

    Args:
        person: The person to check acceptability for.

    Raises:
        ValueError: If person is not in preferences.

    Returns:
        True if person is acceptable, False otherwise.
    """
    if person in self.preferences and self in self.preferences:
        return self.preferences.index(person) <= self.preferences.index(self)
    raise ValueError(f"Either {self} or {person} is not in preferences.")

Proposer 

Proposer(name: str, side: str)

Bases: Person

Proposer class, subclass of Person.

Methods:

  • format_preferences –

    Format the preferences of the person as a string, * indicates acceptable.

  • is_acceptable –

    Check if person is acceptable (ranked at or above self in preferences).

  • propose –

    Propose to the next acceptable responder. If self is next, set match to self.

Attributes:

Source code in src/gale_shapley_algorithm/person.py 
69
70
71
def __init__(self, name: str, side: str) -> None:
    super().__init__(name, side)
    self.last_proposal: Responder | Proposer | None = None

acceptable_to_propose property 

acceptable_to_propose: tuple[Responder | Proposer, ...]

Returns a tuple of acceptable responders to propose to.

is_matched property writable 

is_matched: bool

Returns True if the person is matched to someone or self, False if match is None.

next_proposal property 

next_proposal: Responder | Proposer

Returns the next acceptable responder to propose to, or self if exhausted.

format_preferences 

format_preferences() -> str

Format the preferences of the person as a string, * indicates acceptable.

Source code in src/gale_shapley_algorithm/person.py 
42
43
44
45
46
47
48
49
50
def format_preferences(self) -> str:
    """Format the preferences of the person as a string, * indicates acceptable."""
    lines = [f"{self.name} has the following preferences, * indicates acceptable:"]
    offset_one: int = len(str(len(self.preferences)))
    offset_two: int = max(len(person.name) for person in self.preferences)
    for i, person in enumerate(self.preferences, start=1):
        acceptable = "*" if self.is_acceptable(person) else ""
        lines.append(f"{i}.{'':{offset_one - len(str(i)) + 1}}{person.name:<{offset_two + 1}}{acceptable}")
    return "\n".join(lines)

is_acceptable 

is_acceptable(person: Proposer | Responder) -> bool

Check if person is acceptable (ranked at or above self in preferences).

Parameters:

Raises:

Returns:

  • bool –

    True if person is acceptable, False otherwise.

Source code in src/gale_shapley_algorithm/person.py 
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
def is_acceptable(self, person: Proposer | Responder) -> bool:
    """Check if person is acceptable (ranked at or above self in preferences).

    Args:
        person: The person to check acceptability for.

    Raises:
        ValueError: If person is not in preferences.

    Returns:
        True if person is acceptable, False otherwise.
    """
    if person in self.preferences and self in self.preferences:
        return self.preferences.index(person) <= self.preferences.index(self)
    raise ValueError(f"Either {self} or {person} is not in preferences.")

propose 

propose() -> None

Propose to the next acceptable responder. If self is next, set match to self.

Source code in src/gale_shapley_algorithm/person.py 
90
91
92
93
94
95
96
97
def propose(self) -> None:
    """Propose to the next acceptable responder. If self is next, set match to self."""
    match self.next_proposal:
        case Proposer():  # meaning self is next
            self.match = self
        case responder:
            responder.current_proposals.append(self)
    self.last_proposal = self.next_proposal

Responder 

Responder(name: str, side: str)

Bases: Person

Responder class, subclass of Person.

Methods:

  • format_preferences –

    Format the preferences of the person as a string, * indicates acceptable.

  • is_acceptable –

    Check if person is acceptable (ranked at or above self in preferences).

  • respond –

    Respond to proposals and clear the current_proposals.

Attributes:

Source code in src/gale_shapley_algorithm/person.py 
103
104
105
def __init__(self, name: str, side: str) -> None:
    super().__init__(name, side)
    self.current_proposals: list[Proposer] = []

acceptable_proposals property 

acceptable_proposals: list[Proposer]

Returns a list of acceptable proposals among the current proposals.

awaiting_to_respond property 

awaiting_to_respond: bool

Returns True if current_proposals is not empty.

is_matched property writable 

is_matched: bool

Returns True if the person is matched to someone or self, False if match is None.

format_preferences 

format_preferences() -> str

Format the preferences of the person as a string, * indicates acceptable.

Source code in src/gale_shapley_algorithm/person.py 
42
43
44
45
46
47
48
49
50
def format_preferences(self) -> str:
    """Format the preferences of the person as a string, * indicates acceptable."""
    lines = [f"{self.name} has the following preferences, * indicates acceptable:"]
    offset_one: int = len(str(len(self.preferences)))
    offset_two: int = max(len(person.name) for person in self.preferences)
    for i, person in enumerate(self.preferences, start=1):
        acceptable = "*" if self.is_acceptable(person) else ""
        lines.append(f"{i}.{'':{offset_one - len(str(i)) + 1}}{person.name:<{offset_two + 1}}{acceptable}")
    return "\n".join(lines)

is_acceptable 

is_acceptable(person: Proposer | Responder) -> bool

Check if person is acceptable (ranked at or above self in preferences).

Parameters:

Raises:

Returns:

  • bool –

    True if person is acceptable, False otherwise.

Source code in src/gale_shapley_algorithm/person.py 
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
def is_acceptable(self, person: Proposer | Responder) -> bool:
    """Check if person is acceptable (ranked at or above self in preferences).

    Args:
        person: The person to check acceptability for.

    Raises:
        ValueError: If person is not in preferences.

    Returns:
        True if person is acceptable, False otherwise.
    """
    if person in self.preferences and self in self.preferences:
        return self.preferences.index(person) <= self.preferences.index(self)
    raise ValueError(f"Either {self} or {person} is not in preferences.")

respond 

respond() -> None

Respond to proposals and clear the current_proposals.

Source code in src/gale_shapley_algorithm/person.py 
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
def respond(self) -> None:
    """Respond to proposals and clear the current_proposals."""
    if bool(self.acceptable_proposals):
        match self.match:
            case Proposer() as current_match:
                new_match = self._most_preferred(self.acceptable_proposals + [current_match])
                if new_match != current_match:
                    current_match.is_matched = False
                    self.match = new_match
                    new_match.match = self
            case _:
                new_match = self._most_preferred(self.acceptable_proposals)
                self.match = new_match
                new_match.match = self
    self.current_proposals = []

StabilityResult dataclass 

StabilityResult(is_stable: bool, is_individually_rational: bool, blocking_pairs: list[tuple[str, str]])

Result of a stability check on a matching.

check_stability 

check_stability(algorithm: Algorithm) -> StabilityResult

Check the stability of an algorithm's matching.

Parameters:

  • algorithm

    (Algorithm) –

    An Algorithm instance that has been executed.

Returns:

  • StabilityResult –

    StabilityResult with is_stable, is_individually_rational, and blocking_pairs.

Source code in src/gale_shapley_algorithm/stability.py 
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
def check_stability(algorithm: Algorithm) -> StabilityResult:
    """Check the stability of an algorithm's matching.

    Args:
        algorithm: An Algorithm instance that has been executed.

    Returns:
        StabilityResult with is_stable, is_individually_rational, and blocking_pairs.
    """
    ir = is_individually_rational(algorithm.proposers, algorithm.responders)
    bp = find_blocking_pairs(algorithm.proposers, algorithm.responders)
    return StabilityResult(
        is_stable=ir and len(bp) == 0,
        is_individually_rational=ir,
        blocking_pairs=bp,
    )

create_matching 

create_matching(proposer_preferences: dict[str, list[str]], responder_preferences: dict[str, list[str]]) -> MatchingResult

Create a matching from preference dictionaries.

This is the simplest way to use the library. Provide preference rankings for each side and get back a MatchingResult.

Persons not listed in a preference list are considered unacceptable. Each person is automatically added to their own preference list at the end (making everyone they listed acceptable).

Parameters:

  • proposer_preferences

    (dict[str, list[str]]) –

    Mapping of proposer names to ordered list of responder names.

  • responder_preferences

    (dict[str, list[str]]) –

    Mapping of responder names to ordered list of proposer names.

Returns:

Example

result = create_matching( ... proposer_preferences={ ... "alice": ["bob", "charlie"], ... "dave": ["charlie", "bob"], ... }, ... responder_preferences={ ... "bob": ["alice", "dave"], ... "charlie": ["dave", "alice"], ... }, ... ) result.matches

Source code in src/gale_shapley_algorithm/matching.py 
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
def create_matching(
    proposer_preferences: dict[str, list[str]],
    responder_preferences: dict[str, list[str]],
) -> MatchingResult:
    """Create a matching from preference dictionaries.

    This is the simplest way to use the library. Provide preference rankings
    for each side and get back a MatchingResult.

    Persons not listed in a preference list are considered unacceptable.
    Each person is automatically added to their own preference list at the end
    (making everyone they listed acceptable).

    Args:
        proposer_preferences: Mapping of proposer names to ordered list of responder names.
        responder_preferences: Mapping of responder names to ordered list of proposer names.

    Returns:
        MatchingResult with the matching outcome.

    Example:
        >>> result = create_matching(
        ...     proposer_preferences={
        ...         "alice": ["bob", "charlie"],
        ...         "dave": ["charlie", "bob"],
        ...     },
        ...     responder_preferences={
        ...         "bob": ["alice", "dave"],
        ...         "charlie": ["dave", "alice"],
        ...     },
        ... )
        >>> result.matches
        {'alice': 'bob', 'dave': 'charlie'}
    """
    algorithm = _build_algorithm(proposer_preferences, responder_preferences)
    return algorithm.execute()

find_blocking_pairs 

find_blocking_pairs(proposers: list[Proposer], responders: list[Responder]) -> list[tuple[str, str]]

Find all blocking pairs in a matching.

A blocking pair (p, r) exists when proposer p and responder r both prefer each other over their current matches.

Parameters:

Returns:

  • list[tuple[str, str]] –

    List of (proposer_name, responder_name) blocking pairs.

Source code in src/gale_shapley_algorithm/stability.py 
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
def find_blocking_pairs(proposers: list[Proposer], responders: list[Responder]) -> list[tuple[str, str]]:  # noqa: ARG001
    """Find all blocking pairs in a matching.

    A blocking pair (p, r) exists when proposer p and responder r both prefer
    each other over their current matches.

    Args:
        proposers: List of proposers in the matching.
        responders: List of responders in the matching.

    Returns:
        List of (proposer_name, responder_name) blocking pairs.
    """
    blocking: list[tuple[str, str]] = []
    for proposer in proposers:
        if not (bool(proposer.preferences) and proposer.is_matched):
            continue

        better_than_match = proposer.preferences[: proposer.preferences.index(proposer.match)]
        for responder in better_than_match:
            if not isinstance(responder, Responder):
                continue

            match responder.is_matched:
                case False:
                    blocking.append((proposer.name, responder.name))
                case True if (
                    bool(responder.preferences)
                    and all(item in responder.preferences for item in [proposer, responder.match])
                    and responder.preferences.index(proposer) < responder.preferences.index(responder.match)
                ):
                    blocking.append((proposer.name, responder.name))

    return blocking

is_individually_rational 

is_individually_rational(proposers: list[Proposer], responders: list[Responder]) -> bool

Check if the matching is individually rational.

A matching is individually rational if every matched person finds their match acceptable (ranked at or above themselves).

Parameters:

Returns:

  • bool –

    True if individually rational, False otherwise.

Source code in src/gale_shapley_algorithm/stability.py 
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
def is_individually_rational(proposers: list[Proposer], responders: list[Responder]) -> bool:
    """Check if the matching is individually rational.

    A matching is individually rational if every matched person finds their
    match acceptable (ranked at or above themselves).

    Args:
        proposers: List of proposers in the matching.
        responders: List of responders in the matching.

    Returns:
        True if individually rational, False otherwise.
    """
    persons = proposers + responders
    return all(person.match is None or person.is_acceptable(person.match) for person in persons)