Finding max value algorithm with subset comparison

Question

I have a set of $N$ different values, and my goal is to find the biggest one in the least number of comparisons. Comparing subsets (using the sum of each) is also allowed, and counts as one comparison.

The intuitive algorithm would be comparing them linearly: compare two items, compare the biggest with the next one, repeat. That would give us a total of $N-1$ comparisons.

Since I couldn't come up with anything, I want to know if there is some algorithm to do this more efficiently (making fewer comparisons), taking advantage of subset comparison being allowed.

Answer 1

Consider any algorithm that uses less than $n-1$ comparisons. We run the algorithm, responding as follows:

• If one of the sets is bigger than the other, we say that its sum is larger.
• If the two sets have equal size, we say that their sums are equal.

We can represent each comparison as a vector of length $n$: the comparison $\sum_{i \in A} w_i \gtrless \sum_{i \in B} w_i?$ (where $w_i$ are the weights) corresponds to the vector 1ドル_A - 1_B$, i.e., the vector having value 1ドル$ at the $A$-coordinates, having value $-1$ at the $B$-coordinates, and having value 0ドル$ elsewhere.

Let $\mathbf{x}_1,\ldots,\mathbf{x}_m$ denote the vectors corresponding to comparisons of sets of equal size (so $m < n-1$), and let $\mathbf{1}$ be the constant 1ドル$ vector. Since $m+1 < n$, there is a non-zero vector $\mathbf{v}$ orthogonal to all of $\mathbf{x}_1,\ldots,\mathbf{x}_m,\mathbf{1}$. We can assume that $|v_i| \leq 1$ for all $i$.

Consider the vector $\mathbf{w}_\delta = \mathbf{1} + \delta \mathbf{v}$, where $|\delta| < 1/n$. It is not hard to check that $\mathbf{w}_\delta$ is consistent with our replies to the algorithm. Yet $\mathbf{w}_\delta$ and $\mathbf{w}_{-\delta}$ have different maximal values, so the algorithm will make a mistake on at least one of them.

This argument even works when we are allowed to ask arbitrary queries of the form $\operatorname{sgn}(\sum_i x_i w_i)$.

• Iaka Noe: Conclussion: there's no way, is it? (I'm sorry to ask this, but I'm bad with all this vector stuff and could not understand completely what you were talking about)
• Yuval Filmus: That's what I would conclude from the argument.
• j_random_hacker: IIUC, you're showing that each comparison can be computed as a dot product of 2 vectors whose result is either positive ("first set is larger"), zero ("equal") or negative ("second set is larger"), and then showing that for any set of fewer than $n-1$ comparisons of equal-size sets, there always exist at least 2 weight vectors for which every dot product is zero (since $\mathbf x_i \cdot \mathbf w_{\pm\delta} = \mathbf x_i \cdot \mathbf 1 \pm \delta \mathbf x_i \cdot \mathbf v,ドル and both terms are zero, for different reasons) -- but which have different maximal values. ...
• j_random_hacker: ... There are 2 things I don't yet understand: (1) Can the restriction to equal-size comparisons be done away with? (2) Why is it important to include the condition $|\delta| < 1/n$?
• Yuval Filmus: Your two questions are related. I fix the weights in such a way that if you compare sets of different cardinalities, then the larger one is heavier.