Figure out algorithm for matchmaking.

[JnBrymn]

Context

You are matching people based upon topics they've expressed interest in and the match-making history that they have had. The goal is to identify a set of pairs (or triples) that maximizes the overall "utility" of the round. For the sake of practicality it would also be nice if the algorithm scales well per number of people (though it won't matter too much initially as n is so low).

I don't know what "utility" means in yet, but here are some properties of it:

• Meeting someone new is high utility, meeting someone twice in a row is low or negative utility.
• Meeting for a new topic is high utility, meeting twice in a row for the same topic is negative utility <- but this might be different depending upon how many topics a person has selected. For example, if the use just has 1 topic, then then meeting for the same topic is ok.
• I guess 2 people meeting is higher utility than 3
• In the future... who knows what else we might add to "utility".

Stupid match-making algo:

• enumerate all possible matches and calculate the utility of each
• from the set of all possible matches, enumerate all the set of sets of matches that are allowable (e.g. you don't select 2 different matches that involve the same person), calculate the "aggregate utility" for all sets-of-sets
• pick the best

(This feels like Bogosort)

TODO

• [ ] Research the algo
• [ ] ...
• [ ] At the end of the algo, remember to try and add unmatched people into the matched pairs.
• [ ] Test all the pieces!
• [ ] If we introduce a numpy dependency, make sure it's not to memory hungry: review the change in this dashboard
• [ ] Using my scoring function, compare my manual pairing with the pairing from the algorithm we choose.

[JnBrymn]

Research

• Blog post about match making algo for games
• Cute blog post about the Gale-Shapley algorithm
  • but this appears to make matches among 2 different types of objects (doctors to hospitals)
  • Gale-Shapley Algo Wikipedia
  • Stable Marriage Problem Wikipedia
• Stable Roommates Problem Wikipedia requires only type of entity, so this is closer to our problem.
• Matching: A Python library for solving matching games (github) - includes Stable Roommate algo

To consider next:

• How good is the Stable Roommates Problem solver in the python "matching" library? Maybe we can just use that. (Watch out for how the algorithm deals with an odd number of people and with unstable match rounds... e.g. does it just throw an error?)
• I know it's not provably stable, but what if you just randomly picked matches, and then iteratively tried swapping matches until you couldn't find a better option.
• Eventually if we moved away from rounds, we could have "continuous matching" where as people became available we'd check the match scores with other people waiting and if they were above some threshold score we would match them and if it took too long to reach the threshold, we'd slowly lower it.

[ghost]

Interesting note I thought I'd throw up here.

When we were discussing this algorithm in PennyHack a few weeks ago, I wrote down a couple of thoughts on what makes a priority, and I got similar results to your utility list, although slightly different.

1. The people are the highest priority. It would be good to gather engagement data from people as they move along and attach it to users. i.e. in a follow-up poll post-match one of the questions listed would be "on a scale of 1-10, how interested did X seem in the topic?" This would allow for matches to be made where you have super engaged and interested users in the topic they're discussing, although this could get complicated to track and might not be worth enough. Maybe just the idea of a Penny Chat reliability rating I mentioned in chat a while back - make sure that each person has a reliable/knowledgeable match.

2. Second priority is the topic they're discussing. Similar to the Gale-Shapley algorithm you linked + using the blog post as a reference, users could start with picking the topic they are most interested in learning about, and then other topics they would be less interested in. Once again, this would drive the most engagement, but would also probably be tough to implement and require the use of multiple algorithms (probably a more efficient solution out there).

3. Meeting for a new topic is high utility, meeting twice in a row for the same topic is negative utility I had the same thought, but I based it off of how often was it since they last met. Did they match up great with the other criteria, and only miss on this one? Then base it off of how recently they last met. Example 1 - you match great with the other two criteria, but you met in the last chat, prioritize the next in line. Example 2 - you have two people who match well with a 3rd user, but one met with the user 2 weeks ago, the other met with the user 4 weeks ago. They're both pretty recent, but prioritize the 4 week old user before moving on to one that doesn't meet the criteria as well.

[JnBrymn]

I think you're thinking pretty well through this. Once we get more people the "reliability" will be particularly interesting to thing about. And it's weird, too: should we match reliable people only with reliable people? This would be great for them, but I bet you can occasionally mix the unreliable in with the reliable people and convert them into people that are more interested in the chats and therefore more reliable. Another way to put it: if reliable people only meet with reliable people then they feel like the chats are great; if un-reliable people only meet with un-reliable people then they feel like the chats are awful – both groups will be justified in their behavior.

BUT... all that said, all I really hope to do now is to enumerate all the signals that we'll have to play with in the future and get some really basic things in place for now. It will be dumb at first :D

[JnBrymn]

One annoyance with the python matching package is that it requires numpy which is kinda a memory hog. We'll see something like a 20MB bump in memory per worker. That might be ok, but I'm having bad memories of introducing numpy at Eventbrite and causing lots of people grief.

[JnBrymn]

Also concerning is that StableRoomates algorithms can have no stable outcome, and when this happens the algorithm just give you nothing:

from matching.games import StableRoommates
prefs = {
    1: [2, 3],
    2: [3, 1],
    3: [1, 2],
}
game = StableRoommates.create_from_dictionary(prefs)
match = game.solve()
match

{1: None, 2: None, 3: None}

[JnBrymn]

Based on this conversation, I can't directly use the matching library https://github.com/daffidwilde/matching/issues/128 - but I think I might copy bits of the algorithm. It's not that complex.

[ghost]

RE: No stable outcome

Couldn't you run check_stability() after creating the dictionary and before solve, then try and determine some way to figure out which one specifically causes a problem? User would then be asked to resubmit their preferences with a message like "Your choices ended up being invalid, please resubmit" (although that would be frustrating). If you're going to make a fork anyways to implement SRI that could be another good addition to mark which person's preference sent back the error.

RE: matching#128

I think everything here makes sense to me, except how we're going to sort based on multiple criteria. Would it just be run multiple times? Here's what I'm thinking this would turn out to be right now to help better understand my confusion:

1. Stable roommates runs, and matches people up by topic preferences (although how do we get it to match up multiple people to a topic?)
2. Using the people who matched correctly in a topic, it then runs based on preference for another score (reliability, past interest, past chats, etc.) to determine their partner. For example, if you have 3 people in a topic with a score of 94, 65, and 78, the preference would be [1, 3, 2]. Next question is how do we determine this score?
3. That last run generates the final matches and the bot sends out requests.

That all sounds right, but also seems a little too complicated for our use case so I assume you have a simplified version in your head.

This is bringing out the non-existent (yet) data scientist in me :smile:. Glad to be reading up on this though, as I'll probably be implementing a similar project at work.

[JnBrymn]

@deadbender, in my mind, the scoring algorithm can be separated from the matching algorithm. I imaging a score_pair function that takes two players and creates a score based on the players' past interactions. The score is arbitrary, but at least reflects our goals of always matching new people, not matching people that were just match recently, etc.

Now given score_pair, for a given player you can find her score if she is matched with all other players that signed up for the same topic. And with all of those scores in hand, we can create a sorted list of preferences.

From this point forward we don't have to worry about score any more, we just use SRI to dump out the matches and we return the matches.

But I don't know how well SRI will work for our problem. It optimizes "stability" (where no 2 players would prefer one another over the match we chose for them). But with SRI, sometimes stable solutions can't be found while we can at least make matches that are not stable. I'm thinking about using some sort of simulated annealing approach https://en.wikipedia.org/wiki/Simulated_annealing maybe inspired by the traveling salesman problem https://en.wikipedia.org/wiki/Travelling_salesman_problem#Heuristic_and_approximation_algorithms. I did find this R implementation of SRI thought https://rdrr.io/rforge/matchingMarkets/src/R/sri.R.

[JnBrymn]

So, digging a little more this weekend. It seems that rather than a "Stable Roommate" problem, a better model is the "Maximum Weight Matching" problem. Every person can be matched with only some other people and there is an associated score that would be associated with each pair, find a "matching" that maximizes the score.

I've read about half of this paper https://web.eecs.umich.edu/~pettie/papers/ApproxMWM-JACM.pdf and if we implement the algorithm on page 14 then we're set. Problem is I read it and can't tell what it's saying 😬 . I think I could figure it out given a little time but before I go further down that road, I think I'll take a look at this package's max_weight_matching function.

[JnBrymn]

This is pretty neat:

import networkx as nx
G = nx.Graph()
G.add_edge('A', 'B', weight=1)
G.add_edge('B', 'C', weight=1)
G.add_edge('C', 'A', weight=100)
G.add_edge('C', 'D', weight=1)

I'm making a graph that says that person A can connect to B, or C; B can connect to A or C; C can connect A or B or D.

A---B
 \ /
  C
  |
  D

And I'm ascribing weights to how much "utility" would be derived from the match.

If I do this nx.algorithms.max_weight_matching(G) then the result it {('A', 'C')} indicating that this is the matching that will maximize the score. However with nx.algorithms.max_weight_matching(G, maxcardinality=True), the second argument insists that we match the most number of people, no matter the score, and then at least get the best score within that. In this case the result comes back {('A', 'B'), ('C', 'D')} indicating that the algorithm has foregone the highest scoring match in order to make the most matches. Not bad!

The only problem (which isn't a problem at all for now) is that it scales with number of nodes n as O(n^3) - so it'll get slow really fast as we get more people. The paper above said it scaled linearly somehow.