A question on the relation of entropy to the secretary problem

Question

I recently read about the Secretary problem and it made me wonder if there was any relation to the entropy within the quality distribution of secretaries (i.e. how much their quality varies, which we wish to maximize for our single choice).

For example if we were after an estate agent and we know that all estate agents are the same (painful to deal with) then it doesn't matter how many there are, we may as well stop at the first one as the distribution has no entropy. So my question is whether the distribution of secretary quality (i.e. the entropy of the distribution) is related to when we should stop (or is the fact it has non-zero entropy enough)?

Note: I've googled a fair bit and not found anything useful so am assuming I'm mistaken on some (perhaps) fundamental point - so a clarification on my erroneous thinking would be very welcome.

Answer 1

The secretary problem assumes that the candidates are linearly ordered in quality. It makes no assumption about how large the gaps in quality are. You are suggesting that there might be a group of candidates close enough in quality that it doesn't matter which one you pick, which is certainly true in the real world but not in the spirit of the problem.

The concept of entropy does not really come in here. There are $n!$ arrangements of the candidates, presumed all equally likely. The entropy of the distribution is then $n!\sum \frac 1{n!}\log(n!)=\log(n!)\approx n\log n -n$. If you group $k$ candidates into a group because you don't care which one you pick the entropy decreases by $\log(k!)$ but I don't see how that changes things.

Answer 2

The solution to the secretary problem doesn't depend on on the distribution of quality. Even if the candidates have all the same quality, the stopping rule it provides is still optimal—in the sense that no other stopping rule will give a better expected outcome (of course, since all rules yield an equal outcome).

It seems that you are slipping in an extra factor to the problem, namely a cost in doing the search. That changes the problem completely, and you would need to specify the cost in relation to the "cost" of selecting an inferior candidate. This invites also the question of the quality distribution and your utility function with respect to the quality: a vast range of potential problems, most of which would have no easy solution.