How to search for a flat (mathematically)

I'm looking for a flat in Zurich. The market here is tight: good flats get snapped up within hours and if you want a place you need to decide almost on the spot. Therefore, a rigorous approach to flat searching is very important to maximize your chances of finding the best possible flat.

Let's assume I can visit one flat per day, giving me maybe 100 viewings over three months before my lease ends. For the sake of simplicity, let's also (wrongly) assume that everything in Zurich costs the same amount. How can I maximize my chances of getting the best flat?

This is a classic problem in optimal stopping theory. The short answer is: reject the first 37% of flats to calibrate what "good" looks like, then take the first flat that beats everything you've seen. This gives a 37% chance of finding the absolute best flat.

The problem

I have \(n\) flats to view (say \(n = 100\)). Each has some quality ranking from 1 to \(n\), where \(n\) is the best. The flats show up in random order. After viewing flat \(i\), I can compare it to all previous flats, but I don't know how it ranks among the ones I haven't yet seen.

As previously stated, at each viewing I have to decide immediately either to take this flat or to reject it forever. My goal is to maximize the probability of getting the best flat.

The optimal strategy

The optimal strategy has an intuitive form: reject the first \(r\) flats (in the so-called observation phase), then select the first flat which is better than all previously seen. The question is: what \(r\) maximizes success probability?

If the best flat is at position \(k\), I select it only if the best among the first \(k-1\) flats is in the observation window (positions \(1, \ldots, r\)). This has probability \(\frac{r}{k-1}\). Summing over all possible positions of the best flat:

For large \(n\), let \(x = r/n\). The success probability becomes approximately \(-x \ln(x)\), which is maximized when \(x = 1/e \approx 0.368\).

Applying the strategy

For my situation with 100 viewings:

1. Observation phase (flats 1-37): View 37 flats but reject all of them. Use this to understand the state of the market.
2. Selection phase (flats 38-100): Take the first flat that beats everything from the observation phase.

A 37% success rate might seem quite low, but the alternatives are way worse:

• Choosing randomly: \(1/100 = 1\%\) of chance of success
• Always taking the current best: you'll almost certainly settle for one of the first few flats, which is unlikely to be the best

Simulation

Let's verify this with a Monte Carlo simulation.

Why it works

The strategy balances two concerns:

• Information: If \(r\) is too small, I don't know what "good" looks like and might accept a mediocre flat.
• Options: If \(r\) is too large, I might reject the best flat during observation.

The value \(r = n/e\) is the optimal balance. The observation phase is long enough to calibrate expectations, while the selection phase is long enough to likely encounter something good.

Extension: two people with correlated preferences

What if I'm searching with a flatmate who has different tastes? Let's assume that we each rank the flats differently. How does the correlation between our preferences affect the strategy?

Setup

Person A and person B each rank the flats from 1 to \(n\). The key parameter is the correlation \(\rho\) between rankings:

• \(\rho = 1\): identical preferences
• \(\rho = 0\): independent preferences
• \(\rho = -1\): opposite preferences

I use the max-min criterion: maximize \(\min(\text{rank}_A, \text{rank}_B)\), ensuring that neither person gets stuck with a flat they hate. Other approaches are possible (e.g., maximizing the sum of utilities).

With correlation \(\rho\), the probability that both people rank the same flat as their top choice depends heavily on \(\rho\):

• \(\rho = 1\): probability \(= 1/n\) (same as single-person)
• \(\rho = 0\): probability \(\approx 1/n^2\) (both must independently pick it)

As correlation decreases, mutually acceptable flats become rarer. The optimal strategy shifts: we should be less picky (lower threshold) because waiting for perfection is unlikely to work.

Two-person simulation

Practical considerations

The assumptions made in this model are quite strong. In real life, several factors complicate the picture:

• Preferences aren't totally ordered (one flat has better light, another a better commute, etc.).
• Number of flats \(n\) isn't known in advance.
• The flats don't cost the same amount.

Despite these issues, the 37% rule is a useful heuristic: spend the first third of your search learning the market, then commit when you see something that beats everything so far.

Connection to the Secretary Problem

This scenario is mathematically identical to the classic "Secretary Problem" in optimal stopping theory, originally formulated for hiring decisions. The mathematics is exactly the same.

References

1. Ferguson, T. S. (1989). Who Solved the Secretary Problem? Statistical Science, 4(3), 282-289.
2. Gilbert, J. P., & Mosteller, F. (1966). Recognizing the Maximum of a Sequence. JASA, 61(313), 35-73.
3. Freeman, P. R. (1983). The Secretary Problem and its Extensions: A Review. International Statistical Review, 51(2), 189-206.