3 ms·

It doesn't implement the algorithm but not for the reasons you described. The fundamental issue that this algorithm solves is whether to keep waiting for someth

It doesn't implement the algorithm but not for the reasons you described. The fundamental issue that this algorithm solves is whether to keep waiting for something better to pop up or accept what you have now. The fundamental constraint is maximum number of trials you are willing to do. So, if you are looking for rental apartment, you might say that you may keep looking for each day for N days. On day 12 when you find the best apartment you have seen so far, the question is if you should commit to it or keep waiting for better in coming days. One of the conclusion of Secretory Problem is that you should not commit to anything until sqrt(N) and then you should pick the one that is the best you have seen so far. This maximizes the goodness of the apartment you might select. If you want to select the best possible apartment then reject first 37% (also called 1/e rule) then select the best you seen so far. This maximizes the probability that you will select the best of the best out of N but this probability is only 37%. The problem with this approach is that there is much higher chance that it wouldn't beat the quality from square root approach.

pcthrowaway 4y ago
What happens if the best apartment you could have looked at was the first one, which you rejected because you hadn't seen enough by that point. Following the above heuristic, isn't there a chance you never look at another apartment that would be "better than the others you've looked at" once you enter the decision window, and therefore keep looking until you reach N and have to take the last option? (the implications for dating should be obvious here, with it being fairly common for young lovers to break up so they can "see what's out there", and not uncommon for people to reach an age where they feel the need to settle for "what they can get" at that point)
- deleted 4y ago
  [deleted]
- deleted 4y ago
  [deleted]
- eru 4y ago
  > Following the above heuristic, isn't there a chance you never look at another apartment that would be "better than the others you've looked at" once you enter the decision window, and therefore keep looking until you reach N and have to take the last option? Yes, obviously. As Wikipedia says: > The probability of selecting the best applicant in the classical secretary problem converges toward 1/e ~ 0.368. The classic solution to the classic secretary problem works in less than 37% of cases. But in reality, you tend to know a bit about the distribution beforehand, and you are also interested in getting eg the second best secretary (if the best is no longer available), instead of just going for best-or-bust.
kevinpet 4y ago
This isn't the way house hunting works in most markets today (well, at least up until a few months ago). You need to consider each property as it comes up and decide whether to make an offer or not. Either you use broad filter criteria and you look at a few houses before you say "this is a better option than what we've seen, let's make an offer". In which case you can ignore the filter for purposes of fitting the house search to the secretary problem. Or like the parent post, you think you can express what you're looking for exactly through facts that appear in the ads, in which case you look at a few houses, then you buy the first house to appear that exceeds best of what you've seen. What you do not have in most markets is the option to go back and buy a house you looked at two weeks ago. Houses that sit on the market aren't houses that are appealing to buyers who intend to live in them.

pcthrowaway 4y ago

What happens if the best apartment you could have looked at was the first one, which you rejected because you hadn't seen enough by that point. Following the above heuristic, isn't there a chance you never look at another apartment that would be "better than the others you've looked at" once you enter the decision window, and therefore keep looking until you reach N and have to take the last option? (the implications for dating should be obvious here, with it being fairly common for young lovers to break up so they can "see what's out there", and not uncommon for people to reach an age where they feel the need to settle for "what they can get" at that point)

deleted 4y ago
[deleted]
deleted 4y ago
[deleted]
eru 4y ago
> Following the above heuristic, isn't there a chance you never look at another apartment that would be "better than the others you've looked at" once you enter the decision window, and therefore keep looking until you reach N and have to take the last option? Yes, obviously. As Wikipedia says: > The probability of selecting the best applicant in the classical secretary problem converges toward 1/e ~ 0.368. The classic solution to the classic secretary problem works in less than 37% of cases. But in reality, you tend to know a bit about the distribution beforehand, and you are also interested in getting eg the second best secretary (if the best is no longer available), instead of just going for best-or-bust.

kevinpet 4y ago

This isn't the way house hunting works in most markets today (well, at least up until a few months ago). You need to consider each property as it comes up and decide whether to make an offer or not. Either you use broad filter criteria and you look at a few houses before you say "this is a better option than what we've seen, let's make an offer". In which case you can ignore the filter for purposes of fitting the house search to the secretary problem. Or like the parent post, you think you can express what you're looking for exactly through facts that appear in the ads, in which case you look at a few houses, then you buy the first house to appear that exceeds best of what you've seen. What you do not have in most markets is the option to go back and buy a house you looked at two weeks ago. Houses that sit on the market aren't houses that are appealing to buyers who intend to live in them.