Tiebreak proposals for Swiss tournaments

(17-juli-2019) C.L. Pippel, IJmuiden

Discussions about tiebreaks goes back to as far as 1873 (Ahrends, p. 184). Vivid discussions arose when the famous 1914 Mannheim chess tournament was interrupted by World War One. At that point Alekhine was a half point ahead. But Vidmar did have met stronger opponents. The issue of defining rankings for tournaments has been studied in various fields like sports, psychology, decision theory, Condorcet voting. Many ranking methods based on different motivations have been defined.

Direct methods

Solkoff, Buchholz, and variants

The above methods have a practical disadvantage. If a player leaves the tournament early the Solkoff contribution will be flatted in a negative sense. His opponents are thereby disadvantaged. The FIDE has found a solution for this (Forlani). But this solution is complicated and artificial. All direct methods have a fundamental limitation. They do take into account the direct opponents, but not the opponents of the opponents. And the opponents thereof. Four alternative indirect tiebreak methods are presented.

Relative Elo Ratings

The normal distribution function

From general experience in sports we know that the stronger player does not invariably outperform the weaker. A player has good days and bad, good tournaments and bad. By and large at any point in his career, a player will perform around some average level. Deviations from this level occur, large deviations less frequently than small ones. These facts suggest the basic assumption of the Elo system. It is best stated in the formal terms of statistics:

The many performances of an individual wil be normally distributed, when evaluated on an appropriate scale (Elo, 1978, p19).

Development of the Percentage Expectancy Table

The normal probabilities may be taken directly from the standard tables of the areas under de normal curve, when de difference D in ratings is expressed as a z score. The z value of a difference equals D / sigma, where sigma = 2000 / 7. For example, let D = 160. Then z = 160 * 7 /2000 = 0,56. The table / formula gives ,7123 and ,2877 as areas of the two portions under de cumulative curve. These numbers represents the expected scores of the two opponents (Elo, p. 158).

In a rating system (KNDB, FMJD) ratings are updated at regular time intervals. Relevant games are considered. Game by game the difference between actual and expected score is established, according to the percentage expectancy function. Then the existing rating is updated, proportional to the total difference between expected and actual score. However, when computing the relative Elo ratings, we do not assume any existing ratings prior to the tournament. All players in the tournament are assigned a rating, the relative Elo rating, such that for each player the expected score and the actual score are equal. This rating is calculated by a numeric iteration procedure, as no closed formula exists. The relative Elo rating of a tournament is unique, up to a constant.

Example Open de Sangmelima Cameroon 2014

At the start of the iterations (R0) one assumes all players have equal strength. In the subsequent iterations the rating of each player is updated according to -ln(We/W) * 2000 / 7. We is the expected score derived from the cumulative normal distribution, W is the actual score and ln() constitutes the natural logarithm function. The updates are normalized to set the sum of all updates to zero. The iteration is slow, but stable. We may choose at start any average rating level including zero. This does not effect the ordering of the players.

