The house my wife and I live in was recently sold, and so we have started looking for another apartment. Our current lease expires in a year and a half, and so we decided that, given how challenging the rental market is in NYC, that we should start looking right away. We also decided, somewhat arbitrarily, that we would attempt to find an apartment in the next six months, if only because we knew we would get sick of looking pretty quickly.
During the first 5 weeks of our apartment hunt, we found five apartments that we thought were worth looking at. Over six months, I extrapolated that we would get to see about 26 apartments that would satisfy our requirements. What we discovered, with each apartment, is that we basically got to see the apartment and then pretty much decide immediately if we wanted to apply to rent the apartment or not.
It turns out that there is a nifty mathematical algorithm that one can use to optimize one’s chances at picking the best apartment possible. We expect to have 26 apartments to look at, each of which we inspect and then either accept or reject immediately, and we want to optimize our chances of picking the best apartment possible, from the 26 that meet our minimum criteria. This exactly matches a solved problem in mathematics; the Secretary Problem.
In the Secretary Problem, where one has to decide on the best applicant between n randomly ordered applications, an optimal solution is to reject the first n/e applicants, and then accept the next applicant that is better than any applicant you have seen before. The proof of this particular solution is here. I couldn’t reproduce this proof if asked, and there are details in it which are fuzzy for me, but I am pretty sure I understand why it works. Informally, the first n/e applicants act as a sampling space, and this gives you information on how good applicants will be, and that n/e happens to be where you achieve an optimal amount of information on applicant strength, allowing you to make the best determination you can of which next applicant to choose, without raising the probability too high that you’ve already rejected the best applicant.
For our specific apartment hunting problem, with 26 total apartments to view, 26/e (e ≈ 2.71828) ≈ 9.6 ≈ 10 apartments. So, my wife and I looked at 10 different apartments, and while we did this, I informally ranked the apartments based on the criteria my wife and I agreed were important to think about (space, apartment lay-out, cost, location, quality of neighbourhood school, commute time). The 11th apartment either she or I looked was superior in many ways on all of these criteria than any of the others we had looked at, so I whole-heartedly threw in my support for it, knowing that this specific apartment is most likely to be the best apartment we will see.
We’ve submitted an (overly lengthy) application for the apartment. Wish us luck.
Sparr says:
Your choice of the 1/e cutoff gives you the highest probability of selecting the best apartment, but also a significant probability of getting stuck with the last apartment which will be of effectively random quality.
You should have used a sqrt(n) cutoff to maximize your expected apartment quality: https://en.wikipedia.org/wiki/Secretary_problem#Cardinal_payoff_variant
February 28, 2014 — 4:21 pm
David Wees says:
Interestingly enough, in this case, I would have ended up with an apartment that would not be as good as the one I have, since we saw two apartments in the last five that I would have ranked overall #2 and #3 respectively. You are right though, I would much rather choose a better apartment than a worse one, and would not like to get stuck with a horrible one because we ran out of time.
On the other hand, my choice of 26 apartments is probably somewhat arbitrary since we actually have a year and a half to find our apartment and are merely limiting our search time for practical reasons. Maybe n in this case is really more like 80, in which case my choice of stopping value is better, if still not optimal according to this other variant.
February 28, 2014 — 6:50 pm
Brent Williams says:
Very interesting stuff! But can you explain something to me? Essentially, the 10 apartments represented a sample size large enough to get a range of best and worst apartments that will be possible. So taking the next available apartment that is above that range is ideal, and the chances of going above that are minimal. I get that, assuming I didn’t misinterpret it. But what I don’t understand is why the 11th happened to be that one that was superior. Why wouldn’t have been simply the next apartment better than all the 10, which could have been any of the next 16 apartments? I guess I don’t understand how the 11th won out, unless it just happened to be better than the previous 10…
February 28, 2014 — 4:32 pm
David Wees says:
You’re right, I could have chosen any of the remaining 16 apartments, but as it turned out, the 1st of those 16 apartments ended up being superior to any we had seen before, and so, following the original variant of the algorithm, I stopped looking. Note at this point, I still had to convince my wife we had made the right choice, but given we had seen 10 apartments already, this wasn’t that hard to do.
February 28, 2014 — 6:43 pm
Tibs says:
Hi David. There seems to be a typo here. The S.P. has you reject the first n/e applications, and then accept the next one to be superior to all the previous applications, not any.
March 2, 2014 — 1:47 pm
David Wees says:
Doesn’t “any of the other previous candidates” = all?
March 2, 2014 — 2:09 pm
Tibs says:
I thought about it and the confusion comes in the ambiguity of the word “any.”
You mean: “there isn’t any previously-reviewed candidate who is better.”
I read: “the candidate is better than any one of the already-reviewed candidates.” (So this new candidate could be second-worst of them all.)
March 2, 2014 — 11:08 pm