I visited two places to establish criteria, then built a simple search across Greater London on Rightmove using area searches with proximity to Waitrose. The results I then filtered again based on price per square foot and rejecting certain keywords (aiming for a price per sq ft between £500-600 without needing renovation, but looking for no chain + quick sale).
As soon as a high quality and low price to square foot came up I put in an offer without having viewed it (I did view it once before completion).
I live there now... It's a gorgeous apartment purchased about 15% below market rate in a nice area.
Implementing a basic solution to the secretary / optimal stopping problem meant that with criteria that took out the vast majority of average places, I stopped on the first one and committed to it.
That doesn't implement the algorithm nor does it meet the problem because you were able to evaluate all options and not one at a time (whereas you would need to make a irreversible decision on the spot).
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.
Hot housing market with constant stream of options and where the good ones are barely on the market and require an instant decision and full commitment to a quick decision.
Unsure what part doesn't meet the criteria, I consciously used that approach to make the decision.
I'd say that's true of almost every real world example normally discussed. It is quite common for "buyers" to put multiple candidates on ice for as long they can possibly leverage to do so while they evaluate their options, be it in dating, hiring, or purchasing.
Think of the batch-search performed as „one secretary“. You either need to take what that search offered you, or you need to wait for the market to change enough in order to perform the next batch-search.
This is the same problem, but your algorithm was not n/e.
If there are 100 homes on the market, doesn't the optimal algorithm suggest
100/2.718 => 37 homes must be assessed
after which you commit hard to the first home that would be above all of those top 37?
I mean: you can't argue with the results. You underpaid and are delighted with your home! But you share the problem space without having implemented anything close to the ideal solution. In this case your intuition and sophistication resoundingly /trounced/ the ideal solution in terms of efficiency.
> If there are 100 homes on the market, doesn't the optimal algorithm suggest
It's not about the number of homes on the market, it's about how many homes you want to look at total (which is capped by the number of homes on the market). So, you say that you want to look at 10 homes max. You take 37% of either quantity as the evaluation period. After the evaluation period (3.7 houses) you commit to the first house that's better than the best you saw in the evaluation set.
Does that actually work? Just because well-off people shop in Waitrose, does that also mean that houses around Waitrose don't include old council estates?
How did you find/calculate the floor area from Rightmove? In my experience listings _might_ have the area in the floor plan image, so you’d be hoping for floor plans then running OCR to find the area? But I’d expect that to often go wrong or not find anything (missing or duplicate floor plans etc). Would love to know as it’s infuriating that the UK market is based on bedroom count rather than floor area.
Bedroom count is ridiculous, it's an estate agent's marketing game whether a room's a study or another bedroom.
Should just be #kitchens, #bathrooms, #loos, #other IMO. Number of fitted/room-like cupboards etc. would be a bit useful too, but size so variable it would only give a very rough idea.
You didn't implement anything like this, but congrats on finding a home you're happy with using a different algorithm.
You only saw 2 homes -- an arbitrary number not at all tied to how many homes might be on the market. You then instantly chose the first candidate you saw above some arbitrary threshold. I hope you can see this is nothing like the optimal stopping problem outlined in the article.
I did similarly over a few months trying to choose a new apartment to rent. I learned the area and all the types of places that might be available and when one came up that was ideal I jumped on it even though it was in a very low season for apartment availability.
It's a really cool result when you tell people about it, but actually when you think about it, it doesn't seem as useful as it sounds at first. The combination of some fundamental assumptions - you know the number of candidates in advance and you can't go back to previous candidates (*edit - should have added another one here: that you don't know anything about the distribution from which candidates are drawn before you begin) - don't really seem to match any of the purported applications, nor any I could think of quickly off the top of my head.
In reality, you're usually be able to gauge some estimates of the moments of the population distribution before you have to make any decision (which also aren't always final). Ie, you'll be interviewing a couple of candidates before you send out any rejections, you'll see several potential mates before you narrow in on one, you know from experience what a nice appartment looks like when you visit one,...
There are also other problems in other potential applications: a gig economy worker needs to not only optimize the value of the next gig but also the time spent searching for the next gig, when buying a used car the biggest problem is the information asymmetry regarding the true value of the car, not that it's gone if you don't buy right away,...
The even more broken assumption is that the only success factor is to get the single best result. That's not how real life works either: even if the best one got away, there will still be many other options close to it in quality, you'll be perfectly satisfied with any candidate in the top-five percentile or similar.
The traditional example of an application is dating to marry.
The number of 'applicants' isn't what matters, what matters is how many dates the subject can get in the amount of time they're willing to spend looking, this can be estimated reasonably well.
The part where you can't go back, well, it's more true than not.
I say it's the traditional example of an application, but I rather doubt people choose their spouses this way, nor that they should.
My point is that the model assumes that you're starting with zero knowledge about the population when you start dating, that's why you need the burn-in phase where you reject everyone to get a good estimate. In reality, I'd think you'd have a pretty decent prior for the population parameters before you even start dating.
You don't need to know number of candidates if you know the total amount of time (and assume candidates come in uniformly at random).
The most practical use case is selling a house.
There are also variations of the problem which model being able to go back to previously rejected candidates, as well as a probability that the candidate rejects you.
Right, selling a property might actually be a fairly good application of this model, I agree - you shouldn't leave a property listed for too long, and together with the feedback from your agent you should get a meaningful estimate of how many offers to expect in that period.
I'd be curious to see the agent's reaction when someone actually implements that and flat out rejects all the first offers.
It's a garbage premise entirely due to the fact that people - eg job applicants - can be so drastically different one to the next (whether amazing or horrible). The secretary problem fails to bake that in, because it can't handle it inherently (you have to actually interview people to know that). It doesn't actually work in reality.
There's no probability theory that is going to function properly so as to be very useful in such a context, because the best candidate in the world can just as easily show up on the tenth interview as the first or third. Your first three job applicants can be horrible, and the next three can be amazing.
People that buy into the false nature of the secretary problem / optimal stopping theory (that it's actually useful in reality), are falling for the premise that eg several roulette spins in the past directly impact the odds of the present spin. It's a bad premise to utilize for exactly the same reason: the quality of your last candidate doesn't have any strict relationship to the quality of your next candidate.
Optimal stopping theory is only useful for highly indecisive people that can't figure out what they want, so they fall back to handing off their decision-making to something else.
None of what you said is consistent with the derivation of the policy.
Note the policy is probabilistically optimal, not guaranteed to hire the best candidate every time. If you're hiring 1 person, sure you might end up SOL. But if you were hiring 100, this method would get you the best workforce.
Hmm, for auctions I think you really need to also the other agents into account (auction theory builds on game theory). The stopping-time model doesn't have strategic interactions.
Econtalk had a recent episode [0] that discusses this problem and the limitations when applied to real life. There's also a transcript [1] for those who prefer reading.
I found the discussion (and the entire episode) to be a nice reflection on how applying rules/logic/algorithms to big, deeply human problems doesn't always work. While the secretary problem is a fascinating and unintuitive mathematical result, as many other commenters have pointed out, it just doesn't have that many strict uses in people's real lives, outside of the general idea of "try a few of X to get the idea of the field, then pick one".
This was a great episode, I came here to post it but you beat me. Have ordered the book which is published a bit later in the UK but I'm looking forward to reading.
This is useful when you don't have a good prior for where to set your threshold. If you have a firm threshold, yes, you're right that it isn't all that useful.
The form of the solution also suggests a "good-enough" variant, useful when speed or simplicity is more important than optimality: reject the first option you find that genuinely meets all your needs. Accept the next thing you find that beats that first option. It is kind of surprising how often having this sort of approach in your back pocket can come in handy.
If you are threshold hunting, how do you set n? Or is n set based on resources. Would be interesting to see if there are n setting heuristics. Maybe based on how fast the best is getting better in a small sample?
Not really. The problem as described has two issues that makes it unlike most real problems:
1. The problem only deals with optimising finding the best candidate, the "optimal" solution therefore has a high probability of picking a really bad candidate. In reality this failure mode is quite unacceptable.
2. While many real problems will have some opportunity loss by waiting, it is quite extraordinary that options are presented in such a linear fashion. In a real hiring situation you'd generally be able to go back to a candidate you interviewed earlier and hire them.
This may seem somewhat contrived, but I tried to come up with some tech analogy.
Let's say that you have some analyzer which takes in a finite amount of physical matter, and then produces some dataset. The analysis is a destructive process, so that the analyzer will only be able to produce N different datasets - until it runs out of the physical matter it is analyzing.
The datasets are huge, and will take up all available memory. Before the next dataset is finished, you need to decide whether to store or delete/discard the current. The permanent storage can only hold one of these datasets, and it is impossible to write over it. Once you have stored a dataset permanently, the next ones will get discarded as soon as they've been generated.
Or something like that.
Edit: Wouldn't surprise me if there's some embedded system / machine out there that's bound to select stuff like that.
> 1. The problem only deals with optimising finding the best candidate, the "optimal" solution therefore has a high probability of picking a really bad candidate.
What's "really bad" here and what is the probability of picking a really bad candidate?
The example I first heard about this problem for was with portapotties. At what point do you stop looking through the line of open portapotties to find the cleanest one?
But that’s the best example of thresholds. You’re not going to ever find a perfectly clean one, you’ll obviously choose the first one that meets your standards.
It's useful if you don't know what $threshold is or if you want to get more "bang for your buck".
I believe there's a chapter in Freakonomics that deals with this problem and, if I'm not mistaken, talks about a situation where you might want to figure out some of the best places to eat in town without needing to visit all the places in town.
I've seen thousands of toilets in my life, my policy to finding a toilet in a music festival would be to choose the first one that's "good enough", no need to choose the best one.
In my point of view, this policy is more relevant if you have no prior knowledge about the subject you are evaluating. Even when choosing secretaries, how often it is that you want to find the absolute best one?
I love the secretary problem. For me the value is in illustrating the idea that there can be a good stopping place even with uncertainty. It's a great antidote to the grass-is-always-greener fallacy that can keep one on the indecision train for far too long.
I don't use any of the math, but my simple version is to look at a reasonable* number of options and then pick whatever next one comes up that is reasonably* high in the distribution.
I heard a talk by Esther Perel (recommend her TED talks, numerous interviews and podcast appearances) where she spoke about the differences in mindset when choosing a partner between 30-40 years ago and now.
“Before”, one would choose (or even be strongly recommended) a partner, commit, and make it work.
Now (culturally), one expects to find the absolutely perfect person/flavor and have everything worked out at the time of selection.
You can see how such an attitude would drastically limit the choices.
Another difference is that nowadays partnership is expected to include that person being the perfect lover, perfect co-parent, best friend, partner in crime, sometimes therapist etc. while in the past the expectation that the romantic partner would also be someone to entertain us or always understand us or share hobbies etc. was much much lower.
obviously not absolutes but more of a cultural slider which limits choices and puts more stress on relationships.
> “Before”, one would choose (or even be strongly recommended) a partner, commit, and make it work.
Because divorce was not on the table, so you had to "make it work", even if in the end was just a toxic relationship, where couple in their 60s or 70s plainly hated their spouse.
Humanity has 33 bits of entropy. So with 33 pieces of information about a person that don't depend on each other can very likely uniquely identify any person. Individually a person is likely to meet 10000 different people in their life, that's 14 bits of entropy if you start there.
Male/Female, College educated/not, looks, substance use, desire for children, compatible hobbies, compatible diets, compatible cultures, compatible monetary beliefs, compatible sexual preferences, my own level of attractiveness. Each hard preference has a corresponding reduction in dating pool size.
This is why the old dating app approach was so powerful — you’d answer dozens if not hundreds of questions, and rank them in relative importance to you as well as the relative importance and allowable values of your partner’s answers.
I immediately threw out anyone below 85-90%. My dating pool in a dense urban area over a period of months was tens of people. Once filtered for attractiveness and mutual interest, I was down to single digits. I married the first 99% I went on a date with.
Unfortunately (for others) I don’t know if that method is still available anywhere but the app I was using got acquired and reduced to swiping left and right.
> The probability of selecting the best applicant in the classical secretary problem converges toward 0.368
There are also some pretty big tradeoffs with this strategy. There seems to be a roughly 1/3 chance that you already rejected the best candidate. That's all good if not coming up with a result is acceptable and practically free of cost.
If the stakes are higher though, more conservative strategies might be in order. For example, you might want to sample a much smaller group than n/e first and make a decision based on their median, or even look at their standard deviation to get a reasonable sense about the value distribution - as in the real world values are seldomly distributed uniformly.
If there is a cost to coming up empty, you may also want to employ a hybrid solution, such as going with "1/e-law of best choice" until you hit the 70% mark and then accept the first candidate that is higher than a linear interpolation of the highest value and zero, lerped across the remaining percentage of samples.
Readit News
I visited two places to establish criteria, then built a simple search across Greater London on Rightmove using area searches with proximity to Waitrose. The results I then filtered again based on price per square foot and rejecting certain keywords (aiming for a price per sq ft between £500-600 without needing renovation, but looking for no chain + quick sale).
As soon as a high quality and low price to square foot came up I put in an offer without having viewed it (I did view it once before completion).
I live there now... It's a gorgeous apartment purchased about 15% below market rate in a nice area.
Implementing a basic solution to the secretary / optimal stopping problem meant that with criteria that took out the vast majority of average places, I stopped on the first one and committed to it.
Unsure what part doesn't meet the criteria, I consciously used that approach to make the decision.
If there are 100 homes on the market, doesn't the optimal algorithm suggest
100/2.718 => 37 homes must be assessed
after which you commit hard to the first home that would be above all of those top 37?
I mean: you can't argue with the results. You underpaid and are delighted with your home! But you share the problem space without having implemented anything close to the ideal solution. In this case your intuition and sophistication resoundingly /trounced/ the ideal solution in terms of efficiency.
So you won!
It's not about the number of homes on the market, it's about how many homes you want to look at total (which is capped by the number of homes on the market). So, you say that you want to look at 10 homes max. You take 37% of either quantity as the evaluation period. After the evaluation period (3.7 houses) you commit to the first house that's better than the best you saw in the evaluation set.
I guess this was a "sufficient affluence" indicator to filter out undesireable neighbourhoods?
(for readers who don't know: Waitrose is a British high-price-segment supermarket)
Should just be #kitchens, #bathrooms, #loos, #other IMO. Number of fitted/room-like cupboards etc. would be a bit useful too, but size so variable it would only give a very rough idea.
You only saw 2 homes -- an arbitrary number not at all tied to how many homes might be on the market. You then instantly chose the first candidate you saw above some arbitrary threshold. I hope you can see this is nothing like the optimal stopping problem outlined in the article.
In reality, you're usually be able to gauge some estimates of the moments of the population distribution before you have to make any decision (which also aren't always final). Ie, you'll be interviewing a couple of candidates before you send out any rejections, you'll see several potential mates before you narrow in on one, you know from experience what a nice appartment looks like when you visit one,...
There are also other problems in other potential applications: a gig economy worker needs to not only optimize the value of the next gig but also the time spent searching for the next gig, when buying a used car the biggest problem is the information asymmetry regarding the true value of the car, not that it's gone if you don't buy right away,...
The number of 'applicants' isn't what matters, what matters is how many dates the subject can get in the amount of time they're willing to spend looking, this can be estimated reasonably well.
The part where you can't go back, well, it's more true than not.
I say it's the traditional example of an application, but I rather doubt people choose their spouses this way, nor that they should.
The most practical use case is selling a house.
There are also variations of the problem which model being able to go back to previously rejected candidates, as well as a probability that the candidate rejects you.
I'd be curious to see the agent's reaction when someone actually implements that and flat out rejects all the first offers.
There's no probability theory that is going to function properly so as to be very useful in such a context, because the best candidate in the world can just as easily show up on the tenth interview as the first or third. Your first three job applicants can be horrible, and the next three can be amazing.
People that buy into the false nature of the secretary problem / optimal stopping theory (that it's actually useful in reality), are falling for the premise that eg several roulette spins in the past directly impact the odds of the present spin. It's a bad premise to utilize for exactly the same reason: the quality of your last candidate doesn't have any strict relationship to the quality of your next candidate.
Optimal stopping theory is only useful for highly indecisive people that can't figure out what they want, so they fall back to handing off their decision-making to something else.
I found the discussion (and the entire episode) to be a nice reflection on how applying rules/logic/algorithms to big, deeply human problems doesn't always work. While the secretary problem is a fascinating and unintuitive mathematical result, as many other commenters have pointed out, it just doesn't have that many strict uses in people's real lives, outside of the general idea of "try a few of X to get the idea of the field, then pick one".
[0] https://www.econtalk.org/russ-roberts-and-mike-munger-on-wil...
[1] https://www.econtalk.org/russ-roberts-and-mike-munger-on-wil...
Knowing Munger, I'll assume they talked about the heuristic's application in automated systems and it's prefect application there?
Also, dear HN reader, if you don't listen to EconTalk already, you're missing out on one the best podcasts out there.
You usually don’t actually need the best from an arbitrary sample, you need better than $threshold.
Aiming for best from sample when you have $threshold already could just result in opportunity cost.
Be it in hiring, dating, researching holiday destinations or anything.
The form of the solution also suggests a "good-enough" variant, useful when speed or simplicity is more important than optimality: reject the first option you find that genuinely meets all your needs. Accept the next thing you find that beats that first option. It is kind of surprising how often having this sort of approach in your back pocket can come in handy.
1. The problem only deals with optimising finding the best candidate, the "optimal" solution therefore has a high probability of picking a really bad candidate. In reality this failure mode is quite unacceptable.
2. While many real problems will have some opportunity loss by waiting, it is quite extraordinary that options are presented in such a linear fashion. In a real hiring situation you'd generally be able to go back to a candidate you interviewed earlier and hire them.
This may seem somewhat contrived, but I tried to come up with some tech analogy.
Let's say that you have some analyzer which takes in a finite amount of physical matter, and then produces some dataset. The analysis is a destructive process, so that the analyzer will only be able to produce N different datasets - until it runs out of the physical matter it is analyzing.
The datasets are huge, and will take up all available memory. Before the next dataset is finished, you need to decide whether to store or delete/discard the current. The permanent storage can only hold one of these datasets, and it is impossible to write over it. Once you have stored a dataset permanently, the next ones will get discarded as soon as they've been generated.
Or something like that.
Edit: Wouldn't surprise me if there's some embedded system / machine out there that's bound to select stuff like that.
What's "really bad" here and what is the probability of picking a really bad candidate?
So I guess that's a use.
I believe there's a chapter in Freakonomics that deals with this problem and, if I'm not mistaken, talks about a situation where you might want to figure out some of the best places to eat in town without needing to visit all the places in town.
In my point of view, this policy is more relevant if you have no prior knowledge about the subject you are evaluating. Even when choosing secretaries, how often it is that you want to find the absolute best one?
I don't use any of the math, but my simple version is to look at a reasonable* number of options and then pick whatever next one comes up that is reasonably* high in the distribution.
*A lot of gut feeling goes into this.
“Before”, one would choose (or even be strongly recommended) a partner, commit, and make it work.
Now (culturally), one expects to find the absolutely perfect person/flavor and have everything worked out at the time of selection.
You can see how such an attitude would drastically limit the choices.
Another difference is that nowadays partnership is expected to include that person being the perfect lover, perfect co-parent, best friend, partner in crime, sometimes therapist etc. while in the past the expectation that the romantic partner would also be someone to entertain us or always understand us or share hobbies etc. was much much lower.
obviously not absolutes but more of a cultural slider which limits choices and puts more stress on relationships.
Because divorce was not on the table, so you had to "make it work", even if in the end was just a toxic relationship, where couple in their 60s or 70s plainly hated their spouse.
What happens if the secretary you decide to hire is just using you to calibrate their search for what a good boss looks like?
Feels like there would be some interesting maths in that.
https://en.wikipedia.org/wiki/Stable_marriage_problem
Humanity has 33 bits of entropy. So with 33 pieces of information about a person that don't depend on each other can very likely uniquely identify any person. Individually a person is likely to meet 10000 different people in their life, that's 14 bits of entropy if you start there.
Male/Female, College educated/not, looks, substance use, desire for children, compatible hobbies, compatible diets, compatible cultures, compatible monetary beliefs, compatible sexual preferences, my own level of attractiveness. Each hard preference has a corresponding reduction in dating pool size.
Clearly I am also single.
I immediately threw out anyone below 85-90%. My dating pool in a dense urban area over a period of months was tens of people. Once filtered for attractiveness and mutual interest, I was down to single digits. I married the first 99% I went on a date with.
Unfortunately (for others) I don’t know if that method is still available anywhere but the app I was using got acquired and reduced to swiping left and right.
If the stakes are higher though, more conservative strategies might be in order. For example, you might want to sample a much smaller group than n/e first and make a decision based on their median, or even look at their standard deviation to get a reasonable sense about the value distribution - as in the real world values are seldomly distributed uniformly.
If there is a cost to coming up empty, you may also want to employ a hybrid solution, such as going with "1/e-law of best choice" until you hit the 70% mark and then accept the first candidate that is higher than a linear interpolation of the highest value and zero, lerped across the remaining percentage of samples.