Pl Title      Name        Cn Rating + = - N Pts Whl Wl | R0  We0 Up0    |  R1    We1  Up1   |  R2    We2  Up2   | Rk R28  |
1  gmi   Leopold Kouomou  cm   2296 3 3 0 6  9  25  34 | 0,0 6,0 137,7  |  137,7 8,0  32,6  |  170,3 8,1  36,2  |  2 304,0|
2        Gerard Ngankou   cm   2265 3 3 0 6  9  25  34 | 0,0 6,0 137,7  |  137,7 7,7  42,9  |  180,6 8,0  38,3  |  1 312,7|
3        Mouanji Iliassou cm        4 0 2 6  8  16  23 | 0,0 6,0 104,0  |  104,0 9,0 -33,9  |   70,1 8,5 -10,6  |  6  18,3|
4        Armand Abouem    cm        3 1 2 6  7  30  39 | 0,0 6,0  65,9  |   65,9 6,0  41,7  |  107,6 6,5  25,6  |  3 185,3|
5        Landry Nga       cm        1 5 0 6  7  28  37 | 0,0 6,0  65,9  |   65,9 6,3  31,1  |   97,0 6,6  20,5  |  4 180,9|
6  mi    Bruno Fopa       cm   2262 2 3 1 6  7  21  28 | 0,0 6,0  65,9  |   65,9 7,7 -28,3  |   37,5 7,5 -12,8  |  9 -26,6|
7        Desire Ghuendou  cm        2 3 1 6  7  18  25 | 0,0 6,0  65,9  |   65,9 8,2 -45,6  |   20,3 7,6 -17,6  | 10 -63,0|
8        Maturin Tomi     be        2 2 2 6  6  26  35 | 0,0 6,0  21,8  |   21,8 6,4 -17,1  |    4,7 6,0   6,0  |  5  33,6|
9        Arnaud Foto      cm        2 2 2 6  6  25  32 | 0,0 6,0  21,8  |   21,8 6,3 -15,9  |    6,0 6,2  -3,6  |  8 -19,4|
10       Patrick Akono    cm        1 3 2 6  5  31  40 | 0,0 6,0 -30,3  |  -30,3 4,4  36,2  |    5,9 5,2  -5,6  |  7 -16,3|
11       Bernard Mambo    cm        2 0 4 6  4  28  37 | 0,0 6,0 -94,0  |  -94,0 3,7  18,8  |  -75,3 4,2  -8,6  | 11 102,5|
12       David Wabo Daco  cm        1 2 3 6  4  23  31 | 0,0 6,0 -94,0  |  -94,0 4,7 -45,7  | -139,7 4,1  -3,3  | 12 177,2|
13       Barel Bimogo     cm        1 1 4 6  3  23  31 | 0,0 6,0 -176,2 | -176,2 3,8 -66,9  | -243,1 3,1  -5,4  | 13 299,4|
14       Prince Mvondo    cm        1 0 5 6  2  28  37 | 0,0 6,0 -292,1 | -292,1 1,7  50,2  | -241,8 2,5 -59,1  | 14 330,6|

It is easy to check the result of the above calculation:

 Gerard Ngankou             313,0                                  Leopold Kouogueu Kouomou   304,0
 Opponents                  R28    Diff  We                        Opponents                  R28    Diff  We
 Patrick Akono              -16,3  329,3 1,75                      Prince Arnaud Mvondo      -330,6  634,6 1,97
 Landry Nga                 180,9  132,1 1,36                      Maturin Nyamsi Tomi         33,6  270,4 1,66
 Maturin Nyamsi Tomi        33,6   279,4 1,67                      Patrick Akono              -16,3  320,3 1,74
 Bernard Mambo             -102,5  415,5 1,85                      Armand Abouem              185,3  118,7 1,32
 Leopold Kouogueu Kouomou   304,0    9,0 1,03                      Gerard Ngankou             312,7   -8,7 0,98
 Armand Abouem              185,3  127,7 1,35 +                    Landry Nga                 180,9  123,1 1,33 +
Expected Score                           9,0 points               Expected score                           9,0 points

Domain

The iteration requires an indivisible (that is, strongly connected or irreducible) domain. In every possible partition of players into two nonempty subsets, some player of the second set has defeated at least one player in the first set (Glickman, p. 5). Finding all maximal strongly connected components is a mathematical puzzle in its own right.

Remark: one can introduce a virtual opponent who draws to all other players to make the domain indivisible.

Least Squares Method

Principle

If a player has a win, loss or draw his comparison outcome is set to 1, -1 or 0 respectively. The least-squares method constructs a mean square approximation of the skew symmetric comparison outcomes R by the differences of the desired least-squares ratings (Cheboratev, 1999, p. 18):

Determine q = (q1,...,qn) such that ΣiΣj(rij - (qi-qj)nij)2 is a minimum (Gulliksen, 1956)

where

Calculation

The LSM-ratings (q) are a solution of the set of linear equations:

where

