Return to Question

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.

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.

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.

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.

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 0 and 1 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 good a 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.

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.

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.

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.

Thanks.

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.

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 0 and 1 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 good a 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.