Popular algorithms (stopping rules) with output - a prefix of a permutation What are some popular settings, when we look at the elements of a randomly generated permutation one by one, and we use certain stopping rule which, as a result gives us a prefix of the observed permutation?
For example, in the secretary problem, we have candidates represented by numbers showing how strong is the candidate. The candidates come in a random order and we aim to select the best one. So in fact, we are looking at the elements of a random permutation and we follow certain strategy (stopping rule) to select a candidate. For the secretary problem, it is known that the optimal strategy is to see the first $\lfloor\frac{n}{e}\rfloor$ elements of the permutation and then choose the first left-to-right maxima that you see (the first candidate who is better than each of the already observed candidates).
Can you think of other such examples, where we have certain popular stopping rules when looking at permutations? Any well-known problem where this situation occurs or a real-life situation would count as an answer!
Note: I know that this is not a specific math question, so the moderators can move it if there is some better place for this question to be asked.
 A: Generalized Secretary Problems:
One flavour is as follows.
Consider the general $(J, K)-$secretary problem,
where $n$ totally ordered items arrive in a random order. An algorithm observes the relative merits of arriving items and is allowed to make $J$ selections. The
objective is to maximize the expected number of items
selected which are among the $K$ best items (best, 2nd best to $K$th best).
The
objective is to maximize the expected payoff, which
is the number of items selected among the best $K$
items, where expectation is over the random arrival
permutation. The performance ratio is the expected
payoff divided by $\min\{J, K\}$. Observe that no adversary
is involved in the problem, and hence randomization is
unnecessary to achieve optimality.
There are some partial results for this, see this paper:
For example, if $(J,K)=(2,1)$ an asymptotic ratio of
$$
\frac{1}{e}+\frac{1}{e^{1.5}}
$$
is achievable. See the paper for details and more results.
Prophet Inequalities:
A sequence of random variables $X_{i}$ arrive from known distributions
${\mathcal {D}}_{i}$. When each $X_{i}$ arrives, the decision-making process must decide whether to accept it and stop the process, or whether to reject it and go on to the next variable in the sequence. The value of the process is the single accepted variable, if there is one, or zero otherwise.
A prophet, knowing the whole sequence of variables, can obviously select the largest of them, achieving value  $\max _{i}X_{i}$ for any specific instance of this process, and expected value $\mathbb {E} [\max _{i}X_{i}]$. The prophet inequality states the existence of an online algorithm for this process whose expected value is at least half that of the prophet: No algorithm can achieve a greater expected value for all distributions of inputs. See Wikipedia for more.
Two Phase Prophet Inequality:
An adversary chooses $2n$ items with values $v_1, v_2, \ldots, v+{2n}$ and a random order is applied to these
values. Then, there are two phases of Prophet Inequality:
(1) Phase 1. The Decision Maker (DM) is presented with
the first $n$ items (according to the random order) in an online fashion and must make an irrevocable
decision, and once a value is accepted the phase stops.
(2) Phase 2. The DM is presented with the
last $n$ items (according to the random order) in an online fashion and must make an irrevocable
decision at each step.
The payoff is the sum of values obtained in the two phases. See this paper.
