30.4. 30.4 Kings and serfs in tournaments

Sociologists are often interested in determining the most dominant actors in a social network. Moreover, dominance in animal societies is an important theme in ecology and population biology. Social networks are generally modelled as digraphs with vertices representing actors and arcs representing dominance relations among actors. The concept of “king” is very closely related to dominance in digraphs. Kings and serfs were initially introduced to study dominance in round-robin competitions. These concepts were latter extended to more general families of digraphs such as multipartite tournaments, quasi-transitive digraphs, semicomplete multipartite digraphs and oriented graphs. In this section our focus will be on algorithmic aspects of kings and serfs in tournaments and their applications in majority preference voting.

A king in a tournament dominates every other vertex either directly or through another vertex. To make the idea more formal we define a path of length from a vertex to a vertex in a tournament (or any digraph) as a sequence of arcs where is the initial vertex of , is the terminal vertex of and the terminal vertex of is the same as the initial vertex of , for all . If there is a path of length 1 or 2 from a vertex to a vertex , then is said to be reachable from within two steps. Analogously, if there is a path of length or from to then is said to be reachable from within steps. Let be an -tournament. A vertex in is called an r-king, where , if every other vertex in the tournament is reachable within steps from . A vertex is called an r-serf if is reachable within if is reachable within steps from every other vertex in , In particular, a 2-king is simply called a king and a 2-serf is called a serf.

Figure 30.10.  A tournament with three kings A tournament with three kings \{u,v,y\} and three serfs \{u,v,x\} . Note that z is neither a king nor a serf and \{u.v\} are both kings and serfs. and three serfs A tournament with three kings \{u,v,y\} and three serfs \{u,v,x\} . Note that z is neither a king nor a serf and \{u.v\} are both kings and serfs.. Note that A tournament with three kings \{u,v,y\} and three serfs \{u,v,x\} . Note that z is neither a king nor a serf and \{u.v\} are both kings and serfs. is neither a king nor a serf and A tournament with three kings \{u,v,y\} and three serfs \{u,v,x\} . Note that z is neither a king nor a serf and \{u.v\} are both kings and serfs. are both kings and serfs.

A tournament with three kings \{u,v,y\} and three serfs \{u,v,x\} . Note that z is neither a king nor a serf and \{u.v\} are both kings and serfs.


S. B. Maurer introduced the dual terms of king and serf in a delightful exposition of a tournament model for dominance in flocks of chicken. In his influential series of papers on dominance in animal societies, H. G. Landau proved that every tournament has a king (although he did not use the word king). In fact, he showed the following.

Theorem 30.16 (Landau, 1953) Every vertex of maximum score in a tournament is a king.

The proof is quite intuitive. Suppose to the contrary that is a vertex with maximum score in a tournament and is not a king. Then there exists another vertex in such that is not reachable from within 2 steps. But this means that and all out-neighbours of are reachable from in 1 step and so , a contradiction. Another classical result by J. W. Moon states that

Theorem 30.17 (Moon, 1968) A tournament without transmitters (vertices with in-degree 0) contains at least three kings.

It is natural to ask if the bound on the number of kings given in Theorem 30.17 is tight. The answer is yes, as demonstrated by the following example.

Example 30.2 Let be a tournament with vertex set . Let us denote by , an arc directed from to . Suppose that the arc set of consists of the arcs , , all arcs of the form , with and all arcs of the form with . Then it can be easily verified (Exercise 30.4-2) that has no transmitters and , and are the only kings in .

K. B. Reid proved the existence of a tournament with an arbitrary number of vertices and an arbitrary number of kings, with few exceptions.

Theorem 30.18 (Reid, 1982) For all integers there exists a tournament on vertices with exactly kings except when or when (in which case no such -tournament exists).

Hence no tournament has exactly two kings. The above theorems can be stated just as well in terms of serfs. To see this, note that the converse of a tournament , obtained by reversing the arcs of , is also a tournament and that the kings and serfs of and are interchanged.

The king set of a tournament consists of all kings in the tournament. We can define the serf set analogously. The problem of determining the king set of a tournament is very important both for theoretical and practical considerations. In voting theory literature, political scientists often refer to the uncovered set in majority preference voting. This uncovered set is actually the king set for the tournament whose vertices consist of the candidates to be elected and arcs represent the outcomes of the two-way race between candidates. Here we present a simple polynomial time algorithm for determining the king set of a tournament. Given an -tournament , let us define an matrix as

