Is "A solution wins if there's no strictly better solution in multiple measures" a valid winning criterion?

Question

To cite a recently sandboxed challenge by l4m2:

Solution win if there's no strictly better solution, aka. no solution that take less or same amount of items in mapping table, less or same amount of instrucions, and at least one of amounts of items and instructions is less.

I understand this statement as

A solution is measured in two ways: the number of items in the mapping table, and the number of instructions. A solution wins if no other solution is strictly better; solution A is strictly better than solution B if A is strictly better in one measure and at least as good in the other, i.e. (A[1]<B[1] && A[2]<=B[2]) || (A[1]<=B[1] && A[2]<B[2]) (assuming lower score is better in both measures).

I'm worried about this winning criterion because it permits many "winners" and we don't know which measure to primarily optimize for. The worst part is that, given an existing "winning" solution, one can tweak a little bit and post another "winning" solution, and then we have "another winner", not "the latter winning against the former".

On the other hand, l4m2 claimed that multiple winners is not a problem because we already have something like "shortest code in each language wins", and we can get a collection of, say, "an exact bound of table size for each instruction count".

Is the proposed winning criterion valid?

Related: Why do we have objective winning criteria?

Answer 1

Yes, it is valid

After having some discussion with multiple users, I now feel like it should be a valid winning criterion.

The "winning criterion" is there mostly to motivate the answerers to optimize the code further. While the proposed winning criterion does not give one objective to optimize for, one can choose one of two objectives (or both at once), so that the new answer strictly beats the previous one.

@tsh's fastest-algorithm is probably not a good fit here because the relationship between \$O(VE^2)\$ and \$O(V^2 E)\$ can be resolved by specifying the relationship between \$V\$ and \$E\$ in the challenge (e.g. by saying \$E=O(V \log{V})\$ which makes \$O(V^2 E)\$ superior); IIRC lack of such relationship is considered unclear.

Answer 2

\$\require{begingroup}\begingroup \newcommand{xx}{\color{red}{\textsf{x}}} \newcommand{oo}{\color{green}{\textsf{o}}} \newcommand{slash}[2]{ #1\overset{\LARGE\backslash}{\phantom{.}}\overset{\Large #2}{\phantom{l}} } \$ (this is not really an answer, rather it's a way to show what else can be done if the consensus is that it is not allowed), given the current situation that people don't like for some reasons ^(*); personally I think that even if some people don't like it, it causes no harm (unlike what would happen if challenges without winning criteria are posted) and doesn't have any reason to be prohibited)

Assume that in the original challenge, there are two positive-integer scores A and B, which should be minimized, and in a reasonable program, they both does not exceed some easy-to-calculate threshold -- in the example above, 5 is used.

Solution 1

Parametrize the solution space. For example, programs have to minimize A+2B.

This is not very interesting, because there can be interesting solutions that trades A for very good B, or vice versa.

Solution 2

Assume that if a solution with a score (A, B) is possible, then (A+1, B) and (A, B+1) are both possible. (i.e., smaller scores are strictly better)

Assume that someone have a solution with score (4, 2). So the solution can be represented with this table

$$\begin{array}{c|ccc} \slash{A}{B} & 1 & 2 & 3 & 4 & 5 \\ \hline 1 & \xx & \xx & \xx & \xx & \xx \\ 2 & \xx & \xx & \xx & \xx & \xx \\ 3 & \xx & \xx & \xx & \xx & \xx \\ 4 & \xx & \oo & \oo & \oo & \oo \\ 5 & \xx & \oo & \oo & \oo & \oo \\ \end{array} $$

Where \$\xx\$ denotes impossible scores, \$\oo\$ denotes possible scores.

Obviously, better solutions have less \$\xx\$. So let the score of a submission to be the number of \$\xx\$ in the table, assume that both coordinates are constructed from 1 to 5. The score of this solution would be 17.

Now assume that someone else have another solution with score (2, 3). The table would be:

$$\begin{array}{c|ccc} \slash{A}{B} & 1 & 2 & 3 & 4 & 5 \\ \hline 1 & \xx & \xx & \xx & \xx & \xx \\ 2 & \xx & \xx & \oo & \oo & \oo \\ 3 & \xx & \xx & \oo & \oo & \oo \\ 4 & \xx & \xx & \oo & \oo & \oo \\ 5 & \xx & \xx & \oo & \oo & \oo \\ \end{array} $$

and the final score would be 13.

Observe that both answers can be combined:

$$\begin{array}{c|ccc} \slash{A}{B} & 1 & 2 & 3 & 4 & 5 \\ \hline 1 & \xx & \xx & \xx & \xx & \xx \\ 2 & \xx & \xx & \oo & \oo & \oo \\ 3 & \xx & \xx & \oo & \oo & \oo \\ 4 & \xx & \oo & \oo & \oo & \oo \\ 5 & \xx & \oo & \oo & \oo & \oo \\ \end{array} $$

and it results in a better score, 11.

This is a simple relatively-efficient implementation of the score calculation algorithm: Try it online! (input format: first line: dimension of the board, remaining lines: the reachable points, any format is accepted)

Of course, with this, the score of the answers posted later will always be strictly better than the score of the older answers. Nevertheless, it still encourages creativity (to find good answers), the same thing as what winning criteria does.

Besides, we already have answer-chaining.

^(*): nobody who downvoted left any comment. \$\endgroup\$

Answer 3

Allow multiple winners

We already had a tag fastest-algorithm.

Consider there is a challenge which input a graph \$ G(V, E) \$ and output something. The big-O notation may be measured in both V, and E. Someone may come up with an algorithm \$O(V^2E)\$ while others provide \$O(VE^2)\$ algorithm. Without given the assumption of the relation of \$V\$ and \$E\$, there is no way to tell which algorithm is better.

The above example not only happened when writing challenges on this site. But also happened in the real world. Most real-world libraries provide these functional by including both algorithm so caller may chose which one to use. Both algorithm could be considered good enough in such case.

We should also allow multiple winners as they are both good but no one better.