Secretary Problem (Optimal Stopping) When Interviews Are Costly The Secretary problem is an optimal stopping problem. Imagine hiring one secretary out of $n$ applicants, who are interviewed in random order and either rejected or hired on the spot (as soon as one is hired, the interview process is ended). You cannot "go back" to an earlier candidate. The applicants that have been seen can be ranked. The original problem is to maximize the chance of getting the best applicant under those conditions.
A crucial aspect of the problem is that "no going back" restriction. If, after interviewing a given candidate, you decide not to hire them, you are not permitted later to go back and change your mind. That is a key part of the problem as normally stated. However, I'm interested in a modified version of the problem. There are two differences versus the usual setup.
First, remove the "no going back" rule. Or, put another way, let's say you don't have to make your decision until you're finished interviewing everyone. That change on its own dramatically simplifies the problem of maximizing the chances of getting the best applicant. All you do is interview all $n$ candidates, and only once all have been seen do you then decide on the best.
But second, suppose we want to take account of a cost of each interview. Thinking of the real situation, interviewing certainly takes time, and it also may involve money (e.g. paying for candidates' travel expenses). If we care about both the probability of getting the best candidate but also of minimizing the total cost to find our new employee, it may be that interviewing all $n$ candidates is not longer the best approach.
I don't know enough statistics to express the problem precisely, but the aim now has changed from being "maximize the probability of hiring the best candidate" to "optimize the combination of probability-of-best-hire with cost-of-whole-process" (or at very least "provide a method by which probability and cost may be traded against each other").
Is anyone aware of that version of the problem having been analyzed?
 A: Although mathematically not the same, the following problem shows you have to think about things probabilistically, as well as framing a dynamic optimization decision (optimal policy) problem.  Look at example 2 on p. 166 Applied Probability Models with Optimization Applications (conclusion of solution on p. 167 not in preview though). Full version at http://dtic.mil/cgi-bin/GetTRDoc?AD=AD0699891 . Streetwalker's Dilemma
In order to solve this, you first need to properly formulate an optimization problem. You need to establish a reward, as measured in dollars, depending on the "goodness" of the person hired. Your objective will be to maximize reward minus costs incurred through hiring.  You will need to input a probability distribution for the rewards of the pool of candidates. (The book I linked actually will help you do this, if you are sophisticated enough to handle it. Really cheap on amazon.com too. It's a serious book, and a serious problem, but the framing it as a streetwalker's dilemma is meant to be humorous.)
The key is, you must come up with a probability distribution as to the reward (goodness, as measured in dollars) associated with the pool of candidates you have not yet interviewed.  You need the reward to be in dollars in order to allow the rewards and costs to be combined into a single objective function (reward minus costs incurred in the hiring process) to be maximized.
If you keep the "no going back" rule, and don't incur interview expenses for candidates not yet interviewed (even if already scheduled?), then the solution will basically be the same as shown on https://en.wikipedia.org/wiki/Secretary_problem , except that applicant "being best" in your case needs to account for the cost of interviewing all candidates to date. So the goodness of an applicant = reward in dollars if that candidate is hired minus (cost of all previous interviews plus the current interview).
If you get rid of the no going back rule, I presume you still want to be able to terminate the process "early", because otherwise, you simply interview all candidates, incur the fixed cost of doing so, and choose the best candidate, after having interviewed all of them. So presume you can go back, and you can terminate early. The Dynamic Programming formulation needs to be modified to assess the maximum of the rewards of all the applicants interviewed to date minus all interview costs to date. This is as opposed to the no going back rule which is based on the reward of the current candidate minus all interview costs to date.
Even if the person who asked this question does not actually implement and solve the Dynamic Programming formulation, getting the person to properly frame the question, and think about the inputs which affect the answer, might be the most valuable contribution, and allow them to doing something "pretty good", even if not optimal.  Coming up with the probability distribution of rewards for the not yet interviewed candidates is the most difficult and important part of the whole "solution" process. An exact Dynamic Programming solution of an "off the mark" probability distribution of rewards will not be a good real-world solution.