Note that if the percentage expectancy function of the relative Elo ratings is replaced by a linear relationship, for example the "algorithm of 400", then relative Elo ratings are identical to LS-ratings except for a scaling factor. Multiplying LS-ratings with a factor 800 gives a comparable rating in the Elo-domain (FIDE Rating Regulations effective from 1 July 2017, table 8.1b).

Example Open de Sangmelima Cameroon 2014

Pl Title      Name        Cn Rating + N  s WhlWl |Rk  LS-Rtg|
1  gmi   Leopold Kouomou  cm   2296 3 6  3 25 34 | 2  0,643 |
2        Gerard Ngankou   cm   2265 3 6  3 25 34 | 1  0,708 |
3        Mouanji Iliassou cm        4 6  2 16 23 | 5  0,059 |
4        Armand Abouem    cm        3 6  1 30 39 | 3  0,420 |
5        Landry Nga       cm        1 6  1 28 37 | 4  0,392 |
6  mi    Bruno Fopa       cm   2262 2 6  1 21 28 | 9 -0,042 |
7        Desire Ghuendou  cm        2 6  1 18 25 |11 -0,122 |
8        Maturin Tomi     be        2 6  0 26 35 | 6  0,054 |
9        Arnaud Foto      cm        2 6  0 25 32 |10 -0,047 |
10       Patrick Akono    cm        1 6 -1 31 40 | 8 -0,030 |
11       Bernard Mambo    cm        2 6 -2 28 37 |12 -0,234 |
12       David Wabo Daco  cm        1 6 -2 23 31 |13 -0,425 |
13       Barel Bimogo     cm        1 6 -3 23 31 |15 -0,694 |
14       Prince Mvondo    cm        1 6 -4 28 37 |14 -0,683 |

It is easy to check the result of the above calculation as follows:

 Gerard Ngankou              0,708  3                              Leopold Kouogueu Kouomou   0,643   3
 Opponents                  LS-Rtg  Diff                           Opponents                  LS-Rtg  Diff
 Patrick Akono              -0,030  0,738                          Prince Arnaud Mvondo       -0,683  1,326
 Landry Nga                  0,392  0,316                          Maturin Nyamsi Tomi         0,054  0,589
 Maturin Nyamsi Tomi         0,054  0,654                          Patrick Akono              -0,030  0,673
 Bernard Mambo              -0,234  0,942                          Armand Abouem               0,420  0,223
 Leopold Kouogueu Kouomou    0,643  0,065                          Gerard Ngankou              0,708 -0,065
 Armand Abouem               0,420  0,288                          Landry Nga                  0,392  0,251 +
s1                                  3,00 (Wins minus losses)      s2                                  3,00 (Wins minus losses)

Recursive Buchholz

Let

Rb
- Recursive Buchholz ratings
RbOpp
- Average Opponents Rb-rating
s
- Score percentage - 50%, or alternatively,
- Average of the skew symmetric score points, or
- Average of Wins -/- Losses

Rb, RbOpp, s are n×1 column vectors indexed by player. The Recursive Buchholz Rating Rb is a solution of: (Gonzalez-Diaz et al., 2011, p. 7)

Remark: although the perspective of RB and LSM are quite different, both ratings are proportional

Skew symmetric score systems

A score system is skew symmetric if for all possible outcomes (x, y),

Any traditional score system can be transformed to this form (Chebotarev, 1989, p.1104):

    |x 3 .|                   |x 0 .|
A = |0 x 1|    transpose(A) = |3 x 1|
    |. 1 x|                   |. 1 x|

R = (A - transpose(A)) / 2

    | x  1½   . |
R = |-1½  x   0 |
    | .   0   x |

Example Provinciaal Brabants Kampioenschap PNDB 2018

