socialchoicekit.deterministic_matching module

class socialchoicekit.deterministic_matching.GaleShapley(resident_oriented: bool = True, zero_indexed: bool = False)

Bases: object

Resident-oriented Gale Shapley algorithm (RGS) is a deferred acceptance algorithm that finds a stable matching in the two sided matching setting. It is resident optimal.

Parameters

resident_orientedbool

If True, the social choice function will be resident-oriented. If False, the social choice function will be hospital-oriented. Resident-oriented by default.

zero_indexedbool

If True, the output of the social choice function will be zero-indexed. If False, the output will be one-indexed. One-indexed by default.

scf(resident_profile: StrictProfile, hospital_profile: StrictProfile, c: ndarray) → List[Tuple[int, int]]

The social choice function for this voting rule. Returns one item allocated for each agent.

Parameters

resident_profile StrictProfile

A (N, M) array, where N is the number of residents and M is the number of hospitals. The element at (i, j) indicates the resident’s preference for hospital j, where 1 is the most preferred hospital. If the resident finds a hospital unacceptable, the element would be np.nan.

hospital_profile: StrictProfile

A (M, N) array, where M is the number of hospitals and N is the number of residents. The element at (i, j) indicates the hospital’s preference for resident j, where 1 is the most preferred resident. If the hospital finds a resident unacceptable, the element would be np.nan.

c: np.ndarray

A M-array containing the capacities of the hospitals.

Returns

List[Tuple[int, int]]

A list containing assignments (resident, hospital) for each assignment.

class socialchoicekit.deterministic_matching.Irving(zero_indexed: bool = False)

Bases: object

Algorithm for computing an optimal stable matching introduced in [ILG1987] and modified for cardinal utilities (called weighted preference lists in the paper). This algorithm works with a simplified version of the hospital resident problem (HR) where each hospital can only take one resident, and the number of hospitals and residents are equal. We call this the stable marriage problem (SM). We replace residents with men and hospitals with women. The algorithm also will only work with complete valuation profiles.

Parameters

zero_indexedbool

If True, the output of the social choice function will be zero-indexed. If False, the output will be one-indexed. One-indexed by default.

construct_sparse_rotation_poset_graph(rotations: List[List[Tuple[int, int]]], preference_lists_1: Dict[int, ndarray], eliminating_rotation_of_pair: Dict[Tuple[int, int], int]) → Dict[int, List[int]]

This is an internal routine to construct sparse rotation poset graph P’ as described in [ILG1987] Nodes: rotation Edges: From rule 1 and 2

Rule 1: If (m, w) is a member of a rotation, say pi, and w’ is the first woman below w in m’s list such that (m, w’) is a member of some other rotation, say rho, then P’ contains adirected edgefrom pi to rho. Rule 2: If (m, w’) is not a member of any rotation, but is eliminated by some rotation, say pi, and w is the first woman above w’ in m’s list such that (m, w) is a member of some rotation, say rho, then P’ contains a directed edge from pi to rho. The way we implement Rule 2 is for all pairs (m, w) that are members of some rotation, we find all pairs (m, w’) where w’ is between w and the next w’’ such that (m, w’’) is a member of some rotation.

Parameters

rotations: List[List[Tuple[int, int]]]

preference_lists_1: Dict[int, np.ndarray]

preference_lists_2 is not necessary.

eliminating_rotation_of_pair: Dict[Tuple[int, int], int]

eliminate_rotations(stable_matching: List[Tuple[int, int]], rotations: List[List[Tuple[int, int]]]) → List[Tuple[int, int]]

This is an internal routine to apply a series of eliminations to a stable matching in the order given in the rotations parameter. Eliminating with valid rotations will ensure stability. Algorithm as described in [ILG1987].

Parameters

stable_matching: List[Tuple[int, int]]

A stable matching. This is in the form outputted by Gale-Shapley.

rotations: List[List[Tuple[int, int]]]

