Sort algorithm for inconsistent (non-transitive) human preferences

Question

Suppose I have a file with a single line (joke) in each line. I want to sort the jokes by how funny I find them. My first thought is to implement any sorting algorithm (preferably one that makes as few comparisons as possible) and have a comparison algorithm. I just sit and choose which of each pair of jokes she presented to me was funnier.

There is a problem with this. My joke is not a complete order. It does not have transitivity. For example, I might think that B is funnier than A when they are presented, and that C is funnier than B, but when I introduced A and C, I find A funnier than C. If ">" means "funnier," this means that C> B and B> A does not mean C> A. The correctness of the sorting algorithms depends on this.

But still it seems that there should be an algorithm that sorts the list of jokes, so that the one on top is most preferable to other jokes, and the one on the bottom is less preferable to other jokes, even if there are separate exceptions.

I do not know how to do this Google. Is there an algorithm for sorting preferences? The answer is not applicable here , as it makes users' preferences be transitive.

Answer 1

If you present your decisions as a directed graph, where each joke is a node, and each directed edge indicates that one joke is better than the other, then you can get the order by building the path following the edges and visits of each node exactly once.

This type of graph is called a tournament, and the path is called Hamiltonian. I have good news for you, Bab, the Hamiltonian has proven to exist if the graph is strongly connected. A strong connection simply means that each node can be reached from each node, obeying the direction of the edges, so keep adding edges until this is true.

Tournament: https://en.wikipedia.org/wiki/Tournament_(graph_theory)

Hamiltonian Way: https://en.wikipedia.org/wiki/Hamiltonian_path