Pl               Name          rating   R1      R2      R3      R4      R5      R6      R7       R8    +  ±  N   % ±    It1    It2    It3    It4    It5    It6  Rk
1   mi  Frank Teer               2208  2/3b   2/13w    1/2b    2/4w    2/5b   2/17w    2/6w    2/7b    7  7  8  43,8%  54,3%  60,0%  61,1%  62,3%  62,4%  62,8%  2
2   mf  Andrew Tjon A Ong        2192 2/21w    2/6b    1/1w    2/7w   2/12b    2/4w    2/9b    2/8w    7  7  8  43,8%  54,7%  59,9%  61,6%  62,7%  63,0%  63,3%  1
3       Jan Kornilov                   0/1w   1/11b   1/15b   2/16w   1/23w   2/14b            1/4b    2  1  7   7,1%  12,2%  11,4%  12,2%  11,7%  11,9%  11,7%  9
4       Piet van Erp                          2/21b    1/8w    0/1b   2/10w    0/2b   2/17b    1/3w    3  1  7   7,1%  20,7%  24,1%  26,6%  27,2%  27,9%  28,0%  3
5       Luud Ector               1908 2/19w   1/12b   1/18w    2/8b    0/1w    0/6b   2/22w   2/15b    4  2  8  12,5%  17,3%  18,9%  19,8%  20,0%  20,2%  20,2%  6
6       Wiebe Cnossen            1916 1/20w    0/2w   1/11b   2/19b   2/15w    2/5w    0/1b   1/14b    3  1  8   6,3%  16,9%  15,6%  16,9%  16,2%  16,5%  16,3%  8
7       Jules Martens            2001 2/17b   2/15w   1/10w    0/2b   1/22b    1/8b   2/21w    0/1w    3  1  8   6,3%  14,7%  17,0%  19,7%  20,1%  20,8%  20,9%  4
8       Ties Slagter             1955 2/22b   2/23w    1/4b    0/5w    1/9b    1/7w   2/10w    0/2b    3  1  8   6,3%  12,1%  17,1%  18,6%  19,8%  20,2%  20,5%  5
9       Jan van den Hooff        1996 1/16w   0/10b   2/19w   2/23b    1/8w   1/12w    0/2w   2/22b    3  1  8   6,3%   8,3%   7,9%   8,8%   8,6%   9,0%   8,9% 11
10      Ton Sprangers                 2/11w    2/9w    1/7b   0/12b    0/4b   2/24w    0/8b   2/18w    4  1  8   6,3%   8,3%   9,9%  10,1%  10,8%  10,8%  11,0% 10
11      Lev Gilevych                  0/10b    1/3w    1/6w   2/21b   1/14w   1/22b   1/18w   2/17b    2  1  8   6,3%   3,8%   4,7%   4,3%   4,5%   4,4%   4,5% 12
12      Frank Swagemakers        1900 2/25w    1/5w   2/20b   2/10w    0/2w    1/9b                    3  2  6  16,7%  18,3%  18,7%  18,6%  18,6%  18,6%  18,6%  7
13      Joop Achterstraat        1993 2/14b    0/1b   1/16w   2/20w   0/17b   1/18b   0/15b   2/23w    3  0  8   0,0%  -0,5%  -3,9%  -4,1%  -5,1%  -5,1%  -5,4% 15
14      Tanya-Marie Cnossen      1942 0/13w   2/16b   1/23b   1/22w   1/11b    0/3w   2/20b    1/6w    2  0  8   0,0%  -4,7%  -5,8%  -7,1%  -7,6%  -7,9%  -8,1% 16
15      Martien van Erp               1/18b    0/7b    1/3w   2/25w    0/6b   2/23b   2/13w    0/5w    3  0  8   0,0%  -4,8%  -2,8%  -4,5%  -3,9%  -4,4%  -4,2% 14
16      Arnold Beset                   1/9b   0/14w   1/13b    0/3b   0/24w           2/25w   2/21b    2 -1  7  -7,1% -18,0% -21,2% -24,0% -24,4% -25,2% -25,1% 20
17      Roland Coray                   0/7w   2/25b   1/22b   2/18b   2/13w    0/1b    0/4w   0/11w    3 -1  8  -6,3%  -7,1%  -4,2%  -4,2%  -3,3%  -3,4%  -3,1% 13
18      Yaroslav Gilevych             1/15w   1/19b    1/5b   0/17w   2/20b   1/13w   1/11b   0/10b    1 -1  8  -6,3%  -6,6%  -9,9%  -9,6% -10,5% -10,3% -10,6% 17
19      Piet Jonkers             1817  0/5b   1/18w    0/9b    0/6w           0/21b   2/24b   2/25w    2 -2  7 -14,3% -24,4% -25,4% -27,9% -27,8% -28,5% -28,3% 22
20      Oleksandra Chumachenko   1914  1/6b   2/24w   0/12w   0/13b   0/18w   2/25b   0/14w            2 -2  7 -14,3% -22,9% -24,7% -27,9% -28,1% -29,0% -29,0% 23
21      Johan Rijnen                   0/2b    0/4w   2/24b   0/11w   2/25b   2/19w    0/7b   0/16w    3 -2  8 -12,5% -16,7% -18,1% -18,8% -18,9% -19,0% -19,0% 19
22      Harm van der Veen              0/8w           1/17w   1/14b    1/7w   1/11w    0/5b    0/9w    0 -3  7 -21,4% -16,0% -15,0% -13,5% -12,9% -12,6% -12,4% 18
23      Simon Rompa              1833 2/24b    0/8b   1/14w    0/9w    1/3b   0/15w           0/13b    1 -3  7 -21,4% -22,5% -24,2% -25,0% -25,2% -25,5% -25,5% 21
24      Egor Kornilov                 0/23w   0/20b   0/21w           2/16b   0/10b   0/19w            1 -4  6 -33,3% -43,0% -49,2% -50,6% -52,2% -52,3% -52,8% 24
25      Peter van Poppel              0/12b   0/17w           0/15b   0/21w   0/20w   0/16b   0/19b    0 -7  7 -50,0% -54,5% -60,7% -61,1% -62,6% -62,5% -63,0% 25

