# I. Introduction

he problem of ranking players in a tournament has been the subject of various research investigations. This tournament structure also arises in other environments like the problems of soliciting customer preferences of a set of products, establishing funding priorities of a set of projects [5], establishing searching priorities for a set of search engines in the internet. It is known that the results of a tournament can be represented in adigraph, G=(V, A) known as tournament graph, where vertices correspond to players and arcs correspond to match results. A tournament result is said to be upset (or violation) if a lowly-ranked player has defeated a highly-ranked player. Ali [1], Cook [6], Goddard [5], Poljak [3] and many others have concentrated on the problem of determining ranks based on the results of the tournament. A constructive lower bound on the tournament ranking function was obtained in [4]. In [2], a heuristic solution to optimize the number of violations has been developed. This paper presents a new version of MST algorithm which reduces the number of violations compared to MST algorithm. The problem of minimizing the number of upsets is equivalent to finding the minimum number of arcs in adigraph deletion of which results in an acyclic digraph.


# II. Preliminaries

Before describing the new algorithm, we present here a brief discussion on MST algorithm [2] and GIK algorithm [1]. MST: For ease of discussion we recapitulate some of the definitions used in MST algorithm.

1. cutset(i, k, j) -is the difference between the numbers of outgoing arcs from set (i, k) to set (k + 1, j) and outgoing arcs from set (k + 1, j) to set (i, j), where set (i, j) is the set of vertices corresponding to players ranked from i to j. 2. maxwin(i, j) -is the maximum number of wins of a player in set (i, j). 3. pair(i, j) -corresponds to an upset if the player ranked j defeats the player ranked i. MST () Repeat until swap = false swap ?false for i= 1 to size-1 do for j = i + 1 to size do for k=i to j-
1 do if cutset(i,k,j)< 0 swap ?true elseif cutset(i,k,j)= 0 if pair(i,j) or ( i -l , k + l) or (k,j+ l) is upset then swap ? true swap respective pair else if maxwin(i, k) < maxwm(k + 1, j) swap respective pair endif endif if swap = true then swap set ({i, k), {k+ 1,j}) © 2017 Global Journals Inc. (US) ( )

# G

This problem is knownas Minimum Feedback Arc set Problem, and is NP-hard for general digraphs [1].

Assuming the number of players in the tournament to be n, complexity of the MST algorithm can be derived as follows: In the k-loop, calculation of cutset value requires O(n) operations. Each of the i, j and k-loop will be done at most n times for a single swap, which will reduce the number of violations by 1. The amount of computation for this is at most O(n 4 ). Since there can be at most O(n 2 ) violations initially, the algorithm requires at most O(n 6 ) calculations.


# GIK: This algorithm is based on the IK algorithm [ ].

When applying the IK algorithm to rank a tournament, two basic steps are executed in case of a tie. The first attempts to break the tie by restoring the players, while the second (which is applied when the first step fails) randomly ranks the players involved in the tie. The GIK algorithm differs from the IK procedure in these two steps. The restoring method is different, and if this restoring method does not resolve the ties, an attempt is made to rank the players in a manner that will reduce the overall number of violations.

