0
$\begingroup$

I want to rank a population $P=\{P_1,\ldots,P_n\}$. I am given a set $R=\{R_1,\ldots,R_k\}$ of partial rankings. The partial rankings may have varying sizes (e.g. the first ranking ranks only 8 individuals, the next ranking ranks 20 individuals, ...).

I want to assign points to each combination of individual $P_i$ and ranking $R_i$. If $P_i$ does not participate in $R_i$, $P_i$ should get 0 points. If $P_i$ participates in $R_i$, $P_i$ should get points depending on their rank in $R_i$ and the size of $R_i$.

The total points of an an individual $P_i$ is the sum of their points in their 4 best rankings.

How should I design the function that assigns points for a certain rank $j$ in a ranking of size $s$?

Improve this question
$\endgroup$
13
  • 3
    $\begingroup$ This question is not mathematical. You may want to try stats.stackexchange.com instead. $\endgroup$
    – Iosif Pinelis
    Commented Jan 30 at 15:42
  • 1
    $\begingroup$ One case that is commonly studied, similar to your description but not exactly the same, is when we have a round-robin tournament where every player competes head-to-head against every other player. (So this would be like all your partial rankings $R$ have size $2$.) Even in this case it is quite nontrivial to assign scores to the players. One interesting approach is the "Kendall-Wei" method, where we encode the tournament as a matrix and use a principal eigenvector of this matrix to assign the scores to each player. $\endgroup$
    – Sam Hopkins
    Commented Jan 30 at 15:42
  • 1
    $\begingroup$ @Max The assumption that the rankings are consistent is a big assumption. If you want to assume that, you should say so explicitly. In the tournaments business I discussed, the fact that the rankings are not always consistent (there can be upsets in a tournament) is a big source of the struggle to come up with a good raking method. $\endgroup$
    – Sam Hopkins
    Commented Jan 30 at 16:17
  • 2
    $\begingroup$ @IosifPinelis : As I wrote in my answer below, this is a question in the area of Social Choice, and it is mathematical. It is true that the question is not well phrased, but I think this is why the author posted this question - because he needs references to learn how to properly phrase it. $\endgroup$
    – Eilon
    Commented Jan 31 at 5:43
  • 2
    $\begingroup$ My (uneducated) opinion is that the suggested scheme is flawed from the beginning and cannot be salvaged by any tune-up. Imagine that we have 20 people with very different abilities (or whatever is being ranked) about which everybody agrees. Imagine we have all possible rankings of subgroups of 4, say. Then no matter what the function is, all but the bottom 4 people will get the maximal possible score from the proposed procedure, so if the goal is to choose a few best rather than to weed out a few worst, this approach will be totally useless. With less fair grouping it gets even worse. $\endgroup$
    – fedja
    Commented Feb 13 at 21:11

2 Answers 2

Reset to default
3
$\begingroup$

The question is in the area called social choice. You can look for textbooks that write on this topic, like Chapter 22 in "Game Theory" by Maschler, Solan, and Zamir. There are many ways to define a function as you describe. For example, the top individual gets $|P|$ points, the next gets $|P|-1$ points, etc. Or the last ranked individual gets $1$ point, the one above it $2$ points, etc. To properly answer your question, one should determine the properties required from the function you look for. Once you read some literature on social choice, you will be able to better phrase your question.

Improve this answer
$\endgroup$
2
$\begingroup$

This is an interesting question. An expert in social choice would have an interesting reply. As a semi-expert I can say semi-interesting things.

As you may know, a common voting setting in social choice is to take in a set of rankings $R_1,\dots,R_m$, each a linear order on a finite set $P$, and aggregate them into a full ranking $R$. Classically each ranking is an order or permutation on P. A partial ranking would be an order on a subset of P, or more generally could e.g. be any subset of pairwise comparisons that is consistent with some ranking. The case of aggregating partial rankings into a final order has definitely been studied.

  • Some voting rules are based on pairwise comparisons. Any ranking implies a pairwise comparison between each pair of items in the ranking. It is easy to extend such a rule to partial rankings because they just give a smaller set of pairwise comparisons. For example, some rules are based on the tournament graph that Sam Hopkins mentioned, where $P$ are the vertices and the edge $(u,v)$ could e.g. be weighted by the fraction of all pairwise comparisons between $u$ and $v$ that are won by $u$. A voting rule can take this graph as input and use it to pick a winner. An old reference is "Choosing from a tournament" by Moulin.

  • If you did not have partial rankings, then you would be using the Borda count, which gives the top candidate in a ranking n points, the next n-1, etc., and outputs an aggregate ranking by total points. But, I haven't heard of one that uses this "best 4 rankings" idea. Normally we think of voting as wanting to aggregate lots and lots of rankings together, not throw away information about how good an alternative is!

  • But you also have partial rankings. A natural approach if the order has $k$ candidates in it is to award 1 point for first, $\frac{k-2}{k-1}$ for second, $\frac{k-3}{k-2}$ for third and so on down to $0$ for last. But any such rule would "reward" trying to only compete against bad alternatives. So it seems tricky. You could also just give 0 points for last, 1 point for second-to-last, up to k points for first. This would penalize being atop a small ranking.

  • All of this is without considering "best of 4", which should be easy to do computationally, but interesting to justify.

A quick search finds one paper that is very relevant: "The original Borda count and partial voting". It sounds like it discusses some of these issues.

Improve this answer
$\endgroup$

You must log in to answer this question.

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