|Workshop on Topology: Identifying Order in Complex Systems|
|Topic:||Hodge Decomposition and Online Ranking on Random Graphs|
|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.