Chapter 25. Comparison Based Ranking

In practice often appears the problem, how to rank different objects. Researchers of these problems frequently mention different applications, e.g. in biology Landau [ 159 ], in chemistry Hakimi [ 100 ], in networks Kim, Toroczkai, Miklós, Erdős, and Székely [ 147 ], Newman and Barabási [ 193 ], in comparison based decision making Bozóki, Fülöp, Kéri, Poesz, Rónyai and [ 34 ], [ 35 ], [ 145 ], in sports Iványi, Lucz, Pirzada, Sótér and Zhou [ 127 ], [ 128 ], [ 131 ], [ 129 ], [ 130 ], [ 168 ], [ 217 ], [ 231 ], [ 260 ].

A popular method is the comparison of two—and sometimes more—objects in all possible manner and distribution some amount of points among the compared objects.

In this chapter we introduce a general model for such ranking and study some connected problems.

25.1. 25.1 Introduction to supertournaments

Let , be positive integers, , and vectors of nonnegative integers with and .

An -supertournament is an sized matrix , whose columns correspond to the players of the tournament (they represent the rankable objects) and the rows correspond to the comparisons of the objects. The permitted elements of belong to the set , where means, that the player is not a participants of the match corresponding to the -th line, while means, that received points in the match corresponding to the -th line, and .

The sum (dots are taken in the count as zeros) of the elements of the -th column of is denoted by and is called the score of the th player :

The sequence is called the score vector of the tournament. The increasingly ordered sequence of the scores is called the score sequence of the tournament and is denoted by .

Using the terminology of the sports a supertournament can combine the matches of different sports. For example in Hungary there are popular chess-bridge, chess-tennis and tennis-bridge tournaments.

A sport is characterized by the set of the permitted results. For example in tennis the set of permitted results is , for chess is the set , for football is the set and in the Hungarian card game last trick is . There are different possible rules for an individual bridge tournament, e.g. .

The number of participants in a match of a given sport is denoted by , the minimal number of the distributed points in a match is denoted by , and the maximal number of points is denoted by .

If a supertournament consists of only the matches of one sport, then we use and instead of vectors , and and omit the parameter . When the number of the players is not important, then the parameter is also omitted.

If the points can be divided into arbitrary integer partitions, then the given sport is called complete, otherwise it is called incomplete. According to this definitions chess is a complete (2,2)-sport, while football is an incomplete (2,3)-sport.

Since a set containing elements has -element subsets, an -tournament consists of matches. If all matches are played, then the tournament is finished, otherwise it is partial.

In this chapter we deal only with finished tournaments and mostly with complete tournaments (exception is only the section on football).

Figure 25.1 contains the results of a full and complete chess+last trick+bridge supertournament. In this example , , and . In this example the score vector of the given supertournament is , and its score sequence is .

Figure 25.1.  Point matrix of a chess+last trick-bridge tournament with Point matrix of a chess+last trick-bridge tournament with n=4 players. players.

Point matrix of a chess+last trick-bridge tournament with n=4 players.

In this chapter we investigate the problems connected with the existence and construction of different types of supertournaments having prescribed score sequences.

At first we give an introduction to -tournaments (Section 25.2), then summarize the results on (1,1)-tournaments (Section 25.3), then for -tournaments (Section 25.4) and for general -tournaments (Section 25.5).

In Section 25.6 we deal with imbalance sequences, and in Section 25.7 with supertournaments. In Section 25.8 we investigate special incomplete tournaments (football tournaments) and finally in Section 25.9 we consider examples of the reconstruction of football tournaments.

Exercises

25.1-1 Describe known and possible multitournaments.

25.1-2 Estimate the number of given types of multitournaments.