TITLE:
Sinkhorn ratings, and new strongly polynomial time algorithms
for Sinkhorn balancing, Perron eigenvectors, and Markov chains
AUTHOR:
Warren D. Smith
ABSTRACT:
We describe a new method, ``Sinkhorn 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 ``strongly polynomial time'' algorithm 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 distribution of an $N$-state
Markov chain with known transition matrix. Along the way we also present a new formulation
of the Perron-Frobenius eigenvector
and Markov stationary distribution problems as concave-$\cup$ minimization
problems, and present a powerful new technique for proving monotonicity statements e.g. about
Markov chains.
KEYWORDS:
Voting paradoxes, rating systems, Sinkhorn matrix balancing,
Perron-Frobenius eigenvectors, Markov chains, strongly polynomial
algorithms, linear algebra, minimum-entropy statistical estimators,
concavity, monotonicity.
DATE: 23 June 2005