The worst-case scenario requires 8 weighings to identify the balanced permutation, and a 9$^{th}$ weighing to verify it.
As Penguino pointed out:
- A balanced permutation will not have each of the four balls on one side lighter than a different one on the right. Thus, 8642 cannot balance because $8>7$, $6>5$, $4>3$, and $2>1$. But 8641 could balance because $1<2$.
- This leaves 21 potential balancing scenarios, which they listed (but missed 8431).
I've arranged the 21 into a sort of tree:
$$\begin{matrix} \\
&&& 8761 & & & &\\
&&& 8751 & 8651 & & &\\\
&&& 8741 & 8641 & 8541 & & \\
&& 8732& 8731 & 8631 & 8531 & 8431 & \\
&&& 8721 & 8621 & 8521 & 8421 & 8321 \\
&& 8632\\
8543 & 8542 & 8532\\
& & 8432
\end{matrix}$$
These permutations are partially ordered. Any entry directly below or directly to the right of another must weigh less than that other. I.E., we know 8741 weighs less than 8751 because $4<5$. Likewise by transitivity, we know 8421 must weigh less than 8751.
Going along the other diagonal, we don't know for sure about the relative weights. For example, we can't predict which of 8541 and 8621 weighs more without weighing. There are a few others that are not shown clearly, due to the 2-dimensional nature of the chart. For example, we know 8632 weighs more than 8631, even though it's below, to the left.
The longest chains are from 8761 to 8321. There are 16 of them, each of length 9.
The best choice for first weighing is 8631. This permutation has 8 heavier permutations and 6 lighter ones. Thus weighing it will eliminate at least 7 permutations (including 8631, itself).
The worst-case is when 8631 weighs more than its counterpart, eliminating only 7 cases, leaving 14:
$$\begin{matrix} \\
&&& 8761 & & & &\\
&&& 8751 & 8651 & & &\\\
&&& 8741 & 8641 & 8541 & & \\
&& 8732& 8731 & & & & \\
&&& 8721 & & & & \\
&& 8632\\
8543 & 8542 & 8532\\
&& 8432
\end{matrix}$$
The next best choice is 8741, which will eliminate 3 cases if it is lighter than its counterpart, and 5 cases if it is heavier. Worst case: lighter, leaving us with 11 (rearranging columns for clarity of ordering):
$$\begin{matrix} \\
8732 & & & & 8731 \\
& & & & 8721 \\
& & & 8651\\
& & & 8641 \\
& 8543 \\
& 8542 & & 8541\\
8632 & 8532 & 8432 \\
\end{matrix}$$
At this point, no chain is longer than 4 permutations, so no guess can be guaranteed to eliminate more than 2 options. There are 4 guesses: 8731, 8641, 8542, and 8532, which, between them are guaranteed to eliminate 8 permutations, leaving us with three.
Of the remaining options, the longest possible chain is of length 2, so no guess can be guaranteed to remove more than one permutation. For example, the last three might be: 8732, 8632, 8541. Two more weighings are required to limit the options down to 1 permutation.
So, one possible worst-case set of weighings is:
- First: 8631: result: heavy, reduce 21 to 14
- Second: 8741: result: light, reduce 14 to 11
- Third: 8731: result: heavy, reduce 11 to 9
- Fourth: 8641: result: light, reduce 9 to 7
- Fifth: 8542: result: light, reduce 7 to 5
- Sixth: 8532: result: heavy, reduce 5 to 3
- Seventh: 8632: result: light, reduce 3 to 2
- Eighth: 8732: result: heavy, reduce 2 to 1.
- Conclude: 8541 is the balanced permutation.
There are other options than the above, for example first and second weighing of 8541, 8731 is guaranteed to reduce the number of permutations to at most 11, as well.
But in any case, no matter the algorithm chosen, it could take up to 8 weighings to identify the correct permutation, and a 9$^{th}$ weighing to verify that it does balance.