Sinkhorn ratings, and new strongly polynomial time algorithms for Sinkhorn balancing, Perron eigenvectors, and Markov chains
Warren D. Smith · 2005
This paper simultaneously makes new con- tributions to political science, probability and statistics, and linear algebra. We describe a new method, ratings, for pairwise-comparison based ranking of chessplayers, web pages, or football teams; it also may be used to rank the candidates in an election in which each vote is a partial ordering of the candidates. We also describe the first polynomial al- gorithm for finding the Perron-Frobenius eigenvector of a matrix with non-negative entries, and the second strongly polynomial time algorithm (and the first practical one) for Sinkhorn balancing a matrix with non-negative entries. The former also may be regarded as the first strongly polynomial algorithm for finding the stationary distribu- tion of an N-state Markov chain with known transition matrix. Along the way we also present a new formula- tion of the Perron-Frobenius eigenvector and Markov sta- tionary distribution problems as concave-( minimization problems, and present a powerful new technique for prov- ing monotonicity statements e.g. about Markov chains.