Check the match of the maximum of each subset
You can do the following. For every $i\in\{1,\dotsc,n\}$, start with the set $I=\{k\,:\,a_k\leqslant a_i\}$. Let $K=\{k\,:\,\exists j\ b_k^j=\max\{b^j_\ell\,:\,\ell\in I\}=a_i\}$. If $K=\emptyset$, then $I$ is a counterexample. If $i\in K$ then there is no counterexample with $i\in I$ and $a_i=\max\{a_k\,:\,k\in I\}$. If $K\neq\emptyset$ and $i\not\in K$ then any counterexample $J$ with $i\in J$ and $a_i=\max\{a_k\,:\,k\in J\}$ will be a subset of $I\setminus K$. So we can replace $I$ by $I\setminus K$, and iterate.

It is necessary and sufficient that for every $i$ we end up with $i\in K$.