25.5. 25.5 Existence of an -tournament with prescribed score sequence

In this section we show that for arbitrary prescribed sequence of nondecreasingly ordered nonnegative integers there exists an -tournament

25.5.1. 25.5.1 Existence of a tournament with arbitrary degree sequence

Since the numbers of points are not limited, it is easy to construct a -tournament for any .

Lemma 25.6 If , then for any vector of nonnegative integers there exists a loopless directed multigraph with outdegree vector so, that .

Proof. Let and for , and let the remaining values be equal to zero.

Using weighted graphs it would be easy to extend the definition of the -tournaments to allow arbitrary real values of , , and . The following algorithm, Naive-Construct works without changes also for input consisting of real numbers.

We remark that Ore in 1956 [ 197 ], [ 198 ], [ 199 ] gave the necessary and sufficient conditions of the existence of a tournament with prescribed indegree and outdegree vectors. Further Ford and Fulkerson [ 78 ][Theorem11.1] published in 1962 necessary and sufficient conditions of the existence of a tournament having prescribed lower and upper bounds for the indegree and outdegree of the vertices. Their results also can serve as basis of the existence of a tournament having arbitrary outdegree sequence.

25.5.2. 25.5.2 Description of a naive reconstructing algorithm

Sorting of the elements of is not necessary.

Input. : the number of players ;

: arbitrary sequence of nonnegative integer numbers.

Output. : the point matrix of the reconstructed tournament.

Working variables. : cycle variables.

Naive-Construct

  1  
                     FOR
                   
                   
                  
                     TO
                   
                     2    
                     FOR
                   
                   
                  
                     TO
                   
                     3          4     5  
                     FOR
                   
                   
                  
                     TO
                   
                     6       7  
                     RETURN
                   
                   
               

The running time of this algorithm is in worst case (in best case too). Since the point matrix has elements, this algorithm is asymptotically optimal.

25.5.3. 25.5.3 Computation of

This is also an easy question. From now on we suppose that is a nondecreasing sequence of nonnegative integers, that is . Let .

Since is a finite set for any finite score vector , exists.

Lemma 25.7 (Iványi [ 127 ]) If , then for any sequence there exists a -tournament such that

and is the smallest upper bound for , and is the smallest possible upper bound for .

Proof. If all players gather their points in a uniform as possible manner, that is

then we get , that is the bound is valid. Since player has to gather points, the pigeonhole principle [ 24 ], [ 25 ], [ 64 ] implies , that is the bound is not improvable. implies . The score sequence shows, that the upper bound is not improvable.

Corollary 25.8 (Iványi [ 128 ]) If , then for any sequence holds .

Proof. According to Lemma 25.7 is the smallest upper bound for .

25.5.4. 25.5.4 Description of a construction algorithm

The following algorithm constructs a -tournament having for any .

Input. : the number of players ;

: arbitrary sequence of nonnegative integer numbers.

Output. : the point matrix of the tournament.

Working variables. : cycle variables;

: the number of the “larger part” in the uniform distribution of the points.

Pigeonhole-Construct

  1  
                     FOR
                   
                   
                  
                     TO
                   
                     2       3       4    
                     FOR
                   
                   
                  
                     TO
                   
                     5          6          7    
                     FOR
                   
                   
                  
                     TO
                   
                     8          9         10  
                     RETURN
                   
                   
               

The running time of Pigeonhole-Construct is in worst case (in best case too). Since the point matrix has elements, this algorithm is asymptotically optimal.

25.5.5. 25.5.5 Computation of and

Let be the sum of the first elements of . be the binomial coefficient . Then the players together can have points only if . Since the score of player is , the pigeonhole principle implies .

These observations result the following lower bound for :

If every player gathers his points in a uniform as possible manner then

These observations imply a useful characterization of .

Lemma 25.9 (Iványi [ 127 ]) If , then for arbitrary sequence there exists a -tournament having as its outdegree sequence and the following bounds for and :

Proof. (25.15) follows from (25.13) and (25.14), (25.16) follows from the definition of .

It is worth to remark, that if is integer and the scores are identical, then the lower and upper bounds in (25.15) coincide and so Lemma 25.9 gives the exact value of .

In connection with this lemma we consider three examples. If , then and , that is is twice larger than . In the other extremal case, when and , then , , so is times larger, than .

If , then Lemma 25.9 gives the bounds . Elementary calculations show that Figure 25.2 contains the solution with minimal , where .

