2

I'm trying to write an algorithm (specifically in Ruby) that will rank teams based on their record against each other. If a team A and team B have won the same amount of games against each other, then it goes down to point differentials.

Here's an example:

A beat B two times
B beats C one time
A beats D three times
C bests D two times
D beats C one time
B beats A one time

Which sort of reduces to

A[B] = 2
B[C] = 1
A[D] = 3
C[D] = 2
D[C] = 1
B[A] = 1

Which sort of reduces to

A[B] = 1
B[C] = 1
A[D] = 3
C[D] = 1
D[C] = -1
B[A] = -1

Which is about how far I've got

I think the results of this specific algorithm would be:

A, B, C, D

But I'm stuck on how to transition from my nested hash-like structure to the results.

My psuedo-code is as follows (I can post my ruby code too if someone wants):

For each game(g):
  hash[g.winner][g.loser] += 1

That leaves hash as the first reduction above

hash2 = clone of hash
For each key(winner), value(losers hash) in hash:
  For each key(loser), value(losses against winner):
    hash2[loser][winner] -= losses

Which leaves hash2 as the second reduction

Feel free to as me question or edit this to be more clear, I'm not sure of how to put it in a very eloquent way. Thanks!

5
  • 5
    ELO?
    – user40980
    Commented Jun 12, 2014 at 3:40
  • It definitely looks similar to it, but there seem to be various versions of it
    – Tom Prats
    Commented Jun 12, 2014 at 3:53
  • 1
    You're missing a time component. (In sports at least) a recent win is often much more significant then a win in the past.
    – Pieter B
    Commented Oct 10, 2014 at 9:25
  • Your "solution" is just code. It doesn't describe the algorithm you are using, it doesn't give a justification for the algorithm.
    – gnasher729
    Commented Jun 8, 2015 at 11:15
  • For example "A beats B twice and loses once" is absolutely not the same as "A beats B once". The latter leaves the possibility that A is much much stronger than B, the former doesn't. You have destroyed information with that change.
    – gnasher729
    Commented Jun 8, 2015 at 11:17

3 Answers 3

2

Rating the relative strengths of teams/contestants is sort of a solved problem, so why re-invent the wheel?

There is the Elo rating system, originally devised for chess, and there is also the Glicko (pdf) rating system.

Both systems try to model the probability that one contestant will win against another, and produce a score representing their relative strength. I.e. higher rating means a stronger player.

The Elo system is zero-sum, and has a few thorny edge cases.

The Glicko system is not zero-sum, but it also models the confidence of the score as well; i.e. a player with a single data point isn't weighted as high as a player with many data points. It tries to fix some of the downsides of the Elo system.

Based on your question you probably want one of these systems, even if you don't realize it yet.

1
  • Thanks for the additional insight. What I actually wanted was to just choose based off of wins, then point difference, then total points, then direct matchups, butttt I was told to make it differently. I'll look into these for later though
    – Tom Prats
    Commented Jul 8, 2015 at 1:20
1

You appear to be dealing with a feedback arc set. Because each team plays more than once, you're looking at a more complex situation than the minimum case though you could conceivably do the number of wins as a weight and still wind up with a restricted case that has a valid approximate solution in O(log|V|loglog|V|) time.

1

If this is a real life problem, then you must expect inconsistent data, like A beats B, B beats C, C beats A. You already showed inconsistent amounts of information: A played B and D three times each, but didn't play C at all.

I'd make a model describing how likely a team is to beat another team, and find values that agree best with the model. For example "every team has a strength from 0 to 10. If a team is stronger by an amount x ≥ 0 than another team, then it will beat that team with probability 1 - exp (-x^2) / 2". So with identical strength chances are even, but a much stronger team is very likely to win most games.

You could start with an initial guess that every team has a strength of 5, and estimate the chances to get the result of your data. Then you modify the data randomly and check if that improves the chances of getting your data.

Your Answer

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

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