Inferring Rankings Under Constrained Sensing
Srikanth Jagabathula Devavrat Shah Massachusetts Institute of Technology

W24

Recover popular rankings from partial information.
Motivation: Elections, Betting, Webpage ranking, etc.

Setup: Election with n candidates Given: # of people who rank candidate j at position i Problem: Recover # of people who prefer each ranking

Thematic connections to: -- Compressive Sensing, Fourier Transforms. Theoretical results: -- Bound of O(n) on # of rankings that can be recovered. -- Novel Combinatorial algorithm to achieve bound of O(n).