We call , the out-degree matrix of . When there is no danger of ambiguity we will drop the subscript and simply denote the out-degree matrix by . King-Set takes a tournament as input, calculates the out-degree matrix of and uses it to generate the king set of . Let be the zero matrix and let be the identity matrix.

King-Set( )

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

Algorithm description

The algorithm works on the same principle as the algorithm for finding the number of paths, from one vertex to another, in a digraph (Exercise 30.4-1 asks you to derive this algorithm). The entry of the matrix is equal to the number of paths of length two from vertex to vertex (check this!). Therefore, the entry of matrix counts the number of paths of length one or two from to ; and if vertex is a king, all entries in the row of must be non-zero.

The computational complexity of Algorithm King-Set depends on the way is computed. If naive matrix multiplication is used, the algorithm runs in time. However, using the fast matrix multiplication by Coppersmith and Winograd, the running time can be reduced to . The Reader should note that by using the duality of kings and serfs, King-Set can be adapted for finding the serf set of a tournament.

King sets in majority preference voting

Kings frequently arise in political science literature. A majority preference voting procedure asks each voter to rank candidates in order of preference. The results can be modeled by a tournament where vertices represent the candidates and arcs point toward the loser of each two way race, where candidate defeats candidate if some majority of voters prefer to . Political scientists are often interested in determining uncovered vertices in the resulting tournament. A vertex is said to cover another vertex if defeats and also defeats every vertex that defeats. The covering relation is clearly transitive and has maximal elements, called uncovered vertices. An uncovered vertex has the strategically important property that defeats any other vertex in no more than two steps, i.e., either

  1. defeats or

  2. there is some third alternative such that defeats and defeats .

Thus an uncovered vertex is actually a king. In fact the uncovered set, consisting of all uncovered vertices, is precisely the set of all kings (see Exercise 30.4-8).

The idea behind finding kings in a tournament can be easily extended to finding -kings for any positive integer .

King-Set( )

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

The above algorithm runs in if the matrix multiplications are performed naively, and in time if fast matrix multiplication is incorporated.

As we have seen, kings dominate in tournaments. However, there exists a stronger notion of dominance in tournaments in the form of strong kings. Let us write to denote that defeats in a tournament , or in other words is an arc of . If and are disjoint subsets of vertices of then we write to denote that all vertices in defeat all vertices in . We define , where denotes the vertex set of . Let . When no ambiguity arises, we drop the subscript from the notation.

A vertex in a tournament is said to be a strong king if or for every other vertex of .

Note that is the number of paths of length two through which is reachable from . Therefore, , where is the out-degree matrix of .

Obviously, it is not true that every king is a strong king. For example, Figure 30.11 demonstrates a tournament with three kings, namely , and . However, only and are strong kings as . Figure 30.11 also shows that when searching for the most dominant vertex in real life applications, a king may not be the best choice (vertex is a king, but it defeats only one vertex and is defeated by all other vertices). Therefore, choosing a strong king is a better option. This intuition is further confirmed by the fact that, in the probabilistic sense it can be shown that in almost all tournaments every vertex is a king.

Figure 30.11.  A tournament with three kings and two strong kings

A tournament with three kings and two strong kings


We have already shown that every tournament has a king. We now prove that every tournament has a strong king.

Theorem 30.19 Every vertex with maximum score in a tournament is a strong king.

Proof. Suppose is a vertex with maximum score in a tournament that is not a strong king. Then there is a vertex in such that and . Let be the vertex set of . Define

Then and . This implies that , a contradiction.

The problem of finding strong kings is no harder than finding kings in tournaments. Like King-Set , we present a polynomial time algorithm for finding all strong kings in a tournament using the out-degree matrix .

Strong-Kings( )

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

Strong-Kings has the same order of running time King-Set .

So far we have been focusing on finding certain type of dominant vertices (like kings and strong kings) in a tournament. Another very important problem is to construct tournaments with a certain number of dominant vertices. Maurer posed the problem of determining all 4-tuples for which there exists a tournament on vertices with exactly kings and serfs such that of the kings are also serfs. Such a tournament is called an -tournament. For example the tournament given in Figure 30.11 is a -tournament. Reid gave the following characterization of such 4-tuples.

