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

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.

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`

2`TO`

`FOR`

3 4 5`TO`

`FOR`

6 7`TO`

`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.

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 .

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`

2 3 4`TO`

`FOR`

5 6 7`TO`

`FOR`

8 9 10`TO`

`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.

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 .

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.

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`

2 3`TO`

4 5`IF`

6`RETURN`

7 8`IF`

9`RETURN`

`RETURN`

In worst case *
Interval-Test
* runs in time even in the general case (in the best case the running time of

`Interval-Test`

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`

3 4 5 6 7 Computation of 8`TO`

9`Interval-Test`

10 11`IF`

21 12 13`GO TO`

14`Interval-Test`

15`IF`

17 16 17`GO TO`

18 19`IF`

37 20`GO TO`

14 21 Computation of 22 23`GO TO`

24`Interval-Test`

25 26`IF`

37 27 28`GO TO`

29`Interval-Test`

30 31`IF`

33 32 33`GO TO`

34 35`IF`

37 36`GO TO`

27 37`GO TO`

`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`

`MinF-MaxG`

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`

3 4 5 6 7`TO`

`FOR`

Computation of 8 9`TO`

10 11`IF`

`FOR`

Computation of 12 13 14`TO`

15 16`IF`

`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 .

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
*

1Initialization 2 3 4`MinF-MaxG`

`FOR`

5`TO`

`FOR`

6 7`TO`

`FOR`

8 9 10`TO`

Score slicing for players 11`IF`

`FOR`

12`DOWNTO`

13`Score-Slicing2`

Score slicing for 2 players 14 15 16`IF`

`RETURN`

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`

Initialization 3 4 5 6`TO`

`WHILE`

There are missing and additional points 7 8`AND`

9 10 11`WHILE`

12 13 14 15`WHILE`

`FOR`

16 17 18 19 20 21`DOWNTO`

`FOR`

22 23`DOWNTO`

No missing points 24 25 26 27 28 29`WHILE`

`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 [
127
] the algorithm *
Score-Slicing
* resulted the point table reprezented in Figure 25.4.

The algorithm *
Mini-Max
* starts with the computation of .

`MinF-MaxG`

`MinF-MaxG`

`Interval-Test`

`Mini-Max`

`Interval-Test`

`MinF-MaxG`

`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`

`Score-Slicing2`

At first *
Mini-Max
* computes the results of calling calling

`Score-Slicing2`

`Score-Slicing2`

In the second place *
Mini-Max
* calls

`Score-Slicing2`

In the third place *
Mini-Max
* calls

`Score-Slicing2`

In the fourth place *
Mini-Max
* calls

`Score-Slicing2`

`MINI-MAX`

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`

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`

`Mini-Max`

Lines 1–46 of *
Mini-Max
* require uses of

`MinG-MaxF`

The reconstruction part (lines 47–55) uses algorithm *
Score-Slicing2
*, which runs in time [
127
].

`Mini-Max`

`Score-Slicing2`

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