11 ms·
The Secretary Problem
- nicolashahn 4y agoEntering my thirties still single, I think about this a lot. First read about it in Algorithms To Live By.
- moontear 4y agoSeems like you haven’t found the right secretary yet.
- hayst4ck 4y agoI've also thought about that. At first N seemed daunting, but then I added in a bit of the drake equation (https://en.wikipedia.org/wiki/Drake_equation https://en.wikipedia.org/wiki/Drake_equation) style thinking. 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.
- throwaway98797 4y agothis made me chuckle, i too think like this and yes im single
- svnt 4y agoThis 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.
- andrei_says_ 4y agoI 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.
- darkwater 4y ago> “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.
- fyhn 4y agoAnd like in all things, there is probably a better middle ground. Don't commit forever to a horrible partner, but also don't look for the "perfect person" with whom there will be no difficulties. Neither is good. Look for the "good enough" partner and really try to make it work.
- darkwater 4y agoAbsolutely. And don't be afraid to end a relationship that's not working, learn from it and be a wiser/better partner in your next one (if you are interested in having a relationship again).
- itsoktocry 4y ago
- ZeroGravitas 4y agoSeems like marraige (and to some degree the employment form) would complicate matters because both sides are looking for the optimum. 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.
- alcover 4y agoIt's seemingly solvable. https://en.wikipedia.org/wiki/Stable_marriage_problem https://en.wikipedia.org/wiki/Stable_marriage_problem
- aesthesia 4y agoInterestingly, the traditional algorithmic solution is inherently asymmetric: it gives better outcomes to one gender than the other.
- greenail 4y agoAre you basing this on math or history?
- qbit42 4y agoThis is a mathematical statement, see the end of the Wikipedia section "Algorithmic solution", where it states "Among all possible different stable matchings, it always yields the one that is best for all men among all stable matchings, and worst for all women."
- quickthrower2 4y agoIt is this useful in real life? 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.
- exmadscientist 4y agoThis 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.
- quickthrower2 4y agoIf 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?
- prennert 4y agon depends on your resource budget. Your resources might be limited by availability (how many secretary applicants are there), time (how long does each test take vs how much time can you invest), etc.
- quickthrower2 4y agoBut your budget might be flexible depending in what you get out of it. For example you have cashed up investors.
- 22c 4y ago
- buro9 4y agoI found a home to purchase by implementing this. 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.
- taurath 4y agoI 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.
- DocTomoe 4y ago> with proximity to Waitrose 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)
- implements 4y ago”Put the papaya down, Orlando!”
- Paul_S 4y agoDoes 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?
- n4r9 4y ago
- deleted 4y ago[deleted]
- Gatsky 4y agoHmm. So if you keep waiting for a better option, the chance of choosing the best one decreases after you've rejected 3.
- StevenWaterman 4y agoYou're reading the graph wrong - the X axis is the number of available options. More options = less likely to pick the top one
- 988747 4y agoNo, that's not how it works. There is a chance that one of the first 3 candidates is the best one, but as the total number of candidates increases the probability of that being the case decreases. 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.
- Pinus 4y agoApplied to the problem of picking a toilet at a music festival: https://www.youtube.com/watch?v=ZWib5olGbQ0 https://www.youtube.com/watch?v=ZWib5olGbQ0 .
- leoff 4y agoI'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?
- TrackerFF 4y agoIt seems to me that this would be a fair strategy (the immediate rejection or acceptance part, that is) if N is very large. 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.
- Jaxan 4y agoFrom the article: “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.”
- fyhn 4y agoGiven that you can compare all N against each other, and then select, which this assumes you cannot.
- labrador 4y agoCan I assume all things remain constant so, for example, the quality of applicants doesn't improve over time as they finish their year at the local college?
- divan 4y agoBeautifully told in https://algorithmstoliveby.com https://algorithmstoliveby.com
- JKCalhoun 4y agoI had considered, but not tried, using this algorithm for a dark-seeking robot (perhaps a pedigree of the Braitenberg or BEAM style robots). 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.
- syntaxing 4y agoIsn’t this a typical maze problem for a robot but the cost function is optimized for reward for darker spots? If that’s the case wouldn’t a-star hybrid or particle filters solve your problem?
- JKCalhoun 4y agoMaybe. I'll have to look into the algorithms you mentioned. To me there was a Secretary Problem use-case because we don't know what the light amplitude range is - we don't know what "dark" is (and will vary at different times of the day, vary by room, etc.). Also it's simple enough that you can imagine even a cellular-size organism implementing something like it.
- _8j50 4y agoYou know what I can't accept about statistical probability? While it does indeed acurately measure past events, to accept it you also have to accept that outcomes are not random but somehow implementing causal events a certail way like in the solution to this problem will result in more likelihood of desired results. 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.
- t_mann 4y agoYou may want to check out https://en.wikipedia.org/wiki/Causal_inference https://en.wikipedia.org/wiki/Causal_inference - the issues that you point out are all well understood and being addressed as well as possible within the limitations of our current knowledge of statistics, the logical fundamentals and the available data. 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.
- theginger 4y agoThat article doesn't seem to explain why it is called the Secretary problem. Was it just because someone choose to illustrate it with a hiring a secretary example, or was there some peculiar reason this is or was the practice when it came to hiring a secretary?
- ape4 4y agoMaybe because secretaries are "rankable" (a term used in the article). Perhaps by words-per-minute typing speed.
- jfengel 4y agoThe answer appears to be "sexism". The problem has a number of names, all of which seem to revolve around men choosing women. The original name is "fiancée problem". (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?
- ChadNauseam 4y agoI've always heard it called the marriage problem or the secretary problem, both of which are gender neutral.
- JKCalhoun 4y agoWhen you review candidates for a position you cannot know if a better one has yet to apply nor (it is assumed) can you go back to a previous candidate (the assumption I suppose is that they now have a job). 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).
- Udo 4y ago> 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.
- pythko 4y agoEcontalk 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". [0] https://www.econtalk.org/russ-roberts-and-mike-munger-on-wild-problems/ https://www.econtalk.org/russ-roberts-and-mike-munger-on-wil... [1] https://www.econtalk.org/russ-roberts-and-mike-munger-on-wild-problems/#audio-highlights https://www.econtalk.org/russ-roberts-and-mike-munger-on-wil...
- Balgair 4y agoI'll sheepishly admit I'm so low on time that I can't listen to Econtalk as much as I'd like these days. 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.
- shaftoe444 4y agoThis 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.
- nurettin 4y agoInteresting that we have this Turkish proverb: Allah'ın hakkı üçtür - Translation: God gives (ordains) three chances. Almost matches the optimal chance for success rounded down.
- t_mann 4y agoIt'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,...
- adventured 4y agoIt'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.
- rererr 4y agoI 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. *A lot of gut feeling goes into this.
- BeFlatXIII 4y ago1-1/e is one of my favorite numbers. Not only is it the fraction of candidates rejected by the Secretary Problem, but it's also the probability of a one in N chance event occurring in at least one of N trials.
- anamax 4y agoThe secretary problem (max odds of best) isn't the only problem in that space. It's often good to go for a "within 10% of best" solution.