I vaguely remember a question we had on a distant math exam where you had to pick the best restaurant. I think the math showed the best strategy was to try the first 1/e (36%) than pick the next best one. Anyone recall this problem or the details? Is my memory correct?
Yes, that is the solution for the optimal stopping problems. Try 37 % of whatever and then choose the first one that you come to that is better than the best of the original 37%.
A nice brief discussion here.
A more complex discussion here. Thanks for naming the problem and your link.
https://imathworks.com/math/math-proof-of-stopping-theorem-for-bounded-stopping-times/
Is there a clearer proof?
Is there a way to apply this to politicians? 
I have one logical problem with this solution - what if the best possible was found in the first 37%? At what point do you get to go back to that one?
The general framing of the question excludes revisiting an already rejected candidate:
I don’t know if there’s a version that takes your rules into consideration .
The thing that makes the problem interesting is that you cannot go back and choose a previously rejected candidate. If you could do that, it would be a completely different problem, and the (fairly trivial) solution would be to try every candidate and then go back and choose the best one.
Well, then, that’s a pretty poor way to pick your soul mate (yes, I know the header in the article is joking).
Or is it the best way?
(No. Probably not.)
I will describe the problem as I first heard it and demonstrate one approach, which is not best, but just a plausible one.
You are given a stack of a 1000 of sheets of paper each with a number on it. Turn them one at a time and stop at some point (which could be the last one) and say that this is your choice for the largest number. What are your odds of doing so?
Well suppose you play the strategy of looking through the first 500 and noting the largest one you see. Then you turn the next 500 looking for a number larger than the one you noted. You might of course, not find one in which case you lose. But you certainly have at least one chance in 4 of success. You will win whenever the second highest number is in first half (one chance in 2) and the highest is in the second half (also one chance in 2). But there are other ways to win. If the 3rd highest is in the first half (1/2), the 1st and 2nd in the second half (1/2 each) and latter precedes the former (1/2) you still win. That adds 1/16 to your chances. Next possibility is the 4th highest comes in the 1st half (1/2), the other three in the 2nd half (1/2 each) and 1st precedes each of the other 2 (1/2 each), adding 1/64 to your odds. Summing the infinite series gives you one chance in 3 of success.
But it turns out that going halfway is not optimal. Your best bet is to go 1/e (about 37%) of the way and, IIRC, your odds of success are also 1/e.
That’s helpful, thanks.