m-ad rating system

[Rémi Coulom]

We see that the basic m-ad rating satisfies the stability condition:

• • A' + B' = A + B

If we assume that young weaker players tend to make faster progress than old stronger players, then this "stability condition" will cause rating deflation.

Rémi

[Dirt]

We see that the basic m-ad rating satisfies the stability condition:

• • A' + B' = A + B

If we assume that young weaker players tend to make faster progress than old stronger players, then this "stability condition" will cause rating deflation.

Rémi

I don't really see deflation. If everyone starts out at, say, zero and no one is ever dropped from the list then the average should always be zero. I do think that people new to the list would usually be vastly over rated, and intermediate players could inflate their rating by preferentially playing them. I guess above a certain level the ratings would stabilize, but below that things would be a permanent mess.

[Rémi Coulom]

We see that the basic m-ad rating satisfies the stability condition:

• • A' + B' = A + B

If we assume that young weaker players tend to make faster progress than old stronger players, then this "stability condition" will cause rating deflation.

Rémi

I don't really see deflation. If everyone starts out at, say, zero and no one is ever dropped from the list then the average should always be zero. I do think that people new to the list would usually be vastly over rated, and intermediate players could inflate their rating by preferentially playing them. I guess above a certain level the ratings would stabilize, but below that things would be a permanent mess.

Yes, you are right: it all depends on the initial rating of new entrants. In a setting like a game server, where players may choose their opponents, such a system would not work at all. Players greedy for rating points would always play against new entrants.

I think it is important in a good incremental rating system to give a higher variability of rating to newcomers than to established players. The "stability condition" given by Wlod is, in my opinion, a very bad property for a rating system, whatever the initial rating of newcomers.

Rémi

[wlod]

Reminder: Stability of a m-ad rating list means that the average rating is always the same, say M. It is achieved by assigning rating M to every new player, and by making the sum of the post-game ratings of the two players the same as the pre-game sum.

I think it is important in a good incremental rating system to give a higher variability of rating to newcomers than to established players.

It's not that simple. Each stick has two ends. I don't want the well established ratings to be messed up bad (neither up nor down) by the newcomers. This is why the games between players who are at the given moment similar should have a higher weight than games between players who are different. That's all. And that's what the m-ad system does (see the previous post about the m-ad weight).

The "stability condition" given by Wlod is, in my opinion, a very bad property for a rating system, whatever the initial rating of newcomers.

The stability condition, together with the fixed size floating pools of players, is excellent and perhaps the only chance to compare meaningfully players from different epochs. Let me present and explain such system.

We will have several rating lists. First of all a list for the entire chess public. Then the top lists say of the top 4096 players, 2048, 1024, ..., 128, 64, 32 (with their separate ratings). The top lists will store more players than 4096, ..., 32 respectively, but only 4096, ..., 32 will be active with respect to the given list at any time. Everybody is active on the general list but only strong players are active on the top lists. The strongest players are active on all lists.

It works as follows. When just before the game, both you and your partner are among top 4096 players of the general list then your game counts also for the top 4096 list. If this is your first ever game which counts for the top 4096 list then your pre-game top-4096 rating is that list's constant. For the sake of this post let's assume that each list has the initial rating constant equal 1000. Thus your pre-game rating on the top 4096 will be 1000. When this happens then one of the top 4096 players stops being active on the top 4096 list. S/he may become active again on that same top 4096 list if later s/he will do well in competitions. Then s/he will continue with the their frozen top-4096 rating--it will be defrosted.

And those who are active on the top-4096 list, and who are there in the top 2048, have their games rated also on the top-2048 list. Etc. (There is still one fine point to address but I want to keep this post reasonably non-long).

The fixed number of the active players on the list assures us that the comparisons between players from different times are meaningful. On the other hand, when the size of the pool of players varies then the top players have more of the pretty strong players to milk, and those pretty strong players have accumulated points from so-so strong players, etc. The greater number of the players the better chance for the top player to set a record. But when the size of the pool of active players on the given list is fixed then your rating has the same meaning relatively to the strength of the players from your own time as a rating of a player from the past or from the future with respect to their time.

Regards,

• Wlod

[wlod]

M-ad rating can be applied to any game or even any collection of competitions, between two players, where the result of each game or encounter can be represented by a real number a between 0 and 1. The result of the game is understood to be the result of the first player. The second player result of the same game is b := 1-a.

Rating may depend on different factors, but the basic m-ad rating function

• • Df = Df(A B a)

depends only on the pregame ratings A B of the two players, and on the result of the game a. I will provide an especially suitable, specific basic function, but at this moment let me just insist, that it satisfies the 0-sum axiom, namely:

