Producing a total or partial order from an inconsistent relation

Question

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?

Answer 1

It's hard to say without more context and more modelling. It will require some assumptions on how the results of the comparison function relate to the (hidden) desired total order.

It's possible you might want the Bradley-Terry-Luce model. If so, there are many standard algorithms. See also https://cs.stackexchange.com/a/85204/755.

It's possible you might want some ranking system, like Elo, etc.

It's possible you might want a ranked voting system, such as IRV, Condorcet method, Borda count, or any of many others. They all have various flaws and tradeoffs. There is a proof that no system will have all the properties we might want -- see, e.g., Arrow's theorem and the problem of non-transitivity (that even if each of your friend's individual preferences is transitive, i.e., a total order, then there is no guarantee that there exists a global total order that is consistent with all of them).