0
$\begingroup$

The secretary problem is a famous and old problem. You can find the basic definition of this problem here: https://en.wikipedia.org/wiki/Secretary_problem

Now I'm concerned with the k-secretary problem. A problem of choosing k candidates out of a queue of length n. This case has also been addressed, but, in my situation, the selector does not know n, that is, the length of the queue is unknown and only an upper bound for the length of the queue is known. Does anybody know whether or not the k-secretary problem with unknown n has been addressed in the literature or not? For the case k=1, there has been some work regarding the case where n might not be known. But in the general k>1 case, I'm wondering if it has been addressed or not.

P.S: Maybe we could add a simplifying assumption that when the upper bound for n is known, the distribution of n between 0 and the upper bound is uniform. If this assumption makes it possible for you to answer, please don't hesitate.

Another simplifying assumption I might be able to have is that k<=n

UPDATE: I intend to use this problem in an AI problem about selection. To explain it briefly, in my problem, the selector wants to choose k secretary out of a queue of length at most n (which the exact value is unknown). The selector only cares about secretaries to be good enough, but he will find whether or not candidates are good enough only after the problem is finished and the whole queue is visited. So, being a good secretary is a true or false situation. He hopes he can select k good secretaries. His value function which he intends to maximize would be (number of good secretaries he has chosen)/k. So if he fails to choose exactly k secretaries, his target ratio will be lower because the numerator of his value function would be lower but the denominator would still be k. But how could he have any sense of the candidates being good enough at the time of visiting them? He knows a metric. Say, how beautiful a secretary is, is a good predictor of how much good secretary he or she will be and upon arrival of each secretary, the selector can evaluate his or her exact beauty (metric). I don't want to make this problem too complicated, so I would only say the selector has thought about his metric before the problem starts, and he only tries to act like the classic k-secretary problem, but at the end of the day, what he cares most about is the success ratio which I explained earlier. I wanted to see if this problem is already addressed in the literature and I'm not looking about the probabilities of success, although if provided it would be great. I'm concerned with the strategy that leads to the optimal or even a good enough suboptimal solution. If there is any further question, please let me know.

Thanks.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ I suppose $k$ is deterministic, so the problem is somewhat ill posed, as in case $n \in[1,\dots,k-1]$ there is no way to win. I do think you would need an assumption on the law of $n$, much like you did, but perhaps something like $n$ being uniform between $[k+1,ck]$ for $c>1$. Even in this case, the events in which $n-k$ is small might still make the whole game really easy to fail, I would suggest start by looking at $n$ uniform in $[c_1 k ,c_2k]$ with $c_2>c_1>1$ and try to obtain the probability of success in terms of $k,c_1,c_2$. $\endgroup$
    – Kernel
    Commented May 3, 2021 at 8:27
  • $\begingroup$ @Kernel You are right. I did not fully explain my problem because I did not want to have an answer to be dim. In the case where n<k, assume that it is more or less like a binary scenario. I will update my question now that someone responded and I'll tell the slight difference between my problem and the secretary problem. I should also mention that I'm not a statistician and I want to know the optimal selecting strategy (knowing the stopping index) and use it as an application in another problem. It would be really helpful if you could introduce some papers about this. $\endgroup$
    – m0ss
    Commented May 3, 2021 at 9:20

0

Reset to default

You must log in to answer this question.