Timezone: »

 
Oral
Inferring rankings under constrained sensing
Srikanth Jagabathula · Devavrat Shah

Wed Dec 10 05:00 PM -- 05:20 PM (PST) @
in Oral session 9: Sparse Learning and Ranking »
Motivated by applications such as elections, web-page ranking, revenue maximization in gambling, etc. we consider the question of inferring popular rankings. In many of these applications, the number of distinct popular rankings are usually very few. However, the data available for inferring them is highly constrained. As the first main result of this paper, we provide a simple and novel algorithm to recover the popular rankings and their popularity exactly under a natural set of assumptions. Specifically, under a natural stochastic model, our algorithm recovers them exactly as long as the number of distinct popular rankings up to $O(n)$ over $n$ candidates (or elements). In certain applications, like ranked election, the interest is only in recovering the most popular (or mode) ranking. As the second result, we provide an algorithm based on Fourier transform over symmetric group to recover the most popular ranking under natural majority condition. Interestingly enough, this algorithm becomes a maximum weight matching on an appropriately defined weighted bipartite graph. The questions considered in this paper are thematically related to the currently popular topic of compressed sensing. The existing results in the literature do not apply to our problem as the information is constrained and can not be sampled randomly. Thus, the results of this paper correspond to constrained compressed sensing.

Author Information

Srikanth Jagabathula (NYU)
Devavrat Shah (Massachusetts Institute of Technology)

Devavrat Shah is a professor of Electrical Engineering & Computer Science and Director of Statistics and Data Science at MIT. He received PhD in Computer Science from Stanford. He received Erlang Prize from Applied Probability Society of INFORMS in 2010 and NeuIPS best paper award in 2008.

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors