StableRoommates returning None for simple problems

[MartinMohlenkamp]

This simple example:

import matching
from matching.games import StableRoommates
preferences = {'A' : ['B'], 'B' : ['A']}
game = StableRoommates.create_from_dictionary(preferences)
game.solve()

returns {A: None, B: None}

I think the problem is in stable_roommates.py within forget_successors. Line 113 player.unmatch() erases the correct matching, which is then never recovered.

I have version '1.3.2'.

[daffidwilde]

Hi @MartinMohlenkamp, thanks for bringing this up but this behaviour is expected currently. The StableRoommates class implements Irving's algorithm which consists of two phases:

• The first phase eliminates any unreasonable pairings (in this example there are none) through one-way, temporary proposals. The player.unmatch() line is required to clear up these proposals in any other example.
• The second phase locates and removes all-or-nothing cycles from the preference lists (see the linked paper for details on that.) However, this stage requires at least one player to have more than one player in their preference list. As this is not the case here, the second_phase() function is never called and no matches are set.

I hope that clears things up. I appreciate that this appears rather unsatisfying, but I would prefer not to muck about with the algorithm implementation for the sake of a trivial case. Having said that, I'd happily accept a small catch in the StableRoommates.solve() method for when len(players) == 2.

Let me know your thoughts

[MartinMohlenkamp]

@daffidwilde, the problem is not specific to two players. These also fail:

preferences = {'A' : ['B','C','D'],
          'B' : ['A','C','D'],
          'C' : ['A','B','D'],
          'D' : ['A','B','C']}

preferences = {'A' : ['B','C','D'],
          'B' : ['A','C','D'],
          'C' : ['D','B','A'],
          'D' : ['C','B','A']}

Based on your description, in any case when the second phase does not trigger, the code will fail. What if player.unmatch() was moved from the end of phase 1 to the beginning of phase 2? That would leave the matches intact when phase 2 is not called.

[daffidwilde]

Yes, you are absolutely right. That is quite the oversight by me.

Your solution sounds good, and I've run it through some other examples as well without issue. So, yeah, I'm happy for the unmatching to happen in the second phase 😄

[daffidwilde]

Hi @MartinMohlenkamp, I've implemented the changes you've suggested here and released a new version on PyPI

I'll close the issue now, but if anything else comes up then please let me know! Thanks again