galeShapley.marriageMarket: Gale-Shapley Algorithm: Stable Marriage Problem
In matchingR: Matching Algorithms in R and C++

Description Usage Arguments Details Value See Also Examples

This function computes the Gale-Shapley algorithm and finds a solution to the stable marriage problem.

galeShapley.marriageMarket(
  proposerUtils = NULL,
  reviewerUtils = NULL,
  proposerPref = NULL,
  reviewerPref = NULL
)

`proposerUtils`	is a matrix with cardinal utilities of the proposing side of the market. If there are `n` proposers and `m` reviewers, then this matrix will be of dimension `m` by `n`. The `i,j`th element refers to the payoff that proposer `j` receives from being matched to proposer `i`.
`reviewerUtils`	is a matrix with cardinal utilities of the courted side of the market. If there are `n` proposers and `m` reviewers, then this matrix will be of dimension `n` by `m`. The `i,j`th element refers to the payoff that reviewer `j` receives from being matched to proposer `i`.
`proposerPref`	is a matrix with the preference order of the proposing side of the market. This argument is only required when `proposerUtils` is not provided. If there are `n` proposers and `m` reviewers in the market, then this matrix will be of dimension `m` by `n`. The `i,j`th element refers to proposer `j`'s `i`th most favorite reviewer. Preference orders can either be specified using R-indexing (starting at 1) or C++ indexing (starting at 0).
`reviewerPref`	is a matrix with the preference order of the courted side of the market. This argument is only required when `reviewerUtils` is not provided. If there are `n` proposers and `m` reviewers in the market, then this matrix will be of dimension `n` by `m`. The `i,j`th element refers to reviewer `j`'s `i`th most favorite proposer. Preference orders can either be specified using R-indexing (starting at 1) or C++ indexing (starting at 0).

The Gale-Shapley algorithm works as follows: Single men ("the proposers") sequentially make proposals to each of their most preferred available women ("the reviewers"). A woman can hold on to at most one proposal at a time. A single woman will accept any proposal that is made to her. A woman that already holds on to a proposal will reject any proposal by a man that she values less than her current match. If a woman receives a proposal from a man that she values more than her current match, then she will accept the proposal and her previous match will join the line of bachelors. This process continues until all men are matched to women.

The Gale-Shapley Algorithm requires a complete specification of proposers' and reviewers' preferences over each other. Preferences can be passed on to the algorithm in ordinal form (e.g. man 3 prefers woman 1 over woman 3 over woman 2) or in cardinal form (e.g. man 3 receives payoff 3.14 from being matched to woman 1, payoff 2.51 from being matched to woman 3, and payoff 2.15 from being matched to woman 2). Preferences must be complete, i.e. all proposers must have fully specified preferences over all reviewers and vice versa.

In the version of the algorithm that is implemented here, all individuals – proposers and reviewers – prefer being matched to anyone to not being matched at all.

The algorithm still works with an unequal number of proposers and reviewers. In that case some agents will remain unmatched.

This function can also be called using galeShapley.

A list with elements that specify who is matched to whom and who remains unmatched. Suppose there are n proposers and m reviewers. The list contains the following items:

proposals is a vector of length n whose ith element contains the number of the reviewer that proposer i is matched to. Proposers that remain unmatched will be listed as being matched to NA.
engagements is a vector of length m whose jth element contains the number of the proposer that reviewer j is matched to. Reviwers that remain unmatched will be listed as being matched to NA.
single.proposers is a vector that lists the remaining single proposers. This vector will be empty whenever n<=m.
single.reviewers is a vector that lists the remaining single reviewers. This vector will be empty whenever m<=n.

galeShapley.collegeAdmissions

nmen <- 5
nwomen <- 4
# generate cardinal utilities
uM <- matrix(runif(nmen * nwomen), nrow = nwomen, ncol = nmen)
uW <- matrix(runif(nwomen * nmen), nrow = nmen, ncol = nwomen)
# run the algorithm using cardinal utilities as inputs
results <- galeShapley.marriageMarket(uM, uW)
results

# transform the cardinal utilities into preference orders
prefM <- sortIndex(uM)
prefW <- sortIndex(uW)
# run the algorithm using preference orders as inputs
results <- galeShapley.marriageMarket(proposerPref = prefM, reviewerPref = prefW)
results

Loading required package: Rcpp
$proposals
     [,1]
[1,]    3
[2,]    1
[3,]    2
[4,]   NA
[5,]    4

$engagements
     [,1]
[1,]    2
[2,]    3
[3,]    1
[4,]    5

$single.proposers
[1] 4

$single.reviewers
numeric(0)

$proposals
     [,1]
[1,]    3
[2,]    1
[3,]    2
[4,]   NA
[5,]    4

$engagements
     [,1]
[1,]    2
[2,]    3
[3,]    1
[4,]    5

$single.proposers
[1] 4

$single.reviewers
numeric(0)