2
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – D.W. ♦
    Jan 16, 2021 at 8:52

1 Answer 1

Reset to default
1
$\begingroup$

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).

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Thank you! This is exactly the answer I was looking for. You explained why there is no perfect solution and still offered me alternatives in the same space. $\endgroup$
    – Nic
    Jan 16, 2021 at 15:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.