  The prophet inequality is one of the cornerstone problems in optimal stopping
theory and has become a crucial tool for designing sequential algorithms in
Bayesian settings. In the i.i.d. $k$-selection prophet inequality problem, we
sequentially observe $n$ non-negative random values sampled from a known
distribution. Each time, a decision is made to accept or reject the value, and
under the constraint of accepting at most $k$. For $k=1$, Hill and Kertz [Ann.
Probab. 1982] provided an upper bound on the worst-case approximation ratio
that was later matched by an algorithm of Correa et al. [Math. Oper. Res.
2021]. The worst-case tight approximation ratio for $k=1$ is computed by
studying a differential equation that naturally appears when analyzing the
optimal dynamic programming policy. A similar result for $k>1$ has remained
elusive.
  In this work, we introduce a nonlinear system of differential equations for
the i.i.d. $k$-selection prophet inequality that generalizes Hill and Kertz's
equation when $k=1$. Our nonlinear system is defined by $k$ constants that
determine its functional structure, and their summation provides a lower bound
on the optimal policy's asymptotic approximation ratio for the i.i.d.
$k$-selection prophet inequality. To obtain this result, we introduce for every
$k$ an infinite-dimensional linear programming formulation that fully
characterizes the worst-case tight approximation ratio of the $k$-selection
prophet inequality problem for every $n$, and then we follow a dual-fitting
approach to link with our nonlinear system for sufficiently large values of
$n$. As a corollary, we use our provable lower bounds to establish a tight
approximation ratio for the stochastic sequential assignment problem in the
i.i.d. non-negative regime.
