Hodge Decomposition and Online Ranking on Random Graphs

Workshop on Topology: Identifying Order in Complex Systems
Topic:Hodge Decomposition and Online Ranking on Random Graphs
Speaker:Lek-Heng Lim
Affiliation:University of Chicago
Date:Wednesday, April 4
Time/Room:2:30pm - 3:30pm/David Rittenhouse Lab.(Room A-7), University of Pennsylvania

Suppose a large number of voters have each rated or compared a small subset of a large number of alternatives, how could we rank the alternatives based on these data? The rank aggregation problem is fraught with famous difficulties --- Arrow's impossibility, Saari's chaos, NP-hardness of Kemeny optima. To complicate matters further, let's say the ratings do not come all at once but trickles in on a daily basis and we would like to regularly update our ranking. Let's say we also want a measure of reliability or quality of our ranking. We will disucss a method based on Hodge decomposition that meets all these requirements. This is joint work with Yuan Yao.