# The secretary problem goes on budget

Secretary problem describes a scenario where a company wants to hire the best secretary from sequential interviews of candidates that can be done only once.

In budget secretary problem a company has an initial budget $$B=1$$ (expressed in unicorn dollars) that uses to hire as many secretaries as possible to maximize the total work load.

There are one or more candidates. Each candidate has a value between $$(0, 1]$$, uniformly distributed. This value is the total work load the secretary can handle for the company.

Only after each interview, the company knows the candidate value and can send him/her a proposal with a salary that does not exceed the remaining budget or the candidate value.

The candidate will accept the job with a probability that is the ratio between the proposed salary and his/her value.

If the job is accepted, then the budget is cut down by the proposed salary and the total work load is increased by the candidate value.

If no proposal was done or if it was declined, the candidate will ghost the company forever.

Can you help the company define the best strategy to invest the budget to maximize the total work load over $$N$$ candidates?

Disclaimer: Companies should never choose quantity over quality while hiring....

In my first answer, I assumed all values are unknown to us. Now let's consider the scenario where we know the value of a secretary before making an offer.

Again, consider the 2-secretary scenario again. We do know $$v_1$$ before making the first offer, but not $$v_2$$. For the second secretary we again thus just offer our remaining budget.

The expected reward for the second secretary (not knowing their value) offered budged $$b$$ is $$b^2/2+(1-b)b$$ (see first answer).

Assume the first secretary has value $$v_1$$ and is offered budget $$b$$. W.l.o.g. we can assume $$b\leq v_1$$ here, since the optimal solution surely does not offer more than necessary for secretary 1 to surely accept.

We again consider two cases: Either secretary 1 accepts and offer of $$b$$, or secretary 1 declines.

The expected workload of secretary 1 is simply $$v_1$$ in the first scenario and $$0$$ in the second. The probabilities are $$b/v_1$$ and $$1-b/v_1$$, respectively.

For the second secretary, the expected value depends on whether the first secretary acceoted. If the first accepted, we have $$(1-b)$$ budget left and thus have an expected workload of $$(1-b)^2/2+b(1-b)$$. If the first secretary declined, the second surely accepts the offer of $$1$$ and has expected workload $$1/2$$.

So in total we get an expected workload of

$$(b/v_1)(v_1+(1-b)^2/2+b(1-b))+(1-b/v_1)(0+1/2)$$

We can simplify this to $$f(b)=-b^3/(2 v_1) + b + 1/2$$, i.e., a simple polynomial in $$b$$. We want to find the maximum under the constraint $$b\leq v_1$$ as this is not explicitly handled in the term. Taking the derivative, we find that $$f(b)$$ has two extrema at $$b=\pm \sqrt{\frac{2}{3}v_1}$$. The one at negative $$b$$ is a minimum, the one at positive $$b$$ a maximum. Between those, $$f(b)$$ is monotonically increasing. Thus, we simply have that if $$\sqrt{\frac{2}{3}v_1}$$ is within the interval $$[0,v_1]$$ we offer that value, otherwise we just offer $$v_1$$.

So the optimal strategy is:

$$\mathit{offer}(v_1)=\begin{cases}\sqrt{\frac{2}{3}v_1} & \text{ if } \sqrt{\frac{2}{3}v_1}\leq v_1 \\ v_1 & \text{ else } \end{cases}$$

The condition is satisfied iff $$v\geq 2/3$$, so equivalently (and more readable):

$$\mathit{offer}(v_1)=\begin{cases} v_1 & \text{ if }v_1 < 2/3 \\ \sqrt{\frac{2}{3}v_1} & \text{ if } v_1 \geq 2/3 \end{cases}$$

For the expected workloads in each case, we compute $$f(v_1)$$ and $$f(\sqrt{\frac{2}{3}v_1})$$:

$$f(v_1)=-v_1^2/2 + v_1 + 1/2 \\ f(\sqrt{\frac{2}{3}v_1})=\sqrt{\frac{8}{27}v_1}+1/2$$

