[math-fun] secretary problem
I was just reading a PDF about the secretary problem and all of the analyses I've ever seen seems to start with the assumption that the optimal strategy will necessarily be of the form "examine the first K candidates and then take the first candidate better than any you've seen so far", and if you haven't picked any candidate before that you MUST pick the N'th. And the math goes from there to derive the usual N/e value for K. What got me curious [and this has actually drifted in and out of my pondering for some time now] is whether there's a proof that includes proving that the *assumption* is correct, also. I could see a strategy, for example, where you examine K candidates and then take the *second* best [that is, wait until you get one better than K, and then take the one better than that second one]. There might be other strategies more subtle or something beyond my ken. I don't see how to prove the assumption: that that's the best *possible* selection strategy. ??? /Bernie\ -- Bernie Cosell Fantasy Farm Fibers mailto:bernie@fantasyfarm.com Pearisburg, VA --> Too many people, too few sheep <--
Well, clearly it's a suboptimal strategy in the following way. If after seeing N-2 candidates, I still haven't seen one better than the K'th, I know I only have two left. If the next one is above the median seen so far, I'm probably certainly doing better to pick that one and pass on the last, than to wait for the last. And of course a similar argument applies for N-3, and so on. Unless I'm missing something? On Tue, Jun 17, 2014 at 5:06 PM, Bernie Cosell <bernie@fantasyfarm.com> wrote:
I was just reading a PDF about the secretary problem and all of the analyses I've ever seen seems to start with the assumption that the optimal strategy will necessarily be of the form "examine the first K candidates and then take the first candidate better than any you've seen so far", and if you haven't picked any candidate before that you MUST pick the N'th. And the math goes from there to derive the usual N/e value for K.
What got me curious [and this has actually drifted in and out of my pondering for some time now] is whether there's a proof that includes proving that the *assumption* is correct, also. I could see a strategy, for example, where you examine K candidates and then take the *second* best [that is, wait until you get one better than K, and then take the one better than that second one]. There might be other strategies more subtle or something beyond my ken. I don't see how to prove the assumption: that that's the best *possible* selection strategy. ???
/Bernie\
-- Bernie Cosell Fantasy Farm Fibers mailto:bernie@fantasyfarm.com Pearisburg, VA --> Too many people, too few sheep <--
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- http://golly.sf.net/ --
On 17 Jun 2014 at 17:31, Tom Rokicki wrote:
Well, clearly it's a suboptimal strategy in the following way.
I assume when you say "it" you mean the "standard assumed optimal strategy"?
If after seeing N-2 candidates, I still haven't seen one better than the K'th, I know I only have two left. If the next one is above the median seen so far, I'm probably certainly doing better to pick that one and pass on the last, than to wait for the last.
I can't quickly do the math to see if that has a better expected outcome than the 'standard strategy'....
... And of course a similar argument applies for N-3, and so on.
But if that's the case, then you have the old paradox of "I'm going to give you an exam next week and it'll be a surprise". But perhaps not. Is this what you were thinking: "examine the first K candidates. Take the first candidate that is larger than the *median* of those first K" [rather than wait for one that's larger than any of the first K]. I haven't a clue if replacing "larger than any" with "larger than the median" makes for a better or worse strategy. Or if there's a combined strategy. [look at the first K. Then if you hit one larger among the next L, take it [obviously with K+L<N], but if not THEN you take the first one larger than the median of the ones you've seen so far. This seems to confirm my unease that the usual "assumption" [examine K and take the next that beats any of the K] probably needs to be proven to be an optimal strategy before you go and solve for K. /Bernie\ -- Bernie Cosell Fantasy Farm Fibers mailto:bernie@fantasyfarm.com Pearisburg, VA --> Too many people, too few sheep <--
I'd always assumed that the scoring scheme was 1 point for choosing the worst, and N for choosing the best, and so on for intermediate ranks. Rich ---- Quoting Bernie Cosell <bernie@fantasyfarm.com>:
On 17 Jun 2014 at 17:31, Tom Rokicki wrote:
Well, clearly it's a suboptimal strategy in the following way.
I assume when you say "it" you mean the "standard assumed optimal strategy"?
If after seeing N-2 candidates, I still haven't seen one better than the K'th, I know I only have two left. If the next one is above the median seen so far, I'm probably certainly doing better to pick that one and pass on the last, than to wait for the last.
I can't quickly do the math to see if that has a better expected outcome than the 'standard strategy'....
... And of course a similar argument applies for N-3, and so on.
But if that's the case, then you have the old paradox of "I'm going to give you an exam next week and it'll be a surprise". But perhaps not. Is this what you were thinking:
"examine the first K candidates. Take the first candidate that is larger than the *median* of those first K" [rather than wait for one that's larger than any of the first K]. I haven't a clue if replacing "larger than any" with "larger than the median" makes for a better or worse strategy. Or if there's a combined strategy. [look at the first K. Then if you hit one larger among the next L, take it [obviously with K+L<N], but if not THEN you take the first one larger than the median of the ones you've seen so far.
This seems to confirm my unease that the usual "assumption" [examine K and take the next that beats any of the K] probably needs to be proven to be an optimal strategy before you go and solve for K.
/Bernie\
-- Bernie Cosell Fantasy Farm Fibers mailto:bernie@fantasyfarm.com Pearisburg, VA --> Too many people, too few sheep <--
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
That leads to a very different strategy, since the difference between best and second-best (say) is very small when N is large. So the optimal strategy in the "best is 1, others are 0" fails miserably here -- expectation n/e + (1 - 1/e) * n/2 = n(1/2 + 1/2e) = 0.6839...n, while you can get arbitrarily close to n with the strategy "only pick someone guaranteed to be in the top (say) 99%". Charles Greathouse Analyst/Programmer Case Western Reserve University On Tue, Jun 17, 2014 at 9:40 PM, <rcs@xmission.com> wrote:
I'd always assumed that the scoring scheme was 1 point for choosing the worst, and N for choosing the best, and so on for intermediate ranks.
Rich
----
Quoting Bernie Cosell <bernie@fantasyfarm.com>:
On 17 Jun 2014 at 17:31, Tom Rokicki wrote:
Well, clearly it's a suboptimal strategy in the following way.
I assume when you say "it" you mean the "standard assumed optimal strategy"?
If after seeing N-2 candidates, I still haven't seen one better
than the K'th, I know I only have two left. If the next one is above the median seen so far, I'm probably certainly doing better to pick that one and pass on the last, than to wait for the last.
I can't quickly do the math to see if that has a better expected outcome than the 'standard strategy'....
... And of course a similar argument applies for
N-3, and so on.
But if that's the case, then you have the old paradox of "I'm going to give you an exam next week and it'll be a surprise". But perhaps not. Is this what you were thinking:
"examine the first K candidates. Take the first candidate that is larger than the *median* of those first K" [rather than wait for one that's larger than any of the first K]. I haven't a clue if replacing "larger than any" with "larger than the median" makes for a better or worse strategy. Or if there's a combined strategy. [look at the first K. Then if you hit one larger among the next L, take it [obviously with K+L<N], but if not THEN you take the first one larger than the median of the ones you've seen so far.
This seems to confirm my unease that the usual "assumption" [examine K and take the next that beats any of the K] probably needs to be proven to be an optimal strategy before you go and solve for K.
/Bernie\
-- Bernie Cosell Fantasy Farm Fibers mailto:bernie@fantasyfarm.com Pearisburg, VA --> Too many people, too few sheep <--
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
On Tue, Jun 17, 2014 at 10:00 PM, Charles Greathouse <charles.greathouse@case.edu> wrote:
That leads to a very different strategy, since the difference between best and second-best (say) is very small when N is large. So the optimal strategy in the "best is 1, others are 0" fails miserably here -- expectation n/e + (1 - 1/e) * n/2 = n(1/2 + 1/2e) = 0.6839...n, while you can get arbitrarily close to n with the strategy "only pick someone guaranteed to be in the top (say) 99%".
I agree that the strategy that maximizes the expected rank of the choice is different from the strategy that maximizes the chance that this rank is 1. For example, if you're maximizing expected rank, and the next-to-last candidate has rank n-2 of the n-1 you've seen so far, it's clearly better to take that than the next one. But I don't understand your proof that there are strategies that make the expected rank arbitrarily close to n. Choosing the first candidate that's guaranteed to be in the top 99% seems wrong; how can you get an expected rank of n setting your sights so low? Did you mean guaranteed to be in the top 1%? I guess that works for n sufficiently large; the chance that you won't see anyone in the top 1% in that last 1% is vanishingly small when n is sufficiently large. But while this shows that the expected rank approaches n as n approaches infinity, it doesn't give the correct strategy for any finite n. What is the right strategy to maximize expected rank for a given n? Andy
On Tue, Jun 17, 2014 at 9:40 PM, <rcs@xmission.com> wrote:
I'd always assumed that the scoring scheme was 1 point for choosing the worst, and N for choosing the best, and so on for intermediate ranks.
Rich
----
Quoting Bernie Cosell <bernie@fantasyfarm.com>:
On 17 Jun 2014 at 17:31, Tom Rokicki wrote:
Well, clearly it's a suboptimal strategy in the following way.
I assume when you say "it" you mean the "standard assumed optimal strategy"?
If after seeing N-2 candidates, I still haven't seen one better
than the K'th, I know I only have two left. If the next one is above the median seen so far, I'm probably certainly doing better to pick that one and pass on the last, than to wait for the last.
I can't quickly do the math to see if that has a better expected outcome than the 'standard strategy'....
... And of course a similar argument applies for
N-3, and so on.
But if that's the case, then you have the old paradox of "I'm going to give you an exam next week and it'll be a surprise". But perhaps not. Is this what you were thinking:
"examine the first K candidates. Take the first candidate that is larger than the *median* of those first K" [rather than wait for one that's larger than any of the first K]. I haven't a clue if replacing "larger than any" with "larger than the median" makes for a better or worse strategy. Or if there's a combined strategy. [look at the first K. Then if you hit one larger among the next L, take it [obviously with K+L<N], but if not THEN you take the first one larger than the median of the ones you've seen so far.
This seems to confirm my unease that the usual "assumption" [examine K and take the next that beats any of the K] probably needs to be proven to be an optimal strategy before you go and solve for K.
/Bernie\
-- Bernie Cosell Fantasy Farm Fibers mailto:bernie@fantasyfarm.com Pearisburg, VA --> Too many people, too few sheep <--
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Andy.Latto@pobox.com
The version of this problem that I've heard is that there are N pieces of paper, each with a positive integer written on its face. They are lying face down on the table. You chose and discard them one at a time until you decide to keep the most recently one chosen. Your objective is to end up with the biggest number possible. Note that the range of numbers is not specified. Brent Meeker On 6/17/2014 8:33 PM, Andy Latto wrote:
On Tue, Jun 17, 2014 at 10:00 PM, Charles Greathouse <charles.greathouse@case.edu> wrote:
That leads to a very different strategy, since the difference between best and second-best (say) is very small when N is large. So the optimal strategy in the "best is 1, others are 0" fails miserably here -- expectation n/e + (1 - 1/e) * n/2 = n(1/2 + 1/2e) = 0.6839...n, while you can get arbitrarily close to n with the strategy "only pick someone guaranteed to be in the top (say) 99%". I agree that the strategy that maximizes the expected rank of the choice is different from the strategy that maximizes the chance that this rank is 1. For example, if you're maximizing expected rank, and the next-to-last candidate has rank n-2 of the n-1 you've seen so far, it's clearly better to take that than the next one.
But I don't understand your proof that there are strategies that make the expected rank arbitrarily close to n. Choosing the first candidate that's guaranteed to be in the top 99% seems wrong; how can you get an expected rank of n setting your sights so low? Did you mean guaranteed to be in the top 1%? I guess that works for n sufficiently large; the chance that you won't see anyone in the top 1% in that last 1% is vanishingly small when n is sufficiently large.
But while this shows that the expected rank approaches n as n approaches infinity, it doesn't give the correct strategy for any finite n. What is the right strategy to maximize expected rank for a given n?
Andy
On Tue, Jun 17, 2014 at 9:40 PM, <rcs@xmission.com> wrote:
I'd always assumed that the scoring scheme was 1 point for choosing the worst, and N for choosing the best, and so on for intermediate ranks.
Rich
----
Quoting Bernie Cosell <bernie@fantasyfarm.com>:
On 17 Jun 2014 at 17:31, Tom Rokicki wrote:
Well, clearly it's a suboptimal strategy in the following way. I assume when you say "it" you mean the "standard assumed optimal strategy"?
If after seeing N-2 candidates, I still haven't seen one better
than the K'th, I know I only have two left. If the next one is above the median seen so far, I'm probably certainly doing better to pick that one and pass on the last, than to wait for the last.
I can't quickly do the math to see if that has a better expected outcome than the 'standard strategy'....
... And of course a similar argument applies for
N-3, and so on.
But if that's the case, then you have the old paradox of "I'm going to give you an exam next week and it'll be a surprise". But perhaps not. Is this what you were thinking:
"examine the first K candidates. Take the first candidate that is larger than the *median* of those first K" [rather than wait for one that's larger than any of the first K]. I haven't a clue if replacing "larger than any" with "larger than the median" makes for a better or worse strategy. Or if there's a combined strategy. [look at the first K. Then if you hit one larger among the next L, take it [obviously with K+L<N], but if not THEN you take the first one larger than the median of the ones you've seen so far.
This seems to confirm my unease that the usual "assumption" [examine K and take the next that beats any of the K] probably needs to be proven to be an optimal strategy before you go and solve for K.
/Bernie\
-- Bernie Cosell Fantasy Farm Fibers mailto:bernie@fantasyfarm.com Pearisburg, VA --> Too many people, too few sheep <--
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
I don't think this is clear at all. Take an individual sport where little chance is involved, like tennis or pocket billiards: often there is one person dominating the number one spot for years on end. --Dan
. . . the difference between best and second-best (say) is very small when N is large.
I was talking about the secretary problem with valuations 1, 2, ..., N, not the problem of hiring an employee in real life. (I don't know why we'd discuss the latter on math-fun.) Charles Greathouse Analyst/Programmer Case Western Reserve University On Wed, Jun 18, 2014 at 9:40 AM, Dan Asimov <dasimov@earthlink.net> wrote:
I don't think this is clear at all. Take an individual sport where little chance is involved, like tennis or pocket billiards: often there is one person dominating the number one spot for years on end.
--Dan
. . . the difference between best and second-best (say) is very small when N is large.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
The question Dan Asimov raised (which I paraphrase as "How are outliers distributed?") strikes me as one that's well-suited to math-fun, in at least two ways: it's an interesting mathematical question, and it's an interesting question about mathematicians! Then again, raising questions about the distribution of achievement at the high end of the talent-spectrum in STEM fields is the kind of thing that college presidents get fired for. So if anyone chooses to follow up on the second issue I mention in this message, I hope we can keep the discussion thoughtful and civil. (Rich, feel free to pre-emptively shut down this topic if based on your experience you feel it's unlikely to lead to anything other than elevated cortisol levels.) Jim Propp On Wed, Jun 18, 2014 at 10:12 AM, Charles Greathouse < charles.greathouse@case.edu> wrote:
I was talking about the secretary problem with valuations 1, 2, ..., N, not the problem of hiring an employee in real life. (I don't know why we'd discuss the latter on math-fun.)
Charles Greathouse Analyst/Programmer Case Western Reserve University
On Wed, Jun 18, 2014 at 9:40 AM, Dan Asimov <dasimov@earthlink.net> wrote:
I don't think this is clear at all. Take an individual sport where little chance is involved, like tennis or pocket billiards: often there is one person dominating the number one spot for years on end.
--Dan
. . . the difference between best and second-best (say) is very small when N is large.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Why don't we just stick to the mathematics involved. Here's a bit: Let f: R -> [0,oo) be a smooth probability density, and let X_1,...,X_n be independent random variables with this density. Define F(x) := Prob(X_j <= x) = Integral{-oo,x} f(u) du. Define M_n := max{X_1,...,X_n}. Then, Prob(M_n <= x) = F(x)^n. Call this G(x). So, the probability density g_n(x) of M_n is g_n(x) = (d/dx) F(x)^n = n F(x)^(n-1) f(x). (If the X_j are standard normal, we have f(x) = exp(-x^2/2)/sqrt(2 pi).) So, the expected value of M_n is E(M_n) = n Integral_{-oo,oo} u F(u)^(n-1) f(x) A little graph of this as a function of n appears on the page: < http://applet-magic.com/samplemax3.htm >, about 3/4 of the way down the page. --Dan On Jun 18, 2014, at 8:01 AM, James Propp <jamespropp@gmail.com> wrote:
The question Dan Asimov raised (which I paraphrase as "How are outliers distributed?") strikes me as one that's well-suited to math-fun, in at least two ways: it's an interesting mathematical question, and it's an interesting question about mathematicians!
Then again, raising questions about the distribution of achievement at the high end of the talent-spectrum in STEM fields is the kind of thing that college presidents get fired for. So if anyone chooses to follow up on the second issue I mention in this message, I hope we can keep the discussion thoughtful and civil. (Rich, feel free to pre-emptively shut down this topic if based on your experience you feel it's unlikely to lead to anything other than elevated cortisol levels.)
Aaaaargh^n. I meant: ----- So, the expected value of M_n is E(M_n) = n Integral_{-oo,oo} u F(u)^(n-1) f(u) du ----- --Dan
Here are a couple of simple statistical questions that I don't know the answers to, that have bearing on what we would expect to see in the outliers of a distribution. Suppose we take n independent samples from a normal distribution (let's fix the distrubution as having mean 0 and variance 1). As n increases, what happens to the expected value of (largest sample - 2nd largest sample)? How sensitive is this answer to the normality of the distribution? What do we need to know about the distribution to conclude that as n increases, this difference will behave the way it does for a normal distribution? Andy On Wed, Jun 18, 2014 at 11:01 AM, James Propp <jamespropp@gmail.com> wrote:
The question Dan Asimov raised (which I paraphrase as "How are outliers distributed?") strikes me as one that's well-suited to math-fun, in at least two ways: it's an interesting mathematical question, and it's an interesting question about mathematicians!
Then again, raising questions about the distribution of achievement at the high end of the talent-spectrum in STEM fields is the kind of thing that college presidents get fired for. So if anyone chooses to follow up on the second issue I mention in this message, I hope we can keep the discussion thoughtful and civil. (Rich, feel free to pre-emptively shut down this topic if based on your experience you feel it's unlikely to lead to anything other than elevated cortisol levels.)
Jim Propp
On Wed, Jun 18, 2014 at 10:12 AM, Charles Greathouse < charles.greathouse@case.edu> wrote:
I was talking about the secretary problem with valuations 1, 2, ..., N, not the problem of hiring an employee in real life. (I don't know why we'd discuss the latter on math-fun.)
Charles Greathouse Analyst/Programmer Case Western Reserve University
On Wed, Jun 18, 2014 at 9:40 AM, Dan Asimov <dasimov@earthlink.net> wrote:
I don't think this is clear at all. Take an individual sport where little chance is involved, like tennis or pocket billiards: often there is one person dominating the number one spot for years on end.
--Dan
. . . the difference between best and second-best (say) is very small when N is large.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Andy.Latto@pobox.com
The usual payoff for the secretary problem is 1 if you choose the best candidate and 0 otherwise, in which case you should never select a candidate if you've seen a better one previously. From this the optimality of the general strategy follows directly. If you're using some other payoff scheme then it probably isn't optimal. For example if your payoff is 0 if you choose the worst candidate and 1 otherwise, you should select the first candidate who is better than the worst you've seen so far. Charles Greathouse Analyst/Programmer Case Western Reserve University On Tue, Jun 17, 2014 at 8:06 PM, Bernie Cosell <bernie@fantasyfarm.com> wrote:
I was just reading a PDF about the secretary problem and all of the analyses I've ever seen seems to start with the assumption that the optimal strategy will necessarily be of the form "examine the first K candidates and then take the first candidate better than any you've seen so far", and if you haven't picked any candidate before that you MUST pick the N'th. And the math goes from there to derive the usual N/e value for K.
What got me curious [and this has actually drifted in and out of my pondering for some time now] is whether there's a proof that includes proving that the *assumption* is correct, also. I could see a strategy, for example, where you examine K candidates and then take the *second* best [that is, wait until you get one better than K, and then take the one better than that second one]. There might be other strategies more subtle or something beyond my ken. I don't see how to prove the assumption: that that's the best *possible* selection strategy. ???
/Bernie\
-- Bernie Cosell Fantasy Farm Fibers mailto:bernie@fantasyfarm.com Pearisburg, VA --> Too many people, too few sheep <--
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
You never really have the "best", unless there are few candidates and one of them stands out. There are performance probability distributions. It would be tremendously helpful is someone with actual experience in hiring decisions could chime in with a real-world solution, rather than depending on mathematical theory of dubious value. -- Gene
________________________________ From: Charles Greathouse <charles.greathouse@case.edu> To: math-fun <math-fun@mailman.xmission.com> Sent: Tuesday, June 17, 2014 6:00 PM Subject: Re: [math-fun] secretary problem
The usual payoff for the secretary problem is 1 if you choose the best candidate and 0 otherwise, in which case you should never select a candidate if you've seen a better one previously. From this the optimality of the general strategy follows directly.
If you're using some other payoff scheme then it probably isn't optimal. For example if your payoff is 0 if you choose the worst candidate and 1 otherwise, you should select the first candidate who is better than the worst you've seen so far.
Charles Greathouse Analyst/Programmer Case Western Reserve University
On Tue, Jun 17, 2014 at 8:06 PM, Bernie Cosell <bernie@fantasyfarm.com> wrote:
I was just reading a PDF about the secretary problem and all of the analyses I've ever seen seems to start with the assumption that the optimal strategy will necessarily be of the form "examine the first K candidates and then take the first candidate better than any you've seen so far", and if you haven't picked any candidate before that you MUST pick the N'th. And the math goes from there to derive the usual N/e value for K.
What got me curious [and this has actually drifted in and out of my pondering for some time now] is whether there's a proof that includes proving that the *assumption* is correct, also. I could see a strategy, for example, where you examine K candidates and then take the *second* best [that is, wait until you get one better than K, and then take the one better than that second one]. There might be other strategies more subtle or something beyond my ken. I don't see how to prove the assumption: that that's the best *possible* selection strategy. ???
/Bernie\
-- Bernie Cosell Fantasy Farm Fibers mailto:bernie@fantasyfarm.com Pearisburg, VA --> Too many people, too few sheep <--
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
I thought we were discussing the secretary problem rather than real-world hiring. In the real world candidates are rarely accepted until everyone (or rather, all candidates deemed worth interviewing) has been interviewed. (There are many other differences, of course -- perception of candidates is more cardinal than ordinal, for one.) Charles Greathouse Analyst/Programmer Case Western Reserve University On Tue, Jun 17, 2014 at 10:04 PM, Eugene Salamin via math-fun < math-fun@mailman.xmission.com> wrote:
You never really have the "best", unless there are few candidates and one of them stands out. There are performance probability distributions. It would be tremendously helpful is someone with actual experience in hiring decisions could chime in with a real-world solution, rather than depending on mathematical theory of dubious value.
-- Gene
________________________________ From: Charles Greathouse <charles.greathouse@case.edu> To: math-fun <math-fun@mailman.xmission.com> Sent: Tuesday, June 17, 2014 6:00 PM Subject: Re: [math-fun] secretary problem
The usual payoff for the secretary problem is 1 if you choose the best candidate and 0 otherwise, in which case you should never select a candidate if you've seen a better one previously. From this the optimality of the general strategy follows directly.
If you're using some other payoff scheme then it probably isn't optimal. For example if your payoff is 0 if you choose the worst candidate and 1 otherwise, you should select the first candidate who is better than the worst you've seen so far.
Charles Greathouse Analyst/Programmer Case Western Reserve University
On Tue, Jun 17, 2014 at 8:06 PM, Bernie Cosell <bernie@fantasyfarm.com> wrote:
I was just reading a PDF about the secretary problem and all of the analyses I've ever seen seems to start with the assumption that the optimal strategy will necessarily be of the form "examine the first K candidates and then take the first candidate better than any you've seen so far", and if you haven't picked any candidate before that you MUST pick the N'th. And the math goes from there to derive the usual N/e value for K.
What got me curious [and this has actually drifted in and out of my pondering for some time now] is whether there's a proof that includes proving that the *assumption* is correct, also. I could see a strategy, for example, where you examine K candidates and then take the *second* best [that is, wait until you get one better than K, and then take the one better than that second one]. There might be other strategies more subtle or something beyond my ken. I don't see how to prove the assumption: that that's the best *possible* selection strategy. ???
/Bernie\
-- Bernie Cosell Fantasy Farm Fibers mailto:bernie@fantasyfarm.com Pearisburg, VA --> Too many people, too few sheep <--
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
On 6/17/2014 7:04 PM, Eugene Salamin via math-fun wrote:
You never really have the "best", unless there are few candidates and one of them stands out. There are performance probability distributions. It would be tremendously helpful is someone with actual experience in hiring decisions could chime in with a real-world solution, rather than depending on mathematical theory of dubious value.
I've hired about a half-dozen secretaries and here are some real-world criteria: 1. Never hire a secretary prettier than you wife (don't ask me how I know this). 2. Hire a secretary who has raised children - she'll be able to deal with anything. 3. Don't hire a secretary who is in the Marine reserves. Brent Meeker
Alright, I'll buy it --- why the "Marine reserves" ? WFL On 6/18/14, meekerdb <meekerdb@verizon.net> wrote:
On 6/17/2014 7:04 PM, Eugene Salamin via math-fun wrote:
You never really have the "best", unless there are few candidates and one of them stands out. There are performance probability distributions. It would be tremendously helpful is someone with actual experience in hiring decisions could chime in with a real-world solution, rather than depending on mathematical theory of dubious value.
I've hired about a half-dozen secretaries and here are some real-world criteria:
1. Never hire a secretary prettier than you wife (don't ask me how I know this).
2. Hire a secretary who has raised children - she'll be able to deal with anything.
3. Don't hire a secretary who is in the Marine reserves.
Brent Meeker
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
On 6/18/2014 4:03 AM, Fred Lunnon wrote:
Alright, I'll buy it --- why the "Marine reserves" ? WFL
Once she called up an engineer in my division and said, "Come to the office." Then he showed up at my door saying, "You wanted to see me?" I was puzzled. Then I hear the secretary saying, "No, Mr. Leach I wanted to see you about this paragraph I was typing, I think you should..." In general she thought that she was my deputy supervisor - sort of drill sergeant to my colonel. Brent
On Tue, 17 Jun 2014, meekerdb wrote:
I've hired about a half-dozen secretaries and here are some real-world criteria:
1. Never hire a secretary prettier than you wife (don't ask me how I know this).
2. Hire a secretary who has raised children - she'll be able to deal with anything.
3. Don't hire a secretary who is in the Marine reserves.
Anyone tempted to take this seriously should note that points 2 and 3 are probably illegal under US law. Even making conversation about stuff like this (marital status, military service, many others) in a job interview can get you sued. -- Tom Duff. Unable to display help.
Points 1 and 2 are both gender-stereotyping and heteronormative. In an attempt to get this less off-topic, there's a non-heteronormative matching algorithm (the `Blossom algorithm') which runs in polynomial time. -- Adam P. Goucher
Sent: Wednesday, June 18, 2014 at 5:43 PM From: "Tom Duff" <td@pixar.com> To: math-fun <math-fun@mailman.xmission.com> Subject: Re: [math-fun] secretary problem
On Tue, 17 Jun 2014, meekerdb wrote:
I've hired about a half-dozen secretaries and here are some real-world criteria:
1. Never hire a secretary prettier than you wife (don't ask me how I know this).
2. Hire a secretary who has raised children - she'll be able to deal with anything.
3. Don't hire a secretary who is in the Marine reserves.
Anyone tempted to take this seriously should note that points 2 and 3 are probably illegal under US law. Even making conversation about stuff like this (marital status, military service, many others) in a job interview can get you sued.
-- Tom Duff. Unable to display help.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Maybe that should read `Bossom' algorithm --- which as Sir Thomas Beecham allegedly remarked when introduced to a (woodwind?) player of that ilk, is "a funny sort of name --- neither one thing nor t'other" ? But I couldn't locate the quotation --- only another one involving a cricketer by the name of Bob Cunis, which I forbear to repeat ... WFL On 6/18/14, Adam P. Goucher <apgoucher@gmx.com> wrote:
Points 1 and 2 are both gender-stereotyping and heteronormative.
In an attempt to get this less off-topic, there's a non-heteronormative matching algorithm (the `Blossom algorithm') which runs in polynomial time.
-- Adam P. Goucher
Sent: Wednesday, June 18, 2014 at 5:43 PM From: "Tom Duff" <td@pixar.com> To: math-fun <math-fun@mailman.xmission.com> Subject: Re: [math-fun] secretary problem
On Tue, 17 Jun 2014, meekerdb wrote:
I've hired about a half-dozen secretaries and here are some real-world criteria:
1. Never hire a secretary prettier than you wife (don't ask me how I know this).
2. Hire a secretary who has raised children - she'll be able to deal with anything.
3. Don't hire a secretary who is in the Marine reserves.
Anyone tempted to take this seriously should note that points 2 and 3 are
probably illegal under US law. Even making conversation about stuff like this (marital status, military service, many others) in a job interview can get you sued.
-- Tom Duff. Unable to display help.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
On 6/18/2014 9:43 AM, Tom Duff wrote:
On Tue, 17 Jun 2014, meekerdb wrote:
I've hired about a half-dozen secretaries and here are some real-world criteria:
1. Never hire a secretary prettier than you wife (don't ask me how I know this).
2. Hire a secretary who has raised children - she'll be able to deal with anything.
3. Don't hire a secretary who is in the Marine reserves.
Anyone tempted to take this seriously should note that points 2 and 3 are probably illegal under US law. Even making conversation about stuff like this (marital status, military service, many others) in a job interview can get you sued.
I didn't say you should give those as reasons, or ever mention them. If you do that you're probably too dumb to have a secretary. But of course you're right that they are somewhat tongue-in-cheek. Brent
* Eugene Salamin via math-fun <math-fun@mailman.xmission.com> [Jun 18. 2014 13:57]:
You never really have the "best", unless there are few candidates and one of them stands out. There are performance probability distributions. It would be tremendously helpful is someone with actual experience in hiring decisions could chime in with a real-world solution, rather than depending on mathematical theory of dubious value.
All I can say is that the models we have discussed here are next to useless in practice. There are situations where you'll hire the first person that is capable of doing the job (vacancy needs urgently be filled). On the other side you may spend well over a year (and serious cash) until you decide (lifetime position as a professor, will be your colleague indefinitely). Yet another aspect left out: person may decline job offer. This tends to be more likely with good people. And there is the sympathy/chemistry factor that is very often underestimated by both parties. Best, jj
 -- Gene
[...]
participants (13)
-
Adam P. Goucher -
Andy Latto -
Bernie Cosell -
Charles Greathouse -
Dan Asimov -
Eugene Salamin -
Fred Lunnon -
James Propp -
Joerg Arndt -
meekerdb -
rcs＠xmission.com -
Tom Duff -
Tom Rokicki