Combination of Rankings - A Proper Merging of Experts Views

Let’s assume that several experts have a view on the rankings of some variables. Take for example the temperature in many cities in one month. There is only one true ranking that will be revealed in the next month by measuring the temperature at the locations. One will find, for example, that Hong Kong > Ho Chi Minh City > Singapore > Paris > London > … > Edinburgh. Depending on their quantitative models or their convictions and experiences, our experts will end up with different rankings. Moreover, they may prefer to rank only some of the cities they know well (e.g. South East Asia), or for which their models work. Experts (or external party) may also have a more or less strong confidence in their views.

That is, we have:

one true ranking that is unknown

and

several rankings that potentially span only a subset of the entire list
for each ranking, a percentage that expresses the confidence in the ranking

Question: How do we combine all these rankings to estimate the one true ranking?

Let’s define as a baseline this simple strategy:

Transform each ranking into a uniform defined on [0,1], i.e. for ranking #i, u_k = rank_k / length(ranking #i) in [0,1]
For each element to be ranked, (weight) average its transformed ranks u_k to obtain v_k
Rank the v_k variables to obtain the final ranking

Can we do better?

Here, I propose an approach based on transforming the input rankings into a markov chain.

The algorithm:

Consider a directed graph G = (V, E), where G = the elements to be ranked. E is initially empty.

