3 ms·

It's not about optimal matches at all - it's about when to stop looking. The assumption is you don't known the set of potential matches, or the order they come

It's not about optimal matches at all - it's about when to stop looking. The assumption is you don't known the set of potential matches, or the order they come in, or anything really. But there is a deadline for the decision (or a maximum number of attempts). So how to balance making attempts to gather information with committing to a final decision so you don't run out of time? All else being equal, the rule is 1/e. Spend the first 37% of your time/attempts gathering information, then commit to the next option that's better than you've seen. This doesn't guarantee a good match (or even a match!) but probabilistically the strategy is optimal.

fierro 4y ago
exactly. The optimal stopping solution maximizes the probability you find the best candidate. That probability ends up being quite low, unfortunately.
maxminminmax 4y ago
>but probabilistically the strategy is optimal. For what value function? It is basically never the case that my value function is "all choices other than the optimal are equally bad" -- which is what this rule is based on. As a personal opinion, this drives me up the wall. There is a great problem here, and there is a whole area (several of them, actually!) of applied math dedicated to it (Statistical Decision Theory, Reinforcement Learning, you name it). Instead we get this toy version -- which at best is an oversimplified intro to he subject, and at worst an excuse to bamboozle with math-fairy-dust -- brought out as some kind of rule "to live by". Your algorithm is bad, and you should feel bad.
- taeric 4y ago
  I'm confused, isn't this literally one of the founding problems to "Statistical Decision Theory"? That is, this may be a simplified version of the problem, but it is a legit problem from that field. And the results being presented here don't disagree with the legit problem, do they? Now, is it a simplification of a simplification? Sure. I'm not clear on why it is as bad as you are putting forth, though.
  - robrenaud 4y ago
    People discuss it as though it has basically any real life applicability, but the assumptions are violated by basically every important real life decision ever. Don't get me wrong, I love algorithms, CS and math and very much liked learning the secretary problem and solution. I just wouldn't think of it as practically useful.
    - taeric 4y ago
      I'm guessing you see/hear this discussed way more than I do, then. :D

fierro 4y ago

exactly. The optimal stopping solution maximizes the probability you find the best candidate. That probability ends up being quite low, unfortunately.

maxminminmax 4y ago

>but probabilistically the strategy is optimal. For what value function? It is basically never the case that my value function is "all choices other than the optimal are equally bad" -- which is what this rule is based on. As a personal opinion, this drives me up the wall. There is a great problem here, and there is a whole area (several of them, actually!) of applied math dedicated to it (Statistical Decision Theory, Reinforcement Learning, you name it). Instead we get this toy version -- which at best is an oversimplified intro to he subject, and at worst an excuse to bamboozle with math-fairy-dust -- brought out as some kind of rule "to live by". Your algorithm is bad, and you should feel bad.

taeric 4y ago
I'm confused, isn't this literally one of the founding problems to "Statistical Decision Theory"? That is, this may be a simplified version of the problem, but it is a legit problem from that field. And the results being presented here don't disagree with the legit problem, do they? Now, is it a simplification of a simplification? Sure. I'm not clear on why it is as bad as you are putting forth, though.
- robrenaud 4y ago
  People discuss it as though it has basically any real life applicability, but the assumptions are violated by basically every important real life decision ever. Don't get me wrong, I love algorithms, CS and math and very much liked learning the secretary problem and solution. I just wouldn't think of it as practically useful.
  - taeric 4y ago
    I'm guessing you see/hear this discussed way more than I do, then. :D