Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I have the following setup:

There is a collection of items I and a collection of partial rankings V. That is, an element of V is a total ordering on a subset of I. There is no expectation of consistency among the elements of V: it may be that x < y for one element and y < x for another.

I would like to assign a score $s : I \to \mathbb{R}$ which in some sense captures these rankings. That is, I would like s(x) < s(y) to mean "x tends to be less than y for elements of V which have both in their domain". I'm not sure of what a good way to do this is.

Arrow's impossibility theorem puts some constraints on what can be achieved here, because given a set of votes and a scoring function like this we could use the scoring function to define a total order on the items, which is then constrained by the theorem.

I suppose I'm really looking for references rather than an answer to this question (although both would be appreciated): I'm sure there's a body of theory around this, but I have no idea what it is like or what it's called, so I'm at a bit of a loss as to where to start looking for a solution.

share|improve this question
If your partial rankings were all the same size, then the ranking score at least seems to be special --- that is, assign the ranking loser a score of 1, the next-up 2, etc.; and then sum over partial rankings. This score seems to be in a special sub-variety of the scoring simplex, which behaves well w.r.t. permutations --- details escape me, but for a Reference, I'm recalling this much as it was in a recent AMS Notices (in the past one or two years, I think). –  some guy on the street May 8 '10 at 15:37
Unfortunately the rankings are not likely to be of the same size - they're probably all going to be of similar size (and small compared to the size of I) though. –  David R. MacIver May 8 '10 at 15:41
add comment

2 Answers

One phrase people use for this problem is "rank aggregation." It often comes up in the context of search engines and document retrieval, where you might have multiple ways of ranking search results.

I'd add more details, but I'd just be repeating the nice answer to this previous MathOverflow question: Defining "average rank" when not every ranking covers the whole set

share|improve this answer
Ah, thanks. I looked but failed to find that. Possibly worth closing my question as a duplicate then. –  David R. MacIver May 8 '10 at 15:42
add comment

This sounds like "noisy sorting", see Braverman and Mossel.

share|improve this answer
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.