The Secretary Problem
en.wikipedia.org
en.wikipedia.org
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.
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)
The rub is that this area is not well-connected to the tube, at least for another 10-15 years.
EDIT: Okay, 2. Missed the one in Greenwich. Still huh.
Unsure what part doesn't meet the criteria, I consciously used that approach to make the decision.
n is finite as time provides the limit to n. We were looking to move within 6 months (this was a hard requirement based on personal circumstances) and I'd already established the number of likely options according to the rate they appeared on the market.
In all of the part of greater London you considered, 7 or fewer possibilities seems quite low, but I don’t know how tight your criteria were in practice relative to that market. If your criteria were that tight, I congratulate you on securing 1 of the 7 suitable properties.
The question then becomes: how much do the simplifications made affect the outcome of applying what we know about the secretaries problem to the real world situation? Someone could probably write a neat article about it.
OP has not understood the significant differences between this clearly defined mathematical problem and his own experiences, not sure why people are indulging him.
Most real life problems will never perfectly match to this kind of math problem simply because real life usually offers more flexibility than a strictly defined mathematical scenario.
Reminds me of the joke with the mathematician and the engineer who can take as many steps as they want to get to the pot of gold in front of them with the condition that every step is maximum half of the distance remaining. The mathematician is absolutely livid because he knows he'll never reach it, while the engineer is happy because he'll be there for all practical purposes.
Instead, it sounds like you arbitrarily decided to use 2 examples to pick a selection threshold for the "price to square foot" at which you'd accept a property.
2. You established a threshold of acceptability and took a candidate that met that threshold rather than saying, after X properties, I’ll take the next property that’s better than the best so far.
Your approach is much closer to the standard method of buying a house - you have constraints, needs, and wants, and buy a house that fits those.
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)
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.
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.
https://www.theguardian.com/money/2010/may/20/home-informati...
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.
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.
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,...
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.
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.
Plus, for the dating especially, there's a lot of "je ne sais quoi" which requires sampling and can not be polled from the population at large.
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.
If your rule of thumb says that you should only start bidding after a third of the auctions are finished, I hope you see that there's a pretty obvious way for others to arbitrage against you.
Auction theory studies both optimal bids and optimal auction designs - imho it's one of the more useful areas of economics: https://en.wikipedia.org/wiki/Auction_theory
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.
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.
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.
Choosing one which you know not to be the best is not considered any better than choosing none.
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?
If you somehow still have to immediately hire or reject all candidates and care about expected average, instead of just finding the best candidate. The optimal solution will have you reject fewer candidates outright, and then have the criteria for how good a candidate should rank to get hired lower gradually throughout interviewing, and drop sharply towards the end of the candidate list.
So I guess that's a use.
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.
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.
“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.
This isn't 1950. Divorce (and even easier, separation) has been "on the table" for a long time. Yet the culture around dating and marriage today is miles away from decades ago.
You can tell yourself old couples hate each other, because of course some do. But people have been happily "making it work", across cultures, for centuries. It's about the expectations you have in a partner and what you want from the relationship. If that's made-for-TV-movie romance until eternity, good luck.
Edit: typo
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.
> The probability of selecting the best applicant in the classical secretary problem converges toward 0.368
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.
The only thing that this tells me is there is an underlying causal relationship. Otherwise, what is the alternative? That all events in reality are a complete throw of the dice and probability just makes sense of how things were pre-determined?
Another issue I have is (taking the problem at hand for example), the applicants are ordered randomly right? Thay discards a key piecie of information on their ordering (first applicants want it most or they are undesirable for example).
And when you randomize, that simply means you discarded the information about your new reordering. In reality, your arbitrary shuffling has a cause. If I asked you to pick a number at random, there is a reason why you arrived at that number and that reason or cause also has cause and so on, so nothing that is a product of cause can be truly random.
Last point for this post, what does the pool of candidates look like? keeping it simple, 3 people apply, since you shuffled them, the desparate first applicant is middle,the mediocre last applicant stays last and the talented person that applied a bit late is first. So you get bad or mediocre. Since you get to shuffle only once, this ordering I mentioned really has two groups which are desirable top talent person and undesirable mediocre or bad hires. So if your shuffling is truly random it is similar to a coin toss where probability is 50%. My point with this is, in reality not just in hiring but in many other things the vitality curve applies where you really only want the top 10/20%. It might work if your goal is "the best of the mediocre middle" but if your goal is binary "top 10%" vs "bad hire" the implication here is your sampling of the first person is the equivalent if a coin toss but the coin toss here was really your one chance shuffling of applicants. Does this make sense? The solution makes sense to me if maybe you kept reshuffling their order after each interview.
Ignoring ordering for example isn't a problem with stochastic modelling per se, but just with this specific model when applied in a specific context - you could of course use a different model to account for ordering as well. Similar for whether you want to optimize the expected average outcome or some other statistic like a given percentile. Those models exist already, don't blame the discipline for your lack of knowledge.
If you came to these conclusions on your own, I applaud your critical thinking. The next steps however would be to search the literature, realize these aren't new ideas but instead have been discussed and solved, and learn them.
I am sure technically they are but in a real hiring process if talent supply is low, you should probably go with the first guy that meets or exceeds your expectations.
Knowing where the darkest place in a room is seems unknowable for a simple robot.
So take a random walk for perhaps 3 minutes or so while recording the darkest light level. Then wander for another 7 minutes stopping if you record a lower light level during the initial wander.
Within 10 minutes I would like to think your robot will have done better than average at finding the darkest place in a room.
(Secretaries were historically male, but by the 1940s when the problem was devised, it had become a largely female profession. It became less about being a trusted adviser, and more about operating a typewriter.)
I suppose it makes a vague kind of sense that you don't get to call back a potential "applicant" for marriage. You get to evaluate one at a time, and if you reject them, you don't get a second chance.
I don't know why that shifted to "secretary". Maybe it seemed marginally less sexist?
As the article points out, it is also known as the Marriage Problem for similar reasons. The name "Googol Game" is where I first heard about it (and I believe it was Martin Gardner that presented it as such).
Almost matches the optimal chance for success rounded down.
It's often good to go for a "within 10% of best" solution.
But for smaller and more manageable N, I would assume you're better off with just ranking them all, and work out some decision threshold afterwards - when you have all the information at hand.
“If the decision can be deferred to the end, this can be solved by the simple maximum selection algorithm of tracking the running maximum (and who achieved it), and selecting the overall maximum at the end. The difficulty is that the decision must be made immediately.”
Different failure mode for this algorithm is when you get your candidates presented in the "worst to best" order - it makes you set your threshold low, and then settle for an average candidate.