Should coffee machines be deconcentrated?

Question

We model some region by convex and compact $E\subset \mathbb R^2$. $N\ge 1$ coffee machines are provided for the people living on $E$, of capacities $\alpha_1,\ldots, \alpha_N>0$. Assume the population of $E$ is uniformly distributed such that

$$\sum_{n=1}^N \alpha_n = \ell(E),$$

where $\ell$ is the Lebesgue measure. If locating the machines at $x_1,\ldots, x_N\in E$ with $X:=(x_1,\ldots, x_N)$, the transportation cost is given as

$$F(X):=W_2(\mu_X,\ell) \quad\mbox{with}\quad \mu_X:=\sum_{n=1}^N \alpha_n\delta_{x_n}, \quad\quad \forall X\in E^N,$$

where $W_2$ denotes the Wasserstein metric of order $2$. As $F:E^N\to\mathbb R_+$ is Lipschitz and $E^N$ is compact, its minimum is attained. Can we find a minimiser $X^*=(x_1^*,\ldots, x_N^*)\in E^N$ for $F$ such that $x^*_m\neq x^*_n$ for all $m\neq n$?

Answer 1

Disclaimer: I'm not confident about this argument because of the way you framed your question and me being not an expert on any of the involved objects. I hope someone can confirm this or correct me.

Let $X = (x_1,\ldots, x_N)$ be a minimiser.

Then $W_2(\mu_{X},\ell)^2 = \int_{E} \, \vert x - T(x) \vert^2 \, \mathrm{d}x$ for a map $T$ such that $\mu_{X} = \ell \circ T^{-1}$.

Let $\hat{A}_j := \{T = x_j\}$ for $j \in \{1, \dots, N\}$. The $\hat{A}_j$ may not be disjoint, when $x_i = x_j$ for $i \neq j$ or because they could agree on sets of Lebesgue measure zero. But we can select disjoint $A_1, \dots, A_n$ such that $\ell(A_j) = \alpha_j$ and $A_j \subseteq \{T = x_j\}$, by throwing away duplicates and then decomposing the kept $\hat{A}_j$ in pieces of the right Lebesgue measure and also throwing away Lebesgue measure zero intersections.

Then $$W_2(\mu_{X},\ell)^2 = \int_{E} \, \vert x - T(x) \vert^2 \, \mathrm{d}x = \int_{E} \, \sum_{j = 1}^{N} \vert x - T(x) \vert^2 \, \mathbb{1}_{A_j} \, \mathrm{d}x\\ = \sum_{j = 1}^{N} \int_{E} \,\vert x - T(x) \vert^2 \, \mathbb{1}_{A_j} \, \mathrm{d}x = \sum_{j = 1}^{N} \int_{A_j} \, \vert x - x_j \vert^2.$$.

But the term $\sum_{j = 1}^{N} \int_{A_j} \, \vert x - x_j \vert^2$ is minimised for fixed $A_1, \dots, A_n$ iff each $x_j$ is the centroid of $A_j$. Here centroid is meant as in https://en.wikipedia.org/wiki/Centroid#By_integral_formula. That means that the $x_j$ really have to be the centroids $\tilde{x}_j$ of the $A_j$, because otherwise $$ W_2(\mu_{\tilde{X}}, \ell)^2 \leq \int_{E} \, \vert x - \tilde{T}(x) \vert^2 \, \mathrm{d}x = \sum_{j = 1}^{N} \int_{A_j} \, \vert x - \tilde{x}_j \vert^2 < \sum_{j = 1}^{N} \int_{A_j} \, \vert x - x_j \vert^2 = W_2(\mu_{X},\ell)^2 $$ for $\tilde{X} = (\tilde{X}_1, \dots, \tilde{X}_n)$ and $\tilde{T} = \sum_{j = 1}^{n} \tilde{x}_j \mathbb{1}_{A_j}$, hence $X$ wouldn't have been a minimiser.

Now suppose $x_1 = x_2$. Then $A_1$ and $A_2$ and also $A_1 \cup A_2$ have the same centroid $x_1 = x_2$. We now just need to decompose $A_1 \cup A_2$ into $\tilde{A}_1$ and $\tilde{A}_2$ with $\ell(\tilde{A}_1) = \alpha_1, \ell(\tilde{A}_2) = \alpha_2$ but different centroids, because then $$\int_{\tilde{A}_1} \, \vert x - \tilde{x}_1 \vert^2 + \int_{\tilde{A}_2} \, \vert x - \tilde{x}_2 \vert^2 < \int_{\tilde{A}_1} \, \vert x - x_1 \vert^2 + \int_{\tilde{A}_2} \, \vert x - x_2 \vert^2 = \int_{A_1 \cup A_2} \vert x - x_1 \vert^2 = \int_{A_1} \, \vert x - x_1 \vert^2 + \int_{A_2} \, \vert x - x_2 \vert^2,$$ which again cannot be the case if $X$ actually is a minimiser.

But this recomposition of $A_1 \cup A_2$ into $\tilde{A}_1 \cup \tilde{A}_2$ should be possible by for example intersecting with a half-plane.