From: David desJardins <xxxxxxxxxxxxxxxxxxxxxx>
Newsgroups: rec.games.backgammon
Subject: Restatement of FIBS Rating Theorem
Date: 22 Dec 1998 10:19:05 -0800
Organization: UC Berkeley Math Department
Message-ID: <vohhfuoqbty.fsf@bosco-fddi.berkeley.edu>
Reply-To: David desJardins <xxxxxxxxxxxxxxxxxxxx>

In view of several constructive comments which have helped to point out
those aspects of my posted proof which were difficult to follow (as well
as one typo), let me make the following attempt to restate the theorem
and proof in terms that (almost?) everyone can accept.  Note that this
is exactly the same proof, just restated more clearly.

DEFINITION.  A (FIBS/Elo-style) rating system is one in which:
  1. Each player has a rating which is a real number;
  2. If Player A with rating RA defeats Player B with rating RB, then
     Player A gains G(RA-RB) rating points, and Player B loses the same;
  3. The function G(x) is strictly positive: G(x) > 0 for all real x;
  4. The function G(x) is nonincreasing: G(x) <= G(y) if x > y.

THEOREM.  In a (FIBS/Elo-style) rating system, suppose that Player A has
rating RA, and Player B has rating RB.  Set a "target rating" RT.  Then,
there is an integer N such that if Player A wins N times in succession
against Player B, Player A's rating will exceed RT after the N wins.

PROOF of THEOREM.  By conservation of rating points [property 2], when
Player A has rating X, player B has rating Y such that X+Y = RA+RB.
Therefore the rating difference at that time is:

    X-Y = 2*X-(X+Y) = 2*X-RA-RB.

If X < RT, then X-Y = 2*X-RA-RB < 2*RT-RA-RB.  Since G is nonincreasing
[property 4]:

    G(X-Y) >= G(2*RT-RA-RB).

Also, because G is strictly positive [property 3]:

    G(2*RT-RA-RB) > 0.

Choose N such that N >= (RT-RA) / G(2*RT-RA-RB), which is finite by the
previous inequality.  Assume that Player A's rating after N games
remains below RT.  Then, for each of the first N wins, Player A's rating
X is less than RT, so Player A gains at least G(2*RT-RA-RB) rating
points for that win.  Therefore, Player A's rating after N wins is at
least

    RA + N * G(2*RT-RA-RB) >= RA + (RT-RA) = RT.

contradicting the assumption.  Therefore N wins are sufficient.  QED.

                                        David desJardins