Forum Archive :
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
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
RA + N * G(2*RT-RA-RB) >= RA + (RT-RA) = RT.
contradicting the assumption. Therefore N wins are sufficient. QED.
- Constructing a ratings system (Matti Rinta-Nikkola, Dec 1998)
- Converting to points-per-game (David Montgomery, Aug 1998)
- Cube error rates (Joe Russell+, July 2009)
- Different length matches (Jim Williams+, Oct 1998)
- Different length matches (Tom Keith, May 1998)
- ELO system (seeker, Nov 1995)
- Effect of droppers on ratings (Gary Wong+, Feb 1998)
- Emperical analysis (Gary Wong, Oct 1998)
- Error rates (David Levy, July 2009)
- Experience required for accurate rating (Jon Brown+, Nov 2002)
- FIBS rating distribution (Gary Wong, Nov 2000)
- FIBS rating formula (Patti Beadles, Dec 2003)
- FIBS vs. GamesGrid ratings (Raccoon+, Mar 2006)
- Fastest way to improve your rating (Backgammon Man+, May 2004)
- Field size and ratings spread (Daniel Murphy+, June 2000)
- Improving the rating system (Matti Rinta-Nikkola, Nov 2000)
- KG rating list (Daniel Murphy, Feb 2006)
- KG rating list (Tapio Palmroth, Oct 2002)
- MSN Zone ratings flaw (Hank Youngerman, May 2004)
- No limit to ratings (David desJardins+, Dec 1998)
- On different sites (Bob Newell+, Apr 2004)
- Opponent's strength (William Hill+, Apr 1998)
- Possible adjustments (Christopher Yep+, Oct 1998)
- Rating versus error rate (Douglas Zare, July 2006)
- Ratings and rankings (Chuck Bower, Dec 1997)
- Ratings and rankings (Jim Wallace, Nov 1997)
- Ratings on Gamesgrid (Gregg Cattanach, Dec 2001)
- Ratings variation (Kevin Bastian+, Feb 1999)
- Ratings variation (FLMaster39+, Aug 1997)
- Ratings variation (Ed Rybak+, Sept 1994)
- Strange behavior with large rating difference (Ron Karr, May 1996)
- Table of ratings changes (Patti Beadles, Aug 1994)
- Table of win rates (William C. Bitting, Aug 1995)
- Unbounded rating theorem (David desJardins+, Dec 1998)
- What are rating points? (Lou Poppler, Apr 1995)
- Why high ratings for one-point matches? (David Montgomery, Sept 1995)