Figure 25.2.  Point matrix of a Point matrix of a (0,10,6) -tournament with f=10 for \mathbf{q}=(0,0,0,40,40,40) .-tournament with Point matrix of a (0,10,6) -tournament with f=10 for \mathbf{q}=(0,0,0,40,40,40) . for Point matrix of a (0,10,6) -tournament with f=10 for \mathbf{q}=(0,0,0,40,40,40) ..

Point matrix of a (0,10,6) -tournament with f=10 for \mathbf{q}=(0,0,0,40,40,40) .

In 2009 we proved the following assertion.

Theorem 25.10 (Iványi [ 127 ]) For a nondecreasing sequence of nonnegative integers is the score sequence of some -tournament if and only if

where

The theorem was proved by Moon [ 184 ], and later by Kemnitz and Dolff [ 144 ] for -tournaments is the special case of Theorem 25.10. Theorem 3.1.4 of [ 133 ] is the special case . The theorem of Landau [ 159 ] is the special case of Theorem 25.10.

25.5.6. 25.5.6 Description of a testing algorithm

The following algorithm Interval-Test decides whether a given is a score sequence of an -tournament or not. This algorithm is based on Theorem 25.10 and returns if is a score sequence, and returns otherwise.

Input. : minimal number of points divided after each match;

: maximal number of points divided after each match.

Output. : logical variable ( shows that is an -tournament).

Local working variable. : cycle variable;

: the sequence of the values of the loss function.

Global working variables. : the number of players ;

: a nondecreasing sequence of nonnegative integers;

: the sequence of the binomial coefficients;

: the sequence of the sums of the smallest scores.

Interval-Test

  1  
                     FOR
                   
                   
                  
                     TO
                   
                     2       3    
                     IF
                   
                     4          5       
                     RETURN
                   
                     6       
                     IF
                   
                     7             8          
                     RETURN
                   
                     9  
                     RETURN
                   
                   
               

In worst case Interval-Test runs in time even in the general case (in the best case the running time of Interval-Test is ). It is worth to mention, that the often referenced Havel–Hakimi algorithm [ 100 ], [ 109 ] even in the special case decides in time whether a sequence is digraphical or not.

25.5.7. 25.5.7 Description of an algorithm computing and

The following algorithm is based on the bounds of and given by Lemma 25.9 and the logarithmic search algorithm described by D. E. Knuth [ 152 ][page 410].

Input. No special input (global working variables serve as input).

Output. : (the minimal );

: (the maximal ).

Local working variables. : cycle variable;

: lower bound of the interval of the possible values of ;

: upper bound of the interval of the possible values of .

Global working variables. : the number of players ;

: a nondecreasing sequence of nonnegative integers;

: the sequence of the binomial coefficients;

: the sequence of the sums of the smallest scores;

: logical variable (its value is , when the investigated is a score sequence).

MinF-MaxG

  1        
                   Initialization   2  
                     FOR
                   
                   
                  
                     TO
                   
                     3       4       5     6     7        
                   Computation of    8  
                     Interval-Test 
                     
                     9  
                     IF
                   
                    10      11    
                     GO TO
                   21  12    13  
                     Interval-Test 
                     
                    14  
                     IF
                   
                    15    
                     GO TO
                   17  16    17  
                     IF
                   
                    18      19    
                     GO TO
                   37  20  
                     GO TO
                   14  21        
                   Computation of   22    23  
                     Interval-Test 
                     
                    24  
                     IF
                   
                    25      26    
                     GO TO
                   37  27    28  
                     Interval-Test 
                     
                    29  
                     IF
                   
                    30      31    
                     GO TO
                   33  32    33  
                     IF
                   
                    34      35     
                     GO TO
                   37  36  
                     GO TO
                   27  37  
                     RETURN
                   
                   
               

MinF-MaxG determines and .

Lemma 25.11 (Iványi [ 128 ]) Algorithm MinG-MaxG computes the values and for arbitrary sequence in time.

Proof. According to Lemma 25.9 is an element of the interval and is an element of the interval . Using Theorem B of [ 152 ][page 412] we get that calls of Interval-Test is sufficient, so the run time of Interval-Test implies the required running time of MinF-MaxG .

25.5.8. 25.5.8 Computing of and in linear time

Analyzing Theorem 25.10 and the work of algorithm MinF-MaxG one can observe that the maximal value of and the minimal value of can be computed independently by the following Linear-MinF-MaxG .