Theorem 30.20 Suppose that and . There exists an -tournament if and only if the following conditions hold.

  1. ,

  2. and ,

  3. either or and ,

  4. is none of , , or .

However, the corresponding problem for strong kings has been considered only recently. For , a tournament on vertices is called an -tournament if it has exactly strong kings. The construction of - tournaments follows from the results proved by Chen, Chang, Cheng and Wang in 2004. The results imply the existence of -tournaments for all satisfying

Algorithm - Tournament takes positive integers and as input satisfying the constraints (26.2) and (26.3) and outputs an -tournament and the set of its strong kings. Also for any vertex of a tournament , we adopt the notation of Chen et al. in letting (respectively, ) denote the set of vertices reachable from in one step (respectively, set of vertices from which is reachable in one step). Note that and are often referred to as the first out-neighbourhood and first in-neighbourhood of respectively.

-Tournament( )

  1     3  null digraph on  verices   4  
                  IF
                
                is odd   5       6       7  
                  IF
                
                  8    
                  FOR
                
                
               
                  TO
                
                  9         10         11  
                  IF
                
                is even  12      13      14      15    choose  arbitrarily  16      17      18      19      20      21    
                  IF
                
                 22       
                  FOR
                
                
               
                  TO
                
                 23            24            25  
                  RETURN
                
                
            

Algorithm description

The algorithm consists of performing two separate inductions to generate an -tournament, one for odd and one for even . If is odd then we start by letting , the regular tournament on vertices (which always exists for odd ), and inductively add vertices to that are defeated by all the vertices of . Thus the resulting tournament has vertices and kings (the vertices of ). The construction for even is a bit more involved. We start with . Note that every vertex of has score . We then add three vertices , and and several arcs to such that for a fixed existing vertex of .

Figure 30.12.  Construction of an Construction of an (n,k) -tournament with even k .-tournament with even Construction of an (n,k) -tournament with even k ..

Construction of an (n,k) -tournament with even k .


The resulting tournament (illustrated in Figure 30.12) has vertices with scores , , and , for all vertices of . Now by Theorem 30.19 all vertices of and the new vertex are strong kings of , while and are not (Exercise 30.4-9). Thus is a -tournament that can now be extended to an -tournament by adding more vertices that are defeated by all the existing vertices of (just like in the case of odd ).

- Tournament runs in quadratic time as it takes operations to construct a regular tournament and the remaining steps in the algorithm are completed in linear time.

Exercises

30.4-1 The out-degree matrix of an -vertex oriented graph is an matrix whose entry is given by . Describe an algorithm based on the out-degree matrix for finding the number of paths of length between any two vertices of the graph.

30.4-2 Draw the tournament discussed in Example 30.2 and show that it has no transmitters and exactly three kings.

30.4-3 Using the 5-tournament in Example 30.2 give the construction of an -tournament with no transmitters and exactly three kings.

30.4-4 For every odd number , give an example of an -tournament, in which all vertices are serfs.

30.4-5 Prove that any tournament on 4 vertices contains a vertex which is not a king.

30.4-6 A bipartite tournament is an orientation of a complete bipartite graph. A vertex of a bipartite tournament is called a 4-king

(or simply a king) if there is a directed path of length 4 from to every other vertex of the tournament.

Footnote. Several bipartite and multipartite tournaments have no 2-king or 3-king. However, a multipartite tournament with at least one vertex of in-degree zero contains a 4-king. Therefore it is logical to look for 4-kings in a multipartite tournament.

Derive an algorithm to obtain all 4-kings in a bipartite tournament and compare its complexity with the complexity of - Kings for finding -kings in ordinary tournaments.

30.4-7 As the name suggests a multipartite tournament is an orientation of a complete multipartite graph. Extend the algorithm obtained in Exercise 30.4-6 to find all 4-kings in multipartite tournaments. Again compare the performance of your algorithms with - Kings .

30.4-8 Prove that the uncovered set arising in majority preference voting is exactly the king set of the majority preference tournament.

30.4-9 Show that when is even, the output of - Tournament has exactly kings.