Optimal stopping

In this issue's article "Mathematics, marriage and finding somewhere to eat", David Smith investigated the problem of finding the best potential partner from a fixed number of potential partners using a strategy called optimal stopping.

Problem

You are faced with N potential partners that are presented to you in a random sequence one after the other. Your task is to choose the best partner using the following strategy: you examine the first M-1 of the potential partners and then choose the next one to come along that is better than all those you have previously examined (or the last partner if none appears). This results in a minimum of M potential partners being examined. You can assume that all the partners can be ranked uniquely, there are no two partners that are equally desirable.

What is the best value of M for large N?

Solution

Acknowledgement

This problem was provided by Dr David K. Smith, Mathematical Statistics and Operational Research Department, University of Exeter.