stable roommate: "Every player must rank all other players." vs. `forget_pair`

[JnBrymn]

I have a stable roommate game with lots of players, but the game is sparse in that a large portion of the pairs are inadmissible.

During creation you check that every player must rank all other players., but I've noticed that forget_pair can be used to remove pairs before solve is called.

prefs = {
    0: [2,1,3],
    1: [0,3,2],
    2: [3,1,0],
    3: [1,0,2],
}
game = StableRoommates.create_from_dictionary(prefs)
game.players[0].forget(game.players[1])
game.players[1].forget(game.players[0])
match = game.solve()
match

results in

{0: 2, 1: 3, 2: 0, 3: 1}

So is the check really important or can it be omitted? Or equivalently, can I use forget_pair in this way or should it be renamed _forget_pair to signal that it should not be used.

If the check is not important, then it will be easier to instantiate my game because I will only need to list the admissible preferences rather than all of them.

[daffidwilde]

That's an interesting point to raise. Strictly speaking, an instance of SM requires all suitors to rank all reviewers (and vice versa), so the check is required. However, there is nothing stopping you from doing what you've done here, so what is the point of it?

The game that I believe you are describing is often called the "stable marriage problem with incomplete lists" (SMI). In SMI, you don't need the sets of suitors and reviewers to be of the same size, and players need only rank a subset of the other party. Thankfully, there always exists a stable matching for an instance of SMI. According to this PhD thesis (Section 1.1.4)*, a suitably extended version of the SM algorithm will also solve instances of SMI, albeit with an altered definition of "stability."

Given that your example completes without error, I'd say that things are roughly alright, but I cannot guarantee that the algorithm will always work as it stands. Not to mention that if (as can happen in SMI) the matching results in someone not being matched, then StableMarriage.check_validity() and StableMarriage.check_stability() will both throw errors.

But, yes, in answer to the other part of your question, renaming Player.forget() as Player._forget() seems sensible given that it is only used internally.

* that thesis has acted as a sort of reference text for a lot of the algorithms in this library

[daffidwilde]

I apologise, I misread the start of your issue there and thought you were asking about stable marriage 😅

Please give me a few minutes to get back to your actual request re: stable roommates

[daffidwilde]

Okay, so it's all much the same. SR is a special case of the stable roommates problem with incomplete lists SRI, and Irving's algorithm for SR can be extended to work for SRI. However, as with SR, a stable matching is not guaranteed for all instances of SRI. Also, as above, the check_ methods will likely fail, and I cannot guarantee that the algorithm will complete for any instance of SRI.

I've requested access to a book co-authored by Irving that offers both of the extensions I've mentioned here (for SMI and SRI) so I'll get to implementing these as soon as I can manage.

Apologies if it takes a while but I'm writing up my own thesis now and time is a precious commodity.

[JnBrymn]

No problem at all. Very interesting work that you're doing here. And the code looks really polished. I was happy at how approachable it was.

I think what I'm looking for is most akin to SRI... but I might not really care about stability! In my case people have asked to be matched up for conversations in a number of topics. People can request for matches in multiple topics. And people have been matched before, so I don't want to keep matching the same people or putting the same people in the same topic. Based upon this information, for every person that asked to be matched, I can create an incomplete ranking for them with other people in that topic. I don't so much care about stability, because people that are matched can't see the other matches, so there's no cheating. I just want to optimize the (somewhat arbitrary) score based on the topics everyone is interested in and their history.

Best wishes w/ your thesis! Close this as you see fit.

[daffidwilde]

Thank you very much, and sorry if you can't use matching for your task. It sounds like a really interesting one.

I think in the scenario you are describing the matching.games.stable_roommates.first_phase() function may be of help to you. This step would remove any irrational pairs from the preference lists, but, as you say, achieving "stable" (i.e. totally rational) matches is not so important. The first phase works by assigning tentative and not-necessarily commutative matches to the players, removing any "successors" to their proposer from each player's preference list, so you have a set of one-way matches to resolve as you choose.

The trouble with the first phase algorithm is that a player can have their preference list emptied if they are "unpopular" and are removed by everyone else. In such a case, they cannot be matched to anyone subsequently without artificially replacing some of their preference list (and other players'.) Again, if stability is not essential and you'd rather just have a good match, then this might not be a problem.

I'll close this issue now, but if you do have other questions about using matching then feel free to open another.