toptrading: Compute the top trading cycle algorithm

In matchingR: Matching Algorithms in R and C++

Description

This package implements the top trading cycle algorithm.

Usage

toptrading(utils = NULL, pref = NULL)

Arguments

utils	is a matrix with cardinal utilities of all individuals in the market. If there are n individuals, then this matrix will be of dimension n by n. The i,jth element refers to the payoff that individual j receives from being matched to individual i.
pref	is a matrix with the preference order of all individuals 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 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).

Details

The top trading algorithm solves the following problem: A set of n agents each currently own their own home, and have preferences over the homes of other agents. The agents may trade their homes in some way, the problem is to identify a set of trades between agents so that no subset of agents can defect from the rest of the group, and by trading within themselves improve their own payoffs.

Roughly speaking, the top trading cycle proceeds by identifying cycles of agents, then eliminating those cycles until no agents remain. A cycle is a sequence of agents such that each agent most prefers the next agent's home (out of the remaining unmatched agents), and the last agent in the sequence most prefers the first agent in the sequence's home.

The top trading cycle is guaranteed to produce a unique outcome, and that outcome is the unique outcome in the core, meaning there is no other outcome with the stability property described above.

Value

A vector of length n corresponding to the matchings being made, so that e.g. if the 4th element is 6 then agent 4 was matched to agent 6.

Examples

# example using cardinal utilities
utils <- matrix(c(
  -1.4, -0.66, -0.45, 0.03,
  0.72, 1.71, 0.59, 0.07,
  0.44, 1.76, 1.71, -0.27,
  0.26, 2.18, 1.4, 0.12
), byrow = TRUE, nrow = 4)
utils
results <- toptrading(utils = utils)
results

# example using ordinal preferences
pref <- matrix(c(
  2, 4, 3, 4,
  3, 3, 4, 2,
  4, 2, 2, 1,
  1, 1, 1, 3
), byrow = TRUE, nrow = 4)
pref
results <- toptrading(pref = pref)
results

Example output

Loading required package: Rcpp
      [,1]  [,2]  [,3]  [,4]
[1,] -1.40 -0.66 -0.45  0.03
[2,]  0.72  1.71  0.59  0.07
[3,]  0.44  1.76  1.71 -0.27
[4,]  0.26  2.18  1.40  0.12
     [,1]
[1,]    1
[2,]    2
[3,]    3
[4,]    4
     [,1] [,2] [,3] [,4]
[1,]    2    4    3    4
[2,]    3    3    4    2
[3,]    4    2    2    1
[4,]    1    1    1    3
     [,1]
[1,]    1
[2,]    2
[3,]    3
[4,]    4

matchingR documentation built on May 25, 2021, 9:07 a.m.