This function computes the Irving (1985) algorithm for finding a stable matching in a one-sided matching market.
is a matrix with cardinal utilities for each individual in the
market. If there are
is a matrix with the preference order of each individual in the
market. This argument is only required when
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
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
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 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
A vector of length
n corresponding to the matchings that were
formed. E.g. if the
4th element of this vector is
4 was matched with individual
6. If no stable
matching exists, then this function returns
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
# 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
Add the following code to your website.
For more information on customizing the embed code, read Embedding Snippets.