Description Usage Arguments Details Value Examples

This function computes the Irving (1985) algorithm for finding a stable matching in a one-sided matching market.

1 |

`utils` |
is a matrix with cardinal utilities for each individual in the
market. If there are |

`pref` |
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
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`

.

A vector of length `n`

corresponding to the matchings that were
formed. E.g. if the `4`

th element of this vector is `6`

then
individual `4`

was matched with individual `6`

. If no stable
matching exists, then this function returns `NULL`

.

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
``` |

Embedding an R snippet on your website

Add the following code to your website.

For more information on customizing the embed code, read Embedding Snippets.