This function computes the Irving (1985) algorithm for finding a stable matching in a one-sided matching market.
roommate(utils = NULL, pref = NULL)is a matrix with cardinal utilities for each individual in the
market. If there are n individuals, then this matrix will be of
dimension n-1 by n. Column j refers to the payoff that
individual j receives from being matched to individual 1, 2,
..., j-1, j+1, ...n. If a square matrix is passed as utils, then
the main diagonal will be removed.
is a matrix with the preference order of each individual in the
market. This argument is only required when utils is not provided.
If there are n individuals, then this matrix will be of dimension
n-1 by n. The i,jth element refers to j's
ith most favorite partner. Preference orders can either be specified
using R-indexing (starting at 1) or C++ indexing (starting at 0). The
matrix pref must be of dimension n-1 by n. Otherwise,
the function will throw an error.
A vector of length n corresponding to the matchings that were
formed. E.g. if the 4th element of this vector is 6 then
individual 4 was matched with individual 6. If no stable
matching exists, then this function returns NULL.
Consider the following example: A set of n potential roommates, each
with ranked preferences over all the other potential roommates, are to be
matched to rooms, two roommates per room. A matching is stable if there is no
roommate r1 that would rather be matched to some other roommate
d2 than to his current roommate r2 and the other roommate
d2 would rather be matched to r1 than to his current roommate
d1.
The algorithm works in two stages. In the first stage, all participants begin unmatched, then, in sequence, begin making proposals to other potential roommates, beginning with their most preferred roommate. If a roommate receives a proposal, he either accepts it if he has no other proposal which is better, or rejects it otherwise. If this stage ends with a roommate who has no proposals, then there is no stable matching and the algorithm terminates.
In the second stage, the algorithm proceeds by finding and eliminating
rotations. Roughly speaking, a rotation is a sequence of pairs of agents,
such that the first agent in each pair is least preferred by the second
agent in that pair (of all the agents remaining to be matched), the second
agent in each pair is most preferred by the first agent in each pair (of
all the agents remaining to be matched) and the second agent in the
successive pair is the second most preferred agent (of the agents
remaining to be matched) of the first agent in the succeeding
pair, where here 'successive' is taken to mean 'modulo m',
where m is the length of the rotation. Once a rotation has been
identified, it can be eliminated in the following way: For each pair, the
second agent in the pair rejects the first agent in the pair (recall that the
second agent hates the first agent, while the first agent loves the second
agent), and the first agent then proceeds to propose to the second agent
in the succeeding pair. If at any point during this process, an agent
no longer has any agents left to propose to or be proposed to from, then
there is no stable matching and the algorithm terminates.
Otherwise, at the end, every agent is left proposing to an agent who is also proposing back to them, which results in a stable matching.
Note that neither existence nor uniqueness is guaranteed, this algorithm
finds one matching, not all of them. If no matching exists, this function
returns NULL.
# NOT RUN {
# example using cardinal utilities
utils <- matrix(c(
-1.63, 0.69, -1.38, -0.03,
2.91, -0.52, 0.52, 0.22,
0.53, -0.52, -1.18, 0.53
), byrow = TRUE, ncol = 4, nrow = 3)
utils
results <- roommate(utils = utils)
results
# example using preference orders
pref <- matrix(c(
3, 1, 2, 3,
4, 3, 4, 2,
2, 4, 1, 1
), byrow = TRUE, ncol = 4)
pref
results <- roommate(pref = pref)
results
# }
Run the code above in your browser using DataLab