<p>I am trying to find a way to return a list of ideal matches based on preferences.</p>
<p>This is similar to the <a href="https://en.wikipedia.org/wiki/Stable_roommates_problem" rel="nofollow noreferrer">Stable Roommate Problem</a>. I have a list of people, and each person has ranked everyone else from most to least desirable. Given their preferences, I want to match everyone up as ideally as possible.</p>
<p>Here's what I mean by ideal matching: Let's say the system adds a number to a count for every match. If someone's paired with their top choice, +1 to the count; with their 2nd choice--&gt;+2, 3rd--&gt;+3, etc. I'm trying to find a set of matches that results in the lowest count possible.</p>
<p><strong>Is there an existing algorithm that would work to achieve the lowest score possible?</strong></p>
<p>There are a lot of solutions out there using Irving's Algorithm, like <a href="https://github.com/virinchivarma/GameTheory/blob/master/stable_roommates/stable_roommates.py" rel="nofollow noreferrer">this one</a>, but those solutions don't return a list of matches when stable matching isn't possible.</p>

CC BY-SA 4.0
2021-08-11T20:12:52.500Z
@Giskard fair. My b, I'm new here. I'll do my best to define what I'm looking for more objectively:

Let's say the system adds a number to a count for every match. If someone's paired with their top choice, +1 to the count; with their 2nd choice-->+2, 3rd-->+3, etc. 

I'm trying to find a set of matches that results in the lowest count possible. Stable matching I believe would do that. However, when stable matching isn't possible, I still want to return a set of matches that keeps the count as low as possible. Does that make sense?

Happy to clarify further as needed. Thanks!
jameskyolk
CC BY-SA 4.0
2021-08-11T20:25:00.130Z
Seems to me that you have two separate questions here. Please [edit the body of your question](https://economics.stackexchange.com/posts/47174/edit) so that it becomes one of these, and if you would like, you can post the other one as a separate question. 1) What algorithim achieves the lowest score? 2) If a stable matching exists, does it achieve the lowest score? (I don't think this is generally true.)
Giskard
CC BY-SA 4.0
2021-08-12T04:49:50.263Z
It is also possible to formulate these problems as a mixed-integer programming problem. There are some papers showing how variants and extensions of the SRP can be formulated and solved.
Erwin Kalvelagen
CC BY-SA 4.0
2021-08-12T14:01:59.840Z
@Giskard done! ty
jameskyolk
CC BY-SA 4.0
2021-08-12T14:23:02.600Z
@ErwinKalvelagen I'll look into that, thanks!
jameskyolk
<algorithms><matching>
Stable roommates problem: returning a list of ideal matches, even when stable matching doesn't exist
jameskyolk
# Stable roommates problem: returning a list of ideal matches, even when stable matching doesn't exist

(Asked by: username_0 on 2021-08-10)

I am trying to find a way to return a list of ideal matches based on preferences.

This is similar to the [Stable Roommate Problem](https://en.wikipedia.org/wiki/Stable_roommates_problem). I have a list of people, and each person has ranked everyone else from most to least desirable. Given their preferences, I want to match everyone up as ideally as possible.

Here's what I mean by ideal matching: Let's say the system adds a number to a count for every match. If someone's paired with their top choice, +1 to the count; with their 2nd choice-->+2, 3rd-->+3, etc. I'm trying to find a set of matches that results in the lowest count possible.

**Is there an existing algorithm that would work to achieve the lowest score possible?**

There are a lot of solutions out there using Irving's Algorithm, like [this one](https://github.com/virinchivarma/GameTheory/blob/master/stable_roommates/stable_roommates.py), but those solutions don't return a list of matches when stable matching isn't possible.

**Tags:** algorithms, matching
> **Comments:**
> **username_0**: @Giskard fair. My b, I'm new here. I'll do my best to define what I'm looking for more objectively:  Let's say the system adds a number to a count for every match. If someone's paired with their top choice, +1 to the count; with their 2nd choice-->+2, 3rd-->+3, etc.   I'm trying to find a set of matches that results in the lowest count possible. Stable matching I believe would do that. However, when stable matching isn't possible, I still want to return a set of matches that keeps the count as low as possible. Does that make sense?  Happy to clarify further as needed. Thanks!  
> **username_1**: Seems to me that you have two separate questions here. Please [edit the body of your question](https://economics.stackexchange.com/posts/47174/edit) so that it becomes one of these, and if you would like, you can post the other one as a separate question. 1) What algorithim achieves the lowest score? 2) If a stable matching exists, does it achieve the lowest score? (I don't think this is generally true.)  
> **username_2**: It is also possible to formulate these problems as a mixed-integer programming problem. There are some papers showing how variants and extensions of the SRP can be formulated and solved.  
> **username_0**: @Giskard done! ty  
> **username_0**: @ErwinKalvelagen I'll look into that, thanks!  

---

## 0 answers

