Offers arrive one per period, you may take one or wait, and waiting costs something and eventually runs out. The recursion is two lines and its answer has a shape: accept an offer exactly when it beats what carrying on is worth. That shape is almost always stated as though it were obvious. Here it is a measurement — every way of choosing which offers to accept in which period is enumerated and evaluated, and the winner is then tested for whether it is a threshold at all.
Core ideas
Three ideas: what the state is, why the threshold falls, and what it takes to prove the rule has the shape the recursion assumed.
Not which offers have been seen, not their average, not how long you have been looking. Offers are independent draws from a known distribution, so the past is uninformative about the future and the only thing that matters is how many chances remain. That is the whole modelling content of the problem, and it is the assumption to interrogate first: it fails the moment offers are correlated or the distribution has to be learned.
V(t) is what the whole remaining search is worth with t periods to go, and an offer should be taken exactly when it beats V(t−1) — what you would get by refusing. With fewer periods left there is less to wait for, so V is smaller and the bar is lower. In the final period the bar is zero: there is nothing to carry on to, so any offer at all is taken.
The recursion assumes it by construction: it compares each offer against one number. But a rule could in principle accept an offer of 20 and refuse one of 30, and nothing in the recursion rules that out — it simply never considers it. So the lab enumerates every accept-set in every period, evaluates each resulting rule exactly, and then asks whether the winner has the property that accepting an offer implies accepting every larger one.
The material
The definition, the table it produces, and the enumeration that turns an assumption into a result.
In each of T periods one offer arrives, drawn independently from a known distribution over values. You may accept it and stop, or refuse it and pay a search cost c to go on; a refused offer cannot be recalled. If you refuse the last one you get nothing.
Let V(t) be the expected value of the whole remaining search with t periods left, before the offer is seen. Then V(0) = 0 and V(t) = E[max(x, V(t−1))] − c. The optimal rule with t periods left is: accept x if and only if x > V(t−1).
The lab refuses a distribution whose probabilities do not sum to exactly 1, rather than renormalising it — the same discipline as the transition rows earlier on this course, and for the same reason. It also charges the search cost at every period including the last, so V(1) is the mean of the offers minus c rather than the mean.
Read the accept-sets down the table. With three periods left only 30 is taken; with two, 20 and 30; with one, everything. The rule tightens as you look further ahead and relaxes as the deadline approaches, which is the opposite of the way impatience usually feels and is exactly what the arithmetic says: what you are comparing an offer against is the value of the chances that remain, and there are fewer of them each period.
A rule, in full generality, is a choice of which offers to accept in each period. With three distinct offer values and three periods that is nine independent yes-or-no decisions, so 512 rules. The lab constructs all 512, evaluates each of them exactly by working backwards over the distribution — a computation that asks what this rule is worth rather than what carrying on is worth — and reports the best.
The best is worth 71/3, which is what the recursion said; its accept-sets are exactly the ones the thresholds describe; and it passes the shape test, which is that in every period, accepting an offer implies accepting every larger one. So on this instance the threshold form is not an assumption that happened to be convenient. It is a measured property of the winner of an exhaustive search.
Offers of 8, 14 and 40 with probabilities 3/5, 3/10 and 1/10, four periods, a search cost of 1. The thresholds come out 399/25, 72/5, 12 and 0, so with three or four periods left only the 40 is accepted — even though it arrives one time in ten.
The whole search is worth 4341/250, about 17.36, against a mean offer of 13. Almost all of that is the tenth that pays 40: with the same shape of problem but the 40 removed the search is worth a little over 10. Waiting is worth doing here because of a tail, which is a real feature of real searches and the reason an average is a poor summary of one.
Two offers, 10 and 30, equally likely, four periods, and a look now costs 5. The thresholds are 75/4, 35/2, 15 and 0, and the accept-set is the same in every period but the last: take the 30, refuse the 10.
Compare that with the same offers at a cost of 1, where the thresholds are 103/4, 47/2, 19 and 0. The expensive search is worth 155/8 and the cheap one 215/8. At the high cost a second look adds 5/2, a third 5/4 and a fourth only 5/8: the cost eats the option value, and the rule stops changing long before the deadline does.
Offers are independent draws from a distribution you already know, which rules out the most interesting thing about real search: that the offers you have seen tell you something about the ones to come. It also rules out recall, since a refused offer is gone; rules out the offer arriving late or not at all; and treats the search cost as the same in every period. The recursion will produce a threshold for any of those situations if you hand it this model, and the threshold will be exactly right for the wrong problem.
One more, less obvious. The objective maximises the expected value of what you end up with, so a rule that occasionally ends with nothing is penalised only by the size of that nothing. In the instance here the optimal rule refuses everything but 30 in the first period; if the deadline matters more than the money, the rule you want is not this one, and no amount of exact arithmetic on the expectation will say so.
Interactive
The threshold is the value of carrying on, and its shape is measured rather than assumed
Method
Four steps, and the last of them is the one that separates a rule you can defend from a rule you have assumed.
V(0) = 0. Everything else is built on that, and it is where the recursion bottoms out — the same role the last stage played on a network.
E[max(x, V(t−1))], which means replacing every offer below V(t−1) by V(t−1) itself and then averaging. Doing it that way rather than by cases makes the threshold visible in the arithmetic instead of implied by it.
V(t) = E[max(x, V(t−1))] − c. The threshold with t periods left is V(t−1), not V(t): it is what you are giving up by accepting, not what the search is worth.
Offers strictly above the threshold are accepted. The thresholds should fall as the deadline nears; if they do not, either the search cost is large enough that the rule barely moves, or something in the setup is wrong.
With S offer values and T periods there are 2^(S×T) rules, which is 512 at three and three. Evaluating all of them and checking that the winner is a threshold rule turns the shape from an assumption into a measurement, and it is affordable exactly at the size a page can show.
Three offers, three periods, a search cost of 1. The recursion first, then the exhaustive search over every way of deciding which offers to accept when.
The two accept-set rows being identical is a stronger statement than the two values being equal. A rule worth the same as the optimum would be enough to confirm the number; matching set by set says the recursion found the same rule and not merely an equally good one, which is what makes the shape test meaningful.
For a rehearsal, set the search cost to 0 and recompute by hand. The thresholds become 0, 20 and 70/3, the whole search is worth 230/9, and with two periods left only the 30 is now accepted — a free look makes the rule fussier, not less. Then put the cost up to 6: the thresholds drop to 0, 14 and 46/3, and the 20 becomes acceptable again with two and with three left. So the accept-set with two periods left changes between a cost of 0 and a cost of 1, and confirming that is the exercise.
The harder rehearsal: construct offers on which the best of all accept-sets is not a threshold rule. You will not manage it with independent draws and a constant cost — there is a proof that it cannot happen — and the useful part is working out which of those two conditions your attempted counterexample keeps breaking.
You should be able to write V(t) = E[max(x, V(t−1))] − c, compute it period by period in exact fractions, identify the threshold as V(t−1) rather than V(t), explain why the thresholds fall as the deadline nears, and say precisely what the recursion assumes about the shape of a rule and how the page establishes it instead.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.