Aggregation of partial rankings, p-ratings and top-m lists

ABSTRACT

We study the problem of aggregating partial rankings. This problem is motivated by applications such as meta-searching and information retrieval, search engine spam fighting, e-commerce, learning from experts, analysis of population preference sampling, committee decision making and more. We improve recent constant factor approximation algorithms for aggregation of full rankings and generalize them to partial rankings. Our algorithms improved constant factor approximation with respect to all metrics discussed in Fagin et al's recent important work on comparing partial rankings. We pay special attention to two important types of partial rankings: the well-known top-m lists and the more general p-ratings which we define. We provide first evidence for hardness of aggregating them for constant m, p.

REFERENCES

• 1: Nir Ailon , Moses Charikar, Fitting tree metrics: Hierarchical clustering and Phylogeny, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.73-82, October 23-25, 2005 [doi>10.1109/SFCS.2005.36]
• 2: Nir Ailon , Moses Charikar , Alantha Newman, Aggregating inconsistent information: ranking and clustering, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060692]
• 3: N. Ailon, M. Charikar, and A. Newman. Proofs of conjectures in 'aggregating inconsistent information: ranking and clustering'. Technical Report, Princeton University, TR-719-05, 2005.
• 4: Noga Alon, Ranking Tournaments, SIAM Journal on Discrete Mathematics, v.20 n.1, p.137-142, 2006 [doi>10.1137/050623905]
• 5: Dennis S. Arnon , George E. Collins , Scott McCallum, Cylindrical algebraic decomposition I: the basic algorithm, SIAM Journal on Computing, v.13 n.4, p.865-877, Nov. 1984 [doi>10.1137/0213054]
• 6: Dennis S. Arnon , George E. Collins , Scott McCallum, Cylindrical algebraic decomposition II: an adjacency algorithm for the plane, SIAM Journal on Computing, v.13 n.4, p.878-889, Nov. 1984 [doi>10.1137/0213055]
• 7: K. J. Arrow. Social Choice and Individual Values. John Wiley and Sons, New York, 1951.
• 8: Mark Montague , Javed A. Aslam, Condorcet fusion for improved retrieval, Proceedings of the eleventh international conference on Information and knowledge management, November 04-09, 2002, McLean, Virginia, USA [doi>10.1145/584792.584881]
• 9: J. C. Borda. Mémoire sur les élections au scrutin. Histoire de l'Académie Royale des Sciences, 1781.
• 10: George E. Collins, Hauptvortrag: Quantifier elimination for real closed fields by cylindrical algebraic decomposition, Proceedings of the 2nd GI Conference on Automata Theory and Formal Languages, p.134-183, May 20-23, 1975
• 11: M.-J. Condorcet. Éssai sur l'application de l'analyse à la probabilité des décisions rendues à la pluralité des voix. 1785.
• 12: Don Coppersmith , Lisa Fleischer , Atri Rudra, Ordering by weighted number of wins gives a good ranking for weighted tournaments, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.776-782, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109642]
• 13: P. Diaconis and R. Graham. Spearman's footrule as a measure of disarray. Journal of the Royal Statistical Society, Series B, 39(2):262--268, 1977.
• 14: Cynthia Dwork , Ravi Kumar , Moni Naor , D. Sivakumar, Rank aggregation methods for the Web, Proceedings of the 10th international conference on World Wide Web, p.613-622, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.372165]
• 15: C. Dwork, R. Kumar, M. Naor, and D. Sivakumar. Rank aggregation revisited. Manuscript, 2001.
• 16: Ronald Fagin , Ravi Kumar , Mohammad Mahdian , D. Sivakumar , Erik Vee, Comparing Partial Rankings, SIAM Journal on Discrete Mathematics, v.20 n.3, p.628-648, August 2006 [doi>10.1137/05063088X]
• 17: Ronald Fagin , Ravi Kumar , Mohammad Mahdian , D. Sivakumar , Erik Vee, Comparing and aggregating rankings with ties, Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 14-16, 2004, Paris, France [doi>10.1145/1055558.1055568]
• 18: Ronald Fagin , Ravi Kumar , D. Sivakumar, Comparing top k lists, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 19: Ronald Fagin , Ravi Kumar , D. Sivakumar, Efficient similarity search and classification via rank aggregation, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872795]
• 20: Vladimir Filkov , Steven Skiena, Integrating Microarray Data by Consensus Clustering, Proceedings of the 15th IEEE International Conference on Tools with Artificial Intelligence, p.418, November 03-05, 2003
• 21: Aristides Gionis , Heikki Mannila , Panayiotis Tsaparas, Clustering Aggregation, Proceedings of the 21st International Conference on Data Engineering, p.341-352, April 05-08, 2005 [doi>10.1109/ICDE.2005.34]
• 22: J. Hodge and R. E. Klima. The Mathematics of Voting and Elections: A Hands-On Approach, volume 22 of Mathematical World. AMS, 2000.
• 23: J. Kemeny and J. Snell. Mathematical Models in the Social Sciences. Blaisdell, New York, 1962. Reprinted by MIT Press, Cambridge, 1972.
• 24: J. G. Kemeny. Mathematics without numbers. Daedalus, 88:571--591, 1959.
• 25: M. Kendall and J. D. Gibbons. Rank correlation methods. Edward Arnold, London, 1990.
• 26: W. Rand. Objective criteria for the evaluation of clustering methods. Journal of the American Statistical Association, 66(336):846--850, 1971.
• 27: Alexander Strehl , Joydeep Ghosh, Relationship-based clustering and cluster ensembles for high-dimensional data mining, The University of Texas at Austin, 2002
• 28: Y. Wakabayashi. The complexity of computing medians of relations. Resenhas, 3(3):323--349, 1998.