4
$\begingroup$

So, I wanna make a ranking method for teams in the EPL, there are 20 teams in EPL, therefore there are $20!$ configurations of ranking assignment, my final ranking assignment would be the one that minimizes the loss function

$Loss=$ Number of matches where the lower ranked team defeat the higher ranked team

I think you can make a matrix where each element $a_{ij}$, the element of $i$-th row and $j$-th column, would be the number of times the $i$-th ranked team defeat the $j$-th ranked team.

You would make $20!$ different matrices, where each matrix is just like the other with swapped rows and columns. The diagonal would still be in the diagonal.

The final ranking assignment would then be the one that minimizes the Loss Function, which can be calculated by summing the elements of the lower triangle of the matrix.

From my understanding, in this case, it would be equivalent to maximizing the summation of the elements of the upper triangle of the matrix. Because the loss function is equivalent, as in always giving the same final ranking assignment, to

$Loss=-$ Number of matches where the higher ranked team defeat the lower ranked team

But iterating through $20!$ different matrices is very slow, I wonder if there is any method to find the optimum ranking assignment quickly.

$\endgroup$
1
  • $\begingroup$ What is EPL? Can you spell it out? $\endgroup$ Jun 11 '19 at 21:40
0
$\begingroup$

I encountered the same problem when trying to order the nodes in a complete asymmetric graph. My objective is similar: maximize the difference between the sum of the lower entries and the sum of the upper entries. Here is a greedy solution in pytorch. I have not looked into any guarantee that it converges nor that it is optimal. However, when comparing with a brute force method for random matrices up to n=9, it always reached the same solution. Assuming that the produced solution is optimal, the number of steps required to reach it seems to be O(nlog(n)) for random matrices.

We first order the nodes by assigning them a value that is the sum of their outgoing edges weights - sum of their incoming edges weights. This quickly brings us closer to the solution.

Then, we build a matrix that contains the gain of moving the ith node to the jth position (I also tried a strategy that evaluates the cost of switching two nodes but it was suboptimal). We select and apply the best move and rebuild the matrix. We repeat the last step until every move has a negative value.

I haven't spent a lot of time trying to optimize the algorithm, let me know if you find any way to improve it.

import torch

def mperm(perm, matrix=None):
    """Applies the permutation `perm` on the rows and columns of `matrix`"""
    if matrix is not None:
        return matrix[perm][:, perm]
    res = torch.zeros(len(perm), len(perm)).long()
    for i, j in enumerate(perm):
        res[i, j] = 1
    return res

def graph_argsort(a, max_steps=100, pre_sort=True):
    
    def move(m, i, j, perm):
        """Moves the node at the ith position to the jth position"""
        i = int(i)
        j = int(j)
        start, stop = sorted((i, j))
        source = list(range(start, stop + 1))
        dest = (source[-1:] + source[:-1]) if i<j else (source[1:] + source[:1])

        m[dest] = m[source]
        m[:, dest] = m[:, source]
        perm[dest] = perm[source]
    
    b = a.detach().cpu().clone().masked_fill(torch.eye(a.shape[-1]).bool(), 0)

    # 1st step: absolute sorting
    if pre_sort:
        result_perm = (-b.sum(0) + b.sum(1)).argsort()
        b = mperm(result_perm, b)
    else:
        result_perm = torch.arange(len(b))
        
    # 2nd step: greedy insertion sort
    for step in range(max_steps):
        # gain from flipping outgoing edges
        top_gain = b.tril(-1).cumsum(0) - b.triu(1).flip(0).cumsum(0).flip(0)
        # gain from flipping incomming edges
        bot_gain = b.triu(1).cumsum(1) - b.tril(-1).flip(1).cumsum(1).flip(1)
        move_weights = (bot_gain - top_gain.T) * 2

        i = move_weights.view(-1).argmax(-1)
        i, j = int(i // b.shape[-1]), int(i % b.shape[-1])

        if move_weights[i, j] <= 0:
            break

        move(b, i, j, result_perm)
    
    return result_perm
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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