A Note on Finding the Minimum With Non-Uniform Comparison Costs

Abstract Let us consider the following seemingly simple scenario: A finite set is given, which has a hidden total order of its elements. A player called the searcher can freely select any two elements and compare them. Furthermore, these comparisons have different positive costs that are known to the searcher in advance. The goal of the searcher is simply to find the minimum element at a minimum total cost. This combinatorial search game naturally appears as a subproblem in an approach to exact solutions of small instances of certain hard combinatorial optimization problems. We show in this note that a simple greedy strategy minimizes the worst-case total cost of the search. While this result as such might be quite expected, interestingly, the proof is not so obvious. We apply an exchange argument within a game-theoretic setting.