A list containing all the rotations to be applied. Each rotation is in the form (m_0, w_0), …, (m_{r-1}, w_{r-1}) where each m_i, w_i are 0-indexed. Rotations must be in the order of application. Subsequent rotations must be exposed after the previous rotation is applied.

Returns

List[Tuple[int, int]]

The stable matching after applying the eliminations.

find_all_rotations_and_eliminations(preference_lists_1: Dict[int, ndarray], preference_lists_2: Dict[int, ndarray]) → Tuple[List[List[Tuple[int, int]]], Dict[Tuple[int, int], int]]

This is an internal routine to find the set of all rotations that we can obtain by eliminating some rotations, as described in [ILG1987]. This includes the rotations that are already exposed in a stable matching. We also note for each pair if there is a rotation that eliminates it. The parameters indicate the reduced preference lists at the time of finding a stable matching.

Complexity

O(n^3)

Parameters

preference_lists_1: Dict[int, np.ndarray]

A dictionary where the key is an integer indicating a man in 0-index. The value is an array of integers. The kth element indicates the man’s kth most preferred woman in his shortlist in 0-index. This shortlist must be reduced. The dictionary must contain n keys and each preference list must be at most n long.

preference_lists_2: Dict[int, np.ndarray]

A dictionary where the key is an integer indicating a woman in 0-index. The value is an array of integers. The kth element indicates the woman’s kth most preferred man in her shortlist in 0-index. This shortlist must be reduced. The dictionary must contain n keys and each preference list must be at most n long.

Returns

