Inequality involving rearrangement: $ \sum_{i=1}^n |x_i - y_{\sigma(i)}| \ge \sum_{i=1}^n |x_i - y_i|. $ If $x_1 \ge x_2 \ge \cdots \ge x_n$ and $y_1 \ge y_2 \ge \cdots \ge y_n$ are real numbers, and $\sigma$ is any permutation, then
$$
\sum_{i=1}^n |x_i - y_{\sigma(i)}| \ge \sum_{i=1}^n |x_i - y_i|.
$$
This must be a known inequality. What is it called, and how is it proven? (Just a reference is OK.)

The conditions are similar to rearrangement inequality. The inequality is a simple statement about minimizing the $\ell^1$ distance between a finite sequence and any rearrangement of another finite sequence.
I searched around and clicked through various pages but couldn't find something relevant. If it is true, perhaps a proof could be constructed by decomposing the permutation into a sequence of transpositions.
 A: We can prove it in a similar way as the rearangement inequality. There are only finitely many possibilities for $\sigma$, so a minimum is achieved, pick $\sigma$ so that it has the least possible number of inversions among all the permutations that minimize the expression.
Suppose by way of contradiction there is $i<j$ with $\sigma(i)>\sigma(j)$. Notice $|x_i-y_{\sigma_i}|+|x_j-y_{\sigma(j)}|\geq |x_i-y_{\sigma(j)}|+|x_j-y_{\sigma(i)}|$.
So the permutation that transposes $i$ and $j$ must also minimize the expression, and has less inversions, a contradiction.
A: For any convex function, such as $f(x) = |x|$, 
$$ \sum f(x_i - y_{\sigma(i)}) \geq \sum f(x_i - y_i)$$
because $(x_i - y_{\sigma(i)})$ majorizes $(x_i - y_i)$.
A reference is the first theorem, 6.A.1, in chapter 6 of Olkin and Marshall's book on majorization, applied to the sequences $x_i$ and $-y_i$.  
They attribute the result to a 1972 article by Peter W Day on general forms of the rearrangement inequality, and give a proof for vectors of real numbers.  Day's article is about more general situations with ordered abelian groups.  The inequality for real vectors must have been known earlier to many people.
A: You may be interested in the following inequality.

Let $f_1, \dots, f_n: \mathbb{R} \rightarrow \mathbb{R}$ be functions such that for all $1 \leq k < n$
the function $f_{k+1} - f_k$ is non-decreasing. In addition, let $y_1 \geq y_2 \geq \dots \geq y_n$. Then,
$$
\sum_{k}f_k(y_{n-k+1}) \geq \sum_k f_k(y_{\sigma(k)}) \geq \sum_k f_k(y_k)
$$

The book "the cauchy-schwarz master class" does not give a formal name for this inequality but just call it "a non-linear rearrangement inequality". See p.81 of the book.

I show a proof based on the inequality above.

Proof. Let
$$
f_k(x) = |x_k - x|
$$
Then
$$
f_{k+1}(x) - f_k(x) =
\begin{cases}
x_{k+1}-x_{k} &\text{if}\ x \leq x_{k+1} \\
2x - x_{k+1} - x_k &\text{if}\ x_{k+1} < x < x_k\\
x_{k} - x_{k+1} &\text{otherwise}
\end{cases}
$$
is non-decreasing, thus the inequality applies. That is,
$$
\sum_k |x_k - y_k| \leq \sum_k |x_k - y_{\sigma(k)}| \leq \sum_k |x_k - y_{n-k+1}|
$$