It is easy to check the result of the above calculation as follows:
  Andrew Tjon A Ong  0,633               Frank Teer          0,627
Opponents           Rb-Rtg             Opponents            Rb-Rtg
  Johan Rijnen      -0,1903              Jan Kornilov        0,1168
  Wiebe Cnossen      0,1629              Joop Achterstraat  -0,0541
  Frank Teer         0,6275              Andrew Tjon A Ong   0,6330
  Jules Martens      0,2088              Piet van Erp        0,2798
  Frank Swagemakers  0,1857              Luud Ector          0,2024
  Piet van Erp       0,2798              Roland Coray       -0,0311
  Jan van den Hooff  0,0885              Wiebe Cnossen       0,1629
  Ties Slagter       0,2046              Jules Martens       0,2088                                       
RbOpp average        0,1959             RbAvg                0,1898
  s                  0,4375 +             s                  0,4375 +
  RbAvg + s          0,633                Own Rb-Rtg         0,627

Generalized Row Sum Method

Principle

Row sum scores (s) are calculated as the sum over k of the skew symmetric outcomes rik. The generalized row sum method is an extension of the row sum method. The idea of the generalization is to complete the missing comparisons. Central to the statistical interpretation of the generalized row sum method is the assumption that the expected value E(rij) of a missing comparison is proportional to the difference of the scores xi, xj of the compared players i and j:

These relationships form a system of n linear equations in n unknowns xi. For γ = m.n + ε-1 the system of equations is equivalent to:

where

Parameter ε is said to be well-chosen if for any outcome matrix R = (rik) the value of its contribution to xi is nonnegative for a maximal win and nonpositive for a maximal loss (Chebotarev, 1997, p14).

Calculation

The generalized row sums (x) are a solution of the set of lineair equations:

where

Note that LS-ratings can be obtained as a limit of the generalized row sum calculation by setting ε-1 = 0 and γ = 1.

Example Trainingsvierkamp Harm Wiersma Huizum 2005 (Blitz)

   n = 4                                              m = 2, 1/ε = 2×4
