All stable matchings in the stable roommates problem with incomplete lists

Usage

sri(prefs = NULL, nAgents = NULL, seed = NULL, p.range = NULL)

Arguments

prefs
valuation matrix of dimension nAgents x nAgents that gives column-players' ranking over other players in decreasing order of preference (i.e. most preferred first).
nAgents
integer that gives the number of players in the market.
seed
integer setting the state for random number generation.
p.range
range of two intergers p.range = c(p.min, p.max), where p.min < p.max. Produces incomplete preference lists with the length of each player's list randomly sampled from the range [p.min, p.max]. Note: interval is always too small because non-permissible matches are automatically deleted.

Value

sri returns a list with the following items.
prefs
agents' preference list.

matching
edgelist of matched pairs, inculding the number of the match (matching).

Description

Finds all stable matchings (if one exists) in the stable roommates problem with incomplete lists using the Prosser (2014) constraint encoding based on either given or randomly generated preferences.

References

Gusfield, D.M. and R.W. Irving (1989). The Stable Marriage Problem: Structure and Algorithms, MIT Press.

Prosser, P. (2014). Stable Roommates and Constraint Programming. Lecture Notes in Computer Science, CPAIOR 2014 Edition. Springer International Publishing, 8451: 15--28.

Irving, R.W. and S. Scott (2007). The stable fixtures problem: A many-to-many extension of stable roommates. Discrete Applied Mathematics, 155: 2118--2129.

Examples

## Roommate problem with 10 players, given preferences:
prefs <- matrix(rep(1:10, 10), 10, 10)
sri(prefs=prefs)
$prefs [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [1,] 2 1 1 1 1 1 1 1 1 1 [2,] 3 3 2 2 2 2 2 2 2 2 [3,] 4 4 4 3 3 3 3 3 3 3 [4,] 5 5 5 5 4 4 4 4 4 4 [5,] 6 6 6 6 6 5 5 5 5 5 [6,] 7 7 7 7 7 7 6 6 6 6 [7,] 8 8 8 8 8 8 8 7 7 7 [8,] 9 9 9 9 9 9 9 9 8 8 [9,] 10 10 10 10 10 10 10 10 10 9$matchings
matching playerA playerB
1        1       1       2
2        1       3       4
3        1       5       6
4        1       7       8
5        1       9      10

## Roommate problem with 10 players, random preferences:
sri(nAgents=10, seed=1)
$prefs [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [1,] 3 3 10 5 9 5 10 4 5 3 [2,] 4 6 2 6 6 8 3 3 7 1 [3,] 5 10 6 2 7 4 4 9 4 6 [4,] 7 5 1 10 4 2 9 7 3 7 [5,] 2 7 9 8 8 1 8 5 10 5 [6,] 8 8 8 9 10 7 2 10 2 4 [7,] 9 4 7 1 1 9 5 2 1 2 [8,] 6 1 5 7 2 3 1 6 8 8 [9,] 10 9 4 3 3 10 6 1 6 9$matchings
matching playerA playerB
1        1       1       2
2        1       3      10
3        1       4       6
4        1       5       9
5        1       7       8

## Roommate problem with no equilibrium matching:
sri(nAgents=10, seed=2)
$prefs [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [1,] 2 6 7 1 10 1 8 3 4 4 [2,] 7 3 4 2 3 10 10 10 7 9 [3,] 5 7 10 7 1 7 6 1 1 8 [4,] 10 9 2 8 2 2 2 2 3 3 [5,] 6 5 6 6 6 5 9 7 2 1 [6,] 8 4 1 5 4 4 3 4 5 2 [7,] 3 1 8 10 7 3 4 6 10 5 [8,] 4 10 5 9 9 8 1 9 8 6 [9,] 9 8 9 3 8 9 5 5 6 7$matchings
[1] "No stable matching exists for this instance."

## Roommate problem with 3 equilibria:
sri(nAgents=10, seed=3)
$prefs [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [1,] 2 6 1 10 3 3 9 7 8 1 [2,] 8 5 2 2 8 2 1 10 6 3 [3,] 4 9 9 9 2 8 10 9 4 4 [4,] 3 4 8 8 4 7 5 4 1 6 [5,] 9 10 4 6 10 5 2 3 5 7 [6,] 6 8 10 7 9 9 4 1 7 2 [7,] 5 1 5 1 1 1 6 6 2 5 [8,] 10 3 6 5 7 10 8 2 3 9 [9,] 7 7 7 3 6 4 3 5 10 8$matchings
matching playerA playerB
1         1       1       4
2         1       2       6
3         1       3      10
4         1       5       7
5         1       8       9
6         2       1       3
7         2       2       6
8         2       4      10
9         2       5       9
10        2       7       8
11        3       1       3
12        3       2       6
13        3       4      10
14        3       5       7
15        3       8       9