srp

Stable roommates problem solver

This solver finds a stable matching (if such matching exists) for a given preference relation on a finite set of participants.

The preference relation can be specified in one of two ways:

• each participant has a list of potential partners ordered according to desirability or
• each participant assigns every participant a score.

This program was implemented as the final project for the course Constraint Programming (winter 2013/2014) at Charles University in Prague. The final report including results of analysis of performance is available here.

Problem definition

Stable roommates problem

Let's assume we have n participants. Each participant knows some of the participants, let's call these her potential partners. Each participant has a linear ordering of her potential partners according to preference.

Note that a participant may or may not consider herself a potential partner, i.e. the relation of potential partnership is not irreflexive.

A matching is an equivalence relation on participants that has classes of size at most 2, i.e. assigns each participant one or none partner. Matching must assign a potential partner to each of the participants.

An instability in a matching is a pair of participants each of whom prefers (according to their personal preference relations) the other to their current partner.

A stable matching is a matching that doesn't admit an instability.

In stable roommates problem, given preferences of each participant, the task is to find a stable matching.

Further reading: Wikipedia

Perfect matching

A perfect matching is a matching in which every participant is assigned somebody else.

Once we can solve general SRP, we can force a perfect matching by making sure that no participant considers herself a potential partner.

Tools

• SICStus Prolog 4.2.3
  • Solver uses libraries lists and clpfd
  • Tests use library plunit
  • Performance measurement uses library random
• NaturalDocs 1.52
  • Only required for generating documentation

Usage

srp(+Preferences, -Partners).

Preferences is a list of lists of integers. Every participant is identified by an integer between 1 and n, where n is the length of Preferences. i-th member of Preferences lists the ids of all potential partners of participant with the id i ordered from the most desirable to the least desirable.

Partners is a permutation of integers between 1 and n. i-th member of Partners is the id of the partner of the participant i in the stable matching found by the program.

Tests

This project uses plunit library for unit testing. To run the tests, consult a source file and execute goal:

plunit:run_tests.

Detailed instructions for running the tests are available in plunit documentation.

Documentation

Code documentation can be generated using NaturalDocs. A Windows batch script that facilitates the task is provided in NaturalDocs/build.bat.

Code documentation is also available on the project's GitHub web page. Note that this version is not synchronized automatically with master branch and may be outdated.