Inferring Rankings from First Order Marginals

Motivated by applications in ranked-choice voting, we consider the problem of recovery of an election profile—encoded by a function f on the symmetric group—given only partial data. In particular, we investigate the combinatorial structure of the matrix of first order marginals, which gives the number of votes cast that ranked each alternative in each position. We investigate conditions on f that allow us to exploit this combinatorial structure to recover the original function f. As the matrix of first order marginals is the Fourier coefficient of the permutation representation of the symmetric group, this work sits within the context of algebraic compressed sensing, which tackles the question of how to recover a sparse function f on a finite group given only a subset of the Fourier coefficients of f.