I was thinking about game ladder scoring recently. I recall being frustrated at Supreme Commander for putting me lower on the ladder than someone I’ve beaten. I want a ladder algorithm that won’t allow that.
In particular, I want a ladder function l: (P × P → Z) × P → R which assigns to each player a number and satisfies the following properties [P is the set of players, Z is the integers, R is the reals; the first argument to l is the set of games played: given two players p and q, it returns how many times p has defeated q]:
- If g(p,q) > g(q,p) then l(g,p) > l(g,q) (if I’ve beaten you more times than you’ve beaten me, then I have a higher ladder score than you).
- If for all players q, g(p,q) = h(p,q) and g(q,p) = h(q,p), then l(g,p) = l(h,p) (your score doesn’t change if you haven’t played any games).
Of course, property #1 already causes problems. Let’s say p has defeated q once, q has defeated r once, and r has defeated p once; the vice-versas are zero. Then l(g,p) > l(g,q) > l(g,r) > l(g,p), which is impossible. I really had no right to be mad at Supreme Commander for ranking someone I had defeated above me; it’s impossible to avoid.
That doesn’t solve the problem though. Saying it’s unsolvable isn’t a solution… we’ve got to find the best solvable solution.
I could relax the constraint in rule #1 to be ≥ rather than >, but then the problem becomes too solvable. A plethora of trivial solutions emerges: l(g,p) = 0 for all p, l(g,p) = 0 for all p but the one person who has beaten every player more times than he has been beaten by them, etc. We need to add another property to get rid of these trivial solutions.
The ≥ constraint forces every player in a cycle to be assigned the same number. We can’t get around that. So maybe we can try to say that if you’re not in a cycle with a player, then your score is distinct from his.
I knew I put that second property in there for a reason. That, too, is impossible. Picture two cycles of size, say, 50. Pick one element p from the first cycle, q from the second. Can you change a bunch of arrows, as long as you don’t change any arrows to or from p or q to make the two cycles one big cycle? Of course you can. By our axiom, p‘s and q‘s scores were distinct, but now they’re in a cycle together, so one of them must have changed. But neither p nor q needed to play any games for that to happen. This violates our second property.
So basically you can’t even get close to the two properties I stated above. The fact is that player rankings are nothing like real numbers, so don’t try to force them in.
You can satisfy the second property without the first by summing over all players q the function f(p,q) where f is defined by:
f(p,q) = 1 if g(p,q) > g(q,p), -1 if g(p,q) < g(q,p), and 0 otherwise.
Which has the nice property that you can have many rematches without taking advantage of the scoring. But, of course, it doesn’t have the other nice properties that I want…