Gale_Shapley {rpm}

This is the version of Gale-Shapley stable matching algorithm (translated from the Matlab code in Menzel (2015)).

Description

This code allows the self-matched option

Usage

Gale_Shapley(U, V, return.data.frame = FALSE, cpp = TRUE, nmax = 10 * nrow(U))

Arguments

U

The utility matrix for the women's side. Each row is a woman, each column is a man. The matrix entry (i,j) is the utility that woman i gains from pairing with man j. In other words, the utility is computed from woman i's perspective.

V

The utility matrix for the men's side. Each column is a man, each row is a woman. The matrix entry (i,j) is the utility that man j gains from pairing with woman i. In other words, the utility is computed from man j's perspective.

return.data.frame

logical Should a data.frame of the matching be returned instead of the paring matrix mu?

cpp

logical Should the Rcpp version of the code be used. This is much faster and uses a lot less memory.

nmax

count The maximum number of iterations of the inner loop within the Gale-Shapley algorithm. This can be reduced to speed up the algorithm at the potential cost of many partnerships being non-equilibruim.

Value

The function return depends on the return.data.frame value. If TRUE, it returns

data.frame

a two-column data.frame with the first column a women's index and the second column the men's index of their partner. It has as many rows as there are partnerships.

If FALSE, it returns the following matrix:

mu

If cpp=TRUE, a vector of length the number of women (nrow(U)) with the index of the matching man (i.e., the index is the row in V of the man). If there is no matching man, the index is 0. This can be used to reconstruct the matching matrix. If cpp=FALSE, the matching matrix, where 1 represents a pairing, 0 otherwise. Each row is a woman, each column is a man. The order of the rows is the same as the rows in U. The order of the columns is the same as the columns in V.

References

Goyal, Shuchi; Handcock, Mark S.; Jackson, Heide M.; Rendall, Michael S. and Yeung, Fiona C. (2023). A Practical Revealed Preference Model for Separating Preferences and Availability Effects in Marriage Formation, Journal of the Royal Statistical Society, A. doi:10.1093/jrsssa/qnad031

Dagsvik, John K. (2000) Aggregation in Matching Markets International Economic Review, Vol. 41, 27-57. JSTOR: https://www.jstor.org/stable/2648822, doi:10.1111/1468-2354.00054

Menzel, Konrad (2015). Large Matching Markets as Two-Sided Demand Systems Econometrica, Vol. 83, No. 3 (May, 2015), 897-941. doi:10.3982/ECTA12299

See Also

rpm