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