Hacker News Reader

Comment by buro9 | Hacker News Reader

I 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.

View on HN

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.

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.

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)

> 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.

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.

The key part of the Secretary Problem is that you know the number of applicants, and use this to determine how many candidates to examine (1/e of the total under the optimal policy) to determine the selection threshold.

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.

1. You don’t know how many candidates there so you couldn’t apply the criteria.

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.

One of the criteria is a finite, pre-known number of options. In this scenario, you're never forced to buy a house simply because it's the last one and if you don't buy it there's never going to be more houses available.

Set some timeframe you'd like to buy a house in, x months. For small enough x, you can choose some constant rate of houses coming on to the market per month y. xy is your finite number of options.

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.

This is obviously artificial because after x months, you are not going to buy something much worse than previous things you've rejected just because it's the best remaining option, rather than wait one more month. But having to do that is the crux of the secretary problem.

OP has not understood the significant differences between this clearly defined mathematical problem and his own experiences, not sure why people are indulging him.

It's perhaps important for people to understand that this type of problem is not necessarily a problem of hiring secretaries but rather a mathematical problem presented in less abstract form that people can easier relate to and digest. There could be dozens of variations, one could involve being able to go back one decision point (change your mind on the previous candidate), one could be to use parallelism and multiple evaluators, one could be to not know the total number so you might have seen the last secretary ever, etc.

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.

Crucially, the optimal solution depends on the specific constraints. So you can’t just take a solution derived under one set of assumptions and use it in another situation without losing whatever guarantees it made in the original case.

The engineer is happy because they know to bend forward and reach with their arms.

You raise a good assumption I think is being missed - the choice criteria has not changed between the time of interviewing the first applicant and selecting the n/e-th applicant. The housing market is too volatile for this assumption to hold.

Finite yes... As otherwise you wouldn't have a stopping problem as you could preselect from all options. What I didn't know is how good each option was, whether to wait for better or not.

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.

If fewer than 8 places would meet your criteria from among the current inventory plus what comes onto the market in the next 6 months, then you may have used the algorithm.

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.

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.

So you won!

> 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.

People in this thread also seem to not be aware that the evaluation period can be measured in time as well (as long as the candidates come in uniformly at random, which depending on the time of year, doesn't often happen with houses).

> 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)

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?

It would be somewhat reliable, although - depending on proximity - perhaps not that different from simply drawing a sector around south-west London: https://www.google.com/maps/search/waitrose/@51.505609,-0.33... .

The rub is that this area is not well-connected to the tube, at least for another 10-15 years.

There's a single Waitrose south of the river. Huh.

EDIT: Okay, 2. Missed the one in Greenwich. Still huh.

Most old council estates are privately owned now. Many newer ones are also being sold as shared ownership.

I can't speak for Waitrose specifically, but luxury brands will definitely do a comprehensive analysis of the surrounding area before opening a store. In the US at least, the equivalent is looking for the closest Starbucks or Apple store.

”Put the papaya down, Orlando!”

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.

I live in Scotland. The seller has to provide a "home report" which contains this information. It's fantastic!

We nearly had them in England. :(

https://www.theguardian.com/money/2010/may/20/home-informati...

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.

does rightmove allow filtering by price/sq foot?

Reply on news.ycombinator.com