I was reading up on the secretary problem and thinking about how, in real life, there are costs (time, space, travel, etc.) incurred with each additional interview, which led me to the following variations of the problem: Consider a machine that has a cost each time it is run. Each time this machine is run, it generates a random integer between 1 and a known maximum $M$, inclusive, and then asks the user whether the user wants to accept that random value. If the user does not accept the value, then nothing happens. However, if the user accepts the value, then that machine gives that random integer as a payout and then self-destructs. What is the optimal strategy to maximize money (that is, payout less cumulative costs)...:
(1) ...if the cost is a constant $C$ each time the machine is run?
(2) ...if the cost is linearly increasing, starting at \$1? That is, the machine costs \$1 the first time it is run, \$2 the second time it is run, \$3 the third time it is run, and so forth.
(3) ...if the cost is a general function $c(t)$ of the number of times $t$ that the machine is run? (The previous two questions would then just be the $c(t) = C$ and $c(t) = t$ cases of this problem.)
The constant cost $C$ scenario can be solved using dynamic programming.
Let $V(x)$ be the expected payoff given the machine gave the value $x$ and consider a cutoff strategy $\tau$ that accepts $x\geq \tau$ and declines $x<\tau$.
Clearly, $M$ should be accepted, so $V(M)=M$. Now, suppose $x=M-1$. If accepted, the payoff is $M-1$. If rejected, then the user accepts only $M$, so the machine will run again and again until $M$ comes up. The expected number of runs is $M$ so the expected cost is $CM$. If we compare accepting and rejecting, we get $M-1=M-CM$ so $C=\tfrac{1}{M}$. If the cost is lower than this value, it is better to reject $M-1$ and otherwise to accept.
Now we can generalize. If we accept only the top $n$ values ($M,M-1,\ldots,M-n+1$), then the expected cost until one of them pops up is $\tfrac{CM}{n}$. The expected payoff, once it does, is $\tfrac{M+M-n+1}{2}$ so the condition for rejecting $M-n$ is $M-n=M+\tfrac{-n+1}{2}-\tfrac{CM}{n}$ or $C=\tfrac{n^2+n}{2M}$. If the cost is lower than this value, it is better to accept also $M-n$ and if higher, to reject.
To conclude, the optimal strategy for each $C$ can be computed by solving the equation $n^2+n=2MC$ and finding the $n$, the number of top $n$ integers that should be accepted when they pop-up.
For variations (2) and (3) the idea should be similar, but this time the cutoff strategy depends also on $t$ (more precisely, the stream of future costs). I'm not sure if one can write a tractable solution. I might come back to that later, no promises...