Tell me more ×
Cross Validated is a question and answer site for statisticians, data analysts, data miners and data visualization experts. It's 100% free, no registration required.
up vote 4 down vote favorite

Despite the title, this is a more general and clearly solvable problem, I just can't research it because I have no idea what it's called.

Assume you are trying to buy something (such as a house) where there are many choices and gathering information about each choice is expensive enough to care about. Furthermore, assume that the process takes so long that you must decide whether to buy before you can evaluate the next house. Assume that you are capable of evaluating all the various dimensions each house can be rated on, and coming up with a single number that represents how good that house is for you (call it, HouseValue). Assume that you can express the cost of evaluating a house in terms of that HouseValue. Assume you don't know anything about the statistical distribution of the HouseValue number (I guess you would assume it's normal but you don't know the mean or the variance, but you are the experts and I'll take your word on this).

What is the formula for the optimal time to stop looking and buy the house you just evaluated? I'm pretty sure this is a well-known problem, or very close to a well known problem, but I don't know where to begin looking for it.

(I'm really guessing when I tag this, by the way).

share|improve this question

1 Answer

up vote 8 down vote accepted

I'm pretty sure this is the marriage problem. The idea is: You need to find a spouse. Researching information about a spouse is hard, and you can only look at one at a time. After some time spent looking (which we assume is constant), you can estimate a SpouseValue, which is how happy you would be married to this person. Then you must either marry the candidate, or move on and look for someone new.

The one difference between this and the problem you specify is that in the marriage problem, you have a predefined maximum number of candidates $n$ (after all, you'll have to settle eventually!). Probably this applies to your housing problem too (after all, you need to live somewhere!).

The optimal policy for making a decision under this condition is to first assess $\frac{n}{e}$ (that is $e$ the numeric constant) applicants at random, and accept none of them. Then keep interviewing. For each new candidate, determine if they are the best one seen so far. If they are, stop. This is your spouse (or house). Otherwise, keep going until you have to settle.

That's it. Keep in mind that the policy is optimal, but not guaranteed to pick the best candidate. You get the best one about a third of the time though, even for large $n$, so it's not half bad.

EDIT: Also, this assumes you care more about finding the best house than about the cost of looking...

share|improve this answer
I've even heard of the marriage problem, actually, but had forgotten. This is close, but doesn't help you choose n optimally (well, as stated an infinite value is optimal, I guess). It's still a helpful answer though, for sure. – psr Mar 14 '12 at 4:30
The Cardinal Payoff Variant mentioned in the Wikipedia article sited by this answer seems slightly more appropriate, but assumes payoffs are uniformly distributed, which seems odd to me. – psr Mar 14 '12 at 4:38
Also, the marriage problem assumes you can rank but not assign magnitude. It's not clear whether that's a better a model of purchasing decisions, but I had been assuming magnitude could be assigned, which I think is a significant difference. – psr Mar 14 '12 at 4:45
2  
If magnitude matters, than what you want is probably more like optimal stopping. en.wikipedia.org/wiki/Optimal_stopping. House selling is explicitly mentioned as an example application, and house buying amounts to the same problem (since advertising costs are assumed in the selling problem). – John Doucette Mar 14 '12 at 5:11
Yes, optimal stopping is exactly it. Hopefully I'll eventually update my question with links to an implementation. Thanks – psr Mar 15 '12 at 18:14
show 1 more comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.