Computing Minimum Feedback Arc Set to Quantify the Transitivity in Sports Team

This thesis fulfills the need for a system of optimal ranking of sports teams. The current ranking system used for ranking the teams in tournaments like English Premier League (EPL) and Indian Premier League (IPL) only account for wins and losses, while the approach in this thesis better accounts for how teams perform against each other and the relative strength between them, for example, this approach accounts for 'upsets' where a lower ranked team beats a highly ranked team. A tournament can be represented as a weighted directed graph G, where a directed edge E from team A to team B represents that Team A beat Team B and the edge weight constitutes the Goal Difference (GD) or the points differential between the two teams for that particular match. A feedback arc set (FAS) of G is a subset of its edges which contains at least one edge of every cycle in G. These set of edges which when removed from G, leaves us with a Directed Acyclic graph (DAG). The aim of this project is to solve 'Minimum Feedback Arc Set problem' (MFAS) which in other words is removing minimum number of least weighted edges from G such that the remainder of the graph G' results in a DAG. We solved the minimum feedback arc set problem by framing it as an optimization problem and utilized Gurobi Optimization Library to get the results. A linear Ordering of the resulting DAG gives the ranking of teams in the tournament.;Sub-part of this project is to calculate Coefficient of Transitivity (CoT) of a Tournament. The transitivity of a sports tournament would manifest itself as when a Team A, dominated Team B with a large point differential, and Team B dominated Team C, then Team A should also dominate Team C. However, if Team C beats Team A then we call it as an 'upset' and such upsets gives rise to cycles in the tournament graph G and thus decreases the transitive nature of the tournament. An important finding of this project is that the balance among sports tournaments like Soccer, Football and Cricket can be characterized by calculating the CoT for a particular season.