Why is the stopping rule in the secretary problem 'optimal' when it can be shown not to be optimal for $n=2$? Several authors have proved that the optimal strategy in the secretary problem is a stopping rule whereby the interviewer rejects the first $r-1$ applicants (let $M$ be the best applicant among these $r-1$), then hires the first subsequent applicant who is better than $M$. The argument can be found here.
In the special case where there are only two applicants, this strategy clearly gives the interviewer a success probability of $\frac{1}{2}$. However, it can be shown (via a similar argument to this one) that there is actually a strategy that gives the interviewer a success probability of strictly greater than $\frac{1}{2}$.
Why is there a contradiction here? Why is the 'optimal' strategy not optimal when there are two applicants? Indeed, how do we know that we can't use some similar approach that improves (however slightly) upon the 'optimal' strategy when there are more than two applicants?
 A: In the most abstract version of the secretary problem, you cannot measure each candidate with a number.  Instead, as each candidate comes in, you can insert him/her into the sorted list (total order) of all previous candidates.  I don't see how you can use the envelop paradox trick in this scenario.
You can add your own model and assign numbers to the candidates you've seen, but those are your numbers, and the problem doesn't care.  The initial random permutation is equivalent to this: suppose you have seen $t$ candidates and they are ranked.  Now the $(t+1)$th candidate comes in.  Then he/she is equally likely to be inserted into any of the $(t+1)$ places in the existing list.  So for the $n=2$ case the 2nd candidate is equally likely to be better or worse.  Imagine you flip a fair coin and to decide if the 2nd candidate is better or worse.  That's the problem setting.  Now suppose you model the first candidate as score $S$ and draw a random number from $N(0,1)$ and compare etc.  This doesnt help at all - the probability is still 0.5.  If you claim to do better than 0.5, then you are claiming you can predict a fair coin flip better than 0.5, which is of course impossible.  The key is that the 2nd candidate did not have a number attached a-priori.  Alternatively, you can imagine that given your choice of 1st candidate's score $S$, the universe then decides the 2nd candidate's score $S_2$ to be $S \pm 1$ based on a fair coin flip.
Yet another alternative view: suppose the candidates actually secretly have scores $1, 2, ... n$, but unfortunately for you, those are not revealed to you as they come along.  Instead, the only info revealed to you is the ordering of everyone you've seen so far.  Again, you assigning them some other arbitrary scores of your choice doesn't help.  The $(t+1)$th candidate is still equally likely to be in any of the $(t+1)$ possible insertion locations into the existing list of $t$ previous candidates.
In other versions maybe each candidate is a number (dowry?) and the numbers are a-priori attached to the candidates and revealed to you as they come along, in which case you are right that the envelop paradox trick can apply.  Indeed, I have not seen that version analyzed fully incorporating the envelop paradox trick.  Hmm...
