## 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 [], [], [] gave the necessary and sufficient conditions of the existence of a tournament with prescribed indegree and outdegree vectors. Further Ford and Fulkerson [][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 []) 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 [], [], [] 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 []) 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 []) 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 .

In 2009 we proved the following assertion.

Theorem 25.10 (Iványi []) 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 [], and later by Kemnitz and Dolff [] for -tournaments is the special case of Theorem 25.10. Theorem 3.1.4 of [] is the special case . The theorem of Landau [] 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 [], [] 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 [][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 []) 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 [][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. []) and missing points introduced in []. The greediness of the algorithm Havel–Hakimi [], [] also characterizes this algorithm.

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

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 [].

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.

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

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 .

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 []) 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 []. 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 []. It was formulated by Ford and Fulkerson [][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 []. A. Frank used this property in the analysis of different problems of combinatorial optimization [], [].