1
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • $\begingroup$ 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). $\endgroup$
    – some guy on the street
    Commented May 8, 2010 at 15:37
  • $\begingroup$ 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. $\endgroup$
    – David R. MacIver
    Commented May 8, 2010 at 15:41

2 Answers 2

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ Ah, thanks. I looked but failed to find that. Possibly worth closing my question as a duplicate then. $\endgroup$
    – David R. MacIver
    Commented May 8, 2010 at 15:42
1
$\begingroup$

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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .