I have a list of $n$ items, where each item gives a score to every other item, so I get a $n\times n$ square matrix $M$ of scores. Each score is a natural number. Items also score themselves. Example for $n=4$:

$$ \begin{array}{c|lcr} scores & A & B & C & D \\ \hline A & 3 & 3 & 9 & 11 \\ B & 7 & 1 & 12 & 5 \\ C & 11 & 9 & 8 & 7\\ D & 5 & 12 & 8 & 3 \end{array} $$

Each row $i$ represents the scores that item $i$ give to everyone else, and each column $j$ represents the scores that item $j$ got from everyone else. I'm looking for a way to build a preorder of the $n$ items in a way that is independent on the original order, it relies only on the matrix, and maximices the number of "equivalence classes".

Once items are sorted, each item will be "relabelled" by using as new label the index of its position in the sorted list. If two items are equivalent/equal to each other under the new criteria, both will get a same new label. I want to maximice the number of equivalence classes (be as close as possible to a total order) so that I have as many non-repeated labels as possible.

Using the example above, a method could be to sort the numbers of each column and then lexicographically sort them to get an initial ordering $B < A = D < C$ (since $A=D$ at this point, they are in the same "equivalence class" so far).

To break the equality $A = D$, both items represented by the sorted vector $(3, 5, 7, 11)$, we can exploit the fact that $5$ is the first score where the item, $B$, that gave that score to $D$, is less (under the current sorting) than the item, $D$, that gave that score to $A$. In other words, $M(B, D) = 5$ and $M(D, A) = 5$. Since $B < D$ in the initial ordering, the relationship is spread to $D$ and $A$ so we establish that $D < A$, and the items are now fully sorted as $B < D < A < C$. The lowest score $3$, doesn't help here because $M(A, D) = M(D, A) = 3$. The origins of such score for both items comes from the same "equivalence class". The next score, $5$, comes from different "equivalence classes" that can help break the equality.

That ad-hoc method is just an example to show that I want to exploit any single difference between rows and columns so that I can be as closer to a total order as allowed by the contents of the matrix.

Is there any algorithm related to the problem above?

  • $\begingroup$ What criteria do you want the sort to follow? You talk about a preorder and equivalence classes, but how are you looking to sort them, and what properties do you want the preorder to satisfy? Presumably it should be related to the matrix somehow, but how exactly? Please edit the post to add a clear problem statement. An example is not a substitute for a clear statement of the problem. $\endgroup$
    – D.W.
    Commented May 19, 2023 at 16:33
  • $\begingroup$ @D.W. Edited. I hope it's more clear now. $\endgroup$
    – ABu
    Commented May 19, 2023 at 19:01
  • 1
    $\begingroup$ @InuyashaYagami We use the initial ordering, to keep "refining" itself. That statement traces the origin of the scores given to columns $1$ and $4$. The lowest score, $3$ are given by themselves ($M(1, 4) = 3$ and $M(4, 1) = 3$), but score $5$ have a different origin in each column ($M(2, 4) = 5$ and $M(4, 1) =5$. Since $2<4$ in the initial ordering, we spread that relationship to $4$ and $1$. $\endgroup$
    – ABu
    Commented May 20, 2023 at 12:07
  • 1
    $\begingroup$ @InuyashaYagami I just relabelled the items. Thanks for the suggestion. $\endgroup$
    – ABu
    Commented May 20, 2023 at 12:13
  • 1
    $\begingroup$ Are you aiming only to maximize the number of equivalence classes, or something like this also works: cs.stanford.edu/~rishig/courses/ref/l10b.pdf? The FAS-tournament problem uses a different objective function in order to get an accurate ordering. $\endgroup$ Commented May 20, 2023 at 12:31


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.