In the first case, $$v_1$$ is uniformly distributed over $$[0,2/3)$$, in the second over $$[2/3,1]$$. Taking the integrals over the respective intervals we get the final expected workload:

$$\int_0^{2/3} -v_1^2/2 + v_1 + 1/2 dv_1 + \int_{2/3}^1 \sqrt{\frac{8}{27}v_1}+1/2 d_v1 = 0.506...+0.322...=0.838...$$

For generalization to more secretaries, we can go back to my first answer. If we do not know $$v_1$$, we can still compute an expected value for a budget $$B$$. We can do the same generalization for the case where we know the first value by adapting the computation above.

In the 3-secretary scenario we can then simply compute the expected value when offering $$b$$ to the first secretary by considering the expected value for the remaining two secretaries when the starting budget is $$1-b$$, and then optimize for $$b$$ and we're done. When we observe $$v_2$$ we can then adapt the strategy to optimize for that.

Now for completeness there's still the case where we know ALL values beforehand... :)

• You got it! Numerical simulation confirmed your result, and the proposed generalization seems to be a winner to me! Commented May 18, 2023 at 10:02

Assume we only have two secretaries and offer the first a salary of $$1/2$$ and the second our remaining budget (i.e., $$1/2$$ or $$1$$, depending on whether the first secretary accepted).

First, consider a single secretary being offered a salary of $$1/2$$.:

• Secretary has value $$\leq 1/2$$
• Secretary has value $$> 1/2$$ Both are equally likely. The first case yields expected workload $$1/4$$ for secretary 1, the second expected workload $$0.5$$ (considering they may reject). In total, the expected workload is $$3/8$$.

Now we can tackle the 2-secretary problem. Here we consider three cases:

• Secretary has value $$\leq 1/2$$
• Secretary has value $$> 1/2$$ and accepts
• Secretary has value $$> 1/2$$ and rejects

In the first case, the first secretary accepts and has expected workload $$1/4$$. We offer the second secretary budget $$1/2$$ which, as stated above, yields $$3/8$$ expected workload. In total, we have $$5/8$$ workload in this case.

In the second case the first secretary has some value $$v$$ and the second as stated above an expected workload of $$3/8$$.

In the third case, the second secretary accepts surely and thus has expected workload $$1/2$$.

Given $$v>1/2$$, the second case happens with probability $$(0.5/v)$$ and the third with $$(1-0.5/v)$$. Thus the total expected reward in case $$v>1/2$$ is $$(0.5/v)(v+3/8)+(1-0.5/v)(1/2)=1-\frac{0.0625}{v}$$. Now we haven't resolved the $$v$$ yet, so we integrate this expression from $$1/2$$ to $$1$$ to obtain the total expected reward in case $$v>1/2$$ which turns out to be $$0.4566..$$.

Together with the first case we get a final expected reward of $$1/2(5/8)+0.4566..=0.769178...$$ which is indeed greater than $$0.5$$

Let's generalize: We offer the first secretary $$b$$, and the second the remaining budget. The calculations are the same.

The expected reward for a single secretary offered budged $$b$$ is $$b^2/2+(1-b)b$$.

Case 1 has probability $$b$$ and expected workload $$b/2+(1-b)^2/2+b(1-b)$$.

