Imagine I want to construct a total order from a set of elements, $E$, but the comparison function produces results that are non-deterministic. I produce a list of element pairs (e, e) through repeated application of the comparison function, such that each element in the set is represented at least once.
How can I use this input to produce a total order? What is the class of algorithms that can be applied here?
For greater clarity, I'll provide a concrete example.
What are the best pizza toppings?
My set of elements $E$ includes some popular pizza toppings: pepperoni, cheese, mushroom, pineapple, bellpepper, olive.
Then for each of my friends, I pick randomly sized subsets of toppings and ask my friend to put them in order from best to worst. My friends dutifully reply, and create the input for my algorithm:
- cheese, pepperoni, olive
- cheese, pineapple, mushroom, olive
- bellpepper, mushroom, olive
- pepperoni, cheese, olive
- cheese, bellpepper
There does seem to be a fuzzy order here (everyone agrees olives are the worst) but my friends have not arrived at consensus about which is the better pizza topping: cheese or pepperoni. Considering where items occur in the inputs, and how frequently they occur, I would probably produce an order something like this.
- cheese > pepperoni > bellpepper > pineapple > mushroom > olive
I'm just not sure how to go about formalizing this and making it work for much larger inputs.
I think the solution probably involves graphs and weighted edges, but I lack sufficient familiarity with graph algorithms to recognize whether this is a named area of study. I already came across "topological sorting" but that only works for directed acyclic graphs, and I am specifically interested in inputs that cannot produce a DAG.
I also noticed that this problem seems similar to voting for elected representatives. Is it, in fact, the same class of problem?