The Theory of Round Robin Tournaments
The Theory of Round Robin Tournaments
复制标题
DOI：
10.1080/00029890.1966.11970749
复制
发表时间：
1966-03
影响因子：
0.5
通讯作者：
F. Harary;L. Moser
中科院分区：
文献类型：
--
作者：
F. Harary;L. Moser
在这篇综述文章中，我们详细地研究了一类称为竞赛图的有向图。它们之所以被称为锦标赛，是因为它们代表了循环赛的结构，在循环赛中，球员或球队参与的比赛不会以平局结束，而且每个球员都只相互比赛一次。虽然锦标赛在结构上受到很大的限制，但除了循环赛之外，它们还通过许多经验现象来实现。例如，众所周知，许多鸟类和哺乳动物发展出优势关系，因此对于每一对个体来说，其中一种凌驾于另一种之上。因此，母鸡群的“啄食结构”的有向图是不对称的和完整的，因此是一场锦标赛。锦标赛的另一种实现方式是比例尺，也就是所谓的“配对比较”。例如，假设一个人想知道一个人在一系列相互竞争的产品品牌中的偏好结构。他可以被要求为每一对品牌指明他更喜欢哪一个品牌。如果他不被允许表示漠不关心，他所表达的偏好结构可以通过一场锦标赛来代表。在委员会和选举理论中，锦标赛也出现了类似的情况。假设一个委员会正在考虑四种替代政策。有人争辩说，最好的决定将通过一系列投票来达成，在这些投票中，每项政策都是相互匹配的。这些投票的结果可以用一个有向图来表示，它的点是政策，其线条表明一项政策击败了另一项政策。这样的有向图显然是一场锦标赛。在给出了一些基本的定义之后，我们开发了所有锦标赛都会显示的属性。然后，我们将注意力转向传递性比赛，即那些完全有序的比赛。众所周知，并不是所有的偏好结构都是传递的。因此，人们对了解任何给定的锦标赛的传递性有相当大的兴趣。这种索引是在第二节末尾提出的。在最后一节中，我们考虑了强连通竞赛图的一些性质。
In this review paper, we make a detailed study of a class of directed graphs, known as tournaments. The reason they are called tournaments is that they represent the structure of round robin tournaments, in which players or teams engage in a game that cannot end in a tie and in which every player plays each other exactly once. Although tournaments are quite restricted structurally, they are realized by a great many empirical phenomena in addition to round robin competitions. For example, it is known that many species of birds and mammals develop dominance relations so that for every pair of individuals, one dominates the other. Thus, the digraph of the "pecking structure" of a flock of hens is asymmetric and complete, and hence a tournament. Still another realization of tournaments arises in the method of scaling, known as "paired comparisons." Suppose, for example, that one wants to know the structure of a person's preferences among a collection of competing brands of a product. He can be asked to indicate for each pair of brands which one he prefers. If he is not allowed to indicate indifference, the structure of his stated preferences can be represented by a tournament. Tournaments appear similarly in the theory of committees and elections. Suppose that a committee is considering four alternative policies. It has been argued that the best decision will be reached by a series of votes in which each policy is paired against each other. The outcome of these votes can be represented by a digraph whose points are policies and whose lines indicate that one policy defeated the other. Such a digraph is clearly a tournament. After giving some essential definitions, we develop properties that all tournaments display. We then turn our attention to transitive tournaments, namely those that are complete orders. It is well known that not all preference structures are transitive. There is considerable interest, therefore, in knowing how transitive any given tournament is. Such an index is presented toward the end of the second section. In the final section, we consider some properties of strongly connected tournaments.