The GIK algorithm appears below. 
> . . . >P k ) and R, = (Q 1 > Q 2 > . ?> Q J , then R1||R2 , = (P 1 > P 2 > . . . >P k > Q 1 > Q 2 > . . . > Q J ).

# The GIK Algorithm

Let R = á´?", A = {P 


# III. THE NEW ALGORITHM

In this Section we propose A new version of MST algorithm that results in minimum number of upset compared to the MST algorithm and GIK algorithm for ranking players in a round-robin tournament [].

We consider only simple connected digraphs G=(V,A). Spanning trees of any digraph are denoted by T. A directed cutset(V i ,V j ) is defined as
(V i ,V j )={(k,l)|k ? V i, l ? V j }
For improvement of the algorithm we introduce the following symbols and functions: Sa -start of setA Ea -end of setA Sb -start of setB Eb -end of setB Sc -start of setC Ec -end of setC Cutset(A,B)-is the difference between the numbers of outgoing arcs from set A to set B and outgoing arcs from set B to set A.

Cutset(A,C)-is the difference between the numbers of outgoing arcs from set A to set C and outgoing arcs from set B to set A.

Cutset(B,C)-is the difference between the numbers of outgoing arcs from set B to set C and outgoing arcs from set C to set B.

Procedure: Improved MST 3.


# 4.

5.


# 6.

7. 8.


# 9.

10.


# 11.

12. 13.

14. 15. 16.


# IV. Experimental Results

The new_MST Algorithm has been compared with MST Algorithm and the GIK algorithm on the basis of a set of randomly generated tournaments of sizes ranging from 5 to 50 players. All algorithms have been programmed in C and runs were made on a core i3 machines. We have been measured both in terms of violations and computational time. Here new_MST gives better result compared to MST and GIK with respect to number of violations.  


and D = D\{Pi}. If |D| = á´?", then go to(2).Otherwise go to (4).Let i=i + 1, and go to (12).Execute procedure Arrange on the ranking R.End.If A = á´?", then to go (15); otherwise determinethe current scores of players in A.If A = á´?", then go to (15); otherwise determine D,the dominant set.If |D|>1, then to go (6).Letting P denote the only player in D, form theranking R = R || P , let A = A\{P} and go to(3).If from the last time of updating the currentscores of A [step (2)], set A has changed, thengo to(2).1 , P 2 , . ., P n }. If |D| >2, then go to (9). Let P 1 and P 2 , denote the players in D with P 1 > P 2 . Let R= R|| P 1 ||P 2 , and A=A\{P 1 , P 2 }. Go to (2). If R = á´?", then go to (11).
1No of playerInitial upsetGIKMSTNew MST53.662.661.661.661024.0013.339.008.661547.3339.3325.6624.662089.0038.3325.3322.0025194.33109.6676.3372.3330106.6694.6667.3361.0040482.00138.6688.6679.0050585.66515.00439.00418.33
2No of playerGIKMSTNew MST50.00130.00300.0010100.01030.00900.0110150.01730.00930.0680200.02260.02360.5756250.02660.056388.5506300.03200.02161268.3740 500.043 0.054 V. Conclusion 0.1913 4.14724877.110 63415.8188Year 2017GThis page is intentionally left blank
			© 20 7 Global Journa ls Inc. (US) 1
		
		
			

				


* 
	
		On the minimum violations ranking of a tournament
		
			WDAli
		
		
			MCook
		
		
			Kress
		
	
	
		M qmt Sci
		
			32
			
			1986
		
	




* 
	
		A New Algorithm for Ranking Players of a Round Robin Tournament
		
			MohammadKaykobad
		
		
			QN UAhmed
		
		
			AT MKhalid
		
		
			Rezwan-AlBakhtiar
		
	
	
		Computer Ops Res
		
			22
			2
			
			1995
		
	




* 
	
		Tournament ranking with expected profit in polynomial time
		
			SPoljak
		
		
			VRodl
		
		
			JSpencer
		
	
	
		SIAM JI Disc. Math.I
		
			3
			1988
		
	




* 
	
		Constructive quasi-ramsey numbers and tournament ranking
		
			SPoljak
		
		
			ACzygrinowy
		
		
			V
		
	
	
		SIAM J. Discrete Math
		
			12
			1
			
		
	




* 
	
		Ranking tournaments and group decision making
		
			STGoddard
		
	
	
		Mgmt Sci
		
			29
			
			1983
		
	




* 
	
		Heuristics for ranking players in a round-robin tournament
		
			WDCook
		
		
			IGolan
		
		
			MKress
		
	
	
		Computers Ops Res
		
			15
			
			1988