Input. No special input (global working variables serve as input).

Output. : (the minimal ).

: (the maximal ).

Local working variables. : cycle variable.

Global working variables. : the number of players ;

: a nondecreasing sequence of nonnegative integers;

: the sequence of the binomial coefficients;

: the sequence of the sums of the smallest scores.

Linear-MinF-MaxG

  1        
                   Initialization    2  
                     FOR
                   
                   
                  
                     TO
                   
                     3       4       5     6     7  
                     FOR
                   
                   
                  
                     TO
                   
                        
                   Computation of    8       9    
                     IF
                   
                    10         11  
                     FOR
                   
                   
                  
                     TO
                   
                        
                   Computation of   12      13      14    
                     IF
                   
                    15         16  
                     RETURN
                   
                   
               

Lemma 25.12 Algorithm Linear-MinG-MaxG computes the values and for arbitrary sequence in time.

Proof. Lines 01, 05, 06, and 16 require only constant time, lines 02–06, 07–10, and 11–15 require time, so the total running time is .

25.5.9. 25.5.9 Tournament with and

The following reconstruction algorithm Score-Slicing2 is based on balancing between additional points (they are similar to “excess”, introduced by Brauer et al. [ 36 ]) and missing points introduced in [ 127 ]. The greediness of the algorithm Havel–Hakimi [ 100 ], [ 109 ] also characterizes this algorithm.

This algorithm is an extended version of the algorithm Score-Slicing proposed in [ 127 ].

The work of the slicing program is managed by the following program Mini-Max .

Input. : the number of players ;

: a nondecreasing sequence of integers satisfying (25.17).

Output. : the point matrix of the reconstructed tournament.

Local working variables. : cycle variables.

Global working variables. : provisional score sequence;

: the partial sums of the provisional scores;

: matrix of the provisional points.

Mini-Max

  1  
                     MinF-MaxG 
                     
                        
                   Initialization   2     3     4  
                     FOR
                   
                   
                  
                     TO
                   
                     5    
                     FOR
                   
                   
                  
                     TO
                   
                     6          7       
                     FOR
                   
                   
                  
                     TO
                   
                     8             9      10  
                     IF
                   
                        
                   Score slicing for  players  11    
                     FOR
                   
                   
                  
                     DOWNTO
                   
                    12       
                     Score-Slicing2 
                     
                    13  
                     IF
                   
                        
                   Score slicing for 2 players  14      15      16  
                     RETURN
                   
                   
               

25.5.10. 25.5.10 Description of the score slicing algorithm

The key part of the reconstruction is the following algorithm Score-Slicing2 [ 127 ].

During the reconstruction process we have to take into account the following bounds:

Input. : the number of the investigated players ;

: prefix of the provisional score sequence ;

: matrix of provisional points;

Output. : number of missing points

: prefix of the provisional score sequence.

Local working variables. the number of the additional points;

: missing points: the difference of the number of actual points and the number of maximal possible points of ;

: difference of the maximal decreasable score and the following largest score;

: number of sliced points per player;

: frequency of the number of maximal values among the scores ;

: cycle variables;

: maximal amount of sliceable points;

: the sums of the provisional scores;

: the maximal index with and .

Global working variables: : the number of players ;

: the sequence of the binomial coefficients;

: minimal number of points distributed after each match;

: maximal number of points distributed after each match.

Score-Slicing2

  1     2  
                     FOR
                   
                   
                  
                     TO
                   
                        
                   Initialization   3       4       5     6  
                     WHILE
                   
                   
                  
                     AND
                   
                        
                   There are missing and additional points   7       8    
                     WHILE
                   
                     9         10      11    
                     WHILE
                   
                    12         13      14      15    
                     FOR
                   
                   
                  
                     DOWNTO
                   
                    16         17         18         19         20            21       
                     FOR
                   
                   
                  
                     DOWNTO
                   
                    22            23  
                     WHILE
                   
                        
                   No missing points  24      25      26      27      28      29  
                     RETURN
                   
                   
               

Let us consider an example. Figure 25.3 shows the point table of a -tournament . We remark that the termin point table is used as a synonym of the termin point matrix.

Figure 25.3.  The point table of a The point table of a (2,10,6) -tournament T .-tournament The point table of a (2,10,6) -tournament T ..

The point table of a (2,10,6) -tournament T .

The score sequence of is . In [ 127 ] the algorithm Score-Slicing resulted the point table reprezented in Figure 25.4.

