1
$\begingroup$

As a side-project, I had the idea to write some kind of an algorithm that would evaluate all participations in our weekly Pub quiz, to then calculate the average strength of the participants.

This is the information that I have available:

  • The final score of the group
  • All members of the group for a particular week
    • As such, also the team size
    • As such, also all the past participations of every single person

This is how I attempted to solve it:

The first, and obviously the simplest solution that I had, was thinking of the information that I have as a system of linear equations:

$$ 0 * x_1 + 0 * x_2 + 0 * x_3 + \dots + 0 * x_n = S $$

The idea was that every row represents a game, every participant gets an ID somewhere between 1 and n and every person who participated on that specific week gets a factor 1 in the corresponding row with the rest getting a zero. after solving all the linear equations, the value of each $ x_n $ would represent how strong the person with ID $ n $ is, and the $ S $ would be the final score of the group for that week. (In the case where it's impossible to solve it, use the difference between expected answers and calculated answer as fitness to be minimized). Obviously this had a ton of flaws, the biggest one being that it would predict insane scores for bigger groups, since all the strengths are added together. This seemed like an easy fix with adding:

$$ (0 * x_1 + 0 * x_2 + 0 * x_3 + \dots + 0 * x_n) * (1 - w * log(P)) = S $$

with $ P $ being the number of players. This already worked a lot better, the idea was that the overlap of knowledge goes up logarithmically multiplied by some weight that will get calculated in the future. (can then be rewritten as $ S / (1 - w * log(P)) $ once w is set to some constant). While this "worked" for a couple of months, I am spotting more and more flaws that seem to be unsolvable without scrapping the whole system of linear equations stuff. The reason why I believe ML to not be a good solution for this, and the same reason why I think this isn't purely a data science question, is because with one datapoint being added per week, that's 52 data points per year, which I believe is way too low for any type of actual machine learning.

The problems:

  • The biggest flaw that I see in my system is that for a player $ x_a $ with a low weight it is often that:

$$ (x_1 + \dots + x_n) * (1 - w * log(P)) > (x_1 + \dots + x_n + x_a) * (1 - w * log(P + 1)) $$

which to me seems absolutely absurd. (Adding an extra person to the group leads to lower predicted score than without that person)

  • Second biggest flaw I see that the probabilities are missing from the equation. Assume 4 Players get 20 points on a bad week, then get 30 points on the next week with a 5th player who is participating for the first time. The solution that I get every time is to set the 5th player strength to 10 and make the 30 point game have no influence on the other 4 players. That's definitely not the solution I am looking for though, as I would expect all games to have at least some influence on the strength of all participants.

The question is, are there any real life problems that are similar to this? Does this type or class of problem already have a name?

$\endgroup$

1 Answer 1

1
$\begingroup$

I suspect this is primarily a statistics and data modelling question, rather than a question about computer science.

If you have a model $f$ for predicting the score of a team from the strengths of the participants (i.e., the predicted score is $f(x_1,\dots,x_k)$, where $x_1,\dots,x_k$ represent the strengths of each participant in the team), then you could use inference to try to predict the unknown strengths $x_1,\dots,x_n$ from the observed scores. You would define a loss function $\ell$ that computes how "bad" an incorrect prediction is, such as squared error: $$\ell(\hat{s},s) = (\hat{s}-s)^2,$$ where $\hat{s}$ is the predicted score and $s$ is the true score. Then, you would define a total loss $$L(x_1,\dots,x_n) = \sum_i \ell(f(x_{p_{i,1}},\dots,x_{p_{i,k}}),s_i),$$ where $s_i$ is the score of the $i$th team, and $p_{i,1},\dots,p_{i,k}$ are the participants of the $i$th team. Finally, you would use a numerical optimization algorithm to find $x_1,\dots,x_n$ that minimize $L(x_1,\dots,x_n)$.

This leaves open the question of how to build an appropriate model. That will require domain expertise and possible some intuition and art. I don't know how to choose an appropriate model. I imagine that a team with two members with strengths $x_1,x_2$ does better than a team with one member of strength $(x_1+x_2)/2$ (e.g., in the two-person team, one person might know a lot about action movies and the other person might know a lot about romance movies, so the former can answer some questions that the latter cannot and vice versa), but worse than a team with one member of strength $\max(x_1,x_2)$ (sometimes the two team members both think they know the answer but disagree, and they're basically flipping a coin between them). So, I leave you to devise a plausible model. Perhaps the average strength could be a reasonable starting point for a model, or you could try a few models and see which seem to yield the best results (e.g., at predicting scores for the last two weeks given data on all prior weeks).

You asked about related concepts. You might be interested in the Bradley-Terry model, which is definitely different but still related. You might also be interested in rating systems for individuals in team games. I'm not very well informed on that topic. You might be interested in TrueSkill and TrueSkill2, though I think their model $f$ would be inappropriate for your particular setting.

$\endgroup$
1
  • $\begingroup$ The model is indeed what I was struggling with the most, the first part is already something that I had though of, with Nelder Mead algorithm for coming up with the strengths. $\endgroup$ Dec 23, 2022 at 12:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.