Modeling and recovering non-transitive pairwise comparison matrices

Pairwise comparison matrices arise in numerous applications including collaborative filtering, elections, economic exchanges, etc. In this paper, we propose a new low-rank model for pairwise comparison matrices that accommodates non-transitive pairwise comparisons. Based on this model, we consider the regime where one has limited observations of a pairwise comparison matrix and wants to reconstruct the whole matrix from these observations using matrix completion. To do this, we adopt a recently developed alternating minimization algorithm to this particular matrix completion problem and derive a theoretical guarantee for its performance. Numerical simulations using synthetic data support our proposed approach.