roommate: Compute matching for one-sided markets

In jtilly/matchingR: Matching Algorithms in R and C++

Compute matching for one-sided markets

Description

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

Usage

roommate(utils = NULL, pref = NULL)

Arguments

utils

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.

pref

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.

Details

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.

Value

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.

Examples

# 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

jtilly/matchingR documentation built on Feb. 15, 2023, 3:24 a.m.