Multiplayer video game matchmaking system and methods

1. A computer-implemented method comprising:

as implemented by an interactive computing system configured with specific computer-executable instructions,

selecting a plurality of users from a pool of users, the pool of users available for selection to play an instance of a video game, wherein at least a first portion of the instance of the video game executes on a user computing device of at least one user from the plurality of users and a second portion of the instance of the video game executes on the interactive computing system;

creating a connected graph comprising a plurality of vertexes and a plurality of edges, wherein each vertex is connected by at least one edge from the plurality of edges and wherein each vertex represents a different user from the plurality of users such that each user from the plurality of users is paired within the connected graph with at least one other user from the plurality of users;

accessing user interaction data for each user of the plurality of users, the user interaction data corresponding to the user's interaction with the video game, wherein the user interaction data for the user is selected from data that is more recent than a particular time threshold;

for each edge in the connected graph, assigning a weight to the edge based at least in part on a first churn risk of a first user corresponding to a first node of the edge and a second churn risk of a second user corresponding to a second node of the edge, wherein the first churn risk is based at least in part on the user interaction data for the first user and the second churn risk is based at least in part on the user interaction data for the second user;

selecting a set of edges from the connected graph to obtain a set of selected edges based at least in part on the weights assigned to each edge within the connected graph, wherein each vertex in the connected graph is connected to at least one edge within the set of selected edges; and

initiating a playable instance of the video game using at least a pair of users corresponding to vertexes of one or more edges included in the set of selected edges.

2. The computer-implemented method of claim 1 , wherein the connected graph is a fully connected graph.

3. The computer-implemented method of claim 1 , further comprising determining the first churn risk by applying at least the user interaction data of the first user to a parameter function generated based at least in part on a machine learning algorithm.

4. The computer-implemented method of claim 1 , further comprising predicting a match outcome for a particular instance of the video game played by the first user and the second user based at least in part on the user interaction data of the first user and the user interaction data of the second user.

5. The computer-implemented method of claim 4 , further comprising determining the first churn risk by applying at least the user interaction data of the first user and the predicted match outcome to a parameter function generated based at least in part on a machine learning algorithm.

6. The computer-implemented method of claim 1 , wherein the weight comprises a summation or average of the first churn risk and the second churn risk.

7. The computer-implemented method of claim 1 , wherein selecting the set of edges comprises solving a minimum weight matching problem for the connected graph based at least in part on the weights assigned to each edge of the connected graph.

8. The computer-implemented method of claim 1 , further comprising, for each user of the plurality of users, performing a precomputation process based at least in part on the user interaction data for the user to determine a desired video game match outcome for the user.

9. The computer-implemented method of claim 8 , further comprising:

determining a fully connected graph with each vertex representing a different user from the plurality of users; and

performing a pre-filtering process on the fully connected graph based at least in part on the desired video game match outcome for each user of the plurality of users to obtain the connected graph.

10. The computer-implemented method of claim 1 , wherein:

at least said creating the connected graph occurs during a first time period; and

at least said performing an edge selection process occurs during a second time period later than the first time period.

11. The computer-implemented method of claim 10 , wherein, in response to a change of availability of at least one user in the plurality of users, an updated plurality of users is selected from the pool of users and at least said creating the connected graph is repeated during the first time period using the updated plurality of users.

12. The computer-implemented method of claim 10 , wherein the second time period begins in response to a trigger to initiate the playable instance of the video game.

13. A system comprising:

an electronic data store configured to store user interaction data for users of a video game;

a hardware processor in communication with the electronic data store, the hardware processor configured to execute specific computer-executable instructions to at least:

select a plurality of users available to play an instance of a video game, wherein at least a first portion of the instance of the video game executes on a user computing device of at least one user from the plurality of users and a second portion of the instance of the video game executes on the interactive computing system;

create a connected graph with each vertex representing a different user from the plurality of users such that each user from the plurality of users is paired within the connected graph with at least one other user from the plurality of users;

access user interaction data from the electronic data store for each user of the plurality of users, the user interaction data corresponding to the user's interaction with the video game, wherein the user interaction data for the user is selected from data that is more recent than a particular time threshold;

for each edge in the connected graph, assign a weight to the edge based at least in part on a first churn risk of a first user corresponding to a first node of the edge and a second churn risk of a second user corresponding to a second node of the edge, wherein the first churn risk is based at least in part on the user interaction data for the first user and the second churn risk is based at least in part on the user interaction data for the second user;

select a set of edges from the connected graph based at least in part on the weights assigned to each edge within the connected graph, wherein each vertex in the connected graph is connected to at least one edge within the set of selected edges; and

initiate a playable instance of the video game using at least two users corresponding to vertexes of one or more edges included in the set of selected edges.

14. The system of claim 13 , wherein the hardware processor is further configured to determine the first churn risk by applying at least the user interaction data of the first user to a parameter function generated based at least in part on a machine learning algorithm.

15. The system of claim 13 , wherein the hardware processor is further configured to:

predict a match outcome of a particular instance of the video game played by the first user and the second user based at least in part on the user interaction data of the first user and the user interaction data of the second user; and

determine the first churn risk by applying at least the user interaction data of the first user and the predicted match outcome to a parameter function generated based at least in part on a machine learning algorithm.

16. The system of claim 13 , wherein the hardware processor is further configured to solve a minimum weight matching problem for the connected graph based at least in part on the weights assigned to each edge of the connected graph as part of the edge selection process.

17. The system of claim 13 , wherein the hardware processor is further configured to create the connected graph by at least:

creating a fully connected graph with each vertex representing a different user from the plurality of users;

determining a desired video game match outcome for each user based at least in part on the user interaction data for each user; and

filtering the fully connected graph to obtain the connected graph based at least in part on the desired video game match outcome for each user.

18. A non-transitory computer-readable storage medium storing computer executable instructions that, when executed by one or more computing devices, configure the one or more computing devices to perform operations comprising:

selecting a plurality of users from a pool of users who are available to play an instance of a video game, wherein at least a first portion of the instance of the video game executes on a user computing device of at least one user from the plurality of users and a second portion of the instance of the video game executes on the interactive computing system;

creating a connected graph with each vertex representing a different user from the plurality of users such that each user from the plurality of users is paired within the connected graph with at least one other user from the plurality of users;

accessing user interaction data for each user of the plurality of users, the user interaction data corresponding to the user's interaction with the video game, wherein the user interaction data for the user is selected from data that is more recent than a particular time threshold;

for each edge in the connected graph, assigning a weight to the edge based at least in part on a first churn risk of a first user corresponding to a first node of the edge and a second churn risk of a second user corresponding to a second node of the edge, wherein the first churn risk is based at least in part on the user interaction data for the first user and the second churn risk is based at least in part on the user interaction data for the second user;

selecting a set of edges from the connected graph based at least in part on the weights assigned to each edge within the connected graph, wherein each vertex in the connected graph is connected to one or more edges within the set of selected edges; and

initiating a playable instance of the video game using a plurality of users corresponding to vertexes of one or more edges included in the set of selected edges.

19. The computer-readable, non-transitory storage medium of claim 18 , further comprising determining the first churn risk by applying at least the user interaction data of the first user to a parameter function generated based at least in part on a machine learning algorithm.

20. The computer-readable, non-transitory storage medium of claim 18 , further comprising:

predicting a match outcome of a particular instance of the video game played by the first user and the second user based at least in part on the user interaction data of the first user and the user interaction data of the second user; and

determining the first churn risk by applying at least the user interaction data of the first user and the predicted match outcome to a parameter function generated based at least in part on a machine learning algorithm.