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.
