Randomly matching users

Question

I'm trying to think of an algorithm that randomly pairs Users based on some User defined attributes (location, interests, etc). Many apps and games have implemented similar algorithms, for example, Tinder (the popular dating mobile app) randomly matches Users based on their locations, gender, and age. Though, with Tinder, it doesn't matter about both Users "pairing" with each other. Whereas, I'm trying to pair Users for some sort of instant communication and interaction.

The problem is I don't know where to begin. I don't want to reinvent the wheel if its been done so many times or at least use another implementation as a reference. Though, my Google searches haven't been resourceful, most likely due to not exactly knowing what to search for, such as, a specific algorithm name.

How would I implement a weighted random User matching algorithm? A best match algorithm would be even better. I don't expect you to provide all the code for one (unless it's really easy), psuedo-code/theory or a link to a well defined library or implentation will do.

What I'm thinking of so far:

Storing/Connecting

• Separate Users into two tables: Active and Passive. Active User performs random search/pair algorithm through the Passive table. Sends matched Passive User a match request. Passive User accepts first received match request denies all others. Users are matched for communication and can be removed from the tables. Might need a timeout for the Passive User if it's not "picked" after some time so it can become an Active User.

Searching

• Active User randomly selects set amount of Passive Users based on something like set range from Active Users location. Take into account Passive Users set range from their location?

Weighted Algorithm

• Each User defined attribute is assigned a specific weight for importance. Calculate number of matched attributes (what about similar or in range?) along with their weight combined together. Sort Users based on their match value. Perform storing/connecting stage for the highest matched Passive User. If that User accepts match request, they are connected, if not try next highest matched Passive User. If no connection is made start entire algorithm over.

Answer 1

Here's what I have so far.

How would I implement a weighted random User matching algorithm?

There are multiple parts to implementing such an algorithm. You need a way to determine the similarity between users and a way of rating this similarity. Also, you need a way of performing the algorithm, for instance: do all the users go into a pool and the server makes the matches or do you separate the users and one performs the operation while the other waits to be matched (as stated in the question).

As for determining the similarity between users, look into Collaborative Filtering. This StackExchange question and answer deal with a similar problem. Collaborative Filtering is normally used for recommendation systems (e-commerce site recommending products you may be interested in) but the basis of the algorithms can be applied to matching similarities between users.

Similarity rating depends on the specific algorithm you choose to use but a weighted value is one way to do it. In this case, each attribute a user contains is assigned a weighted value which signifies the importance of that value to the algorithm. The higher the weighted value the more important it is. The weighted value you choose by which you deem more important. This value is meaningless on its own but is useful relative to the algorithm. Similarly, the total computed similar value assigned to the user (outcome value of the whole algorithm with the weights applied) is meaningless on its own but is useful when compared to other users with a computed value.

Once these values are obtained, you can simply sort the users (highest value being most similar) and then connect. But how exactly do you determine similarity between users? One way would be to look at the attributes and see if they equal.

For example, say all users are assigned a "likesMusic" attribute which is a boolean value. To compare this attribute between User 1 and User 2 see if they equal:

if(User1.getLikesMusic() == User2.getLikesMusic()){
    return 1;
else{
    return 0;
}

The value 0 can be used in the algorithm for no match and 1 can be used for exact match. The returned value can then be multiplied by the attributes assigned weight value and added to all the other attribute calculations. This works fine for values that are either a match or not but what about values that can be somewhat of a match? For example, consider an attribute "favFoods" which is a set of a users favorite foods. Users can share some, all, or no favorite foods.

return (User1.getFavFoods().intersection(User2.getFavFoods()) / User1.getFavFoods().size());

The above pseudo-code compares how similar User2's favorite foods are to User1's by getting the amount of intersecting values between sets and dividing by User1's set length. Note: the values will have to be switched to get how similar User1's favorite foods are to User2's. The benefit of this approach is it keeps us in a return range between 0 and 1. This way we can keep our initial values of 1 being an exact match and 0 being no match and everything between will be a somewhat match.

This works fine for sets and lists but what about values that can be in a range? That's where things get a little more complicated. For example, consider each user has an age attribute. The closer the age the better the match. We can take the difference between two users age then the higher the difference the smaller the match value. But at what rate does the match value get smaller when the difference value get larger? This value, rate of decrease, must be chosen by whatever fits your particular application. For example, let's say for every two years difference we decrease the similarity by ten percent. Since 1 will be an exact match, with this rate of decrease, we have:

return 1 - ((abs(User1.getAge() - User2.getAge()) / 2) * 0.1);

Note: you will have to watch out to make sure that the value you are subtracting from 1 does not exceed 1 because we don't want a negative number.

The above equations should cover the majority of situations you will encounter. Now, if we know all the "types" of the users attributes (exact, set, or range), we can use the correct formula to get the value, V, multiply by its weight, W, and get the total match value between two users, M:

M = (V1 * W1) + (V2 * W2) + , ... , + (Vn * Wn)

This algorithm will be enough for a one way match (if you allow set attributes to have different lengths then User1 may match really well with User2 but User2 may not match as well with User1, surprisingly). So, for a two way match you would need to adapt the algorithm. For instance, perhaps you could perform the match algorithm from User1 to User2 and User2 to User1 and average the values to get a total two way match value between the users.

As for how to perform the algorithm (separate users into two tables, Active and Passive, allow Active Users to perform algorithm on Passive Users and send connect request, add users to pool and have server to perform algorithm on each combination of user, or another way), I haven't found much information on which is the best approach. So I guess it's dependent on preference, environment, and efficiency.