This is another of the problems I designed for contests but wasn't able to solve on my own for years. Maybe AoPS is a better place for it, but let me try it here.

**[UPDATE: I have streamlined the exposition after zeb's wonderful proof of my conjectures. Everything stated below as a "conjecture" is true. Note that some comments, as well as fedja's and Suvrit's answers below, refer to an older version of these conjectures, which was false.]**

Let $n\in\mathbb N$ be $\geq 2$, and let $a_1$, $a_2$, ..., $a_n$ and $b_1$, $b_2$, ..., $b_n$ be nonnegative reals such that $a_1\geq a_2\geq ...\geq a_n$ and $b_1\geq b_2\geq ...\geq b_n$. Let $A_n$ denote the $n$-th alternating group, and $S_n$ denote the $n$-th symmetric group. We use the symbol $-$ for set-theoretical complement (since the backslash means something else in group theory).

**Product-sum conjecture.** Then,

$\left(-1\right)^{\binom{n}{2}}\left(\prod\limits_{\pi\in A_n} \left(\sum\limits_{k=1}^n a_kb_{\pi\left(k\right)}\right) - \prod\limits_{\pi\in S_n - A_n} \left(\sum\limits_{k=1}^n a_kb_{\pi\left(k\right)}\right) \right) \leq 0$.

**Sum-maximum conjecture.** We have

$\left(-1\right)^{\binom{n}{2}}\left(\sum\limits_{\pi\in A_n} \max\left\lbrace a_k + b_{\pi\left(k\right)} \mid k\in\left\lbrace 1,2,...,n\right\rbrace \right\rbrace - \sum\limits_{\pi\in S_n - A_n} \max\left\lbrace a_k + b_{\pi\left(k\right)} \mid k\in\left\lbrace 1,2,...,n\right\rbrace \right\rbrace \right) \leq 0$.

zeb has proven both of these conjectures (I am still interested in an analysis-free proof, but rather convinced that zeb's is the natural one). Here are some easy observations:

If the Product-sum conjecture holds, then so does the Sum-maximum one, by the standard "tropical geometry" trick (replace $a_k$ by $x^{a_k}$, replace $b_k$ by $x^{b_k}$, and watch the asymptotics of the sides while $x$ goes to $\infty$).

Both conjectures hold for $n\leq 3$ for very simple reasons.

By the same argument as in the proof of Cauchy's and Vandermonde's determinants, the difference $\prod\limits_{\pi\in A_n} \left(\sum\limits_{k=1}^n a_kb_{\pi\left(k\right)}\right) - \prod\limits_{\pi\in S_n - A_n} \left(\sum\limits_{k=1}^n a_kb_{\pi\left(k\right)}\right) $ is divisible (as a polynomial) by $\prod\limits_{1\leq i < j\leq n}\left(a_i-a_j\right) \prod\limits_{1\leq i < j\leq n}\left(b_i-b_j\right)$. The question is whether the quotient has the same sign as $\left(-1\right)^{\binom{n}{2}}$. I wouldn't be surprised if it is even a polynomial with all coefficients having that same sign, and maybe even Schur-positive times $\left(-1\right)^{\binom{n}{2}}$, whatever this means for symmetric polynomials in two sets of indeterminates. (For $n\leq 3$, this quotient is $1$.)

3more comments