Workshop on Topology: Identifying Order in Complex Systems
Hodge Decomposition and Online Ranking on Random Graphs
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.
Date & Time
April 04, 2012 | 2:30pm – 3:30pm
Location
David Rittenhouse Lab.(Room A-7), University of PennsylvaniaSpeakers
Lek-Heng Lim
Affiliation
University of Chicago