• Df(A B a) + Df(B A 1-a) = 0

Then [...] we [...] define the post-game ratings as:

• • A' := A + Df(A B a)
    B' := B + Df(B A 1-a)

We see that the basic m-ad rating satisfies the stability condition:

• • A' + B' = A + B

The principle of the m-ad rating is simple: you win your opponent points, which also means that you lose your own points:

Let dyn be a constant real number, 0 < dyn < 1, called the dynamic coefficient. The m-ad Df-function is defined as follows:

• • Df(A B a) := dyn*(a*B - b*A)

where b := 1-a. Obviously:

• • Df(B A b) = -Df(A B a)

i.e. the 0-sum condition holds. And if ratings A B > 0 were positive then

• A' := A + Df(A B a) = A + dyn*(a*B - b*A) > A - b*A = a*A >/ 0

hence

• • A' > 0

which means that if the initial rating of each player is positive then all player ratings at all times will be positive. Actually, a m-ad rating list assigns a fixed rating M > 0 to each player new to the list. Thus all m-ad ratings are always positive. Furthermore, the average rating (arithmetic mean) of the list is always equal to M.

Code: Select all

    a= 1    ==>   A'  =  A + dyn*B
    a=1/2   ==>   A'  =  A + dyn*(B-A)/2
    a = 0   ==>   A'  =  A - dyn*A  =  (1 - dyn)*A

Remark: This rating function R may be called multiplicative or exponential.( At one time I called it Ockham rating function). For psychological reasons it may be a good idea to consider also an equivalent rating function, say:

• • r := C + D*log(R)

for some positive constants C D > 0. The derived rating function r may be called additive or logarithmic.

In the next post I'll explain in what precise sense m-ad function R is multiplicative.

Regards,

• Wlod

[wlod]

The principle of the m-ad rating is simple: you win your opponent points, which also means that you lose your own points:

Let dyn be a constant real number, 0 < dyn < 1, called the dynamic coefficient. The m-ad Df-function is defined as follows:

• • Df(A B a) := dyn*(a*B - b*A)

where b := 1-a.

Thus the new ratings are given by formulas:

Code: Select all

    A'  :=  A + dyn*(a*B - b*A)
    B'  :=  B + dyn*(b*A - a*B)

Let's switch to the language of 2-dim vectors and 2x2-matrices. Let I be the diagonal identity matrix, and matrix M be the one suggested by the above rating formulas, i.e.:

Code: Select all

             1   0                           -b   a
    I  :=                           M  :=
             0   1                            b  -a

Next, let X^^ stands for the matrix transposition of matrix X, and let

Code: Select all

    V := [A B]^^      and      V' := [A' B']^^

be the column rating vectors of two players before and after a game. Then

• • V' = (I + dyn*M) * V

where

• • M = [1 -1]^^ * [-b a]

while:

• • [-b a] * [1 -1]^^ = [-1]

It follows that:

Code: Select all

    M*M  =  [1  -1]^^ * [-b  a] * [1  -1]^^ * [-b  a]

         =  [1  -1]^^ * [-1] * [-b  a]  =  -M

i.e.

• • M*M = -M

Let's apply this simple identity:

• (I + p*M) * (I + q*M) =
  • I + (p+q)*M + p*q*M*M =
    I + (p+q)*M - p*q*M =
    • I + (1 - (1-p)*(1-q))*M

The last result (in bold) serves as an induction step for the more general (iterated) one about an n-fold product:

• • Prod(I+p_k*M : k=1...n) = I + (1 - Prod(1-p_k : k=1...n))*M

Let's state the special case of p_k = p for k=1...n as a theorem (why not? ):

THEOREM

• • (I + p*M)^n = I + (1 - (1-p)^n)*M

Corollary

• (I + dyn*M)^n --> I + M (when n --> infinity)

***

I'll continue (I hope),

• Wlod

[wlod]

Code: Select all

             1   0                           -b   a
    I  :=                           M  :=
             0   1                            b  -a

Next, let X^^ stands for the matrix transposition of matrix X, and let

Code: Select all

    V := [A B]^^      and      V' := [A' B']^^

be the column rating vectors of two players before and after a game. Then

• • V' = (I + dyn*M) * V

where

• • M = [1 -1]^^ * [-b a]

while:

• • [-b a] * [1 -1]^^ = [-1]

It follows that:

• • Prod(I+p_k*M : k=1...n) = I + (1 - Prod(1-p_k : k=1...n))*M

Let's state the special case of p_k = p for k=1...n:

THEOREM

• • (I + p*M)^n = I + (1 - (1-p)^n)*M

Corollary

• (I + dyn*M)^n --> I + M (when n --> infinity)

