0
$\begingroup$

Is there interesting mathematics around ranking? (I mean ranking as reputation points here at mathoverflow.)

It looks obvious that there is no way to make adequate ranking --- is it a theorem, at least if the ranking is a function on the set of users?

On the other hand, one may imagine that ranking is a function of pairs of users, and it might take values in something more complicated. In this case there might be rig-proof ranking, but is it even defined?


This post was misunderstood by almost everyone, so let me try to clarify:

On one hand, a straightforward attempt to define ranking brings Arrow's theorem into the game that says --- it is impossible --- there is nothing better than dictatorship. On the other hand, let us take MO as an example, you want to rank users according to your own rule and use it to decide if a post worth investing your time. In this case, rank is a function on the edges of complete oriented graph on all users. But there is another problem --- a user cannot have a sufficient number of interactions to make such a decision --- so either you do not read most of the posts or read too many. We may take into account the ranking of users that have a good rank in your system. One possibility is that instead of a number you get a maximal subgraph formed by disjoint paths from A (you) to B (another user).

What is described is just one possible attempt. Was something like this used somewhere? Did you see other constructions that is impossible to fake?

Another request: please do not bring PageRank here again --- it can be faked easily (assuming you have enuf resources).

$\endgroup$
20
  • 1
    $\begingroup$ PageRank is maybe one keyword here... $\endgroup$ – Sam Hopkins Apr 30 at 23:44
  • 2
    $\begingroup$ rank aggregation problem or minimum feedback arc set $\endgroup$ – RobPratt May 1 at 1:00
  • 3
    $\begingroup$ @AntonPetrunin That may be because the problem itself doesn't give much to go on. The first question - "Is there interesting mathematics around ranking? " - might be worth exploring (though I expect that it's more psychology than math), but the rest looks to me like underdefined statements with very little that can be answered. What do you think "adequate" means? Or "rig-proof"? $\endgroup$ – user44191 May 1 at 2:45
  • 3
    $\begingroup$ I've read your revision (May 4th) but I do not understand what the goal of a ranking might be. What is a ranking, and what would it represent? $\endgroup$ – Ryan Budney May 4 at 21:26
  • 2
    $\begingroup$ Hi Anton, it's still unclear to me what exactly you want to measure or define. It sounds like you have some sort of implied definition, using extrapolation from common-usage English language. I imagine most people want more to go on than that. Reputation in the MO sense is a fairly concrete (albeit, sometimes changing) algorithm. Reputation in an idealized English-language sense is purely subjective. Someone who is very reputable to me might mean nothing to someone else, or the reverse. This is sort of like university rankings. They're all different, and any one is likely justifiable. $\endgroup$ – Ryan Budney May 5 at 2:43
3
$\begingroup$

There is a relatively recent book The science of rating and ranking by Langville and Meyer which provides a reasonable survey.

$\endgroup$
3
  • $\begingroup$ It seems that the title of my questions, moves everybody in wrong direction. (I have a feeling that no one has read the question carefully.) $\endgroup$ – Anton Petrunin May 1 at 2:03
  • 7
    $\begingroup$ Right. If everyone misunderstands the question, it must be because everyone is careless. It couldn't possibly be because the question is poorly worded. $\endgroup$ – Gerry Myerson May 1 at 5:11
  • $\begingroup$ @GerryMyerson, sure the is poorly worded, maybe now I would do it better, but I could not imagine so many misunderstands. $\endgroup$ – Anton Petrunin May 1 at 16:44
2
$\begingroup$

There is a lot of interesting mathematics related to ranking. See, for example this paper which explains how Google ranks web pages using Singular Value decomposition: T. Moh, 25 billion dollar eigenvector. When you mention "impossibility of ranking", you probably mean Arrow's theorem. But there are multiple mathematical formulations of "ranking problems".

$\endgroup$
4
  • $\begingroup$ Indeed, Arrow's theorem might be inteprited as "there is no adequate ranking as a function of user". But is there any research on other types of ranking? $\endgroup$ – Anton Petrunin May 1 at 4:36
  • 1
    $\begingroup$ @Anton Petrunin: sure, I gave you one reference, and the other answer contains another one. Look also under "order statistics". $\endgroup$ – Alexandre Eremenko May 1 at 12:59
  • $\begingroup$ By the way, about google ranking --- it use mathematics, but there are no meanigful mathematical statements about it; or am I wrong? $\endgroup$ – Anton Petrunin May 1 at 16:38
  • 3
    $\begingroup$ @Anton Petrunin Mathematically it is based on the existence of a stationary distribution for a finite Markov chain. Finding it explicitly for a large state space is a non-trivial problem from numerical analysis. $\endgroup$ – R W May 1 at 16:48

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