A Kth best problem is, given some constraint, to find a solution that has the Kth best value compared to all solutions that meet the constraint. One way to write this as a decision problem is to decide whether there are K solutions that achieve a given value.
Garey and Johnson list several NP-hard Kth best problems: Kth Best Spanning Tree, Kth Shortest Path, Kth Largest Subset, and Kth Largest m-Tuple. However each of these problems can be solve in polynomial time if K is restricted to be polynomial in the size of the rest of the input.
Is there a Kth best problem that is NP-hard even if K is restricted to be polynomial in the size of the rest of the input (but poly-time solvable for K=1)? The problem should be natural enough that other Kth best problems can reduce to it, or at least be a good example for how to show NP-hardness of a Kth best problem.