Case 2 has probability $$(1-b)(b/v)$$ and expected workload $$(v+(1-b)^2/2+b(1-b)$$.

Case 3 has probability $$(1-b)(1-b/v)$$ and expected workload $$1/2$$.

Combining cases 2 and 3 again we get that for $$v>b$$ the expected workload is $$(b/v)(v+(1-b)^2/2+b(1-b))+(1-b/v)(1/2)=(-b^3 + 2 b v + v)/(2 v)$$. Integrating from $$b$$ to $$1$$ we get $$1/2 (b^3 \log(b) - 2 b^2 + b + 1)$$. Combining this with case 1 the final expected workload is $$b(b/2+(1-b)^2/2+b(1-b))+1/2 (b^3 \log(b) - 2 b^2 + b + 1)$$.

Now to find the maximum, we can do more calculus and take the derivative which is $$-b^2 + 3/2 b^2 \log(b) + (1 - b)$$. Finding the roots of this term we find there is exactly one maximum of the function, namely an expected workload of $$0.7691998...$$ at $$b=0.496$$.

Personally, I find it fascinating that the optimal value for the first offer is so close to $$0.5$$ but yet not quite $$0.5$$.

As for how to generalize this: I suppose one could be this for a budget $$B$$ and not a set budget of $$1$$ and then iteratively compute optimal offers. E.g., for three secretaries, you offer the first secretary some amount $$x$$. You do the same case distinction, but now for the case they accept you find the optimum when the budget is $$1-x$$ instead of $$1$$. For the other case, where they decline, we already know the best continuation as it reduces to the 2-secretary problem.

I do not see any nice generalization. To me it seems like a bunch of number crunching. In fact, even fpr 2 secretaries I just plugged everything into Wolframalpha at some point...

• What i think is fascinating about your result is that you are limiting the strategy to offer a fixed amount and that is not relative to the outcome of the first interview. So there is margin for optimization. Your answer inspired me to do some numerical simulation. Offer 1/2 (or 0.496) to first candidate and the remaining budget to the second one, results in an average workload similar to your proven value. But instead, if we offer to the first candidate the same of his/her value, and the second one, the remaining budget, we approach an average workload of ~0.8333... Commented May 16, 2023 at 21:13
• I do not want to spoil, but rot13(vs jr yvzvg gur bssre bs gur svefg pnaqvqngr gb or ab zber guna ~0.77, jr trg rira na uvture nirentr jbexybnq ~0.837 va gur gjb-frpergnel-ceboyrz. Gur zvaq oybjvat guvat vf gung gur znkvzhz jbexybnq unccraf jura gur svefg bssre vf yvzvgrq gb n inyhr rdhny (be arne) lbhe cerqvpgrq jbexybnq.). I can share code. I am unable to figure out why. Commented May 16, 2023 at 21:13
• Then I misunderstood what information is present in this scenario. I assumed the value of each secretary was unknown to us. But now that you say it, it also makes sense to assume we knwo the value. After all, that's what the setup in the original secretary problem is as well (and it wouldn't make sense if we didn't). I'll think about the scenario where we know the value of a secretary during the offer. Also thanks for empirically verifying my solution :) Commented May 17, 2023 at 14:11

I think the way you formulated the problem doesn't lead to any interesting strategies.

First, if the company offers a candidate exactly their value $$v$$ they will accept with 100% probability and budget spend = workload. Offering a candidate more than their value doesn't result in more workload so no point in doing that just like in real life :-). Next assume the company offers some amount $$o < v$$. Then the candidate will accept with probably $$o/v$$ and if they accept perform $$v$$ workload. So the expected workload is exactly $$o/v*v=o$$.

In other words, the expected workload done is always equal to the investment done (as long as you don't overpay any candidate). You can lowball a few candidates and introduce a lot of variance but the expected value doesn't change.

• Basically, if companies want "more", they have to increase their budgets. Nice! Commented May 13, 2023 at 12:20
• This is incorrect; if a low offer is accepted one gains value because more budget is left for further candidates. e.g. with 2 value1 candidates, offering 0.5 to the first and then all remaining budget to the second gives an expected workload 1.25 (25% chance of hiring both) Commented May 13, 2023 at 13:07
• @Retudin In your example there is a 25% chance of hiring both, a 25% chance of both refusing and a 50% chance of getting one, expected workload done is exactly 1. Commented May 13, 2023 at 17:28
• @quarague If the first refuses the second will not, since they will get offered 1. "If the job is accepted, then the budget is cut down" Commented May 13, 2023 at 19:39