# Producing a total or partial order from an inconsistent relation

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?

• Your problem isn't well-specified. If the comparison function is truly non-deterministic, the problem can't be solved. Perhaps you have a stochastic model (e.g., that the comparison function outputs an erroneous result with some probability $p$, where $p<1/2$). Also you haven't specified what total order you want or any requirements on what total order the algorithm outputs. I could always output the same order and that would comply with all stated requirements. – D.W. Jan 16 at 8:52