For each ranking with confidence w, add to E the edges (i, j, weight=w) such that i > j in the ranking
For each vertex v in V, for each edge e in E such that e = (v, a in V, weight = w_e), replace this edge by e’ = (v, a in V, weight = w_e / sum(w_b for e’’ in (v, b in V, weight=w_b); in other words, normalizing edges exiting a given node such that their weights sum to 1
Random walk this markov chain to find its stationary distribution

The idea there is that elements at the top of the ranking will be traversed much less times (because few or no other elements are pointing toward them) than elements at the bottom of the ranking (because most of the other elements are pointing toward them).

To obtain the final ranking, we sort the elements by the number of times they were traversed in the graph during the random walks.

Now, some code. Let’s apply it on a small example. I will detail and evaluate thoroughly in subsequent notebooks.

The true ranking to recover:

import numpy as np
import pandas as pd
import networkx as nx

true_ranking = {
    1: 'Kuwait',
    2: 'Cairo',
    3: 'Bucharest',
    4: 'Rome',
    5: 'Singapore',
    6: 'Paris',
    7: 'Hong Kong',
    8: 'Prague',
    9: 'Oslo',
    10: 'Lima',
    11: 'Mexico City',
    12: 'Vancouver',
    13: 'Buenos Aires',
    14: 'Perth',
    15: 'Canberra'
}

true_ranking = pd.Series([rank for rank, city in true_ranking.items()],
                         index=[city for rank, city in true_ranking.items()])

ranking_1 = (
    {1.0: 'Kuwait',
     2.0: 'Singapore',
     3.0: 'Rome',
     4.0: 'Prague',
     5.0: 'Vancouver'},
    0.50)

ranking_2 = (
    {1.0: 'Oslo',
     2.0: 'Mexico City',
     3.0: 'Singapore',
     4.0: 'Prague',
     5.0: 'Hong Kong',
     6.0: 'Paris',
     7.0: 'Rome',
     8.0: 'Lima',
     9.0: 'Kuwait',
     10.0: 'Vancouver',
     11.0: 'Buenos Aires',
     12.0: 'Cairo',
     13.0: 'Bucharest',
     14.0: 'Canberra',
     15.0: 'Perth'},
    0.05)

ranking_3 = (
    {1.0: 'Kuwait',
     2.0: 'Singapore',
     3.0: 'Prague',
     4.0: 'Hong Kong',
     5.0: 'Lima',
     6.0: 'Vancouver',
     7.0: 'Rome',
     8.0: 'Bucharest',
     9.0: 'Cairo',
     10.0: 'Buenos Aires'},
    0.25)

expert_rankings = [
    ranking_1,
    ranking_2,
    ranking_3,
]

Ranking using Random Walks

def build_graph(rankings):
    rank_graph = nx.DiGraph()
    for ranking, ic in rankings:
        for node in ranking.values():
            rank_graph.add_node(node)
    for ranking, ic in rankings:
        for rank_up in range(1, len(ranking)):
            for rank_dn in range(rank_up + 1, len(ranking) + 1):
                u = ranking[rank_up]
                v = ranking[rank_dn]

                if u in rank_graph and v in rank_graph[u]:
                    rank_graph.edges[u, v]['weight'] += ic
                else:
                    rank_graph.add_edge(u, v, weight=ic)
                    
    return rank_graph

def build_markov_chain(rank_graph):
    for node in rank_graph.nodes():
        sum_weights = 0

        for adj_node in rank_graph[node]:
            sum_weights += rank_graph[node][adj_node]['weight']

        for adj_node in rank_graph[node]:
            rank_graph.edges[node, adj_node]['weight'] /= sum_weights
            
    return rank_graph

def random_walk(markov_chain, counts, max_random_steps=1000):
    cur_step = 0
    current_node = graph_nodes[np.random.randint(len(graph_nodes))]
    while cur_step < max_random_steps:
        counts[current_node] += 1
        neighbours = [(adj, markov_chain[current_node][adj]['weight'])
                      for adj in markov_chain[current_node]]

        adj_nodes = [adj for adj, w in neighbours]
        adj_weights = [w for adj, w in neighbours]

        if not adj_nodes:
            return counts
        
        current_node = np.random.choice(adj_nodes, p=adj_weights)

        cur_step += 1
        
    return counts

rank_graph = build_graph(expert_rankings)
markov_chain = build_markov_chain(rank_graph)

graph_nodes = list(markov_chain.nodes())

max_random_steps = 10000
counts = {node: 0 for node in graph_nodes}

nb_jumps = 300
for jump in range(nb_jumps):
    counts = random_walk(markov_chain, counts, max_random_steps)

# rank graph method
final_ranking = sorted([(node, count) for node, count in counts.items()],
                       key=lambda x: x[1])

graph_ranking = (pd.Series([count for node, count in final_ranking],
                          index=[node for node, count in final_ranking])
                 .rank(ascending=True))

graph_ranking

Paris            1.0
Kuwait           2.0
Singapore        3.0
Oslo             4.0
Mexico City      5.0
Hong Kong        6.0
Lima             7.0
Prague           8.0
Rome             9.0
Vancouver       10.0
Canberra        11.0
Bucharest       12.0
Cairo           13.0
Buenos Aires    14.0
Perth           15.0
dtype: float64

Ranking using Average of the Ranks

# average ranking method
rankings = pd.DataFrame(np.nan,
                        columns=sorted(graph_nodes),
                        index=range(len(expert_rankings)))

for idrank in range(len(expert_rankings)):
    for rank, asset in expert_rankings[idrank][0].items():
        rankings[asset].loc[idrank] = rank / len(expert_rankings[idrank][0])
        
sum_weights = sum([expert_rankings[idrank][1]
                   for idrank in range(len(expert_rankings))])
average_rankings = (rankings
                    .multiply([expert_rankings[idrank][1] / sum_weights
                               for idrank in range(len(expert_rankings))],
                              axis='rows')
                    .sum(axis=0))

average_ranking = average_rankings.rank(ascending=True).sort_values()

average_ranking

Oslo             1.0
Mexico City      2.0
Paris            3.0
Canberra         4.0
Perth            5.0
Hong Kong        6.0
Lima             7.0
Kuwait           8.0
Bucharest        9.0
Singapore       10.0
Cairo           11.0
Buenos Aires    12.0
Prague          13.0
Rome            14.0
Vancouver       15.0
dtype: float64

Comparing the Average of Ranks, and the Random Walks Ranks to the True Ranking

Let’s compare the rank (Spearman) correlation of the obtained ranking by each method with the true ranking:

np.round(
    average_ranking.corr(true_ranking, method='spearman'),
    2)

-0.24

np.round(
    graph_ranking.corr(true_ranking, method='spearman'),
    2)

0.37

pd.concat([true_ranking, average_ranking, graph_ranking], axis=1,
          keys=['true', 'w_avg', 'graph'], sort=False)

	true	w_avg	graph
Kuwait	1	8.0	2.0
Cairo	2	11.0	13.0
Bucharest	3	9.0	12.0
Rome	4	14.0	9.0
Singapore	5	10.0	3.0
Paris	6	3.0	1.0
Hong Kong	7	6.0	6.0
Prague	8	13.0	8.0
Oslo	9	1.0	4.0
Lima	10	7.0	7.0
Mexico City	11	2.0	5.0
Vancouver	12	15.0	10.0
Buenos Aires	13	12.0	14.0
Perth	14	5.0	15.0
Canberra	15	4.0	11.0

Conclusion: The Random Walks method for combining several rankings with potentially very different support seems to outperform the standard and naive way of merging rankings. This method alleviates several problems one can encounter in practice such as biases in missing data when performing ranking, etc. More on this later.