sri.RdFinds 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.
sri(prefs = NULL, nAgents = NULL, seed = NULL, p.range = NULL)
| prefs | valuation matrix of dimension |
|---|---|
| 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 |
sri returns a list with the following items.
agents' preference list.
edgelist of matched pairs, inculding the number of the match (matching).
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.
## 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 #>