Pl Naam                      Rating   1  2  3  4  N  |Matches|L + (1/ε)I | + = - Pts  s  |Rk  x    |
 1 Harm Wiersma           GMI  1502  xx 02 22 ..  4  |0 2 2 0|12 -2 -2  0| 3 0 1   6  2  | 1  2,667|
 2 Rein van der Pal       MF   1402  20 xx 02 12  6  |2 0 2 2|-2 14 -2 -2| 3 1 2   7  1  | 2  1,000|
 3 Tjalling van den Bosch      1190  00 20 xx 21  6  |2 2 0 2|-2 -2 14 -2| 2 1 3   5 -1  | 3 -1,000|
 4 Jan Adema                   1217  .. 10 01 xx  4  |0 2 2 0| 0 -2 -2 12| 0 2 2   2 -2  | 4 -2,667|
 
 x = column vector of generalized row sum ratings
 s = column vector wins -/- losses

Statistical model

Check expected values xi == si + Σ(xi-xj)/γ, γ = 1/ε + n.m, γ = 16
All players are expected to complete an equal number of games

  Harm Wiersma      2,67                 Jan Adema         -2,67
  s1                2                    s4                -2
Missing games                         Missing games        
  (x1-x4)/γ         0,333               (x4-x1)/γ          -0,333
  (x1-x4)/γ         0,333               (x4-x1)/γ          -0,333
                    ----- +                                ------ +
  s1 + missing gms  2,67                 s1 + missing gms  -2,67

Direct method

Check (L + (1/ε)I)x == γs, 1/ε = 8, γ = 16
                   L+(1/ε)I   x       (L + (1/ε)I)x
 Harm Wiersma            12   2,6667  32,0004
 Rein van der Pal        -2   1,0000  -2,0000
 Tjalling van den Bosch  -2  -1,0000   2,0000
 Jan Adema                0  -2,6667   0,0000
                                       ------ +
 γ.s1                                 32,0000
 s1                                    2,000

References

W. Ahrends, Zur relativen Bewertung von Turnierpartien, pp 181-192 in: Wiener Schachzeitung, Georg Marco (ed.), Organ des Wiener Schach-Club, IV. Jahrgang., nr. 10/11. October-Novemb., Wien, 1901. ANNO

Mark Glickman, Introductory note to 1928. on‑line

Harold Gulliksen, A Least Squares Solution for Paired Comparisons With Incomplete Data, RB-55-5, Educational Testing Service, Princeton New Jersey, 1955. on‑line

Arpad E. Elo, The Rating of Chessplayers, Past&Present, ISHI Press International, Bronx NY 10453, 2008. ISBN 0-923891-27-7. First printing by Arco Pub., New York, 1978.

P. Yu. Chebotarev, Generalization of the Row Sum Method for Incomplete Paired Comparisons, Automation and Remote Control 50 (1989) 1103-1113. on‑line

P. Yu. Chebotarev, E. Shamis, From Incomplete Preferences to Ranking via Optimization. arXiv.
A version of this paper was published as: P.Yu.Chebotarev, E.V.Shamis. Constructing an objective function for aggregating incomplete preferences, In: A.Tangian and J.Gruber, eds. Econometric Decision Models: Constructing Scalar-Valued Objective Functions. Lecture Notes in Economics and Mathematical Systems, Springer-Verlag, 1997, P.100-124

P. Yu. Chebotarev, E. Shamis, Preference fusion when the number of alternatives exceeds two: indirect scoring procedures, J. Frankl. Inst. 336(2) (1999) 205–226. arXiv

Gonzalez-Diaz, J., Hendrickx, R. L. P., & Lohmann, E. R. M. A. Paired Comparisons Analysis: An Axiomatic Approach to Rankings in Tournaments, CentER Discussion Paper, Vol. 2011-116, Tilburg:Operations research, 2011. on‑line

Luigi Forlano, Treatment of unplayed games for Buchholz tie break: the FIDE rule. on‑line