# Algorithm(s) for creating balanced 5-a-side teams?

I play 5-a-side soccer twice a week. 10 people play each game out of a pool of about 30 people who are giving the opportunity to play as it's first come first serve. Some people play more often than others.

The best matches are the ones where the score stays even throughout the game because they are the most competitive. Our rules are as following: first team to score 5 goals gets 1 point then the goals count resets.

The problem is figuring out how to pick balanced teams. I am going to program a script to log teams and scores over time and I am wondering what algorithm(s) can I use to generate the teams based on this history keeping in mind that we wont always have the same 10 players but we might have the same 8 players, etc?

• This is a modelling problem first and foremost. Only after you come up with a reasonable statistical model, can you start thinking about algorithms. – Yuval Filmus Jun 27 '15 at 5:18
• Indeed. First, you need to come up with some real-world measure of "balancedness" and how the different players contribute to that. – David Richerby Jun 27 '15 at 9:05
• @DavidRicherby Yuval Filmus... Yeah I've realized now the question is actually very vague. I will come up with a model and rephrase the question. Thanks. – Jonathan Jun 27 '15 at 12:17

This is a modelling question. One plausible model might be as follows. Each player as a strength, which is a real number. The strength of a team is the sum of the strengths of the players on the team. If team A plays team B, then team A will win with probability $f(s_A - s_B)$, where $f$ is the logistic function, $s_A$ is the strength of team A, and $s_B$ is the strength of team B.

This is an example of a possible model. It might or might not be a good model. But if we assume this model is correct, then it is possible to infer the approximate strength of each player, given the outcomes of a bunch of matches. If $s$ is a vector that describes the strengths of all players, define $L(s)$ to be the likelihood of this vector. In particular, $L(s)$ is formed by computing the product of the likelihood for each match that was played. To compute the likelihood of a match between $A$ and $B$, you use $s$ to calculate the probability $p$ that A wins (assuming $s$ is the correct strength); if A actually won, the likelihood of that outcome is $p$, otherwise it is $1-p$. (I assume there are no ties.) For any particular $s$, you can calculate the likelihood of each match outcome like this, multiply them together, and get $L(s)$. Now, to find the "best fit", you find the vector $s$ that maximizes $L(s)$. This is known as a maximum-likelihood method.

How do you find the vector $s$ that maximizes $L(s)$? Basically, you use some mathematical optimization method, like gradient descent.

If you assume this model is correct, another procedure to find the strengths of the players would be to use logistic regression. However, ultimately this will end up being equivalent to what I articulated above.

Of course, you might find that the model I outlined is not a good model. In that case, your task is to find a better probabilistic model that describes the probability that team A will beat team B, as a function of the strengths of the players. Then, you can use the techniques sketched above to infer the strengths of each player.

Finally, once you have the strength of each player, the probabilistic model will let you evaluate different ways of assigning people to teams and figure out which one is most balanced (where the probability of winning for team A is as close to one-half as possible).

This approach assumes you only take into account who won, but not the score. It would be possible to consider more sophisticated probabilistic models that also try to describe the distribution of scores as a function of the strengths of the players, but this will be more complex. I suggest you stay simple for now.

You could also look at the Elo rating system and research whether there's any way to generalize it to apply to your setting, where each team has multiple players and you want to rate the strength of each individual player.

• Elo probably isn't a good starting point for football because you'd need to generalize it in two directions. First, you're trying to rate individual players in a team sport; second, Elo assumes that all wins are equal whereas, in football, you'd come to different conclusions if team A beat team B 2-1 than if they won 12-1. – David Richerby Jun 28 '15 at 8:31