Constraint model to produce all stable matchings in the stable roommates problem with incomplete lists

Share:

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.

Usage

1
sri(prefs = NULL, nAgents = NULL, seed = NULL, p.min = NULL)

Arguments

prefs

valuation matrix of dimension nAgents x nAgents that gives column-players' valuation over row players.

nAgents

integer that gives the number of players in the market.

seed

integer setting the state for random number generation.

p.min

integer, when specified produces incomplete preference lists with the length of each player's list randomly sampled from the range [p.min, nrow(prefs)].

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).

Author(s)

Thilo Klein

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.

Examples

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
## Roommate problem with 10 players, given preferences:
prefs <- matrix(rep(1:10, 10), 10, 10)
sri(prefs=prefs)

## Roommate problem with 10 players, random preferences:
sri(nAgents=10, seed=1)

## Roommate problem with no equilibrium matching:
sri(nAgents=10, seed=2)

## Roommate problem with 3 equilibria:
sri(nAgents=10, seed=3)