Let's simplify the formulas by introducing q_k := 1-p_k and q := 1-p = 1-dyn. Then we can write:

• • Prod(I+p_k*M : k=1...n) = I + (1 - Prod(q_k : k=1...n))*M

THEOREM

• • (I + p*M)^n = I + (1 - q^n)*M

First player's success s := det(S) is decided by the success matrix S:

Code: Select all

          a   b
    S :=                    hence  s = a*B - b*A
          A   B

So that:

• M*V = [s, -s]^^

Let

• • V_n := [A_n B_n]^^

be the rating vector of the two players after n-game match; in particular V_0 = V and V_1 = V'. Then:

Code: Select all

    V_n  =  (I + p*M)^n * V  =

        (I + (1-Prod(q_k : k=1...n))*M) * V

        =  V + (1-Prod(q_k : k=1...n)) * M*V

        =  V + (1-Prod(q_k : k=1...n)) * [s, -s]^^

i.e.

Code: Select all

    A_n  =  A + (1-Prod(q_k : k=1...n))*s

    B_n  =  B - (1-Prod(q_k : k=1...n))*s

In particular, when p_1=...=p_n = p = dyn, and q := 1-p, we have:

Code: Select all

    A_n  =  A + (1 - q^n)*s

    B_n  =  B - (1 - q^n)*s

Since

Code: Select all

            A + s  =  (A+B)*a

            B - s  =  (A+B)*b

we get also the following equivalent form of A_n and B_n:

Code: Select all

        A_n  =  (A+B)*a - (q^n)*s

        B_n  =  (A+B)*b + (q^n)*s

I'll give first applications of the above (simple) formulas in the next posts. Furthermore, the general analytic can go also in another direction, which I hope to present.

Regards,

• Wlod

[wlod]

First player's success s := det(S) is decided by the success matrix S:

Code: Select all

          a   b
    S :=                    hence  s = a*B - b*A
          A   B

Indeed, the pre- and post-game ratings A B and A' B' respectively behave in the following natural way:

Code: Select all

    A' < A  &  B' > B  when  s < 0,  i.e. when  a/b < A/B;
    A' = A  &  B' = B  when  s = 0,  i.e. when  a/b = A/B;
    A' > A  &  B' < B  when  s < 0,  i.e. when  a/b > A/B.

Here 0 \< b := 1-a \< 1. When b=0 then a/b = oo is infinity, and bigger than any real number.

We see that m-ad rating is multiplicative.

[wlod]

Code: Select all

        A_n  =  (A+B)*a - (q^n)*s

        B_n  =  (A+B)*b + (q^n)*s

Since 0 < q < 1, we get:

Code: Select all

          A_n  -->  (A+B)*a     when  n --> oo

          B_n  -->  (A+B)*b     when  n --> oo

     A_n / B_n -->  a/b         when  n --> oo

Thus at the end of a long match, with the result of each game equal to a:b (b:=1-a), the ratio of the ratings will be close to a/b. Once again we see that the (basic) m-ad rating function is multiplicative -- that's why, for naive reasons, it's nice to provide players with the logarithm (or a psychologically proper linear function of the logarithm) of the basic function, i.e. with the additive version.

[wlod]

when p_1=...=p_n = p = dyn, and q := 1-p, we have:

Code: Select all

        A_n  =  (A+B)*a - (q^n)*s

        B_n  =  (A+B)*b + (q^n)*s

Assume that the first player's pre-match rating was lower, A < B, but s/he is making progress by achieving score a > 1/2 in each game. How many games it will take the first player to overcome the second? Let's compute a sequence of equivalent inequalities:

Code: Select all

    A_n > B_n

    (A+B)*a - (q^n)*s  >  (A+B)*b + (q^n)*s

    (A+B)*(a-b)  >  2*(q^n)*s

    q^n  <  (A+B)*(a-b) / (2*s)

    n * log(q)  <  log((A+B)*(a-b)/(2*s))

    -------------------------------------
    n  >  log((A+B)*(a-b)/(2*s)) / log(q)
    -------------------------------------

The direction of the last inequality got reversed because log(q) < 0. Next:

Code: Select all

    (A+B)*(a-b)  =  2*s + (A-B)*(a+b)

            =  2*s - (B-A)
hence

        -----------------------------------
        n  >  log(1 - (B-A)/(2*s)) / log(q)
        -----------------------------------

i.e. A_n > B_n if and only if the above inequality "n > ..." holds. Now try the same with Elo .

Observe that the number of games which the first player needs to overcome the second player depends only on variables: a dyn & A/B, but not on specific A & B, meaning that if the pre-match ratings were C*A & C*B, the value of the minimal n would be still the same.