[EM] Markov chain approaches

[Jobst Heitzig]

Some addition:

The second and third example I gave seem to be related to another
Markov-chain method studied by Giora Slutzki and Oscar Volij (Scoring of
web pages and tournaments - axiomatizations, Working paper, Iowa State
University, 2003. Cited after Giora Slutzki and Oscar Volij: Ranking
Participants in Generalized Tournaments, 2003,
http://volij.co.il/publications/papers/ordinalrank3.pdf) and before by
Levchenkov.

Their "fair-bets method" (= Levchenkov's "self-consistent rule")
corresponds to putting

pBA := no. of voters prefering B to A, divided by the sum of those
numbers summed over all B.

They not only choose a winner but rank the options according to their
limit probability. As with my second example, I'm not sure whether the
winner is always in the Smith set.

Interestingly, they characterize this method as the *unique* method
(among all methods constructing a *quasi-order* on the options)
satisfying six axioms they call "dominance", "quasi-completeness",
"separability", "anonymity", "neutrality", and "negative responsiveness
to losses".

"Dominance" seems to say that when there is a beatpath from A to B, but
none from B to A, A must end up above B.

"Quasi-completeness" seems to say that A may only end up incomparable to
B when neither has a beatpath to the other.

"Separability" seems to say that the ranking can be computed
independently in "leagues", which are the maximal classes of options in
which each has a beatpath to each other.

"Anonymity" is just what we know under the name.

If I understand these four axioms right, it seems to me that Tideman and
River fulfil them, hence the crucial point must be the other two axioms:

"Neutrality": Now this is something I did not understand yet.
Quote:
"Neutrality requires that if two problems are such that the ranking
method cannot rank any player [that is, any option! JH] above another,
then the ranking method should still be unable to rank one player above
another when considering the two problems together as a single problem.
And conversely, if two problems are such that in the first one the
ranking method does not rank one player above another, but in the second
problem there are two players that are strictly ordered, then it must be
the case that, when considering the two problems together, there are at
least two players that are ranked one above the other."
At least this seems to apply only in rare cases, where the method fails
to construct any strict ranking at all...

Finally, "negative responsiveness to losses" seems to be the crucial
point implying the fair-bets method: Suppose in some situation, the
method cannot but rank all options equal. Suppose further that now for
each option A some non-negative number lambda(A) is chosen and the
number of voters prefering B to A is multiplied by lambda(A) for each
A,B. Then the axiom requires that the method must now put A above B if
and only if lambda(A)<lambda(B).

I don't know what the rationale behind this last axiom is, but perhaps
someone can find it. However, I have the feeling that it must be somehow
related to the MinMax rule and to breaking cycles at the weakest link...