Figure 25.4.  The point table of The point table of T reconstructed by Score-Slicing . reconstructed by Score-Slicing .

The point table of T reconstructed by Score-Slicing .

The algorithm Mini-Max starts with the computation of . MinF-MaxG called in line 01 begins with initialization, including provisional setting of the elements of so, that , if , and otherwise. Then MinF-MaxG sets the lower bound of in line 07 and tests it in line 10 Interval-Test . The test shows that is large enough so Mini-Max sets in line 12 and jumps to line 23 and begins to compute . Interval-Test called in line 25 shows that is too large, therefore MinF-MaxG continues with the test of in line 30. The result is positive, therefore comes the test of , then the test of . Now in line 35, so is fixed, and the control returns to line 02 of Mini-Max .

Lines 02–09 contain initialization, and Mini-Max begins the reconstruction of a -tournament in line 10. The basic idea is that Mini-Max successively determines the won and lost points of , , and by repeated calls of Score-Slicing2 in line 12, and finally it computes directly the result of the match between and .

At first Mini-Max computes the results of calling calling Score-Slicing2 with parameter . The number of additional points of the first five players is according to line 03, the number of missing points of is according to line 04. Then Score-Slicing2 determines the number of maximal numbers among the provisional scores ( according to lines 09–14) and computes the difference between and ( according to line 12). In line 13 we get, that points are sliceable, and gets these points in the match with in line 16, so the number of missing points of decreases to (line 19) and the number of additional point decreases to . Therefore the computation continues in lines 22–27 and and will be decreased by 1 resulting and as the seventh line and seventh column of Figure 25.5 show. The returned score sequence is .

Figure 25.5.  The point table of The point table of T reconstructed by Mini-Max . reconstructed by Mini-Max .

The point table of T reconstructed by Mini-Max .

In the second place Mini-Max calls Score-Slicing2 with parameter , and get and . At first gets point, then and get both 4 points, reducing to and to . The computation continues in line 22 and results the further decrease of , , , and by 1, resulting , , , and as the sixth row of Figure 25.5 shows.

In the third place Mini-Max calls Score-Slicing2 with parameter , and get and . At first gets points, then further 1 point, and and also both get 1 point, resulting , , , , and , further and . The computation continues in lines 22–27 and results a decrease of by 1 point resulting , , and , as the fifth row and fifth column of Figure 25.5 show. The returned score sequence is .

In the fourth place Mini-Max calls Score-Slicing2 with parameter , and gets and . At first and get points, resulting , and , and , and . Then MINI-MAX sets in lines 23–26 and . The returned point vector is .

Finally Mini-Max sets and in lines 14–15 and returns the point matrix represented in Figure 25.5.

The comparison of Figures 25.4 and 25.5 shows a large difference between the simple reconstruction of Score-Slicing2 and the minimax reconstruction of Mini-Max : while in the first case the maximal value of is and the minimal value is , in the second case the maximum equals to and the minimum equals to , that is the result is more balanced (the given does not allow to build a perfectly balanced -tournament).

25.5.11. 25.5.11 Analysis of the minimax reconstruction algorithm

The main result of this paper is the following assertion.

Theorem 25.13 (Iványi [ 128 ]) If is a positive integer and is a nondecreasing sequence of nonnegative integers, then there exist positive integers and , and a -tournament with point matrix such that

for any -tournament, and algorithm Linear-MinF-MaxG computes and in time, and algorithm Mini-Max generates a suitable in time.

Proof. The correctness of the algorithms Score-Slicing2 , MinF-MaxG implies the correctness of Mini-Max .

Lines 1–46 of Mini-Max require uses of MinG-MaxF , and one search needs steps for the testing, so the computation of and can be executed in times.

The reconstruction part (lines 47–55) uses algorithm Score-Slicing2 , which runs in time [ 127 ]. Mini-Max calls Score-Slicing2 times with , so finishes the proof.

The interesting property of and is that they can be determined independently (and so there exists a tournament having both extremal features) is called linking property. One of the earliest occurrences appeared in a paper of Mendelsohn and Dulmage [ 175 ]. It was formulated by Ford and Fulkerson [ 78 ][page 49] in a theorem on the existence of integral matrices for which the row-sums and the column-sums lie between specified bounds. The concept was investigated in detail in the book written by Mirsky [ 179 ]. A. Frank used this property in the analysis of different problems of combinatorial optimization [ 81 ], [ 85 ].