# American Institute of Mathematical Sciences

June  2021, 3(2): 133-149. doi: 10.3934/fods.2021010

## On the linear ordering problem and the rankability of data

 1 Penn State Behrend, 1 Prischak Building, Erie, PA, 16563, USA 2 Davidson College, P.O. Box 7129, Davidson, NC, 28035, USA

Received  December 2020 Revised  March 2021 Published  June 2021 Early access  April 2021

In 2019, Anderson et al. proposed the concept of rankability, which refers to a dataset's inherent ability to be meaningfully ranked. In this article, we give an expository review of the linear ordering problem (LOP) and then use it to analyze the rankability of data. Specifically, the degree of linearity is used to quantify what percentage of the data aligns with an optimal ranking. In a sports context, this is analogous to the number of games that a ranking can correctly predict in hindsight. In fact, under the appropriate objective function, we show that the optimal rankings computed via the LOP maximize the hindsight accuracy of a ranking. Moreover, we develop a binary program to compute the maximal Kendall tau ranking distance between two optimal rankings, which can be used to measure the diversity among optimal rankings without having to enumerate all optima. Finally, we provide several examples from the world of sports and college rankings to illustrate these concepts and demonstrate our results.

Citation: Thomas R. Cameron, Sebastian Charmot, Jonad Pulaj. On the linear ordering problem and the rankability of data. Foundations of Data Science, 2021, 3 (2) : 133-149. doi: 10.3934/fods.2021010
##### References:

show all references

##### References:
Linear Ordering Polytope: $P^{3}_{ \rm{LO}}$
Simple Digraphs on $3$ vertices
Optimal Solution(s) on Linear Ordering Polytope
College Features from U.S. World News 2013 Rankings
The degree of linearity and the hindsight accuracy of NFL rankings
Correlation between the degree of linearity and the hindsight accuracy of NFL rankings
The absolute difference between the foresight accuracy of two optimal rankings
Diversity among NFL playoff teams in two optimal rankings for years 1992 and 1999
NFL playoff progression in 1992; the opaque team lost the indicated matchup
NFL playoff progression in 1999; the opaque team lost the indicated matchup
 [1] Dinh T. Tran, John A. G. Roberts. Linear degree growth in lattice equations. Journal of Computational Dynamics, 2019, 6 (2) : 449-467. doi: 10.3934/jcd.2019023 [2] C. Davini, F. Jourdan. Approximations of degree zero in the Poisson problem. Communications on Pure & Applied Analysis, 2005, 4 (2) : 267-281. doi: 10.3934/cpaa.2005.4.267 [3] John Sheekey. A new family of linear maximum rank distance codes. Advances in Mathematics of Communications, 2016, 10 (3) : 475-488. doi: 10.3934/amc.2016019 [4] Xin Yang Lu. Regularity of densities in relaxed and penalized average distance problem. Networks & Heterogeneous Media, 2015, 10 (4) : 837-855. doi: 10.3934/nhm.2015.10.837 [5] Raz Kupferman, Asaf Shachar. On strain measures and the geodesic distance to $SO_n$ in the general linear group. Journal of Geometric Mechanics, 2016, 8 (4) : 437-460. doi: 10.3934/jgm.2016015 [6] Jia Shu, Zhengyi Li, Weijun Zhong. A market selection and inventory ordering problem under demand uncertainty. Journal of Industrial & Management Optimization, 2011, 7 (2) : 425-434. doi: 10.3934/jimo.2011.7.425 [7] Shahede Omidi, Jafar Fathali. Inverse single facility location problem on a tree with balancing on the distance of server to clients. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021017 [8] Jian Lu, Huaiyu Jian. Topological degree method for the rotationally symmetric $L_p$-Minkowski problem. Discrete & Continuous Dynamical Systems, 2016, 36 (2) : 971-980. doi: 10.3934/dcds.2016.36.971 [9] Joss Sánchez-Pérez. On the linearity property for allocation problems and bankruptcy problems. Journal of Dynamics & Games, 2018, 5 (1) : 9-20. doi: 10.3934/jdg.2018002 [10] Michael Kiermaier, Johannes Zwanzger. A $\mathbb Z$4-linear code of high minimum Lee distance derived from a hyperoval. Advances in Mathematics of Communications, 2011, 5 (2) : 275-286. doi: 10.3934/amc.2011.5.275 [11] Jesus Idelfonso Díaz, Jean Michel Rakotoson. On very weak solutions of semi-linear elliptic equations in the framework of weighted spaces with respect to the distance to the boundary. Discrete & Continuous Dynamical Systems, 2010, 27 (3) : 1037-1058. doi: 10.3934/dcds.2010.27.1037 [12] Kamil Otal, Ferruh Özbudak. Explicit constructions of some non-Gabidulin linear maximum rank distance codes. Advances in Mathematics of Communications, 2016, 10 (3) : 589-600. doi: 10.3934/amc.2016028 [13] Yong Zhang, Huifen Zhong, Yue Liu, Menghu Huang. Online ordering strategy for the discrete newsvendor problem with order value-based free-shipping. Journal of Industrial & Management Optimization, 2019, 15 (4) : 1617-1630. doi: 10.3934/jimo.2018114 [14] Jaume Llibre, Y. Paulina Martínez, Claudio Vidal. Linear type centers of polynomial Hamiltonian systems with nonlinearities of degree 4 symmetric with respect to the y-axis. Discrete & Continuous Dynamical Systems - B, 2018, 23 (2) : 887-912. doi: 10.3934/dcdsb.2018047 [15] Paul E. Anderson, Timothy P. Chartier, Amy N. Langville, Kathryn E. Pedings-Behling. The rankability of weighted data from pairwise comparisons. Foundations of Data Science, 2021, 3 (1) : 1-26. doi: 10.3934/fods.2021002 [16] Giovanni F. Gronchi, Chiara Tardioli. The evolution of the orbit distance in the double averaged restricted 3-body problem with crossing singularities. Discrete & Continuous Dynamical Systems - B, 2013, 18 (5) : 1323-1344. doi: 10.3934/dcdsb.2013.18.1323 [17] Philippe Ciarlet. Korn's inequalities: The linear vs. the nonlinear case. Discrete & Continuous Dynamical Systems - S, 2012, 5 (3) : 473-483. doi: 10.3934/dcdss.2012.5.473 [18] Jianxun Liu, Shengjie Li, Yingrang Xu. Quantitative stability of the ERM formulation for a class of stochastic linear variational inequalities. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021083 [19] Yanjun Wang, Shisen Liu. Relaxation schemes for the joint linear chance constraint based on probability inequalities. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021132 [20] Mohsen Lashgari, Ata Allah Taleizadeh, Shib Sankar Sana. An inventory control problem for deteriorating items with back-ordering and financial considerations under two levels of trade credit linked to order quantity. Journal of Industrial & Management Optimization, 2016, 12 (3) : 1091-1119. doi: 10.3934/jimo.2016.12.1091

Impact Factor: