Daily Archives: 7th January

Optimal stopping

Imagine a conveyor belt in front of you, on which are placed one hundred various-sized piles of money. You are allowed to stop the belt at any point and take the pile of money in front of you, but you cannot take any pile that has already passed you. Which pile should you take?

There is a mathematical solution to this problem, (sometimes called the Sultan’s Dowry Problem or the Fussy Suitor Problem) which is quite elegant.

  1. Wait until 37% of the piles have gone past you. (The figure of 37% is the reciprocal of e, the base of the natural logarithms.)
  2. Pick the next pile that is better than all the other piles so far.

Here are one hundred randomly-generated piles of money under £100:

£52.33, £80.83, £27.39, £84.75, £63.87, £1.66, £96.82, £76.51, £22.77, £90.94, £24.08, £60.41, £10.38, £95.59, £92.98, £46.80, £85.86, £21.96, £92.22, £29.19, £59.08, £72.22, £45.08, £63.39, £16.38, £71.49, £29.59, £78.62, £30.05, £97.98, £70.95, £3.79, £19.22, £77.52, £1.78, £48.74, £48.71, £35.95, £79.48, £11.50, £47.33, £32.83, £99.19, £3.23, £10.59, £58.22, £21.15, £61.37, £42.78, £25.27, £58.86, £32.82, £91.75, £13.04, £21.76, £72.29, £85.48, £58.81, £8.70, £91.63, £93.30, £23.00, £13.49, £11.67, £95.27, £21.37, £67.27, £90.99, £50.88, £77.22, £9.51, £10.63, £28.23, £63.94, £89.51, £90.12, £68.53, £76.98, £76.83, £92.04, £19.21, £73.82, £71.31, £99.94, £26.96, £86.92, £33.94, £8.25, £13.70, £74.44, £60.08, £11.54, £42.75, £78.67, £41.92, £92.36, £8.25, £92.89, £37.31 and £36.62.

The “best” value from the first thirty-seven piles is £97.98, so you should proceed through the remaining piles until you reach a value greater than this. This means stopping at the 43rd pile: £99.19.

Looking at the data, this strategy doesn’t actually yield the best value – waiting until the 84th pile would yield £99.94, which is slightly more. For large numbers of piles the 37% rule yields the perfect result in only 37% of cases, but this is a greater percentage than any other solution and it usually results in a very good result (i.e. one close to the perfect result).