For $A = \{a_{ij}\} \in R^{n\times n}$, is finding
$$ \max_{\sigma \in S_n}\min_{1 \le i \le n} a_{i,\ \sigma_i} $$
NP-hard?
This seems to be polynomial. Here is a proof. It will be convenient to regard $A$ as an edge-weighted complete bipartite graph $G$. Let $m_1 < \dots < m_\ell$ be the list of edge weights of $G$, let $E_i$ be the set of edges of weight $m_i$, and let $G_i:=G \setminus (E_1 \cup \dots \cup E_i)$. Now test if $G_1$ has a perfect matching (note this can be done in polynomial-time). If no, then the answer is $m_1$. If yes, then test if $G_2$ has a perfect matching and recurse. If $k$ is the first index such that $G_k$ does not have a perfect matching, then output $m_k$ as the answer.