Tuple[List[List[Tuple[int, int]]], Dict[Tuple[int, int], int]

Each item is described below.

List[List[Tuple[int, int]]]

A list containing all the rotations reachable in the stable matching. Each rotation is a list of 0-indexed man-woman pairs.

Dict[Tuple[int, int], int]

A map from a 0-indexed man-woman pair (m, w) to the 0-indexed index (in the first item of the returned tuple) of the rotation that eliminates it.

static find_initial_preference_lists(stable_marriage: List[Tuple[int, int]], profile_1: ndarray, profile_2: ndarray) → Tuple[Dict[int, ndarray], Dict[int, ndarray]]

This is an internal routine to find the initial preference lists.

Parameters

stable_marriage: List[Tuple[int, int]]

profile_1: np.ndarray

0-indexed. Note: this argument will be consumed and change to the preference list after applying al rotations found.

profile_2: np.ndarray

0-indexed. Note: this argument will be consumed and change to the preference list after applying al rotations found.

Returns

Tuple[Dict[int, np.ndarray], Dict[int, np.ndarray]]

all entries are 0-indexed all arrays should have np.integer dtype.

find_maximum_weight_closed_subset(P_prime: Dict[int, List[int]], rotations: List[List[Tuple[int, int]]], valuation_profile_1: IntegerValuationProfile, valuation_profile_2: IntegerValuationProfile) → Set[int]

This is an internal routine to obtain a maximum weight closed subset of the rotation poset graph P’. This routine uses Ford-Fulkerson to find the maximum weight closed subset.

Parameters

P_prime: Dict[int, List[int]]

The rotation poset graph P’, which can be constructed by construct_sparse_rotation_poset_graph

rotations: List[List[Tuple[int, int]]]

Set of all rotations in the rotation poset graph. The index of the rotation corresponds to its index in P’.

valuation_profile_1: IntegerValuationProfile

valuation_profile_2: IntegerValuationProfile

Returns

Set[int]

The maximum weight closed subset of the rotation poset graph P’. Each element is the index of a rotation in the input rotations (and corresponds to a node in P’).

find_rotations(preference_lists_1: Dict[int, ndarray], preference_lists_2: Dict[int, ndarray]) → List[List[Tuple[int, int]]]

This is an internal routine to find the set of all rotations that are exposed in a stable matching, given the preference lists. We find the solution by constructing the graph G(S) as described in [ILG1987] and finding all cycles in G(S).

Complexity

O(n)

Parameters

preference_lists_1: Dict[int, np.ndarray]

A dictionary where the key is an integer indicating a man in 0-index. The value is an array of integers. The kth element indicates the man’s kth most preferred woman in his shortlist in 0-index. Each man’s shortlist does not have to be fully reduced. Only the first and second elements are used. The dictionary must contain n keys and each preference list must be at most n long.

preference_lists_2: Dict[int, np.ndarray]

A dictionary where the key is an integer indicating a woman in 0-index. The value is an array of integers. The kth element indicates the woman’s kth most preferred man in her shortlist in 0-index. Each woman’s shortlist does not have to be reduced. Only the last element is used. The dictionary must contain n keys and each preference list must be at most n long.

Returns

List[List[Tuple[int, int]]]

A list containing all the rotations in exposed the stable matching. Each rotation is a list of 0-indexed man-woman pairs.

static rotation_weight(rotation: List[Tuple[int, int]], valuation_profile_1: IntegerValuationProfile, valuation_profile_2: IntegerValuationProfile) → float

The weight of a rotation as defined in [ILG1987]. The weight of the rotation must be smaller than sys.maxsize to work with Irving.

Parameters

rotation: List[Tuple[int, int]]

Rotations of the form [(m_0, w_0), …, (m_{r-1}, w_{r-1})] where m_i, w_i are 0-indexed.

valuation_profile_1: IntegerValuationProfile

The male valuation profile.

valuation_profile_1: IntegerValuationProfile

The female valuation profile.

Returns

float

The weight of the rotation.

scf(valuation_profile_1: IntegerValuationProfile, valuation_profile_2: IntegerValuationProfile, profile_1: StrictCompleteProfile | None = None, profile_2: StrictCompleteProfile | None = None) → List[Tuple[int, int]]

The social choice function for this voting rule. Returns a stable matching that optimizes social welfare based on the given valuation profile. The optional ordinal profile parameters will be useful if the valuation profile(s) provided are simulated (or estimated) and contains ties. The ordinal profile(s) will be used to maintain stability. The Irving algorithm [ILG1987] assumes a strict ordering of preferences to create rotations. If a strict complete ordinal profile is not given, the ordinal profile will be automatically computed from the valuation profile (ties will be randomly broken). To break ties in some other way, use profile_utils.compute_ordinal_profile.

Parameters

valuation_profile_1: IntegerValuationProfile

A (N, N) array, where N is the number of men and also the number of women. The element at (i, j) indicates the ith man’s cardinal preference for woman j.

valuation_profile_2: IntegerValuationProfile

A (N, N) array, where N is the number of women and also the number of men. The element at (i, j) indicates the ith woman’s cardinal preference for man j.

profile_1: Optional[StrictCompleteProfile]

An optional (N, N) array, where N is the number of men and also the number of women. The element at (i, j) indicates the ith man’s ordinal preference for woman j. 1 is the most preferred. If None, then the ordinal profile will be computed from the valuation profile.

profile_2: Optional[StrictCompleteProfile]

An optional (N, N) array, where N is the number of women and also the number of men. The element at (i, j) indicates the ith woman’s ordinal preference for man j. 1 is the most preferred. If None, then the ordinal profile will be computed from the valuation profile.

Returns

List[Tuple[int, int]]

A list containing assignments (resident, hospital) for each assignment.

static stable_matching_value(stable_matching: List[Tuple[int, int]], valuation_profile_1: IntegerValuationProfile, valuation_profile_2: IntegerValuationProfile) → int

The cardinal utility (social welfare) of a stable matching. In [ILG1987], this is defined as c(S).

Parameters

stable_matching: List[Tuple[int, int]]

A stable matching. This is in the form outputted by Gale-Shapley.

valuation_profile_1: IntegerValuationProfile

valuation_profile_2: IntegerValuationProfile

Returns

int

The cardinal utility (social welfare) of the stable matching.