Optimal worse-case sorting algorithm when some comparisons are cheap

Question

I want to sort a set of items, where some comparisons are expensive and others are cheap. What is an algorithm that will minimize the worse-case number of expensive comparisons?

For instance, I want to rank sports players (assuming performance is completely deterministic, i.e. a game between two players will always have the same result), where some comparisons are already known, but others will require the players to play a game.

More formally, my machine has access to two oracles $f(a, b) \in \{<,=,>,\mathrm{unknown}\}$ and $g(a, b) \in \{<,=,>\}$, and I want to sort my list of items with the smallest worse-case number of calls to $g$ (which of course depends on the specific cases for which $f$ returns "unknown").

One approach I thought of is to extend $f$ into $f'$, which removes the unknown results that can be determined by transitivity, then use a standard sorting algorithm, calling $f'$ first, then $g$ if $f'$ returns "unknown". I'm not sure whether this is optimal (it may depend on the specific sorting algorithm).

I'd be satisfied with an algorithm that is near-optimal. I have about 100 items.

Answer 1

Your problem amounts to finding a linear extension of a given partial order, using the minimum number of comparisons between two elements. @Tassle highlights the following paper, which I believe is the state-of-the-art:

Sorting under Partial Information (without the Ellipsoid Algorithm). Jean Cardinal, Samuel Fiorini, Gwenaël Joret, Raphaël Jungers, J. Ian Munro. Combinatorica 33, 6 (2013), 655–697.

I have seen some papers call this the "SUPI" problem (Sorting Under Partial Information).

However, this algorithm is fairly complicated. If you want to a practical heuristic, that comes with no guarantees, you could try using a greedy heuristic.

Define some metric that represents how much uncertainty their remains about the final order, and that can be computed efficiently. For example, perhaps you can count the number of pairs whose order remains unclear (i.e., they are incomparable in the transitive closure). Then apply the following algorithm:

1. Compute the value of the metric on the current partial order.

2. For each pair $(x,y)$ you could possibly query next:

   • Compute the value of the metric if this query returns $x<y$, and the value if it returns $x>y$, and average those two metrics (or better yet, compute the max of these two metrics).

3. Pick the pair $(x,y)$ that reduces this metric the most. Query this pair $(x,y)$.

4. Update the current partial order with the result of this query (and apply the transitive closure). Go back to step 1 and repeat, until you have obtained a total order.

I don't know how well this will perform in practice, but it would be simple to implement and you could try it out.

The ideal metric would be the entropy, i.e., the log of the number of linear extensions compatible with the current partial order, but unfortunately it is #P-hard to compute that metric, and approximating it takes you deep into complicated algorithms, which I suspect you might want to avoid.